2026 暑期每日一题
6月25日 P4643 [国家集训队] 阿狸和桃子的游戏
观察到题目要求的是得分之差，如果我们将边权均分给两个点，会惊喜的发现对答案没有任何影响，之后就贪心即可。
代码：
#include<bits/stdc++.h>
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<=n;i++) cin>>a[i],a[i]<<=1;
for(int i=1;i<=m;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;i<=n;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)$ 这四个位置，并且无论怎么取反都不会影响它们的异或和，所以直接根据这个性质判断即可。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> a[N],b[N];
void solve(){
int y=1;
for(int i=0;i<N;i++) a[i].clear(),b[i].clear();
cin>>n>>m;
for(int i=1;i<=n;i++){
a[i].push_back(0);
for(int j=1;j<=m;j++){
int x;
cin>>x;
a[i].push_back(x);
}
}
for(int i=1;i<=n;i++){
b[i].push_back(0);
for(int j=1;j<=m;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$ 个点，剩下两个点刚好可以配对，所以按照这样的策略一定能找到最优解。
注意纵坐标并不能忽略，我们在删除之前的点时没有删除与当前点横坐标相等的所有点，所以在横坐标相同的情况下还需要按照纵坐标排序以下，这样彻底规避了线段有交的情况。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,T;
struct node{
int col,x,y,id;
bool operator<(const node &a)const{
if(x!=a.x) return x<a.x;
return y<a.y;
}
};
deque<node> 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<=n;i++) for(int j=1;j<=n+1;j++){
int x,y;
cin>>x>>y;
a.push_back({i,x,y,j});
}
sort(a.begin(),a.end());
for(int i=1;i<=n;i++){
map<int,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;i<=n;i++) cout<<ans[i][0]<<" "<<ans[i][1]<<"\n";
}
int main(){
cin>>T;
while(T--) solve();
return 0;
}7月1日 P15061 琥峪枫
不难发现，可以用 $n$ 个次数求出：
再使用 $n-1$ 次 $ask(i,h+1)$ 得到根节点以及根节点的两个儿子，那 $2f_{root}=dis(lson,1)+dis(rson,1)-dis(root,2)$，叶子节点的权值和根据定义也很好求。
代码：
#include<bits/stdc++.h>
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=(1<<h)-1,rt=-1;
vector<int>b;
long long ans=0,c0=0,c1=0;
for(int i=1;i<=n;i++) ans+=a[i]=ask(i,1);
for(int i=1;i<n;i++) if(!ask(i,h+1)) b.push_back(i);
if(b.size()<3) b.push_back(n);
for(int i=0;i<3;i++){
long long x=ask(b[i],h);
if(!x) rt=b[i];
else c0+=a[b[i]],c1+=x;
}
return (ans+(c1<<1)+(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$，符合要求。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,k,c,x;
int ask(int l,int r){
int xx;
cout<<"? "<<l<<" "<<r<<endl;
cin>>xx;
return xx;
}
signed main(){
cin>>n>>k>>c;
if(c==1){
x=ask(1,n);
cout<<"! ";
for(int i=1;i<=n-x;i++) cout<<"0 ";
for(int i=1;i<=x;i++) cout<<"1 ";
cout<<endl;
return 0;
}
else if(c==2){
int l=1,r=n;
while(l<r){
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;i<pos;i++) cout<<"0 ";
for(int i=1;i<=x;i++) cout<<"1 ";
for(int i=pos+x;i<=n;i++) cout<<"0 ";
cout<<endl;
return 0;
}
int a,b;
a=ask(1,n);
b=ask(n-a+1,n);
if(a==b){
cout<<"! ";
for(int i=1;i<=n-a;i++) cout<<"0 ";
for(int i=1;i<=a;i++) cout<<"1 ";
cout<<endl;
return 0;
}
c=ask(n-b+1,n);
if(b==c){
int l=1,r=n;
while(l<r){
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;i<=pos-1;i++) cout<<"0 ";
for(int i=1;i<=a-b;i++) cout<<"1 ";
for(int i=1;i<=n-a-pos+1;i++) cout<<"0 ";
for(int i=1;i<=b;i++) cout<<"1 ";
cout<<endl;
return 0;
}
else{
int zero=a-b,pos=n-a-zero;
int l=1,r=a;
while(l<r){
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;i<=pos;i++) cout<<"0 ";
for(int i=1;i<=l;i++) cout<<"1 ";
for(int i=1;i<=zero;i++) cout<<"0 ";
for(int i=1;i<=a-l;i++) cout<<"1 ";
cout<<endl;
return 0;
}
return 0;
}
Comments NOTHING