abc308G

比較 scrambled egg 吧。

引理：若 \(x<y<z\)，那麽 \(\min\{x⊕y,y⊕z\}<x⊕z\)。換句話説，blackboard 上有用的只有相鄰的數。

證明：加入考慮到了第 \(i\) 位。若 \(x \& (1<<i),y\& (1<<i),z \& (1<<i)\) 不同為 \(1\)，那麽要麽是 \(0,0,1\) 要麽是 \(0,1,1\)。前者 \(x⊕y<x⊕z\)，後者 \(y⊕z<x⊕z\)。而 \(x<y<z\)，所以不可能一直同爲 \(1\)，所以引理成立。

同樣，若 \(x\le y\le z\)，那麽 \(\min\{x⊕y,y⊕z\}\le x⊕z\)。

只需要用 set 維護就可以了。

#include <bits/stdc++.h>

using namespace std;

#define de(x) cout<<#x<<"="<<x<<endl

using ll = long long;

int q;
multiset<int> nums;
multiset<int> xors;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>q;
	while (q--){
		int ty,x;
		cin>>ty;
		if (ty!=3){
			cin>>x;
		}
		if (ty==1){
			nums.insert(x);
			auto it=nums.lower_bound(x);
			int l=*prev(it),r=*next(it);
			if (it!=nums.begin() && next(it)!=nums.end()){
				xors.erase(xors.find(l^r));
			}
			if (it!=nums.begin()){
				xors.insert(l^x);
			}
			if (next(it)!=nums.end()){
				xors.insert(x^r);
			}
		}
		else if (ty==2){
			auto it=nums.lower_bound(x);
			int l=*prev(it),r=*next(it);
			if (it!=nums.begin() && next(it)!=nums.end()){
				xors.insert(l^r);
			}
			if (it!=nums.begin()){
				xors.erase(xors.find(l^x));
			}
			if (next(it)!=nums.end()){
				xors.erase(xors.find(x^r));
			}
			nums.erase(nums.find(x));
		}
		else{
			cout<<*(xors.begin())<<endl;
		}
	}
	return 0;
}

// 413!413!413!

abc307G

比較 scrambled egg 吧。怎麽評分 \(2330\)，虛高。

很顯然一個加一，一個減一，sum 是不變的。於是根據條件，可以確定所有數是哪些數。

假如有一個數是 \(x\)，有 \(cnt\) 個，可以 dp 如下：

\(dp_{i,j}\) 表示 \(1\sim i\) 中有 \(j\) 個 \(x\) 的最小步數。這樣可以算出來 \(i+1\) 沒有動之前是什麽。

轉移很簡單。

#include <bits/stdc++.h>

using namespace std;

#define de(x) cout<<#x<<"="<<x<<endl

using ll = long long;

const int N = 5e3+3;

ll n,sum;
ll a[N],s[N],x,f,cnt;
ll dp[N][N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n;
	for (int i=1; i<=n; i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
		sum+=a[i];
	}
	x=sum/n;
	cnt=n-abs(sum-x*n);
	f=((sum-x*n)<0?-1:1);
	memset(dp,0x3f,sizeof dp);
	dp[0][0]=0;
	for (int i=0; i<=n; i++){
		for (int j=max(0ll,i-(n-cnt)); j<=min(i*1ll,cnt); j++){
			ll ad=s[i]-j*x-(i-j)*(x+f);
			// to x
			dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+abs(a[i+1]+ad-x));
			// to x+f
			dp[i+1][j]=min(dp[i+1][j],dp[i][j]+abs(a[i+1]+ad-(x+f)));
		}
	}
	cout<<dp[n][cnt]<<endl;
	return 0;
}

// 413!413!413!

abc306G

顯然如果所有經過 \(1\) 的環的 \(\gcd \mid 10^{10^{100}}\)，那麽 Yes 反之 No。當然，沒有環也是 No。

然後我就不會了。感覺這個題解寫的還可以 。

#include <bits/stdc++.h>

using namespace std;

#define de(x) cout<<#x<<"="<<x<<endl

using ll = long long;

const int N = 2e5+5;

int n,m,dep[N],f[N];
vector<int> g[N],rg[N];

void dfs(int v){
	for (auto u : g[v]){
		if (dep[u]==-1){
			dep[u]=dep[v]+1;
			dfs(u);
		}
	}
}

void dfsr(int v){
	f[v]=1;
	for (auto u : rg[v]){
		if (!f[u]){
			dfsr(u);
		}
	}
}

void solve(){
	cin>>n>>m;
	for (int i=0; i<n; i++){
		g[i].clear();
		rg[i].clear();
	}
	for (int i=0; i<m; i++){
		int u,v;
		cin>>u>>v;
		u--,v--;
		g[u].push_back(v);
		rg[v].push_back(u);
	}
	for (int i=0; i<n; i++){
		f[i]=0;
	}
	for (int i=1; i<n; i++){
		dep[i]=-1;
	}
	dep[0]=0;
	dfs(0);
	dfsr(0);
	for (int i=0; i<n; i++){
		if (!f[i]){
			dep[i]=-1;
		}
	}
	int gc=0;
	for (int i=0; i<n; i++){
		if (dep[i]==-1){
			continue;
		}
		for (auto j : g[i]){
			if (dep[j]!=-1){
				gc=__gcd(gc,abs(dep[i]-dep[j]+1));
			}
		}
	}
//	cout<<gc<<endl;
	if (!gc){
		cout<<"No"<<endl;
	}
	else{
		while (gc%2==0){
			gc/=2;
		}
		while (gc%5==0){
			gc/=5;
		}
		if (gc==1){
			cout<<"Yes"<<endl;
		}
		else{
			cout<<"No"<<endl;
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin>>t;
	while (t--){
		solve();
	}
	return 0;
}

// 413!413!413!