2026 暑期每日一题 · ooliver

2026 暑期每日一题 6月25日 P4643 [国家集训队] 阿狸和桃子的游戏观察到题目要求的是得分之差，如果我们将边权均分给两个点，会惊喜的发现对答案没有任何影响，之后就贪心即可。代码： C++ #include using namespace std; const int N=1e5+5; int n,m,ans; int a[N]; int main(){ cin>>n>>m; for(int i=1;i>a[i],a[i]>u>>v>>w; a[u]+=w,a[v]+=w; } sort(a+1,a+1+n); for(int i=1;i>1); return 0; } `#include using namespace std; const int N=1e5+5; int n,m,ans; int a[N]; int main(){ cin>>n>>m; for(int i=1;in;i++) cin>>a[i],a[i]1; for(int i=1;im;i++){ int u,v,w; cin>>u>>v>>w; a[u]+=w,a[v]+=w; } sort(a+1,a+1+n); for(int i=1;in;i++) ans+=pow(-1,i)*a[i]; cout(ans>>1); return 0; }` 6月26日 P15410 「TBOI Round 1」Niton & Matrix 会发现一个点无论怎么变只可能出现在 (i,j),(n-i+1,j),(i,m-j+1),(n-i+1,m-j+1) 这四个位置，并且无论怎么取反都不会影响它们的异或和，所以直接根据这个性质判断即可。代码： C++ #include using namespace std; const int N=1e5+5; int n,m; vector a[N],b[N]; void solve(){ int y=1; for(int i=0;i>n>>m; for(int i=1;i>x; a[i].push_back(x); } } for(int i=1;i>x; b[i].push_back(x); } } for(int i=1;i>1);i++) for(int j=1;j>1);j++) if(a[i][j]^a[n-i+1][j]^a[i][m-j+1]^a[n-i+1][m-j+1]!=b[i][j]^b[n-i+1][j]^b[i][m-j+1]^b[n-i+1][m-j+1]) y=0; cout>T; while(T--) solve(); return 0; } `#include using namespace std; const int N=1e5+5; int n,m; vectorint> a[N],b[N]; void solve(){ int y=1; for(int i=0;iN;i++) a[i].clear(),b[i].clear(); cin>>n>>m; for(int i=1;in;i++){ a[i].push_back(0); for(int j=1;jm;j++){ int x; cin>>x; a[i].push_back(x); } } for(int i=1;in;i++){ b[i].push_back(0); for(int j=1;jm;j++){ int x; cin>>x; b[i].push_back(x); } } for(int i=1;i(n>>1);i++) for(int j=1;j(m>>1);j++) if(a[i][j]^a[n-i+1][j]^a[i][m-j+1]^a[n-i+1][m-j+1]!=b[i][j]^b[n-i+1][j]^b[i][m-j+1]^b[n-i+1][m-j+1]) y=0; cout(y?"Yes\n":"No\n"); return; } signed main(){ int T; cin>>T; while(T--) solve(); return 0; }` 6月30日 P14511 [NFLSPC #8] 轨道交通假设最优策略下交点个数为 0。当我们只管每个点的 x 坐标，将所有点排序后选最前面两个颜色相等的点，然后把前面的点全部删掉，这样每个颜色不被配对但被删掉的点最多有 n-1 个，而每个颜色又有 n+1 个点，剩下两个点刚好可以配对，所以按照这样的策略一定能找到最优解。注意纵坐标并不能忽略，我们在删除之前的点时没有删除与当前点横坐标相等的所有点，所以在横坐标相同的情况下还需要按照纵坐标排序以下，这样彻底规避了线段有交的情况。代码： C++ #include using namespace std; const int N=1e3+5; int n,T; struct node{ int col,x,y,id; bool operator a; int ans[N][2],tag[N]; void solve(){ a.clear(); memset(tag,0,sizeof tag); memset(ans,0,sizeof ans); cin>>n; for(int i=1;i>x>>y; a.push_back({i,x,y,j}); } sort(a.begin(),a.end()); for(int i=1;i mp; while(a.size()){ auto[col,x,y,id]=a.front(); a.pop_front(); if(mp[col]==0) mp[col]=id; else if(!tag[col]){ ans[col][0]=mp[col],ans[col][1]=id; sort(ans[col],ans[col]+2); tag[col]=1; break; } } } for(int i=1;i>T; while(T--) solve(); return 0; } `#include using namespace std; const int N=1e3+5; int n,T; struct node{ int col,x,y,id; bool operatorconst node &a)const{ if(x!=a.x) return xa.x; return ya.y; } }; dequenode> a; int ans[N][2],tag[N]; void solve(){ a.clear(); memset(tag,0,sizeof tag); memset(ans,0,sizeof ans); cin>>n; for(int i=1;in;i++) for(int j=1;jn+1;j++){ int x,y; cin>>x>>y; a.push_back({i,x,y,j}); } sort(a.begin(),a.end()); for(int i=1;in;i++){ mapint,int> mp; while(a.size()){ auto[col,x,y,id]=a.front(); a.pop_front(); if(mp[col]==0) mp[col]=id; else if(!tag[col]){ ans[col][0]=mp[col],ans[col][1]=id; sort(ans[col],ans[col]+2); tag[col]=1; break; } } } for(int i=1;in;i++) coutans[i][0]" "ans[i][1]"\n"; } int main(){ cin>>T; while(T--) solve(); return 0; }` 7月1日 P15061 琥峪枫不难发现，可以用 n 个次数求出： ∑i=1nask(i,1)=3∑i=1nfi−2∑i∈叶子节点fi−froot\sum_{i=1}^{n} ask(i,1) = 3\sum_{i=1}^{n}f_i - 2\sum_{i\in 叶子节点} f_i-f_{root} 再使用 n-1 次 ask(i,h+1) 得到根节点以及根节点的两个儿子，那 2f_{root}=dis(lson,1)+dis(rson,1)-dis(root,2)，叶子节点的权值和根据定义也很好求。代码： C++ #include using namespace std; const int N=5e5+5; long long a[N]; long long ask(int u,int d); long long solve(int subtask,int h){ int n=(1b; long long ans=0,c0=0,c1=0; for(int i=1;i `#include using namespace std; const int N=5e5+5; long long a[N]; long long ask(int u,int d); long long solve(int subtask,int h){ int n=(1h)-1,rt=-1; vectorint>b; long long ans=0,c0=0,c1=0; for(int i=1;in;i++) ans+=a[i]=ask(i,1); for(int i=1;in;i++) if(!ask(i,h+1)) b.push_back(i); if(b.size()3) b.push_back(n); for(int i=0;i3;i++){ long long x=ask(b[i],h); if(!x) rt=b[i]; else c0+=a[b[i]],c1+=x; } return (ans+(c11)+(c0-ask(rt,2))/2)/3; }` 7月2日 P15303 『NFC-OI R1』序列陆先看特殊情况： 1. c=1 直接询问 1 的数量即可。 2. c=2 先询问 1 的数量，再二分找到最后一个 ask(1,i)=0 的位置，询问次数 1+log_2(10^5)=18，刚好。 3. c=0 先询问 1 的数量，记为 s1。令 s2=ask(n-s1+1,n)，若 s1=s2，说明所有的 1 都在最后，直接输出即可。否则序列应该长下面这个样子：（图中 c 与输入的 c 不一致）再令 s3=ask(n-s2+1,n)，若 s3=s2 说明 s2,s3 的位置关系应该如下图：这时图中的 d=s2，b=s1-s2，再和上面一样二分找到最后一个 ask(1,i)=0 的位置即可。若 s3\not = s2 s2,s3 的位置关系大致如下图：由上图可知，c=s2-s3，那么 a=n-s1-c，那就知道了第一个 1 的位置，从第一个 1 的位置开始二分，找到最后一个满足 ask(pos+1,pos+mid)=mid 的位置，就相当于找到了 b，那就做出来了。最后最多询问 3+log_2(10^5)=20，符合要求。代码： C++ #include using namespace std; int n,k,c,x; int ask(int l,int r){ int xx; cout>xx; return xx; } signed main(){ cin>>n>>k>>c; if(c==1){ x=ask(1,n); cout>1; x=ask(1,mid); if(x>0) r=mid; else l=mid+1; } int pos=l; x=ask(1,n); cout>1; x=ask(1,mid); if(x>0) r=mid; else l=mid+1; } int pos=l; cout>1; x=ask(pos+1,pos+mid); if(x==mid) l=mid; else r=mid-1; } cout `#include using namespace std; int n,k,c,x; int ask(int l,int r){ int xx; cout"? "l" "rendl; cin>>xx; return xx; } signed main(){ cin>>n>>k>>c; if(c==1){ x=ask(1,n); cout"! "; for(int i=1;in-x;i++) cout"0 "; for(int i=1;ix;i++) cout"1 "; coutendl; return 0; } else if(c==2){ int l=1,r=n; while(lr){ int mid=(l+r)>>1; x=ask(1,mid); if(x>0) r=mid; else l=mid+1; } int pos=l; x=ask(1,n); cout"! "; for(int i=1;ipos;i++) cout"0 "; for(int i=1;ix;i++) cout"1 "; for(int i=pos+x;in;i++) cout"0 "; coutendl; return 0; } int a,b; a=ask(1,n); b=ask(n-a+1,n); if(a==b){ cout"! "; for(int i=1;in-a;i++) cout"0 "; for(int i=1;ia;i++) cout"1 "; coutendl; return 0; } c=ask(n-b+1,n); if(b==c){ int l=1,r=n; while(lr){ int mid=(l+r)>>1; x=ask(1,mid); if(x>0) r=mid; else l=mid+1; } int pos=l; cout"! "; for(int i=1;ipos-1;i++) cout"0 "; for(int i=1;ia-b;i++) cout"1 "; for(int i=1;in-a-pos+1;i++) cout"0 "; for(int i=1;ib;i++) cout"1 "; coutendl; return 0; } else{ int zero=a-b,pos=n-a-zero; int l=1,r=a; while(lr){ int mid=(l+r+1)>>1; x=ask(pos+1,pos+mid); if(x==mid) l=mid; else r=mid-1; } cout"! "; for(int i=1;ipos;i++) cout"0 "; for(int i=1;il;i++) cout"1 "; for(int i=1;izero;i++) cout"0 "; for(int i=1;ia-l;i++) cout"1 "; coutendl; return 0; } return 0; }`