[CF1115 div2]
https://codeforces.com/contest/2252/problem/A A 题意可知,要使打出的伤害最高,出的牌要最多 我们考虑牌数最多的牌,因为少的牌能用来当多的牌的挡板,是一定能用掉的 所以我们考虑 最多牌的次数为m ,剩下的牌为 n-m 那最多的牌次数最多可以有 n-m+2 个 因为最末尾可以连放两个 于是有两种情况 1.m<=n-m+2 全部牌都能打出 2.m>n-m+2 多的牌太多了 多出的牌为 m - (n-m+2) 减去即可 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include<bits/stdc++.h> using namespace std; typedef long long ll; void solve(){ int n; cin>>n; vector<int> a(n); int sum=0; int m=0; int t=0; vector<int> cnt(1005,0); for(int i=0;i<n;i++){ cin>>a[i]; sum+=a[i]; cnt[a[i]]++; if(cnt[a[i]]>m){ m=cnt[a[i]]; t=a[i]; } } if(m<=n-m+2){ cout<<sum<<'\n'; } else cout<<sum- t * (2*m -n -2)<<"\n"; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int ttt=1; cin>>ttt; while(ttt--){ solve(); } return 0; } https://codeforces.com/contest/2252/problem/B B 留下的字符串为交替,且我们删去的字符也是要交替的 设原来有 N个0 和 M个1 ,最终有 n个0 和 m个1 我们删去了d0 = N - n 个0 d1 = M-m 个 1 且 |d0 - d1| < = 1 代入得 | (N-M) - (n-m) | < =1 令 x = (N-M) y = (n-m) 且 y的值只能在 {-1,0,1} 三者取 因| x - y | <= 1 即 x>2 或 x<-2 无解 若有解 考虑最少操作次数,也就是保留的字符串要最长 理论最长肯定是 原先字符串 01块 的大小 我们可以算出这个 01 块 的 Y 值(即0和1的个数差) 因为 最终 y肯定在{-1,0,1} 三者取 我们遍历一遍 算出 Y 到 y 这个过程中要变的 长度即 min(|Y-y|) 保留的就是01块长度 len - |Y-y| 最后的操作次数就是原长减去保留 ...