codeforce刷题②交互题
打codeforces第⼆周
⼜遇到了很多有意思的题型，可⾃⼰还是太菜了
写份博客记录⼀下憨憨的⾃⼰
做的第⼀道交互题，记录⼀下
1.1407C Chocolate Bunny（交互题+双指针）
题⽬链接：
This is an interactive problem. 这是⼀道交互题
你通过打印问题询问他，他给你结果，让你找到最终的数组
需要清除缓存区，才能保证正确，否则就会Idleness limit exceeded（我第⼀次见这种错误，因为没读清楚题，⼀直在第1个测试点报这个错误还是做题太少了）我把所有的printf换成cout就ac了或者每次输出后都加⼀句cout.flush()或fflush(stdout)
题⽬⼤意
样例解释：给你n=3，说明让你得到的数组中只包括1,2,3三个元素，让你找到最终顺序。
根据结果：他找到的最终顺序是 1 3 2
你可以通过询问来查找，？ 1 2 就是询问你第⼀个位置的数%第⼆个位置数得到的值，在输⼊框中给答案 1 。即1%3 -> 1。
解题思路
每当⽐较两个位置的数 a , b 的时候，进⾏两次 a % b 和 b % a就⼀定可以得出那个⼩的数。 1 % 3 = 1 ,
3 % 1 = 0，所以找那个稍微⼤的数，就是准确的值。
所以，可以运⽤双指针，第⼀个指针指向左边那个未得到答案的位置，第⼆个指针⼀直向后移动，到最后只有⼀个值没有得到，再寻找⼀遍谁未赋值再赋值就可以了。AC代码
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1e4+4;
int ans[maxn];
bool vis[maxn];
int main(){
int n;
scanf("%d",&n);
int x=1;
int s,c;
for(int i=2;i<=n;i++){
cout<<"? "<<x<<' '<<i<<endl;
cin>>s;
cout<<"? "<<i<<' '<<x<<endl;
cin>>c;
if(s<c){
ans[i]=c;
vis[c]=true;
}el{
ans[x]=s;
vis[s]=true;
x=i;
}
}
int xx;
for(int i=1;i<=n;i++){
if(!vis[i]){
xx=i;
break;
}
}
cout<<"!";
for(int i=1;i<=n;i++){
if(ans[i]==0){
ans[i]=xx;
}
cout<<' '<<ans[i];
}
return 0;
}
2.1417 C. k-Amazing Numbers ( 思维 )
这道题的思维真的很奇特~。
⼤致题意
t = 3
给n = 5（数组中有5个数）分别是 1 2 3 4 5
结果是：第⼀个数：所有的包含⼀个数的⼦数组共同包含的最⼩的数（没有则输出-1）
第⼆个数：所有包含两个数的⼦数组共同包含的最⼩的数
.......
解题思路
遍历⼀遍数组找到每个数距离相邻同元素最远的距离（相当于最多差⼏个数能找到第⼆个它）左右两边也要处理。
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 3e5+5;
int a[N];
int d[N];//⽤来存当前位置
int f[N];//⽤来存每个数相邻的最⼩间距
int x[N];//⽤来存每个位置的最⼩值（输出答案时使⽤）
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
memt(x,0x3f,sizeof x);
memt(f,0,sizeof f);
memt(d,0,sizeof d);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
f[a[i]]=max(f[a[i]],i-d[a[i]]);
d[a[i]]=i;
}
for(int i=1;i<=n;i++){
if(f[i]!=0){
f[i]=max(f[i],n+1-d[i]);
x[f[i]]=min(x[f[i]],i);
}
}
int xx=0x3f3f3f3f;
for(int i=1;i<=n;i++){
if(x[i]!=0x3f3f3f3f){
xx=min(x[i],xx);
}
if(xx!=0x3f3f3f3f){
cout<<xx<<' ';
}el{
cout<<"-1 ";
}
}
cout<<endl;
}
return 0;
}
3.1443 B. Saving the City（贪⼼）
题⽬⼤意
有很多城市，城市下⾯可能有炸弹，1表⽰有炸弹，0表⽰没有。
为了拆除所有的炸弹，有两种⽅法。
第⼀种：引爆炸弹其引爆的n+1和n-1的位置的炸弹也会被引爆。
第⼆种：放新的炸弹，和原来炸弹合并在⼀起，⽤其他的炸弹的引爆来引爆它。
解题思路
排除⼀个炸弹的时候⼀定是通过引爆的形式排除的。排除后⾯的可以选择引爆或者与前⾯的连接。这时候贪⼼即可，看哪个便宜，选哪个。AC代码
#include <iostream>
#include <string>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int a,b;
string x;
cin>>a>>b>>x;//个数>b/a+1的时候选a+b 否则n*a
int len=x.size();
bool flag=fal;
int ans=0;
int num=0;
for(int i=0;i<len;i++){
if(x[i]=='1'&&!flag){
flag=true;
ans+=a;
num=0;
}el{
if(x[i]=='0'){
num++;
}
el{
if(num)
ans+=min(a,num*b);
num=0;
}
}
}
cout<<ans<<endl;
}
return 0;
}
