2026 暑期每日一题

ooliver 发布于 6 小时前 25 次阅读 OI

AI 摘要

**引言** 把边权分给点，答案竟毫发无损？翻转如何不影响异或和？2026暑期每日一题，两道巧思题带你破译贪心与矩阵翻转的隐藏规律。

2026 暑期每日一题

6月25日 P4643 [国家集训队] 阿狸和桃子的游戏

观察到题目要求的是得分之差，如果我们将边权均分给两个点，会惊喜的发现对答案没有任何影响，之后就贪心即可。

代码：

C++
#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)$ 这四个位置，并且无论怎么取反都不会影响它们的异或和，所以直接根据这个性质判断即可。

代码：

C++
#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;
}