首页 > 代码库 > HDU 5583 Kingdom of Black and White（模拟）
HDU 5583 Kingdom of Black and White（模拟）
题目戳这
题意：给你一个零一串，如果都是一个或者都是零的部分形成一个联通块，然后我们得到一个值，这个值是每个联通块的零的数目或者一的数目的平方和。然后最多可以改变一个数字，把零改成一或者把一改成零，然后得到的这个数值要最大。
思路：只要把联通块的数字都求出来，然后从前往后扫一遍，两个数字要么前面的加一后面的减一，要么前面的减一后面的加一，如果当前的数字为一，就是要求出这个数的左边加当前数加右边的数的平方，因为要合并。然后更新到最大的就行了。
P.S.这道题，虽然想说莫名其妙WA了好几发，但是做到后面，发现自己扫的时候判断方法稍微有点挫，应该是每扫到一个数，然后就把这个数字减一，然后这个数字的前后都分别加一，得到这两种情况的最大值。刚开始的方法挫死了。
1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 #include<math.h> 5 #include<algorithm> 6 #include<vector> 7 #include<string> 8 #include<queue> 9 #include<map>10 #include<stack>11 #include<set>12 #define ll long long13 #define maxn 10001014 #define PI acos(-1.0) //圆周率15 const ll INF = 1e18;16 const int len=30;17 using namespace std;18 int T;19 string s;20 vector <ll> v;21 ll max(ll a,ll b)22 {23 if(a>b) return a;24 else return b;25 }26 int main()27 {28 int cas=0;29 scanf("%d",&T);30 while(T--)31 {32 v.clear();33 cin>>s;34 int len=s.length();35 36 int flag=-1;37 ll cnt=0;38 ll sum=0;39 for(int i=0;i<len;i++)40 {41 if(s[i]-‘0‘!=flag)42 {43 v.push_back(cnt);44 sum+=cnt*cnt;45 cnt=1;46 flag=s[i]-‘0‘;47 }48 else cnt++;49 }50 sum+=cnt*cnt;51 v.push_back(cnt);52 v.push_back(0);53 54 //cout<<sum<<endl;55 56 if(v.size()==1)57 {58 printf("Case #%d: %I64d\n",++cas,sum);59 continue;60 }61 62 ll ans=sum;63 for(int i=1;i<v.size()-1;i++)64 {65 if(v[i]==1)66 ans=max(ans,sum-v[i-1]*v[i-1]-v[i]*v[i]-v[i+1]*v[i+1]+(v[i-1]+v[i]+v[i+1])*(v[i-1]+v[i]+v[i+1]));67 else68 {69 ans=max(ans,sum-v[i]*v[i]-v[i+1]*v[i+1]+(v[i]-1)*(v[i]-1)+(v[i+1]+1)*(v[i+1]+1));70 ans=max(ans,sum-v[i]*v[i]-v[i-1]*v[i-1]+(v[i]-1)*(v[i]-1)+(v[i-1]+1)*(v[i-1]+1));71 }72 }73 74 printf("Case #%d: %I64d\n",++cas,ans);75 }76 77 return 0;78 }
HDU 5583 Kingdom of Black and White（模拟）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。