Educational Codeforces Round 135 (Rated for Div. 2)
-
题意
- 有n种球，其数量为cnt[i]，每次拿走两个不同种类的球，直到不能操作
- 问最后剩下的球可能是1～n的哪种
-
题解
- 按题意，只需找出一种可能的情况即可
- 存在一种情况，最后的答案是数量最多的种类，其操作方法为：每次都拿走数量小的两种
-
代码
#include <iostream>
using namespace std;
void solve() {
int n,x,t=0,res=0;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>x;
if(x>t) res=i,t=x;
}
cout<<res<<'\n';
}
int main() {
int t; cin>>t;
while(t--) solve();
return 0;
}
-
题意
- 构造一个n的排列，使得x从1操作到n得到的值最大。
- x的操作为：若x<a[i],那么x+=a[i]，否则x=0，x的初始值为0
-
题解
-
x的最大值为(n-1)+n=2n-1。证明如下 x在位置n时，有两种选择，一是变成0，二是不变成0，x+=最大的值(即为n)，显然选二
接着x在n-1时，有如上两种选择，一样的选择x+=a[n-1],而在a[n]=n的情况下，a[n-1]=n-1最优
在确定了a[n-1],a[n]的情况下，a[n-2]就算取1也不能使得x往后操作变大了，所以直接让x在n-2的位置变为0.举例易得，按照下列方法构造可以保证n-2操作完x=0
n-2为偶数时，除去n-1,n都直按空位接逆序排列
n-2为奇数时，1放在a[1]，除去1,n-1,n都直接按空位逆序排列
-
代码
#include <iostream>
using namespace std;
const int N=110;
int ans[N];
void solve() {
int n; cin>>n;
ans[n]=n,ans[n-1]=n-1;
if(n&1) {
ans[1]=1;
for(int i=2;i<=n-2;i++) ans[i]=n-i;
}
else {
for(int i=1;i<=n-2;i++) ans[i]=n-i-1;
}
for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
puts("");
}
int main() {
int t; cin>>t;
while(t--) solve();
return 0;
}
-
题意
- 给定两个长度为n的数组a,b，对于数组中的数可以进行如下操作：x=(string)x.size()
- 问最少需要变化多少次使得两数组元素完全相同(不计顺序)
-
题解
- 先用一个map预处理a,b中已经相同的数，删掉相同的数
- 对于map中剩下的数，都是没有被消除的，那么大于9的数都一定要进行操作，如此才有可能被匹配消除。与上一条一样，有匹配的消除
- 操作完大于9的数，由数据范围可得，此时map中的数都是1～9，那么只有全变成1才有可能匹配消除掉，所以把剩下的不是1的数都操作成1即可
-
代码
#include <iostream>
#include <map>
#include <string>
#include <cmath>
using namespace std;
void solve() {
map<int,int> h;
long long res=0;
int n,x; cin>>n;
for(int i=0;i<n;i++) cin>>x,h[x]++;//a数组用正数计数
for(int i=0;i<n;i++) cin>>x,h[x]--;//b数组用负数计数
for(auto [val,cnt]: h) {//处理预处理完剩下的大于9的数
if(cnt==0) continue;//正负抵消说明匹配完了
if(val>=10) {//没有被匹配剩下来的，且大于9的数要进行操作
string t=to_string(val);
h[val]=0;
h[t.size()]+=cnt;//注意正负有别
res+=abs(cnt);
}
}
for(auto[val,cnt]: h) {//处理剩余的1～9的数
if(cnt==0 || val==1) continue;
res+=abs(cnt);
}
cout<<res<<'\n';
}
int main() {
cin.tie(0);ios::sync_with_stdio(false);
int t; cin>>t;
while(t--) solve();
return 0;
}
|