D. Hemose in ICPC ??
题意：交互题，给一棵树，未知边权，每次可询问一个连通块的最大边权（询问限制次数为log级别），要求输出最大边权。
思路：显然是要二分询问，重点是如何保证图连通，这里要用dfs序解决（新技能get），还有注意这是个交互题，注意交互题格式。
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,x,y,maxx;
vector<int> g[N];
int pos[N*100], tot;
void dfs(int u,int fa){
pos[++tot]=u;
for(int v:g[u]){
if(v==fa) continue;
dfs(v,u);
pos[++tot]=u;
}
}
int query(int l,int r){
set<int> st;
for(int i=l; i<=r; i++) st.insert(pos[i]);
cout<<"? "<<st.size();
for(int i:st) cout<<' '<<i; cout<<endl;
int res; cin>>res; return res; //接受回复
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n;
for(int i=1; i<=n-1; i++){
cin>>x>>y;
g[x].push_back(y); g[y].push_back(x);
}
dfs(1,0);
maxx=query(1,tot);
int l=1, r=tot;
while(1){
if(l+1==r) {cout<<"! "<<pos[l]<<' '<<pos[r]<<endl; return 0;}
int mid=l+r>>1, t=query(l,mid);
if(t==maxx) r=mid;
else l=mid; //注意l和r都是点的位置而非边的位置，所以都是移到mid
}
return 0;
}
?E. Bored Bakry
题意：给一个数组，求一段最长的连续子数组，使得其中所有数字按位与的和（& sum）严格大于按位异或的和（^ sum），要求输出这个长度。
思路：一个子数组满足题意，当且仅当：
- 在某个二进制位，假设为k，子数组中所有数的k位都是1，并且子数组长度是偶数（此时该位的& sum为1，^ sum为0）
- 在k位前面的所有二进制位，^ sum为0。
而实际写代码的时候，数组长度是偶数这个条件并不需要用到，我们只要保证k位的& sum为1,并且1~k位的^ sum都为0即可。
我们用And[ i ]来表示第k位中，前 i 个数字的1的数量（用来判断一段数字是否全为1，如果And[i]-And[p] == i-p，那么就有p+1~i该位都是1，这很显然）
由于还有判断^ sum的要求，我们再弄一个Xor数组，Xor[i]表示a[1]~a[i]所有数字在1~k位的异或和（用来找1~k位^?sum为0的子数组，如果Xor[i] == Xor[p]，那么a[p+1]~a[i]的子数组在1~k位的^ sum为0），注意Xor数组记录的位数随着k的遍历而逐层更新，左边的高位先被更新，右边的低位后被更新。
code：代码很短，但是思维难度很大，我理解了很久才明白。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n,ans;
int a[N], And[N], Xor[N], pre[N];
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n; for(int i=1; i<=n; i++) cin>>a[i];
for(int k=20; k>=0; k--){
for(int i=1; i<=n; i++){
int x = ((a[i]>>k)&1); //a[i]的当前位
And[i]=And[i-1]+x;
Xor[i]^=((And[i]&1)<<k);
}
memset(pre,-1,sizeof(pre));
pre[0]=0; //遇到0肯定是满足的
for(int i=1; i<=n; i++){
if(pre[Xor[i]]==-1) pre[Xor[i]]=i; //最优位置
else{
int p=pre[Xor[i]];
//p+1~i部分满足k层全为1，前面层xorsum全为0，满足题意，更新答案，并且pre位置可以延续
if(And[i]-And[p]==i-p) ans=max(ans,i-p);
else pre[Xor[i]]=i; //否则，说明k层p+1~i不全为1，不满足题意，要更新pre
}
}
}
cout<<ans<<'\n';
}
|