考试周，但还是打了一场，一个周不打了，手生了不少.......
A：http://codeforces.com/contest/1373/problem/A
题意：
第一个商店：1个卖a元
第二个商店：打包卖，b个卖c元。比如买b+1个，那也得买双份，2b个。
求买多少(任意)，第一个商店更便宜，第二个商店更便宜。不存在就-1
解析：
看a与c
如果c<a，不管怎么买，第二个商店都是比第一个商店便宜。
c>a，买一个，第一个商店肯定更便宜。然后看买b个谁优即可。
a==c，怎么买，第二个商店都更便宜。
#include<iostream> #include<cstdio> using namespace std; typedef long long ll; int main() { int t; cin>>t; while(t--) { ll a,b,c; cin>>a>>b>>c; if(c<a) { cout<<"-1 1"<<endl;continue; } if(a<c) { cout<<"1 "; if(a*(b)<=c) cout<<"-1"<<endl; else cout<<b<<endl; } if(a==c) { cout<<"-1 "<<b<<endl; } } }
B：http://codeforces.com/contest/1373/problem/B
题意：
01串，每次的操作是：找到一个连续的01，去掉。
谁最后无法操作，谁就输了。Alice先手。
解析：
刚开始想复杂了，其实直接看0，1的数目即可。
然后取一个min，这个min就是一共能得到多少个连续01串，看下奇偶即可。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<stack> using namespace std; typedef long long ll; int main() { int t; int x,y,k; int i; cin>>t; while(t--) { string s; cin>>s; x=0; y=0; for(i=0;i<s.size();i++) { if(s[i]=='0') x++; if(s[i]=='1') y++; } if(x==y) { if(x%2==0) { cout<<"NET"<<endl; continue; } else { cout<<"DA"<<endl; continue; } } else { k=min(x,y); if(k%2==0) { cout<<"NET"<<endl; continue; } else { cout<<"DA"<<endl; continue; } } } return 0; }
C：http://codeforces.com/contest/1373/problem/C
题意：
给出示例代码：
res = 0 for init = 0 to inf cur = init ok = true for i = 1 to |s| res = res + 1 if s[i] == '+' cur = cur + 1 else cur = cur - 1 if cur < 0 ok = false break if ok break
不咋好解释。。。总之就是，cur从0到inf，每次的cur都要遍历一遍字符串，遇'+'则+，遇'-'则-，res累加每次的遍历长度。当cur<0，内循环结束，当cur>0，即遍历完整串，都没有出现cur<0的情况，就结束整个。求res。
解析：
先记录个字符串的+,-过程的前缀和q[]
当cur<0的时候，res的累加就终止：
cur=x ： 字符串：..........q[i]。i时结束，需要的条件是，cur从idx=1到idx=i时一路加减，cur<0了，这个时候就结束内循环，而res加上的值是 i 。
那么cur需要满足什么呢？假设q[i]=-3，那么，cur==2的时候，cur+q[i]<0，就可以终止了。即cur==-q[i]-1的时候，res+=i。用vis[]记录这个cur，vis[cur]=i。
可能要问了，cur==1的时候，+(-3)也是<0的，为什么不算呢？q[i]=-3，那么之前肯定还有q[i]=-2,-1，所以cur<2的时候已经在前面终止了，每个-q[i]-1，唯一对应一个cur。
cur越大，终止点越往后，但是我们要记录第一个终止点。vis[]也发挥了这个作用。
最后+len，因为最后res+=n，没有出现cur<0，才结束整个程序。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; const int maxn=1e6+10; char s[maxn]; int vis[maxn],q[maxn]; int main() { int t; cin>>t; while(t--) { scanf("%s",s+1); int len=strlen(s+1); memset(vis,0,sizeof(vis)); memset(q,0,sizeof(q)); for(int i=1;i<=len;i++) { if(s[i]=='+') q[i]=1; else q[i]=-1; } q[0]=0; for(int i=1;i<=len;i++) q[i]+=q[i-1]; for(int i=1;i<=len;i++) { if(q[i]<0&&!vis[-q[i]-1]) vis[-q[i]-1]=i; } ll sum=0; for(int i=0;i<=len;i++) if(vis[i]) sum+=vis[i]; else break; cout<<sum+len<<endl; } }
D：http://codeforces.com/contest/1373/problem/D
题意：
0~n-1的数组a[]，找到一个[l,r]，反转里面的数字。
使得整个的a0~an-1的偶数下标的数之和最大，求这个sum。
解析：
经过分析，只有在所选长度为偶数的时候，修改才能生效。
假设有：1，2，3，4，5
原始sum=2+4
我要修改1~4，那么变成：4，3，2，1，5。sum=3+1
修改2~5，变成：1，5，4，3，2。sum=5+3
对应原始sum 2 4
3 1
5 3
2，4调换一下，可以发现，2变成了1/3，4变成了3/5，都是与相邻值发生了交换。
所以有结论：对于每一个偶数位，它要么和i-1交换，要么和i+1交换。记录这两种替换方式的最大连续和即可。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; const int maxn=2e5+10; ll a[maxn]; int main() { int t; cin>>t; while(t--) { int n; cin>>n; ll sum=0; for(int i=0;i<n;i++) { cin>>a[i]; if(i%2==0) sum+=a[i]; } ll maxx=0,ans1=0,ans2=0; for(int i=0;i<n;i+=2) { if(i+1<n) { ans1+=a[i+1]-a[i]; maxx=max(maxx,ans1); if(ans1<0) ans1=0; } if(i>1) { ans2+=a[i-1]-a[i]; maxx=max(maxx,ans2); if(ans2<0) ans2=0; } } cout<<sum+maxx<<endl; } }