还剩最后一次刷codeforces的题，以后就会以算法专题为主了，CF的题主要用来拓拓思路，磨练一下手感。

Wonderful Coloring - 2
模拟+桶
题意：给定n个元素和k个桶，问：当满足每个桶中无相同元素且所有桶中元素个数一致时的方案

思路：
1.我们把每种元素的个数分出，这种元素大于等于k时，所有桶都可以分一个这种元素，多出的就不放入桶中
2.如果这种元素小于k个，就放入left桶中
3.最后把left桶中的所有元素，每k个为一份，每份均分一个给所有桶，不足k个时left桶中的元素就不再放入这k个桶中

#include <bits/stdc++.h>
using namespace std;
using ll = long long;void solve_case() {ll n, k;cin >> n >> k;vector<ll> nums(n);map<ll, vector<ll>> mp;for (ll i = 0; i < n; ++i) {cin >> nums[i];mp[nums[i]].push_back(i);}vector<ll> left;vector<ll> res(n, 0);//等于0细节for (auto p : mp) {if (p.second.size() >= k) {ll c = 0;for (ll j : p.second) {if (c < k)res[j] = ++c;}} else {for (ll j : p.second)left.push_back(j);}}// no more collisions?for (ll i = 0; i + k - 1 < left.size(); i += k)//i + k - 1 < left.size() 判断是否够均分一次k个桶，不够的话剩余的就全部不涂色了{ll c = 0;for (ll j = i; j < i + k; ++j)res[left[j]] = ++c;}for (ll i : res)cout << i << " ";cout << "\n";
}int main() {ios_base::sync_with_stdio(false);cin.tie(NULL);int t;cin >> t;while (t--) {solve_case();}
}

And It’s Non-Zero

前缀和+位运算操作

题意：给定l r两个整数，问如果从l到r一直做位运算的&（and）操作，需要删除多少个数才能让结果不为0

思路：
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1

各个位1的数目为2 2 3

对应答案为：r-l+1-max(l到r区间某个位上1的个数)

操作1：lowbit
返回二进制最低位的1对应的值

x&-x

操作2：统计这个数上那些位是1

s数组表示i这个位置上第j位是1
x^=x&-x可以把每次扫描的最低位消去，或者你直接减去也行

void bits(int x)
{int t=x;while(x){cout<<x<<" ";s[t][f[x&-x]]++;x^=x&-x;///异或操作去除最低位cout<<x<<endl;}cout<<endl;
}

操作3：前缀和维护

for(int i=2;i<=200000;i++){f[i]=f[i>>1]+1;///按理来说，我们只需要吧2^n对应是第几号二进制位存储就行了bits(i);for(int j=0;j<19;j++)s[i][j]+=s[i-1][j];}

#include <bits/stdc++.h>using namespace std;
int t,l,r,s[200000+10][19],f[200000+10];
void bits(int x)
{int t=x;while(x){cout<<x<<" ";s[t][f[x&-x]]++;x^=x&-x;///异或操作去除最低位cout<<x<<endl;}cout<<endl;
}
int main()
{f[0]=0;s[1][0]=1;for(int i=2;i<=200000;i++){f[i]=f[i>>1]+1;///按理来说，我们只需要吧2^n对应是第几号二进制位存储就行了bits(i);for(int j=0;j<19;j++)s[i][j]+=s[i-1][j];}for(cin>>t;t;t--){cin>>l>>r;int ans=0;for(int i=0;i<19;i++)ans=max(ans,s[r][i]-s[l-1][i]);cout<<r-l+1-ans<<endl;}return 0;
}

Mirror in the String
水题，可以练练思维

#include<cstdio>
int _,i,n,f;
char s[200001];
int main(){scanf("%d",&_);while(_--){scanf("%d%s",&n,s+1);f=0;for(i=1;i<n;i++)if(s[i]>s[i+1])f=1;else if(s[i]<s[i+1]||(s[i]==s[i+1]&&!f))break;s[i+1]=0;printf("%s",s+1);for(;i>=1;i--)putchar(s[i]);puts("");}
}

Balanced Stone Heaps
最大值最小，最小值最大，这一类的问题都是二分答案的标志

#include <bits/stdc++.h>
using namespace std;
const int N=200005,INF=0x3f3f3f3f;
int T,n,a[N],b[N];
bool check(int lim)
{for(int i=1;i<=n;++i)b[i]=a[i];///复制？for(int i=n;i>=3;--i){if(b[i]<lim)return 0;int can=min(a[i],(b[i]-lim))/3;b[i]-=can*3;b[i-1]+=can*1;b[i-2]+=can*2;}if(b[1]<lim||b[2]<lim)return 0;return 1;
}
int main()
{for(cin>>T;T;T--){int l=INF,r=0,mid=0,ans;cin>>n;for(int i=1;i<=n;++i){scanf("%d",&a[i]);l=min(l,a[i]);r=max(r,a[i]);///寻找最小值和最大值}while(l<=r){mid=(l+r)>>1;if(check(mid))l=mid+1,ans=mid;elser=mid-1;}printf("%d\n",ans);}return 0;
}