CF1305A Kuroni and the Gifts
思路：
将两个数组都从小到大排序，因为数组里不会有重复元素，所以和也不会重复。
代码：
int main(){
int _=read;
while(_--){
int n;cin>>n;
vector<int>a,b;
int x;
for(int i=0;i<n;i++) cin>>x,a.push_back(x);
for(int i=0;i<n;i++) cin>>x,b.push_back(x);
sort(a.begin(),a.end());
sort(b.begin(),b.end());
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
for(int i=0;i<n;i++){
cout<<b[i]<<" ";
}
cout<<endl;
}
return 0;
}
CF1305B Kuroni and Simple Strings
题意：
给定一个括号序列，删除所有的合法括号序列使得不能再删除。求方法。
思路：
首先，删除一次和删除多次是等价的，所以k只有0和1两种选择。
其次，删除后的序列一定是以某个点为分界点，左边全部是），右边全部是（。
所以就可以设两个指针，分别从开始和结尾向后扫，左指针记录（的位置，右指针记录）的位置，直到两个指针相遇。
答案的输出要升序输出。
代码：
char s[maxn];
int main(){
cin>>s+1;
vector<int>res;
int l=1,r=strlen(s+1);
while(l<r){
if(s[l]==')') l++;
else{
if(s[r]=='(') r--;
else{
res.push_back(l),res.push_back(r);
l++,r--;
}
}
}
if(res.size()==0) puts("0");
else{
cout<<"1
"<<res.size()<<endl;
sort(res.begin(),res.end());
for(int i=0;i<res.size();i++)
cout<<res[i]<<" ";
}
return 0;
}
CF1305C Kuroni and Impossible Calculation
思路：
看到m的数据范围很小，还是犹豫了一下才想到。
做过很多遍的鸽笼原理了。
由于m很小，当n>m时，一定会有两项a[i]的值相同，这就使得答案为0；
反之，直接n^2暴力跑就可以了。
代码：
const int maxn =2e5+100,mod=998244353;
int n,m,a[maxn];
int main(){
n=read,m=read;
for(int i=1;i<=n;i++) a[i]=read;
if(n>m) cout<<"0"<<endl;
else{
ll ans=1;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
ans=ans*abs(a[i]-a[j])%m;
cout<<ans<<endl;
}
return 0;
}
CF1305D Kuroni and the Celebration
思路：
交互题。考虑叶子节点的特殊性：如果两个叶子节点的lca为其中一个的话，这个一定是根节点。不是的话，就删除这两个叶子节点，继续找下一个叶子节点。 最多执行n/2次。
也就是说首先将所有度数为1的点（叶子节点）放到队列里，每次取出两个叶子节点，求他们的lca，如果不是这两个点的话，将该点删除，并将相邻点的度数-1,寻找新的叶子节点。
代码：
int n;
vector<int>g[maxn];
int din[maxn];
queue<int>q;
int ask(int l,int r){
cout<<"? "<<l<<" "<<r<<endl;
fflush(stdout);
int pos;cin>>pos;
return pos;
}
int vis[maxn];
int main(){
cin>>n;
for(int i=2;i<=n;i++){
int u=read,v=read;
g[u].push_back(v);
g[v].push_back(u);
din[u]++;din[v]++;
}
for(int i=1;i<=n;i++)
if(din[i]==1) q.push(i);
for(int i=1;i<=n/2;i++){
int u=q.front();q.pop();
int v=q.front();q.pop();
int res=ask(u,v);
if(res==u||res==v){
cout<<"! "<<res<<endl;
return 0;
}
for(int i=0;i<g[u].size();i++){
int t=g[u][i];
din[t]--;
if(!vis[t]&&din[t]==1) q.push(t);
}
for(int i=0;i<g[v].size();i++){
int t=g[v][i];
din[t]--;
if(!vis[t]&&din[t]==1) q.push(t);
}
vis[u]=1;vis[v]=1;
}
for(int i=1;i<=n;i++)
if(vis[i]==0){
cout<<"! "<<i<<endl;break;
}
return 0;
}