https://codeforces.com/contest/1951
题解参考：https://zhuanlan.zhihu.com/p/691034931
A题
一开始的思路比较绕，wa很多发卡了半小时才过。hansun的思路比较硬直，他在极短的时间内过了A
hansun的题解：https://codeforces.com/contest/1951/submission/255262403
我的想法是分奇偶情况再细分情况讨论，但是这样会造成讨论情况过多导致考虑不周卡住。参考hs的代码，把特殊情况单独拎出来特判，剩下的常规判断就行。
补题AC代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){
ll n; cin>>n;
string s; cin>>s;
ll cnt=count(s.begin(),s.end(),'1');
if(cnt==2) {
for (int i = 0; i < n - 1; i++) {
if (s[i] == s[i + 1] && s[i] == '1') {
cout << "NO\n";
return;
}
}
}
if(cnt&1) cout<<"NO\n";
else cout<<"YES\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll t; cin>>t; while(t--) solve();
return 0;
}
B题
也是卡了半小时，卡在分类情况过多。比赛的时候差一点调出来，但不想调了改cuibo的代码过了去看C了
对于贪心模拟的题目，分类讨论的标准至关重要。一开始我的标准是牛在原地不动或者交换到第一个，这个标准是错误的，因为牛在原地不动是性价比最低的，如果前面有分数更高的牛答案就是0，没有的话也会浪费前面的可以打败的牛。正确的分类标准应该是要么换到第一个去，要么换到第一个比它大的牛那里去，然后特判一下第一个大的牛在第一个的情况，然后模拟就行。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){
ll n,k; cin>>n>>k;
vector<ll> a(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
ll ans1=0,ans2=0;
ll flag=0;
for(int i=1;i<k;i++){
if(a[i]>a[k]){
flag=i; break;
}
}
if(flag){
if(flag!=1) ans1=1;
for(int i=flag+1;i<=n;i++) {
if(a[i]<a[k]) ans1++;
else break;
}
}
if(k!=1) swap(a[1],a[k]);
for(int i=2;i<=n;i++){
if(a[i]<a[1]) ans2++;
else break;
}
cout<<max(ans1,ans2)<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll t; cin>>t; while(t--) solve();
return 0;
}
C题
赛时cuibo说可能时DP，我看了一下，一眼背包（艹），但赛时没看清楚题目调不出来，赛后看清楚了发现可以做但是会爆long long
DP爆long long代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t; cin>>t;
while(t--){
ll n,m,k;cin>>n>>m>>k;
vector<ll> w(n+1);
vector<vector<ll>> dp(n+1,vector<ll>(k+1));
for(ll i=1;i<=n;i++){
cin>>w[i];
}
dp[0][0]=0;
for(ll i=1;i<=k;i++){
if(i<=m) dp[0][i]=i*w[1];
else dp[0][i]=0x3f3f3f3f;
}
for(ll i=1;i<=n;i++){
for(ll j=0;j<=k;j++){
dp[i][j]=dp[i-1][j];
for(ll s=0;s<=m;s++){
if(j>=s) dp[i][j]=min(dp[i-1][j-s]+((j-s)+w[i])*s,dp[i][j]);
}
}
}
cout<<dp[n][k]<<"\n";
}
return 0;
}
贪心即可。分析发现，增加的票价与购买的日期无关，只和已购买的票数有关。那样的话可以将每日价格从小到大排序，依次每天买m张，最后一天买k%m张。对于溢价，第一天为0，之后每天m累乘上之前的和，最后一天处理一下即可。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){
ll n,m,k; cin>>n>>m>>k;
vector<ll> a(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
sort(a.begin(),a.end());
ll re=k; ll ans=0;
for(int i=1;i<=n;i++){
if(re==0) break;
if(re>=m) {
ans+=m*a[i];
re-=m;
}
else {
ans+=re*a[i];
re=0;
}
}
ll t=k/m; ll pri=0;
for(int i=0;i<=t;i++){
if(k-pri<m){
ans+=(k-pri)*pri;
break;
}
else{
ans+=m*pri;
pri+=m;
}
}
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll t; cin>>t; while(t--) solve();
return 0;
}
D题
贪心，如果n%k==0，那么只需要一个摊位为n/k即可。否则的话，就试图让第二个摊位为1，在该摊位买掉k-1个商品，判断第一个摊位能否只买一个就行。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){
ll n,k; cin>>n>>k;
vector<ll> a;
if(n%k==0){
cout<<"YES\n"<<"1\n";
cout<<n/k<<'\n';
return;
}
else if(n<2*(n-k+1)){
cout<<"YES\n"<<"2\n";
cout<<n-k+1<<" "<<1<<'\n';
return;
}
else cout<<"NO"<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll t; cin>>t; while(t--) solve();
return 0;
}