ooliver

2026 暑期每日一题

ooliver OI

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) 得到根节点以及根节点的两个儿子，那 2froot=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+log2(105)=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[PARSE ERROR: Undefined("Command(\"not\")")]=s2

s2,s3 的位置关系大致如下图：

由上图可知，c=s2-s3，那么 a=n-s1-c，那就知道了第一个 1 的位置，从第一个 1 的位置开始二分，找到最后一个满足 ask(pos+1,pos+mid)=mid 的位置，就相当于找到了 b，那就做出来了。

最后最多询问 3+log2(105)=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;
}`