链接：https://codeforces.com/contest/1359
A. Berland Poker
题意：
现在有$n$张牌，$m$张王，共有$k$个人，每个人分得$frac{k}{n}$张牌,你的得分是你手中王牌的个数减去其余人中拥有最多王牌的个数，求最大得分
思路：
分类讨论一下即可，如果$m$大于$left lceil frac{k}{n} ight ceil$,那么答案就为$left lceil frac{m-left lceil frac{k}{n} ight ceil}{k-1} ight ceil$
否则，答案就为$m$
#include<iostream> #include<algorithm> using namespace std; typedef long long ll; int main() { int t; cin>>t; while(t--){ int n,m,k; cin>>n>>m>>k; int num=n/k; if(n%k!=0) num++; if(m>num){ int cnt=(m-num)/(k-1); if((m-num)%(k-1)!=0) cnt++; cout<<num-cnt<<endl; } else cout<<m<<endl; } return 0; }
B. New Theatre Square
题意：
在$n*m$的二维区域内有黑色和白色两种瓷砖，现在你要覆盖白色的瓷砖，你可以选择花费$x$元覆盖一个瓷砖，也可以选择花$y$元覆盖同一行的连续两个瓷砖，求覆盖掉所有白色瓷砖的最小花费
思路:
如果$2*x≤y$的话，答案就为$x*num$,$num$为白色瓷砖的个数
否则，就遍历整个区域，如果$(x,y)$位置是白色瓷砖，那么就观察$(x,y+1)$处，如果也是白色瓷砖就花费$y$元将两块瓷砖同时覆盖，否则就花$x$元
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e3+5; char a[N][N]; int main(){ int t; cin>>t; while(t--){ ll n,m,x,y,num=0; cin>>n>>m>>x>>y; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>a[i][j]; if(a[i][j]=='.') num++; } if(x*2<=y) cout<<num*x<<endl; else { ll ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(a[i][j]=='.'){ if(j<m&&a[i][j+1]==a[i][j]) ans+=y,j++; else ans+=x; } } cout<<ans<<endl; } } return 0; }
C. Mixing Water
题意：
热水的温度为$h$,冷水的温度为$c$,目标温度为$t$,现在不停依次倒入热水，冷水，热水，冷水...，求倒入几次后混合水点的温度最接近$t$(混合水的温度为倒入的水的温度总和/倒入的次数)
思路：
可以发现倒入冷水后的温度始终都为$(h+c)/2$,所以答案不可能为除$2$以外的偶数，所以当$t≤(h+c)/2$时，答案一定为$2$
再观察倒入热水后的规律，发现倒入热水之后，温度的函数为$(x*h+h+x*c)/(2*x+1)$($x$是倒入了几次热水，并且从$0$开始)，而且这个函数是以递减变化的
因此我们可以二分倒入热水的次数，找到最后一次水的温度大于等于$t$的时刻$tim$，再与$tim+1$时刻进行比较看哪个值更接近$t$，就能求出需要倒几次热水
#include<bits/stdc++.h> #define ll long long using namespace std; long double h,c,t,sb; long double pd(int x){ return (h*x+h+c*x)/(2*x+1); } int main(){ ll p; cin>>p; while(p--){ cin>>h>>c>>t; sb=(h+c)/2; if(sb>=t) cout<<2<<endl; else{ int l=0,r=1e9; while(l<r){ ll mid=(r+l+1)/2; if(pd(mid)>=t) l=mid; else r=mid-1; } if(fabs(pd(r+1)-t)<fabs(pd(r)-t)) r++; cout<<2*r+1<<endl; } } return 0; }
D. Yet Another Yet Another Task
题意：
给一个序列，你可以选择一个子段，要求去掉子段最大值后的和最大，求出这个最大值
思路：
可以发现$-30≤n≤30$，那么我们可以在$1-30$的范围内枚举区间的最大值，因为如果当区间最大值为负数或$0$时,区间的其他数肯定也为负数或者为$0$，那么选择这样的一段是没有意义的，最大值肯定为$0$
在枚举区间最大值时，我们记录下(最大子段和-枚举值)的最大值，遇到比枚举值大的数的时候，就将累加的数清零即可
#include<iostream> #include<algorithm> using namespace std; const int maxn=1e5+10; int a[maxn]; int main() { int n,flag=0; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int ans=0,cnt=0; for(int i=1;i<=30;i++){ cnt=0; for(int j=1;j<=n;j++){ if(a[j]>i){ cnt=0; continue; } cnt+=a[j]; if(cnt<0) cnt=0; ans=max(cnt-i,ans); } } cout<<ans; return 0; }