A：http://codeforces.com/contest/1359/problem/A
题意：
n张牌，m张王，k个人，每个人分得n/k张牌，得分为手中王牌数-其他人中所拥有的最大王牌数。存在多个，输出0分。
解析：
a题依然是熟悉的分类讨论~先分第一个人，再分给其他人，分类讨论。关键是这个n/k
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; int main() { int t; cin>>t; while(t--) { int n,m,k; cin>>n>>m>>k; if(m==0) { cout<<"0"<<endl;continue; } if(m<=n/k) cout<<m<<endl; else { int md=m-n/k; if(md<(k-1)) cout<<n/k-1<<endl; else { if(md/(k-1)>=(n/k)) cout<<"0"<<endl; else { if(md%(k-1)==0) cout<<n/k-md/(k-1)<<endl; else cout<<n/k-(md/(k-1)+1)<<endl; } } } } }
B：http://codeforces.com/contest/1359/problem/B
题意：两种覆盖方式：1*1，花费x，1*2，花费y。求把所有.覆盖的最少花费。
解析：
刚开始想边遍历边算的，但是发现这样要考虑很多情况。
看覆盖方式的规格，
如果2*x<=y，肯定直接全放1*1的就行了呀
2*x>y，说明对于挨着的.，肯定是1*2的花费更少，直接放1*2，其他全放1*1即可。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; char mp[1002][1002]; int main() { int t; cin>>t; while(t--) { int n,m,x,y; cin>>n>>m>>x>>y; int sum=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) cin>>mp[i][j]; mp[i][m+1]=‘*‘; } if(x*2>y) { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(mp[i][j]==‘.‘&&mp[i][j+1]==‘.‘) { sum+=y; j++; } else if(mp[i][j]==‘.‘&&mp[i][j+1]!=‘.‘) { sum+=x; } } } } else { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(mp[i][j]==‘.‘) sum+=x; } } } cout<<sum<<endl; } }
C：http://codeforces.com/contest/1359/problem/C
题意：
热水温度h，冷水温度c，目标温度t
先倒热水，再冷水，热水，依次进行，
每次的温度为之前的所有的h+c的和/（倒水次数）
问达到最接近t最少需要倒多少次水。
解析：
模拟一下：
热：h
冷：(h+c)/2
热：(2h+c)/3
冷：(2h+2c)/4==(h+c)/2
可以发现，偶数次，温度一定为：(h+c)/2。所以如果目标温度t<=(h+c)/2，直接输出2次就行了。
奇数次，可以推出公式：
(h+x*h+x*c)/(2*x+1)，x为加入热水的次数。
这个式子，是单调递减的，而且它无限接近于(h+c)/2，这点也印证了t<=(h+c)/2为什么输出2。
接下来就是二分了。
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef long long ll; const int maxn=1e5+10; double h,c,y; double ge(int x) { return (h+x*h+x*c)/(2*x+1); } int main() { int t; cin>>t; while(t--) { cin>>h>>c>>y; if(y<=(h+c)/2) cout<<2<<endl; else { int l = 0 ,r = 1e9; while(l<r) { int md=(l+r+1)>>1; if(ge(md)>=y) l=md; else r=md-1; } if(fabs(ge(r+1)-y)<fabs(ge(r)-y)) //谁更接近y r++; cout<<r*2+1<<endl; } } }
D：http://codeforces.com/contest/1359/problem/D
题意：
给出n个数，找到一个区间，让这段区间的和-最大值最大。
解析：
题中已经指明，a<=30。
所以，我们可以通过枚举最大值max来求。
如果max<a[j]了，此区间断掉，sum=0重新记录。
max>=a[j]，不断更新区间和以及结果：
sum=max(0,sum+a[j]); maxx=max(maxx,sum-i);
也许会有疑惑：每次-i，如果i本身不存在这个数组里怎么办呢？其实不用担心，i如果不存在，但是之前此区间和减掉的是一个比i小的数，它肯定比减去i大，所以不用在意。
#include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; const int maxn=1e5+10; int a[maxn]; int main() { int n ; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int maxx=0; for(int i=1;i<=30;i++) { int sum=0; for(int j=1;j<=n;j++) { if(a[j]>i) sum=0; else { sum=max(0,sum+a[j]); maxx=max(maxx,sum-i); } } } cout<<maxx<<endl; }
Educational Codeforces Round 88 (Rated for Div. 2)(C为二分，D为思维模拟)
原文：https://www.cnblogs.com/liyexin/p/12989842.html