D E (Endfield)

2n + 1 的情形

考虑异或运算的两个重要性质：

1. 恒等律:
2. 归零律:

记 ，则 即为答案。

证明: 由归零律，所有出现过两次的数字变成了 0。由于恒等律，那些只出现一次的数字与 0 异或的结果为那个数字。

2n + 2 的情形

我们可以找到一种序列 的划分方式，使得两个只出现一次的数 处于不同的部分。然后按照 的情形，将两部分分别求异或即可。

一种简单且合理的划分方法：首先求出 的值（等价于求整个序列的异或和），再求出 ，根据 的二进制表示在这一位是否为 1 将序列划分。

时间复杂度，空间复杂度。 这道题没有卡时间复杂度和空间复杂度 时间复杂度做法：位运算、unordered_set（没有卡哈希） 时间复杂度的做法也可以接受：离散化、set等都可以解决

#include<bits/stdc++.h>
// #define int long long
#define all(x) (x).begin(), (x).end()


using namespace std;
typedef long long ll;
using i64 =long long;
using i128 =__int128;
template<class T>void debug(const vector<T> & v,int l,int r){for(int i=l;i<=r;i++){cout<<v[i]<<' ';}cout<<'\n';}
template<class T>void debug(const vector<T> & v){for(int i=1;i<v.size();i++){cout<<v[i]<<' ';}cout<<'\n';}
template<class T>void debug(const T & v){cout<<v<<'\n';}
template<class T>bool chmax(T &a,const T& b) {if(a >= b) return false;a = b; return true;}
template<class T>bool chmin(T &a,const T& b) {if(a <= b) return false;a = b; return true;}
mt19937 rng(time(0));
mt19937_64 rng64((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

ll lowbit(ll x){
	return x&(-x);
}

void Main(){
	ll n;
	cin>>n;
	ll x;
	ll ab = 0;
    for(int i=1;i<=2*n+2;i++){
    	cin>>x;
    	ab^=x;
	}
	ll lb = lowbit(ab);
	ll num1=0,num2=0;
    for(int i=1;i<=2*n+2;i++){
    	cin>>x;
    	if(x&lb)num1^=x;
    	else num2^=x;
	}
	if(num1>num2)swap(num1,num2);
	cout<<num1<<' '<<num2;
}



int32_t main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    
    int _ = 1;
//     cin>>_;

    while(_--)Main();

    return 0;
}

2n + 3 的情形

记三个只出现一次的数分别为 。

设 。

则 ，则 。

令 。

断言 1： 互不相等。

证明 1：

考虑反证法：由 互不相等，且 均不为 0。若 ，则 ，矛盾。

接下来令 。

断言 2： 中有且仅有两个数相等。

证明 2：

不妨设这三个数中最小的数是 ，令，则由 知， 中定然有一个数在第 位为 1，另一个数在该位上为 0。不妨设 在该位上为 ，

设 , 为 最低位所在位置。 由断言 2， 中所有数对应的 的异或和为 。由 在第 位上为 ，且不妨设 在该位为 ， 在该位为 。故可按照 在第 位上是否为 ，将 分成两个部分。每部分的异或值恰好为，那么。

然后，问题就转化为 的情形，共需读入序列 四次(由于牛客所开空间的限制，这里只读一次，并用数组存储)。

时间复杂度，空间复杂度。

#include<bits/stdc++.h>
// #define int long long
#define all(x) (x).begin(), (x).end()

using namespace std;
typedef long long ll;
using i64 =long long;
using i128 =__int128;
template<class T>void debug(const vector<T> & v,int l,int r){for(int i=l;i<=r;i++){cout<<v[i]<<' ';}cout<<'\n';}
template<class T>void debug(const vector<T> & v){for(int i=1;i<v.size();i++){cout<<v[i]<<' ';}cout<<'\n';}
template<class T>void debug(const T & v){cout<<v<<'\n';}
template<class T>bool chmax(T &a,const T& b) {if(a >= b) return false;a = b; return true;}
template<class T>bool chmin(T &a,const T& b) {if(a <= b) return false;a = b; return true;}
mt19937 rng(time(0));
mt19937_64 rng64((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

ll lowbit(ll x){
	return x&(-x);
}

void Main(){
	ll n,x;
	cin>>n;
	vector<ll> ans(4);
	ll xor1 = 0;
	//求a[i]异或和 
    for(int i=1;i<=2*n+3;i++){
    	cin>>x;
    	xor1^=x;
	}
	
	ll lb1 =0;
	//求f[b[i]] 异或和 
	for(int i=1;i<=2*n+3;i++){
		cin>>x;
		lb1^=lowbit(x^xor1);
	}
	//划分为两部分 
	ll xor2 =0;
	for(int i=1;i<=2*n+3;i++){
		cin>>x;
		if((x^xor1)&lb1)xor2^=(x^xor1);
	}
	//第一个数 
	ans[1]=xor1^xor2;
	
	//求第二个数
	ll lb2 = lowbit(ans[1]^xor1);
	if(ans[1]&lb2)ans[2]=ans[1];
	else ans[2]=0;
    for(int i=1;i<=2*n+3;i++){
    	cin>>x;
    	if(x&lb2)ans[2]^=x;
	}
	ans[3]=xor1^ans[1]^ans[2];
	sort(ans.begin()+1,ans.end());
	cout<<ans[1]<<' '<<ans[2]<<' '<<ans[3]<<'\n';
}


int32_t main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    
    int _ = 1;
//     cin>>_;

    while(_--)Main();

    return 0;
}

A wzr的签到题

代码：

#include<iostream>
using namespace std;
typedef long long ll;

void solve(){
    ll n,k;
    cin>>n>>k;
    if(k==2){
        if((n-1)/2%2==1)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
        return ;
    }
    if((n+1)%k==0||n%k==0){
        if(n>k)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    else
        cout<<"No"<<endl;
}

int main(){
    int t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}

G 公主与骑士？

G题正解为分层图最短路

例如样例：

5 5 2 0 4 0 1 5 1 2 5 2 3 3 3 4 5 0 2 100

结果为：

8

我们可以考虑把图分成 层，每往下一层，边权变成 0 的边就增加 1 条。编号为 的点在第 层的编号为 。

在相邻两层之间连两条边权为 的有向边，表示可以把边 或的边权变成 ，然后到下一层的 点或 点。

建图后， 到 的最短路即是用完 次机会的最少花费。

最后可能没有用完 次机会，所以到每层终点的最短路都有可能成为答案，需要取最小值。

代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define inf 0x3f3f3f3f
#define int long long
#define fr first
#define se second
#define pb push_back
typedef pair<int, int> PII;
const int N = 1e6 + 10, mod = 1;
int n, m, k, x, y, s, t;
int dis[N], vis[N], cnt[N];
vector<PII> g[N];
void dijstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> q;
    memset(dis, inf, sizeof dis);
    memset(cnt, inf, sizeof cnt);
    q.push({0, s});
    dis[s] = 0;
    cnt[s] = 0;
    while (!q.empty())
    {
        auto [d, u] = q.top();
        q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto [v, w] : g[u])
        {
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
}
void solve()
{
    cin >> n >> m >> k;
    cin >> s >> t;
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        for (int i = 0; i <= k; i++)
        {
            g[u + n * i].pb({v + n * i, w});
            g[v + n * i].pb({u + n * i, w});
            if (i != k)
            {
                g[u + n * i].pb({v + n * (i + 1), 0});
                g[v + n * i].pb({u + n * (i + 1), 0});
            }
        }
    }
    dijstra();
    int ans = inf;
    for (int i = 0; i <= k; i++)
        ans = min(ans, dis[t + n * i]);
    cout << ans << endl;
    return;
}

signed main()
{
    IOS int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}