2022-2023 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2022)
===
比賽鏈結
---
https://codeforces.com/gym/104030
比賽影片
---
{%youtube G12C-BFRWO8%}
記分板
---
題解
---
### A. Ace Arbiter
---
#### 題目摘要
Alice和Bob打桌球，11分結束，第1局由Alice發球，2、3局由Bob發球，之後每2局交換攻守，計分的方式是先寫本局發球人的分數再寫另一人的分數。然而紀錄的人會亂記分，可能有一場會記多次或不記，但順序不會亂改。問這場比賽可不可能存在，若不存在，請輸出最早記錯的一局
#### 想法
QQ英文看不懂吃超多penalty，這題只是簡單判case題
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
int turn(int x){
if (x==0) return 0;
x--;
x/=2;
if (x&1) return 0;
return 1;
}
int main(){
int n;
scanf("%d", &n);
int lx=-1, ly=-1;
for(int i=1;i<=n;i++){
int x, y;
scanf("%d-%d", &x, &y);
if (x==11&&y==11){
printf("error %d\n", i);
return 0;
}
if (lx==-1||ly==-1){
lx=x, ly=y;
}else{
if (lx+ly==x+y){
if (lx==x&&ly==y) continue;
printf("error %d\n", i);
return 0;
}
if (lx+ly<x+y){
if (lx==11||ly==11){
printf("error %d\n", i);
return 0;
}
if (turn(lx+ly)!=turn(x+y)) swap(lx, ly);
if (lx>x||ly>y){
printf("error %d\n", i);
return 0;
}else{
lx=x, ly=y;
continue;
}
}else{
printf("error %d\n", i);
return 0;
}
}
}
printf("ok\n");
}
```
:::
### B. Berry Battle
---
#### 題目摘要
給定一個$N$個點的樹，每個點上都有一個莓果跟一隻螞蟻，每當你拿掉點$v$的莓果，那麼樹上所有螞蟻都會往$v$前進一步，要求輸出一個順序，在拿完所有莓果的前提下，不能有任何一個瞬間所有螞蟻重疊在同一個點。
#### 想法
注意到因為所有螞蟻會一起前進，會使螞蟻merge的情況只有點到有螞蟻的點以及兩隻螞蟻在不同子樹上往同向前進，容易觀察到如果選完樹直徑上的點，那麼其他所有子樹的螞蟻都會走到樹直徑上，接下來只要輪流把除了樹直徑上的子樹從直徑上往外點就可以了，因為螞蟻都在直徑上，不會滿足merge的第二個條件，而除了直徑的子樹也都不會有螞蟻。
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define all(x) (x).begin(), (x).end()
#define pb push_back
const int IINF = 1e9 + 7;
const ll LINF = 1e18 + 5;
int main(){
int n; cin >> n;
vector<vector<int>> adj(n);
rep (i, 0, n - 1) {
int a, b; cin >> a >> b;
a--, b--;
adj[a].pb(b);
adj[b].pb(a);
}
vector<int> dep(n);
auto dfs = [&](auto self, int u, int pa) -> void {
for (int v : adj[u]) {
if (v == pa) continue;
dep[v] = dep[u] + 1;
self(self, v, u);
}
};
dep[0] = 0;
dfs(dfs, 0, -1);
int st = max_element(all(dep)) - dep.begin();
dep[st] = 0;
dfs(dfs, st, -1);
int ed = max_element(all(dep)) - dep.begin(), red = ed, sred;
if (dep[ed] < 3) {
cout << "NO\n";
exit(0);
}
vector<bool> vis(n, 0);
cout << "YES\n";
vector<int> d;
for (int x : adj[ed]) if (dep[x] + 1 == dep[ed]) {
ed = x;
break;
}
sred = ed;
for (int x : adj[ed]) if (dep[x] + 1 == dep[ed]) {
ed = x;
break;
}
vis[ed] = vis[red] = vis[sred] = 1;
d.pb(ed);
d.pb(red);
d.pb(sred);
// cout << ed << '\n';
while (ed != st) {
cout << ed + 1 << ' ';
for (int x : adj[ed]) if (dep[x] + 1 == dep[ed]) {
ed = x;
break;
}
vis[ed] = 1;
d.pb(ed);
}
cout << ed + 1 << ' ' << sred + 1 << ' ' << red + 1 << ' ';
auto dfs2 = [&](auto self, int u, int pa) -> void {
for (int v : adj[u]) {
if (v == pa || vis[v]) continue;
vis[v] = 1;
cout << v + 1 << ' ';
self(self, v, u);
}
};
for (int x : d) {
dfs2(dfs2, x, -1);
}
}
```
:::
### C. Coffee Cup Combo
---
#### 題目摘要
給你一個01字串，1代表可以喝一杯咖啡並且帶兩杯在身上，0會消耗一杯咖啡，問可以有幾天有咖啡喝
#### 想法
簽到，直接記剩幾杯就好
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n; string s;
int main(){
cin >> n >> s;
int ans = 0, left = 0;
for(int i = 0; i < n ; i++){
if(s[i]=='1'){
ans++;
left = 2;
}else if(left>0){
ans++;
left--;
}
}
cout << ans;
}
```
:::
### D. Disc District
---
#### 題目摘要
給一個圓心在$(0,\, 0)$半徑為$r$的圓，請輸出一個在圓外的格子點，使得沒其他在圓外的格子點比他離圓更近。
#### 想法
輸出$(1, r)$即可，我賽中沒想到所以使用了二分搜。
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
const int IINF = 1e9 + 7;
const ll LINF = 1e18 + 5;
int main(){
ll n; cin >> n;
ll x, y, ans = LINF;
rep (i, 0, n + 2) {
ll l = -1, r = IINF;
while (r - l > 1) {
ll mid = l + r >> 1;
if (1LL * i * i + mid * mid > n * n) r = mid;
else l = mid;
}
if (1LL * i * i + r * r < ans) {
ans = 1LL * i * i + r * r;
x = i, y = r;
}
}
cout << x << ' ' << y << '\n';
}
```
:::
### E. Enigmatic Enumeration
---
#### 題目摘要
問一張不一定連通的簡單圖的最小環數量
#### 想法
注意到$n$很小，可以枚舉每個點當作環上其中一個點，然後跑bfs找最短路，再判會不會有環就好，而環分成奇數邊與偶數邊：
奇數環會滿足有條邊兩端的距離會一樣，所以只要跑完最短路後再枚舉所有邊找最小環就好
偶數環會滿足有個點有至少兩種路徑，所以只要跑完最短路後再枚舉所以點找最小環就好
這樣可能會有跑的最短路會共用邊的情況，然而這是能被忽略的，因為若共邊，則存在一個更小環，而更小環一定會被算到
算出最短環長度後，接下來就是算有多少個，枚舉最短路的方法數再做相乘就能解決，然而每個環會被重複算到環長度次，記得要除掉以免多算
賽中邊的大小開錯得WA，一直以為是實作爛而de不到bug，賽後才被隊友發現QAQ
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
const int N=3005;
vector<int> v[N];
int dis[N];
ll dp[N];
pii p[N<<1];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i=0;i<m;i++){
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
p[i]={a, b};
}
queue<int> q;
int len=n+1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) dis[j]=n+1;
for(int j=1;j<=n;j++) dp[j]=0;
dis[i]=0;
dp[i]=1;
q.push(i);
while(!q.empty()){
int x=q.front();
q.pop();
for(auto e:v[x]){
if (dis[e]>dis[x]+1){
dis[e]=dis[x]+1;
dp[e]=dp[x];
q.push(e);
}else if (dis[e]==dis[x]+1){
dp[e]+=dp[x];
}
}
}
for(int j=1;j<=n;j++) if (dp[j]>1) len=min(len, dis[j]<<1);
for(int j=0;j<m;j++) if (dis[p[j].F]==dis[p[j].S]) len=min(len, dis[p[j].F]+dis[p[j].S]+1);
}
// cout << len << '\n';
ll ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) dis[j]=n+1;
for(int j=1;j<=n;j++) dp[j]=0;
dis[i]=0;
dp[i]=1;
q.push(i);
while(!q.empty()){
int x=q.front();
q.pop();
for(auto e:v[x]){
if (dis[e]>dis[x]+1){
dis[e]=dis[x]+1;
dp[e]=dp[x];
q.push(e);
}else if (dis[e]==dis[x]+1){
dp[e]+=dp[x];
}
}
}
if (len&1){
for(int j=0;j<m;j++) if (dis[p[j].F]==(len>>1)&&dis[p[j].S]==(len>>1)){
ans+=dp[p[j].F]*dp[p[j].S];
}
}else{
for(int j=1;j<=n;j++) if (dis[j]==(len>>1)){
ans+=dp[j]*(dp[j]-1)>>1;
}
}
}
ans/=len;
cout << ans << '\n';
}
```
:::
### F. Foreign Football
---
#### 題目摘要
給你$n$個字串兩兩組合的表，問題是否有唯一解，多組解或無解，若是唯一解請輸出那$n$個字串
#### 想法
假設每個字串的長度為$l_i$，那總長度$s=\sum\limits_{i=1}^{n}l_i$。第$i$列的長度是$(n-1)\times l_i+\sum\limits_{j=1}^{n,\ j\not =i} l_j$，也就是$(n-2)l_i+s$，因此能求到$l_i$，也就是能知道第$i$個字串長怎樣，這樣能做完$n>2$的情況。在$n=2$的情況，只要把其中一個字串複製到屁股，再看有沒有子字串等於另一個字串就好
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
const int IINF = 1e9 + 7, MAXN = 2e6 + 5;
const ll LINF = 1e18 + 5;
const int p = 131, MOD = 1e9 + 7;
ll fpow(ll x, int exp) {
ll res = 1;
while (exp) {
if (exp & 1) res = res * x % MOD;
x = x * x % MOD;
exp >>= 1;
}
return res;
}
int main(){
int n; cin >> n;
vector s(n, vector<string>(n));
int len = 0;
rep (i, 0, n) rep (j, 0, n) {
cin >> s[i][j];
if (i != j) len += s[i][j].size();
}
if (n == 2) {
string a = s[0][1], b = s[1][0];
if (a.size() != b.size()) {
cout << "NONE\n";
exit(0);
}
b += b;
int l = -1, cnt = 0, sz = b.size();
string ans = "";
vector<ll> hash(sz + 1);
hash[0] = 0;
rep (i, 0, sz) hash[i + 1] = (hash[i] * p % MOD + b[i]) % MOD;
ll ha = 0;
for (char c : a) ha = (ha * p % MOD + c) % MOD;
rep (i, 1, a.size()) {
if (ha == (hash[i + a.size()] - hash[i] * fpow(p, a.size()) % MOD + MOD) % MOD) {
l = i;
cnt++;
}
}
if (l == -1) cout << "NONE\n";
else if (cnt > 1) cout << "MANY\n";
else cout << "UNIQUE\n" << b.substr(l + a.size(), a.size() - l) << '\n' << b.substr(0, l) << '\n';
} else {
if (len % (2 * n - 2)) {
cout << "NONE\n";
exit(0);
}
len /= 2 * n - 2;
vector<string> ans;
rep (i, 0, n) {
int slen = 0;
rep (j, 0, n) if (i != j) slen += s[i][j].size();
slen -= len;
if (slen % (n - 2) || slen == 0) {
cout << "NONE\n";
exit(0);
}
slen /= n - 2;
ans.pb(s[i][(i + 1) % n].substr(0, slen));
}
rep (i, 0, n) rep (j, 0, n) if (i != j) {
if (ans[i] + ans[j] != s[i][j]) {
cout << "NONE\n";
exit(0);
}
}
cout << "UNIQUE\n";
for (string t : ans) cout << t << '\n';
}
}
```
:::
### G. Graduation Guarantee
---
#### 題目摘要
給你每題答對的機率，答對得1分，答錯-1分，不回答0分，問得$k$分最大機率
#### 想法
設$dp_{i, j}$為回答$i$題得$j$分的最大機率，因此轉移能變成
\begin{cases}
dp_{0,\, 0}=1 \\
dp_{i,\, j}=dp_{i-1,\, j-1}\times p_i+dp_{i-1, \, j+1}\times (1-p_i)
\end{cases}
注意到若要回答$i$題，一定會選答對機率越大的題，所以要先排序再套dp
要狀壓，不然會吃MLE
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<ld> a(n);
for(int i=0;i<n;i++) cin >> a[i];
sort(a.begin(), a.end(), greater<ld>());
vector<ld> dp(2*(n+1), 0.0);
dp[n]=1.0;
ld ans=0.0;
for(int i=0;i<n;i++){
vector<ld> tmp(2*(n+1), 0.0);
for(int j=-n;j<=n;j++){
if (j<n) tmp[j+n+1]+=dp[j+n]*a[i];
if (j>-n) tmp[j+n-1]+=dp[j+n]*(1.0-a[i]);
}
dp.swap(tmp);
ld res=0.0;
for(int j=k;j<=n;j++) res+=dp[j+n];
ans=max(ans, res);
}
cout << fixed << setprecision(10) << ans << '\n';
}
```
:::
### H. Highest Hill
---
#### 題目摘要
有好多山的高度，求山峰與兩側最近山谷的最大差
#### 想法
分兩次做，一次求左邊的山谷，一次求右邊的，最後再更新答案
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define pb push_back
const int IINF = 1e9 + 7;
const ll LINF = 1e18 + 5;
int main(){
int n; cin >> n;
vector<ll> a(n);
vector<ll> low1(n), low2(n);
rep (i, 0, n) cin >> a[i];
for(int i=0;i<n;i++) low1[i]=low2[i]=a[i];
ll mn=a[0];
for(int i=1;i<n;i++){
if (a[i-1]<=a[i]){
mn=min(mn, a[i]);
}else{
mn=a[i];
}
low1[i]=mn;
}
mn=a[n-1];
for(int i=n-2;~i;--i){
if (a[i+1]<=a[i]){
mn=min(mn, a[i]);
}else{
mn=a[i];
}
low2[i]=mn;
}
ll ans=0;
for(int i=0;i<n;i++) ans=max(ans, a[i]-max(low1[i], low2[i]));
cout << ans << '\n';
}
```
:::
### I. Icy Itinerary
---
#### 題目摘要
給你一張圖，你有兩種走路方式：走有邊或無邊，兩種方式最多只能切換一次，問從點1開始拜訪點的順序
#### 想法
假設目前已經走完一個合法路徑，現在要在插入一個點，問題是這點要插在哪
若走完的合法路徑只有用一種方法走，那不論目前點和最後的點是有邊無邊，可以直接接在最後
若合法路徑用兩種方式，先找到一個前後的走路方式不同的點(mid)，再判斷目前的點和mid該怎麼走，若與先走的走路方式一樣，可以將它插在mid後面，否則把它插在mid前面，而這些都保證做完後還是合法路徑
而要維護插入點，可以用link list實作，而要查詢兩點是否有邊，可以用set維護，複雜度$O(n\log n)$
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ORENOOSHIKYOUMOKAWAIII ios::sync_with_stdio(0), cin.tie(0)
const int N=3e5+10;
int pre[N], suf[N], col[N];
set<int> v[N];
void add(int a, int b){
pre[b]=a;
suf[a]=b;
}
void rmv(int a, int b){
suf[a]=a;
pre[b]=b;
}
int main(){
ORENOOSHIKYOUMOKAWAIII;
int n, m;
cin >> n >> m;
for(int i=0;i<m;i++){
int a, b;
cin >> a >> b;
v[a].insert(b);
v[b].insert(a);
}
for(int i=1;i<=n;i++) pre[i]=suf[i]=i;
int bac1=0, bac2=0, hd=0;
if (v[2].find(1)!=v[2].end()) col[1]=col[2]=1, bac1=2;
else col[1]=col[2]=2, bac2=2;
add(1, 2);
for(int i=3;i<=n;i++){
if (hd==0){
if (col[1]==1){
if (v[i].find(bac1)!=v[i].end()){
add(bac1, i);
bac1=i;
col[i]=1;
}else{
hd=i;
col[i]=2;
bac2=i;
}
}else{
if (v[i].find(bac2)==v[i].end()){
add(bac2, i);
bac2=i;
col[i]=2;
}else{
hd=i;
col[i]=1;
bac1=i;
}
}
}else{
if (col[1]==1){
if (v[i].find(bac1)!=v[i].end()){
if (v[i].find(hd)!=v[i].end()){
int tmp=suf[hd];
if (hd!=tmp) rmv(hd, tmp);
add(bac1, i);
col[i]=1;
add(i, hd);
col[hd]=1;
bac1=hd;
if (hd==tmp) hd=0;
else hd=tmp;
}else{
add(bac1, i);
col[i]=1;
bac1=i;
}
}else{
if (v[i].find(pre[bac1])!=v[i].end()){
int tmp=pre[bac1];
rmv(tmp, bac1);
add(tmp, i);
col[i]=1;
add(bac1, hd);
col[bac1]=2;
hd=bac1;
bac1=i;
}else{
int tmp=pre[bac1];
rmv(tmp, bac1);
add(i, bac1);
col[i]=2;
add(bac1, hd);
col[bac1]=2;
hd=i;
bac1=tmp;
if (bac1==1){
add(1, i);
col[1]=2;
bac1=0;
hd=0;
}
}
}
}else{
if (v[i].find(bac2)==v[i].end()){
if (v[i].find(hd)==v[i].end()){
int tmp=suf[hd];
if (hd!=tmp) rmv(hd, tmp);
add(bac2, i);
col[i]=2;
add(i, hd);
col[hd]=2;
bac2=hd;
if (hd==tmp) hd=0;
else hd=tmp;
}else{
add(bac2, i);
col[i]=2;
bac2=i;
}
}else{
if (v[i].find(pre[bac2])==v[i].end()){
int tmp=pre[bac2];
rmv(tmp, bac2);
add(tmp, i);
col[i]=2;
add(bac2, hd);
col[bac2]=1;
hd=bac2;
bac2=i;
}else{
int tmp=pre[bac2];
rmv(tmp, bac2);
add(i, bac2);
col[i]=1;
add(bac2, hd);
col[bac2]=1;
hd=i;
bac2=tmp;
if (bac2==1){
add(1, i);
col[1]=1;
bac2=0;
hd=0;
}
}
}
}
}
}
int x=1;
while(x!=suf[x]){
cout << x << ' ';
x=suf[x];
}
cout << x << ' ';
if (hd!=0){
x=hd;
while(x!=suf[x]){
cout << x << ' ';
x=suf[x];
}
cout << x << '\n';
}
}
```
:::
### J. Junk Journey
---
#### 題目摘要
給二維點上一些車車以及你的起點及車車的終點，當你推車車整排的車車會一起被推，也就是沒有兩台車車會在同一個點，車車進終點會消失，請你實作你把所有車車推進終點的走路方向，方法數要小於$10 ^ 5$。
#### 想法
純實作題，方法數足夠大不要亂搞都不會超過。衝出去外面，把不小心帶出去的全部塞回去，接下來用一個像電風扇的方式把它們塞進終點，以終點為中心分成四塊，實作請參考下方code。
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second
pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }
#define lpos pos << 1
#define rpos pos << 1 | 1
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }
const int L = 300, D = 330, R = 330, U = 300;
void solve() {
int n; cin >> n;
pii s, t; cin >> s.F >> s.S >> t.F >> t.S;
s = s + make_pair(300, 300), t = t + make_pair(300, 300);
vector g(1005, vector<int>(1005, 0));
int done = 0;
auto push = [&](pii &pos, int d) -> void {
if (d == 1) {
cout << "right\n";
pos.F++;
int tmp = pos.F;
while (g[tmp][pos.S]) tmp++;
for (int i = tmp; i > pos.F; --i) swap(g[i][pos.S], g[i - 1][pos.S]);
} else if (d == 0) {
cout << "left\n";
pos.F--;
int tmp = pos.F;
while (g[tmp][pos.S]) tmp--;
for (int i = tmp; i < pos.F; ++i) swap(g[i][pos.S], g[i + 1][pos.S]);
} else if (d == 2) {
cout << "down\n";
pos.S--;
int tmp = pos.S;
while (g[pos.F][tmp]) tmp--;
for (int i = tmp; i < pos.S; ++i) swap(g[pos.F][i], g[pos.F][i + 1]);
} else {
cout << "up\n";
pos.S++;
int tmp = pos.S;
while (g[pos.F][tmp]) tmp++;
for (int i = tmp; i > pos.S; --i) swap(g[pos.F][i], g[pos.F][i - 1]);
}
if (g[t.F][t.S]) {
done++;
g[t.F][t.S] = 0;
}
};
rep (i, 0, n) {
int x, y; cin >> x >> y;
x += 300, y += 300;
g[x][y] = 1;
}
// 0 1 2 3 / u, d, l, r
while (s.S < R + 1) push(s, 3);
int last = R + 2;
while (g[s.F][last]) last++;
push(s, 0);
while (s.S < last) push(s, 3);
push(s, 1);
while (s.S > R + 1) push(s, 2);
// guarenteed that all the scooter's are inside the chunk
// robot's are now at the right of the chunk
while (done != n) {
// RD
while (t.F > s.F) push(s, 1);
while (t.F < s.F) push(s, 0);
rep (i, t.F, D + 1) {
int cnt = 0;
rep (j, t.S + 1, R + 1) cnt += g[i][j];
if (cnt == 0) {
push(s, 1);
continue;
}
if (i == t.F) {
while (s.S > t.S + 1) push(s, 2);
while (s.S <= R) push(s, 3);
} else {
while (s.S > t.S + cnt) push(s, 2);
while (s.S <= R) push(s, 3);
}
push(s, 1);
}
// LD
while (t.S < s.S) push(s, 2);
while (t.S > s.S) push(s, 3);
for (int i = t.S; i >= L; --i) {
int cnt = 0;
rep (j, t.F + 1, D + 1) cnt += g[j][i];
if (cnt == 0) {
push(s, 2);
continue;
}
if (i == t.S) {
while (s.F > t.F + 1) push(s, 0);
while (s.F <= D) push(s, 1);
} else {
while (s.F > t.F + cnt) push(s, 0);
while (s.F <= D) push(s, 1);
}
push(s, 2);
}
// LU
while (t.F > s.F) push(s, 1);
while (t.F < s.F) push(s, 0);
for (int i = t.F; i >= U; --i) {
int cnt = 0;
rep (j, L, t.S) cnt += g[i][j];
if (cnt == 0) {
push(s, 0);
continue;
}
if (i == t.F) {
while (s.S < t.S - 1) push(s, 3);
while (s.S >= L) push(s, 2);
} else {
while (s.S < t.S - cnt) push(s, 3);
while (s.S >= L) push(s, 2);
}
push(s, 0);
}
// RU
while (t.S < s.S) push(s, 2);
while (t.S > s.S) push(s, 3);
rep (i, t.S, R + 1) {
int cnt = 0;
rep (j, U, t.F) cnt += g[j][i];
if (cnt == 0) {
push(s, 3);
continue;
}
if (i == t.S) {
while (s.F < t.F - 1) push(s, 1);
while (s.F >= U) push(s, 0);
} else {
while (s.F < t.F - cnt) push(s, 1);
while (s.F >= U) push(s, 0);
}
push(s, 3);
}
}
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
### K. Keyboard Queries
---
#### 題目摘要
給一個不知道內容物的字串長度$\ n$，兩種操作
1. $1 \ \ell \ r$ 確定區間$[\ell, \ r]$為迴文
2. $2 \ a \ b \ x \ y$ 問$[a, b]$是否等於$[x, y]$，或是未知
#### 想法
首先先知道不等於的狀況只有$\ b - a \ne y - x$。
可以考慮用支援單點修改區間詢問的資料結構來維護字串的Hash值。
假定一開始為一個1~n的字串
給定一個回文等同於將左右對稱的位置合併成同個標號
可以使用並查集跟啟發式合併來維護字串每個位置目前的標號
但直接枚舉合併位置會太慢
可以使用二分搜從中間去找到第一個不是回文的範圍再往後枚舉(對稱會有單調性)
注意到合併最多只會做到$n - 1$次，因此複雜度$O(n \log^{2}n + Q \log n)$
讚
實作好好顧到奇偶，並且注意並查集祖先同個標籤不要做合併，不然就會瘋狂TLE ==
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second
pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }
#define lpos pos << 1
#define rpos pos << 1 | 1
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
const int MAXN = 1e5 + 5, MOD2 = 998244353, IINF = 1e9 + 7, MOD = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }
struct FenwickTree{
vector<ll> BIT;
FenwickTree(int n) : BIT(n + 1, 0) {}
void mod(int x, ll val) {
while(x < BIT.size()){
BIT[x] += val;
x += x & -x;
}
}
ll query(int x) {
ll res = 0;
while (x) {
res += BIT[x];
x -= x & -x;
}
return res;
}
ll rquery(int l, int r) {
return query(r) - query(l - 1);
}
};
const int c = 131;
int pa[MAXN];
int find(int x) {
return pa[x] == x ? pa[x] : pa[x] = find(pa[x]);
}
void solve() {
int n, q; cin >> n >> q;
rep (i, 1, n + 1) pa[i] = i;
FenwickTree h(n), h2(n);
vector<vector<int>> id(n + 1);
vector<ll> p(n + 1), inv(n + 1);
p[0] = 1;
rep (i, 1, n + 1) p[i] = p[i - 1] * c % MOD;
inv[n] = fpow(p[n], MOD - 2, MOD);
for (int i = n - 1; i >= 0; --i) inv[i] = inv[i + 1] * c % MOD;
rep (i, 1, n + 1) {
id[i].pb(i);
h.mod(i, i * p[i] % MOD);
h2.mod(n - i + 1, i * p[n - i + 1] % MOD);
}
auto calc = [&](int t, int l, int r) -> ll {
if (t == 1) return (h.rquery(l, r) + MOD) % MOD * inv[l - 1] % MOD;
else return (h2.rquery(l, r) + MOD) % MOD * inv[l - 1] % MOD;
};
auto check = [&](int l, int r) -> bool {
return calc(1, l, r) == calc(2, n - r + 1, n - l + 1);
};
int cnt = 0;
while (q--) {
int t, l, r; cin >> t >> l >> r;
auto work = [&]() -> void {
int L = l + r + 1 >> 1, R = r + 1;
while (R - L > 1) {
int mid = L + R >> 1;
if (check(l + r - mid, mid)) L = mid;
else R = mid;
}
if ((r - l) % 2 && L == (l + r + 1) >> 1 && !check(L - 1, L)) R--;
for (int LL = l + r - R, RR = R; LL >= l && RR <= r; LL--, RR++) {
int pl = find(LL), pr = find(RR);
if (pl == pr) continue;
if (id[pl].size() < id[pr].size()) swap(pl, pr);
while (!id[pr].empty()) {
int v = id[pr].back();
id[pr].pop_back();
h.mod(v, (pl * p[v] % MOD) - (pr * p[v] % MOD));
h2.mod(n - v + 1, (pl * p[n - v + 1] % MOD) - (pr * p[n - v + 1] % MOD));
id[pl].pb(v);
pa[v] = pl;
}
}
};
if (t == 1) {
if (check(l, r)) continue;
work();
} else {
int x, y; cin >> x >> y;
if (l > x) swap(l, x), swap(r, y);
if (r - l != y - x) {
cout << "Not equal\n";
} else {
ll L = (h.rquery(l, r) + MOD) % MOD;
ll R = (h.rquery(x, y) + MOD) % MOD;
L = L * p[x - l] % MOD;
if (L == R) cout << "Equal\n";
else cout << "Unknown\n";
}
}
}
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
Sign in with Wallet
Connect another wallet