前情提要：我是沙币
A. Hayato and
贪心，不大想讲
代码写的很丑
void solve (){
vector<int> a;
int n,x;
cin >> n ;
a.push_back(0);
for(int i=1;i<=n;++i) cin >> x,a.push_back(x);
int t1=0,t2=0;
for(int i=1;i<=n;++i) if(a[i]&1) t1++;else t2++;
if((t1>=3)||((t1>=1)&&(t2>=2))){
cout << "YES" << endl;
int sum=0;
if(t1>=3){
for(int i=1;i<=n;++i){
if(a[i]&1) {
cout << i << " ";
sum++;
if(sum==3) break;
}
}
}
else {
for(int i=1;i<=n;++i){
if(a[i]&1){
cout << i << " ";
break;
}
}
for(int i=1;i<=n;++i){
if(!(a[i]&1)){
cout << i << " ";
sum++;
if(sum==2) break;
}
}
}
cout << endl;
}
else cout << "NO" << endl;
}
B. GCD Partition
生动的体现了我数论方面的薄弱
考场上只想出来了一个 \(O(n\sqrt{\sum a_i})\) 的垃圾做法，就不展开了
我们发现，k=2 的时候一定是最优的，因为若 \(d\mid a \,,\,d\mid b\) 则一定有 \(d\mid a+b\)
所以我们发现，合并两个区间一定是不亏的
代码明天补上
D. Bit Guessing
不要问为什么没有 C ，问就是有 Hack 把 std 叉了
第一次在 CF 上做交互题，然后因为输出少一个空格挂掉了
自然考虑按位做，用一个指针 p 指向现在扫到了哪一位
我们发现，不能减到负数是一个十分讨厌的条件，所以我们要从小到大减
每一次减数，有两种可能
1.减的地方是 1
2.不是 1
关于第一种，我们直接令 p++ 就可以，而对于第二种情况，我们发现，当前位到下一个有 1 的这一段中，所有的位都会被翻转
具体的，如果情况为 1 ，则 1 的数量会下降 1，我们将这个位置加入答案
如果我们设增加数为 k，则下一位就在 p+k+1 的位置，我们将其加入答案，然后移动指针到其的下一位
void solve (){
int cnt;
cin >> cnt;
int p=0,now=0,ans=0,re=cnt;
while(re--){
cout << "- " << (1<<p) << endl;
cout.flush();
cin >> now;
cout.flush();
if(cnt==now+1){//减到了 1 上
ans+=(1<<p);
++p;
}
else {
int k=now-cnt+1;
ans+=(1<<(p+k));
p+=k+1;
}
cnt=now;
}
cout << "! " << ans << endl;
EF先鸽着，最早明天
标签：846,cnt,cout,int,Codeforces,mid,Div,now,我们 From： https://www.cnblogs.com/Benzenesir/p/17077462.html