D E (Endfield)

2n + 1 的情形

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

恒等律: $p \oplus 0 = p$
归零律: $p \oplus p = 0$

记 $X = \bigoplus_{i=1}^{2n+1} a_i$ ，则 $X$ 即为答案。

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

2n + 2 的情形

我们可以找到一种序列 $\{a_n\}$ 的划分方式，使得两个只出现一次的数 $a_x, a_y$ 处于不同的部分。然后按照 $2n + 1$ 的情形，将两部分分别求异或即可。

一种简单且合理的划分方法：首先求出 $x = a_x \oplus a_y$ 的值（等价于求整个序列的异或和），再求出 $\text{lowbit}(x)$ ，根据 $a_i$ 的二进制表示在这一位是否为 1 将序列划分。

时间复杂度 $O(N)$ ，空间复杂度 $O(1)$ 。 这道题没有卡时间复杂度和空间复杂度时间复杂度 $O(N)$ 做法：位运算、unordered_set（没有卡哈希）时间复杂度 $O(N*logN)$ 的做法也可以接受：离散化、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 的情形

记三个只出现一次的数分别为 $a_x, a_y, a_z$ 。

设 $X = \bigoplus_{i=1}^{2n+3} a_i = a_x \oplus a_y \oplus a_z$ 。

则 $b_i = a_i \oplus X, \quad 1 \leq i \leq 2n + 3$ ，则 $b_x = a_y \oplus a_z, b_y = a_x \oplus a_z, b_z = a_x \oplus a_y$ 。

令 $X_{new} = \bigoplus_{i=1}^{2n+3} b_i = b_x \oplus b_y \oplus b_z = 0$ 。

断言 1： $b_x, b_y, b_z$ 互不相等。

证明 1：

考虑反证法：由 $a_x, a_y, a_z$ 互不相等，且 $b_x, b_y, b_z$ 均不为 0。若 $b_x = b_y$ ，则 $0 = b_x \oplus b_y = (a_y \oplus a_z) \oplus (a_x \oplus a_z) = a_x \oplus a_y \neq 0$ ，矛盾。

接下来令 $f(x) = \text{lowbit}(x)$ 。

断言 2： $f(b_x), f(b_y), f(b_z)$ 中有且仅有两个数相等。

证明 2：

不妨设这三个数中最小的数是 $f(b_x)$ ，令 $n=f(b_x)$ ，则由 $X_{new} = 0$ 知， $b_y, b_z$ 中定然有一个数在第 $n$ 位为 1，另一个数在该位上为 0。不妨设 $b_y$ 在该位上为， $f(b_x)=f(b_y),f(b_z)>f(b_y)=f(b_x)$

设 $f(b_x) = f(b_y)$ , $m$ 为 $b_z$ 最低位所在位置。由断言 2， $\{ b_n \}$ 中所有数对应的 $f(b_i)$ 的异或和为 $f(b_z)$ 。由 $b_z$ 在第 $m$ 位上为 $1$ ，且 $b_x \oplus b_y \oplus b_z = 0，$ 不妨设 $b_y$ 在该位为 $1$ ， $b_x$ 在该位为 $0$ 。故可按照 $b_i$ 在第 $m$ 位上是否为 $1$ ，将 $\{ b_n \}$ 分成两个部分。每部分的异或值恰好为 $b_x$ ，那么 $a_x=b_x\oplus X$ 。

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

时间复杂度 $O(N)$ ，空间复杂度 $O(1)$ 。

#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的签到题

alt alt alt alt alt alt

代码：

#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

alt

我们可以考虑把图分成 $k+1$ 层，每往下一层，边权变成 0 的边就增加 1 条。编号为 $i$ 的点在第 $j$ 层的编号为 $i + j × n (0 ≤ i < n, 0 ≤ j ≤ k)$ 。

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

建图后， $s$ 到 $t + k × n$ 的最短路即是用完 $k$ 次机会的最少花费。

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

代码

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

题解 | A,D,E,G（中北大学程序设计竞赛）