「ARC 124A」LR Constraints
Link.
我们可以把 $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.