☆ 「ARC 124A」LR Constraints

我们可以把 $1\sim n$ 个盒子里能放的球的编号集合全部求出来。然后就直接来。

注意题目已经给出了 $k$ 个球的位置，所以「Note that for each integer $i$ from $1$ through $K$ , there must be at least one card on which we write $i$ .」这个限制不用管。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define len(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N=1100,MOD=998244353;
int n,k,ts[N],tek[N],fin[N],Rs[N];
set<int> rs[N];
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>k,memset(fin,-1,sizeof fin);
	for(int i=1; i<=k; ++i) {
		char c; cin>>c;
		ts[i]=(c=='R');
		cin>>tek[i];
		Rs[tek[i]]=ts[i];
	}
	for(int i=1; i<=k; ++i) {
		if(~fin[tek[i]]) return puts("0"),0;
		fin[tek[i]]=i;
	}
	for(int i=1; i<=n; ++i) {
		if(~fin[i]) rs[i].emplace(fin[tek[i]]);
		else {
			auto &s=rs[i];
			for(int j=1; j<=k; ++j) s.emplace(j);
			int tmp=0;
			for(int j=i+1; j<=n; ++j) {
				if(!Rs[j]) s.erase(fin[j]);
			}
			for(int j=1; j<i; ++j) {
				if(Rs[j]) s.erase(fin[j]);
			}
		}
	}
	int res=1;
	for(int i=1; i<=n; ++i) res*=len(rs[i]),res%=MOD;
	cout<<res<<"\n";
	return 0;
}

☆ 「ARC 124B」XOR Matching 2

Link.

预处理出 $s(i,j)=a_{i}\oplus b_{j}$ ，以及 $pos(i,x)$ 表示第 $i$ 层值 $x$ 的出现集合，用 std::map 均摊 $\mathcal{O}(n^{2})$ 空间。然后我们在第一层逐列考虑，对于第一层的每一种异或值，找出在每一行出现的位置集合，如果某一行没有出现就不行。最后就看集合大小是否等于 $n$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define int ll
const int N=2100;
int a[N],b[N],xr[N][N],n;
multimap<int,int> mp[N];
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n;
	for(int i=1; i<=n; ++i) cin>>a[i];
	for(int i=1; i<=n; ++i) cin>>b[i];
	for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) xr[i][j]=(a[i] xor b[j]),mp[i].insert({xr[i][j],j});
	vector<int> res;
	for(int j=1; j<=n; ++j) {
		bool ok=0;
		set<int> S;
		for(int i=1; i<=n; ++i) {
			auto rg=mp[i].equal_range(xr[1][j]);
			if(mp[i].find(xr[1][j])!=mp[i].end()) {
				for(auto it=rg.first; it!=rg.second; ++it) {
					S.emplace(it->second);
				}
			}
			else {
				ok=1;
				break;
			}
		}
		if(ok) continue;
		if(S.size()==n) {
			res.push_back(xr[1][j]);
		}
	}
	sort(all(res));
	res.erase(unique(all(res)),res.end()); 
	cout<<res.size()<<"\n";
	for(int x:res) cout<<x<<"\n";
	return 0;
}

☆ 「ARC 124C」LCM of GCDs

Link.

考场做法复杂度有问题啊，虽然屮过去了。有空来补 official editorial 做法。

// Oops, something went wrong.

☆ 「ARC 124D」Yet Another Sorting Problem

Link.

~~你看 ARC 又考置换群了。震撼围观吴老师精确押题。~~

套路题，连边 $i\rightarrow p_{i}$ 后一堆环摆出来。答案是

n+m-(\text{the number of cycles in the graph})+\\ 2\times\max\{\text{the number of cycles of size of 2 or greater consisting of vertice numbered through }1\text{ to }n,\\ \text{the number of cycles of size of 2 or greater consisting of vertice numbered through }n+1\text{ to }n+m\}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int N=200100;
int n,m,p[N],vis[N];
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m; int x0=0,x1=0,res=n+m,ls=0;
	for(int i=1; i<=n+m; ++i) cin>>p[i];
	for(int i=1; i<=n+m; ++i) {
		if(vis[i]) continue;
		int now=i,len=0,qwq=0,qaq=0;
		while(!vis[now]) {
			++len;
			if(now<=n) qwq=1;
			else qaq=1;
			vis[now]=1;
			now=p[now];
		}
		if(!qaq&&len>=2) ++x0;
		if(!qwq&&len>=2) ++x1;
		--res;
	}
	cout<<res+2*max(x0,x1)<<"\n";
	return 0;
}

☆ 「ARC 124E」Pass to Next

Link.

☆ 「ARC 124F」Chance Meeting

Link.