901DIV2 A~D
A:
- 大于等于\(a-1\)的贡献都是a-1.
void solve(){
int ans=0;
int a,b,n;
cin>>a>>b>>n;
ans+=b;
for(int i=1;i<=n;i++){
int x; cin>>x;
if(x>=a) x=a-1;
ans+=x;
}
cout<<ans<<"\n";
}
B:
因为n,m只有50，可以考虑模拟。
- 对于k=1000000和k=1000次的结果，一定是一样的。
- 注意模拟的次数一定和k的奇偶性质一样。
void solve(){
int ans=0;
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++){
cin>>b[i];
}
int flag=0;
if(k>10000){
if(k&1) k=10001;
else k=1000;
}
int now=1;
while(k--){
now^=1;
if(now==0){
int num1,mina1;
num1=0; mina1=1e12;
for(int i=1;i<=n;i++){
if(a[i]<mina1){
mina1=a[i];
num1=i;
}
}
int num2,maxa1;
num2=0; maxa1=0;
for(int i=1;i<=m;i++){
if(b[i]>maxa1) {
num2=i;
maxa1=b[i];
}
}
if(mina1<maxa1){
swap(a[num1],b[num2]);
}
}
else{
int num1,mina1;
num1=0; mina1=1e12;
for(int i=1;i<=m;i++){
if(b[i]<mina1){
mina1=b[i];
num1=i;
}
}
int num2,maxa1;
num2=0; maxa1=0;
for(int i=1;i<=n;i++){
if(a[i]>maxa1) {
num2=i;
maxa1=a[i];
}
}
if(mina1<maxa1){
swap(b[num1],a[num2]);
}
}
}
for(int i=1;i<=n;i++) ans+=a[i];
cout<<ans<<"\n";
}
C:
首先判断一下可不可以：
-
暴力判断：用double存储结果之后，乘以200个2看中间是否会出现整数。
错误的，因为浮点数会出现很不可预料的误差。出现了这样的情况：0.2*2:(去掉整数部分) 0.4 0.8 0.6 0.2 0.4 0.8 0.6 ... 0.6 0.20000001所以不用浮点数的计算来解决判断问题。
-
问题转换为：
给定\(x,y\).现在有\(x/y\)的结果，问这个结果经过无数次的\(*2\)之后，是否会转换为一个整数？- 解决方法：\(y/=gcd(x,y)\).
然后判断y是不是2的倍数，如果是，就可以。不是就不可以。
因为通过乘以2变为整数，分母的众多因子，和2有关系的可以通过乘以2不断消掉，其他的如果出现过类似于\(3,5,7\)这种，必须由分子自行消除掉才可以。
- 解决方法：\(y/=gcd(x,y)\).
-
求解次数问题：
while(1){ int M=t; need[now]=M*m;//整数部分是几 说明需要几个 几个不是几刀捏。 t-=M; t*=2; now++; if(t==0) break; } for(int i=1;i<=200;i++){ ans+=cal(i,need[i]); } int cal(int now,int need){ // cout<<now<<" "<<need<<endl; if(need==0) return 0; int sum=0; if(now==1){ if(hav[now]>need) { hav[now]-=need; return 0; } need-=hav[now]; hav[now]=0; if(need%2==0){ return need/2; } else { hav[need]++; return (need+1)/2; } } else { if(hav[now]>need) { hav[now]-=need; return 0; } need-=hav[now]; hav[now]=0; if(need%2==0){ sum+=need/2; } else { hav[now]++; sum+=(need+1)/2; } sum+=cal(now-1,(need+1)/2); } return sum; }
D:
思路：
有一个结论是，当前mex为x,最终是变为0的，有很多种方式可以到达0，现在如果想要转换为y,也有很多种方式，但是一旦我选择把\(v\)删除，并且v没有被全部删除，我下次一定删除的还是v。
根据贪心的原理，如果v不是最优秀的，我没必要弄v，如果是最优秀的，我就需要一直处理v。
有很多种方式将\(mex\)从v转变为0.最后转变为图论最短路问题。
把每一种方式、路径都处理出来，跑dijikstra即可。
void solve(){
int n; cin>>n;
for(int i=0;i<=n;i++){
vis[i]=0;
ans[i]=-1;
V[i]=0;
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
dis[i][j]=INF;
}
}
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]<=n+1) vis[a[i]]++;
}
int s=-1;
for(int i=0;i<=n;i++){
if(vis[i]==0){
s=i; break;
}
}
if(s==0){
cout<<"0\n"; return ;
}
for(int i=s;i>=0;i--){
for(int j=i-1;j>=0;j--){
dis[i][j]=(vis[j]-1)*i+j;
}
}
priority_queue< pair<int,int> ,vector<pair<int,int>>, greater<pair<int,int>> >q;
q.push({0,s});
while(!q.empty()){
pair<int,int> tsk=q.top();
q.pop();
int u=tsk.second;
if(V[u]) continue;
V[u]=1;
ans[u]=tsk.first;
for(int j=0;j<u;j++){
int now=ans[u]+dis[u][j];
if(ans[j]==-1 || ans[j]>now){
ans[j]=now;
q.push({ans[j],j});
}
}
}
cout<<ans[0]<<"\n";
}