2019百度之星初赛第二场度度熊与运算式1

系统管理员 2021-10-12 19:19 219阅读 0赞

## 题意： ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70][]

## 分析：异或把式子分成了很多块，我们把每一块先贪心相加，如果每一块多一个异或运算，总和-2，也就是说多任意个异或，减少的值都是2的倍数。我们可以从高到低贪心确认每一位能不能为1，能放就打标记，下次就不放了，最后考虑相异或的1的个数的奇偶情况。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N=1e6+5;
    int t,vis[N];
    
    int main() {
        cin>>t;
    	while(t--){
            string s;
    		cin>>s;
    		int cnt=1;
    		memset(vis,0,sizeof(vis));
    		for(int i=0;i<s.size();i++) {
    			if(s[i]=='^') {
                    ///贪心构造
    				for(int j=21;j>0;j--) {
    					if(cnt>=(1<<j) && !vis[j]) {
    						vis[j]=1;
    						cnt-=(1<<j);
    					}
    				}
    				cnt=1;
    			}
    			else cnt++;
    		}
    		for(int j=21;j>0;j--) {
    			if(cnt>=(1<<j) && !vis[j]) {
    				vis[j]=1;
    				cnt-=(1<<j);
    			}
    		}
    		int ans=0;
    		for(int i=21;i>0;i--) if(vis[i]) ans+=(1<<i);
            ///特判最终1的个数
            if((s.size()+1-ans)%2) ans++;
    		printf("%d\n",ans);
    	}
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: /images/20211013/3082a19851d94c4cbfed9e305e9a8859.png

发表评论取消回复

表情：

评论列表（有 0 条评论，219人围观）

还没有评论，来说两句吧...

相关阅读

相关 2019 年百度之星·程序设计大赛 - 初赛四 1006 Totori's Switching Game

题意：判断在一个图（可能有重边,但是没有自环）中是否存在k个生成树，且它们的边互不相同。分析：水题，统计一下每个节点的度，k就是所有节点的最小度。代码：...

亦凉/ 2024年04月17日 06:00/ 0 赞/ 28 阅读

相关 HDU 6675 度度熊与排列【2019百度之星初赛二1002】

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6675 度度熊与排列 **Time Limit: 2000...

- 日理万妓/ 2024年04月17日 05:39/ 0 赞/ 42 阅读

相关 2019百度之星初赛三 1001最短路1（异或）

最短路一题目链接：[http://bestcoder.hdu.edu.cn/contests/contest\_showproblem.php?cid=863&pid=

旧城等待，/ 2023年08月17日 15:41/ 0 赞/ 74 阅读

相关 2019百度之星初赛二 1001 度度熊与数字（因子问题）

1001 度度熊与数字题目链接：[http://bestcoder.hdu.edu.cn/contests/contest\_showproblem.php?cid=8

柔情只为你懂/ 2023年08月17日 15:41/ 0 赞/ 77 阅读

相关【题目记录】——2021 年百度之星·程序设计大赛 - 初赛二

文章目录 1001 签到数学模拟 1002 随机题意思维 1003 魔怔图论欧拉回路 1004 净化数学，思维题目地址 [2

心已赠人/ 2022年09月04日 03:49/ 0 赞/ 160 阅读

相关 2017百度之星资格赛1004度度熊的午饭时光

2017百度之星资格赛1004度度熊的午饭时光 Problem Description 度度熊最期待每天的午饭时光，因为早饭菜品清淡，晚饭减肥不敢吃太多（胖纸的忧

偏执的太偏执、/ 2022年06月10日 01:17/ 0 赞/ 136 阅读

相关百度之星初赛B

A ：传送门：[点我][Link 1] 求联通块个数，对于简单图而言，就是c=v-e,其中c就是联通块个数，v是顶点数，e是边数 include <algorith

àì夳堔傛蜴生んèń/ 2022年05月16日 00:06/ 0 赞/ 137 阅读

相关百度之星初赛 A 杭电6376 度度熊剪纸条

C 度度熊剪纸条链接：[点我][Link 1] Problem Description 度度熊有一张纸条和一把剪刀。纸条上依次写着 N 个数字，数字只可能是 0

Love The Way You Lie/ 2022年05月15日 00:37/ 0 赞/ 171 阅读

相关百度之星初赛 A 杭电6375

B 度度熊学队列链接：[点我][Link 1] Problem Description 度度熊正在学习双端队列，他对其翻转和合并产生了很大的兴趣。初始时有 N

﹏ヽ暗。殇╰゛Y/ 2022年05月15日 00:14/ 0 赞/ 186 阅读

相关 2019百度之星初赛第二场度度熊与运算式1

题意： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L

系统管理员/ 2021年10月12日 19:19/ 0 赞/ 220 阅读