2022-2023 ICPC Northwestern European Regional Programming Contest (NWERC 2022)
===
比賽鏈結
---
https://codeforces.com/gym/104875
比賽影片
---
{%youtube VsYpz2c1pd8%}
記分板
---
題解
---
### A. Alternating Algorithm
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### B. Bottle Flip
---
#### 題目摘要
一圓柱裡有空氣和水，給你高、半徑、空氣密度及水密度，求最低重心發生時的水高度
#### 想法
帶公式三分搜
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define pii pair<int, int>
#define all(x), (x).begin(), (x).end()
ld h, _, da, dw;
const ld eps = 1e-6;
ld calc(ld x){
return (x * x * dw + (h - x) * (h - x) * da) / (x * dw + (h - x) * da);
}
int main() {
cin >> h >> _ >> da >> dw;
ld l = 0, r = h;
while (r - l > eps) {
ld ml = l + (r - l) / 3, mr = r - (r - l) / 3;
if (calc(ml) < calc(mr)) r = mr;
else l = ml;
}
cout << fixed << setprecision(10) << l << '\n';
}
```
:::
### C. Circular Caramel Cookie
---
#### 題目摘要
給一個面積$s$，求最小半徑使得鬆餅上的格子**大於**$s$。
#### 想法
對半徑二分搜後，花$\sqrt s$的時間檢查就好，想有夠久，太笨。
切記大於
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define pb push_back
const ld pi = acos(-1);
const ld eps = 2e-6;
int main() {
ll s; cin >> s;
ld l = 1, r = 1000000;
while (r - l > eps) {
ll tot = 0;
ld mid = (l + r) / 2;
rep (i, 1, 1000000) {
if (i > mid) break;
tot += (ll)sqrtl(mid * mid - double(i * i));
}
tot *= 4;
if (tot > s) r = mid;
else l = mid;
}
cout << fixed << setprecision(10);
cout << r << '\n';
}
```
:::
### D. Delft Distance
---
#### 題目摘要
一張$h\times w$的圖中每格會是圓形或正方形，求從左上到右下不切到圓形或正方形的最短路
#### 想法
對每個格子點的一半多建點，並對所有點對它右、右下及下面的點建邊權，並用dp轉移
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define pii pair<int, int>
#define all(x), (x).begin(), (x).end()
#define pi acos(-1)
const int N=1005;
const ld INF=1e18;
char s[N][N];
ld dis[4][N<<1][N<<1];
ld ans[N<<1][N<<1];
int main() {
int n, m;
cin >> n >> m;
for(int i=0;i<n;i++) for(int j=0;j<m;j++){
cin >> s[i][j];
if (s[i][j]=='X'){
dis[0][i<<1][j<<1]=0.5;
dis[1][i<<1][j<<1]=INF;
dis[2][i<<1][j<<1]=0.5;
dis[0][i<<1][j<<1|1]=0.5;
dis[1][i<<1][j<<1|1]=1.0;
dis[2][i<<1][j<<1|1]=INF;
dis[0][i<<1|1][j<<1]=INF;
dis[1][i<<1|1][j<<1]=1.0;
dis[2][i<<1|1][j<<1]=0.5;
}else{
dis[0][i<<1][j<<1]=0.5;
dis[1][i<<1][j<<1]=INF;
dis[2][i<<1][j<<1]=0.5;
dis[0][i<<1][j<<1|1]=0.5;
dis[1][i<<1][j<<1|1]=pi/4;
dis[2][i<<1][j<<1|1]=INF;
dis[0][i<<1|1][j<<1]=INF;
dis[1][i<<1|1][j<<1]=pi/4;
dis[2][i<<1|1][j<<1]=0.5;
}
}
for(int i=0;i<n;i++){
dis[2][i<<1][m<<1]=0.5;
dis[2][i<<1|1][m<<1]=0.5;
}
for(int j=0;j<m;j++){
dis[0][n<<1][j<<1]=0.5;
dis[0][n<<1][j<<1|1]=0.5;
}
for(int i=0;i<=(n<<1);i++) for(int j=0;j<=(m<<1);j++) ans[i][j]=INF;
ans[0][0]=0;
for(int i=0;i<=(n<<1);i++){
for(int j=0;j<=(m<<1);j++){
if (ans[i][j]>=INF) continue;
if (dis[0][i][j]!=INF) ans[i][j+1]=min(ans[i][j+1], ans[i][j]+dis[0][i][j]);
if (dis[1][i][j]!=INF) ans[i+1][j+1]=min(ans[i+1][j+1], ans[i][j]+dis[1][i][j]);
if (dis[2][i][j]!=INF) ans[i+1][j]=min(ans[i+1][j], ans[i][j]+dis[2][i][j]);
}
}
cout << fixed << setprecision(10)<< ans[n<<1][m<<1]*10 << '\n';
}
```
:::
### E. ETA
---
#### 題目摘要
給$\frac{p}{q}, \ \gcd(p, q) = 1$，構造出一個$n$點$m$邊的圖使得每個點走到$1$的最短路期望值為$\frac{p}{q}$
#### 想法
注意到我們最終只要構出一棵樹就好。
由於能輸出的$n$有一定限制，不妨去枚舉所有可能的$n$，也就是去枚舉每個$q$的倍數，這時候得到的資訊$\ p'\,$為$1$到所有點的路徑長度和
考慮最長能構出來的路徑和為一條鍊，也就是$\frac{(n - 1)n}{2}$，如果這個小於$p'$那就爛掉，再考慮最短的路徑和為全部都深度$1$，如果$p'<n-1$也爛掉。
接著就保證有解了，只要從一條鍊開始，好好將深度從深到淺做一些移動來彌補跟$p'$差距就好。
如果一直找都沒有就無解。
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define pb push_back
const ld pi = acos(-1);
int main() {
ll a, b; scanf("%lld/%lld", &a, &b);
for (int n = b; n <= 1000000; n += b) {
ll dis = 1LL * a * (n / b), cur = 1LL * (n - 1) * n / 2;
if (dis > cur || dis < n - 1) continue;
// cout << cur << ' ' << dis << '\n';
ll d = cur - dis;
vector<int> dep(n);
iota(all(dep), 0);
for (int i = n - 1; i > 1; --i) {
if (d == 0) continue;
int ok = dep[i] - 1;
if (d <= ok) {
dep[i] -= d;
d = 0;
break;
} else {
dep[i] = 1;
d -= ok;
}
}
vector<vector<int>> layer(n);
rep (i, 0, n) {
layer[dep[i]].pb(i);
}
cout << n << ' ' << n - 1 << '\n';
rep (i, 1, n) {
if (layer.empty()) break;
for (int x : layer[i]) {
cout << layer[i - 1].back() + 1 << ' ' << x + 1 << '\n';
}
}
exit(0);
}
cout << "impossible\n" << '\n';
}
```
:::
### F. Faster Than Light
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### G. Going in Circles
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### H. High-quality Tree
---
#### 題目摘要
對於一個二元平衡樹，定義為所有點的左子樹最深深度與右子樹最深深度相差不超過1。給你一顆二元樹，求最少要刪多少點使其變成二元平衡樹
#### 想法
利用分治的想法，先遞迴左子樹使其變平衡樹，再做右子樹，最後看兩者的最深深度(不含被刪除點)，若兩者差>1，對深度深的子樹刪適當的點，因為每個點被刪掉次數只有一次，所以直接暴力刪點就好，複雜度$O(n)$
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int> v[N];
int ch[2][N];
int dep[N], mxd[N], cnt[N];
bool del[N];
int ans;
void dfs(int x, int p, int d){
cnt[x]=1;
dep[x]=mxd[x]=d;
for(auto e:v[x]) if (e!=p){
if (ch[0][x]==0) ch[0][x]=e;
else ch[1][x]=e;
dfs(e, x, d+1);
cnt[x]+=cnt[e];
mxd[x]=max(mxd[x], mxd[e]);
}
}
void dfs3(int x, int d){
if (del[x]) return;
if (dep[x]>=d){
del[x]=1;
ans++;
}
if (!del[ch[0][x]]) dfs3(ch[0][x], d);
if (!del[ch[1][x]]) dfs3(ch[1][x], d);
}
void dfs2(int x){
int d0=dep[x], d1=dep[x];
if (!del[ch[0][x]]) dfs2(ch[0][x]), d0=mxd[ch[0][x]];
if (!del[ch[1][x]]) dfs2(ch[1][x]), d1=mxd[ch[1][x]];
if (d0<d1) swap(d0, d1), swap(ch[0][x], ch[1][x]);
if (d0-d1>1){
dfs3(ch[0][x], d1+2);
}
mxd[x]=min(d0, d1+1);
}
int main(){
int n;
cin >> n;
for(int i=1;i<n;i++){
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
ans=0;
del[0]=1;
dfs(1, 0, 1);
dfs2(1);
cout << ans << '\n';
}
```
:::
### I. Interview Question
---
#### 題目摘要
若一數是$x$的倍數要輸出Fizz，是$y$的倍數數出Buzz，是兩者的倍數輸出FizzBuzz，否則輸出該數，給你$l到r$的輸出，輸出任意一組$x,\ y$
#### 想法
若Fizz(FizzBuzz)出現2次以上，則$x$是最近的兩者差，若出現1次，直接將$x$設為該數，否則直接設成$r+1$，Buzz同理
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define pii pair<int, int>
#define all(x), (x).begin(), (x).end()
int main() {
int l, r; cin >> l >> r;
int a1=-1, b1=-1, a2=-1, b2=-1;
for(int i=l;i<=r;i++){
string s;
cin >> s;
if (s=="Fizz"){
if (a1==-1) a1=i;
else if (a2==-1) a2=i;
}else if (s=="Buzz"){
if (b1==-1) b1=i;
else if (b2==-1) b2=i;
}else if (s=="FizzBuzz"){
if (a1==-1) a1=i;
else if (a2==-1) a2=i;
if (b1==-1) b1=i;
else if (b2==-1) b2=i;
}
}
if (a1==-1&&a2==-1){
cout << r+1 << ' ';
}else if (a2==-1){
cout << a1 << ' ';
}else{
cout << a2-a1 << ' ';
}
if (b1==-1&&b2==-1){
cout << r+1 << '\n';
}else if (b2==-1){
cout << b1 << '\n';
}else{
cout << b2-b1 << '\n';
}
}
```
:::
### J. Justice Served
---
#### 題目摘要
給好多區間，該區間的答案是所有包覆該區間的答案的最大值+1，位被任何區間包覆答案是0，求所有區間答案
#### 想法
先對左端排序，若有人包覆我代表在我之前有人的右端比我的右端大，因此開個線段樹，藉由右界以後的最大值找到目前這線段的答案，再對右界位置單點改成線段答案就好
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
vector<int> v;
inline int id(int x){
return lower_bound(v.begin(), v.end(), x)-v.begin()+1;
}
const int N=4e5+10;
int t[N<<2];
vector<tuple<int, int, int>> p;
int ans[N];
void modify(int v, int l, int r, int x, int k){
if (x==l&&x==r){
t[v]=k;
return;
}
int m=l+r>>1;
if (x<=m) modify(v<<1, l, m, x, k);
else modify(v<<1|1, m+1, r, x, k);
t[v]=max(t[v<<1], t[v<<1|1]);
}
int query(int v, int l, int r, int ql, int qr){
if (ql<=l&&r<=qr) return t[v];
int m=l+r>>1;
int res=0;
if (ql<=m) res=max(res, query(v<<1, l, m, ql, qr));
if (qr>m) res=max(res, query(v<<1|1, m+1, r, ql, qr));
return res;
}
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++){
int a, t;
cin >> a >> t;
v.push_back(a);
v.push_back(a+t);
p.push_back({a, a+t, i});
}
sort(v.begin(), v.end());
sort(p.begin(), p.end(), [](auto a, auto b){
auto [l1, r1, i1]=a;
auto [l2, r2, i2]=b;
if (l1==l2) return r1>r2;
return l1<l2;
});
int sz=v.size();
for(auto [l, r, idx]:p){
ans[idx]=query(1, 1, sz, id(r), sz)+1;
modify(1, 1, sz, id(r), ans[idx]);
}
for(int i=0;i<n;i++) cout << ans[i]-1 << ' ';
cout << '\n';
}
```
:::
### K. Kebab Pizza
---
#### 題目摘要
$N$塊披薩及$K$種配料，每塊披薩上有兩種配料(可能相同)，加配料時必須連續加一段環狀區間，給你每個披薩上的配料(無序)問能不能達成。
#### 想法
轉換為圖論問題，把披薩看做邊，配料看做點。
顯然，一開始可以先將垃圾重邊給去掉。
考慮一種impossible的情況：如果一個點$v$連著三個以上非葉節點的點，那麼他一定是爛的。
原因是在任兩塊含$v$披薩中都會需要放其他配料的披薩，因此配料$v$無法連續。
接下來，會發現需要用到環狀性質的只有環，如果出現其他連通塊會幹到他用結尾連起來$(ex: (1, 2),\, (2, 3),\, (3, 1),\, (4, 5))$
因此若出現一個環，整張圖必須為一塊連通圖，否則impossible。反之各連通塊都無環就OK。
特別注意幾個很靠北的地方：
1. 自環
2. 若連到自環請注意自環不是葉節點
3. 會有沒有度數的點，不要在判連通圖時考慮它
4. 自環不是沒有度數的點
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(a, b, c) for (int a = b; a < c; ++a)
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define pb push_back
const int MAXN = 1e5 + 5;
int pa[MAXN], sz[MAXN], edge[MAXN];
int find(int x) {
return x == pa[x] ? pa[x] : pa[x] = find(pa[x]);
}
bool Union(int a, int b) {
a = find(a), b = find(b);
edge[a]++;
if (a == b) return false;
sz[a] += sz[b];
edge[a] += edge[b];
pa[b] = a;
return true;
}
int main() {
int n, k; cin >> n >> k;
vector<pii> tp(n);
for (auto &[a, b] : tp) {
cin >> a >> b;
a--, b--;
if (a > b) swap(a, b);
}
sort(all(tp));
tp.erase(unique(all(tp)), tp.end());
vector<vector<int>> adj(k);
iota(pa, pa + k, 0);
fill(sz, sz + k, 1);
for (auto [a, b] : tp) {
adj[a].pb(b);
if (a != b) {
adj[b].pb(a);
Union(a, b);
}
}
rep (i, 0, k) {
if (adj[i].size() >= 3) {
int cnt = 0;
for (int x : adj[i]) {
if (x == i) continue;
cnt += adj[x].size() > 1;
}
if (cnt >= 3) {
cout << "impossible\n";
exit(0);
}
}
}
int cyc = 0, cc = 0;
rep (i, 0, k) if (i == find(i)) {
if (adj[i].empty()) continue;
cc++;
cyc += sz[i] <= edge[i];
}
if (cc <= 1 || cyc == 0) cout << "possible\n";
else cout << "impossible\n";
}
```
:::
### L. Last Guess
---
#### 題目大綱
玩wordle，保證過程是好的以及有解，玩了n-1次後，輸出有可能的其中一組解
#### 想法
對於一組解答，會有以下的限制：
* 綠色代表一定是那個字母
* 黑色代表這個字母不可能在這裡出現
* 一個字母出現的次數下界會是在所有詢問中(綠色+黃色)最多的次數
* 其中，若一個字母在一次詢問中同時出現了綠黃黑，代表這個字母在答案出現的次數會恰好[上界 = 下界]是(綠+黃)
因此，可以考慮建最大流模型：
每個位置連邊到匯點流量為1，對於每個字母，對每個位置去記錄他可不可以放在這，可以就連流量為1的邊。
最後要來處理出現上下界問題，可以考慮多建一個點s'，先將源點向每個字母建流量為字母下界的邊，再從s'向每個字母建(上界-下界)流量的邊，最後從s往s'建流量為$m - \sum {下界}$的邊就能很好的完成下界流的要求，
構造答案就檢查字母和位置中間的流量有沒有被流滿就好。
:::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; }
template <typename T>
struct Dinic {
const T INF = numeric_limits<T>::max() / 2;
struct edge {
int v, r; T rc;
};
vector<vector<edge>> adj;
vector<int> dis, it;
Dinic(int n) : adj(n), dis(n), it(n) {}
void add_edge(int u, int v, T c) {
adj[u].pb({v, adj[v].size(), c});
adj[v].pb({u, adj[u].size() - 1, 0});
}
bool bfs(int s, int t) {
fill(all(dis), IINF);
queue<int> q;
q.push(s);
dis[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (const auto& [v, r, rc] : adj[u]) {
if (dis[v] < IINF || rc == 0) continue;
dis[v] = dis[u] + 1;
q.push(v);
}
}
return dis[t] < IINF;
}
T dfs(int u, int t, T cap) {
if (u == t || cap == 0) return cap;
for (int &i = it[u]; i < (int)adj[u].size(); ++i) {
auto &[v, r, rc] = adj[u][i];
if (dis[v] != dis[u] + 1) continue;
T tmp = dfs(v, t, min(cap, rc));
if (tmp > 0) {
rc -= tmp;
adj[v][r].rc += tmp;
return tmp;
}
}
return 0;
}
T flow(int s, int t) {
T ans = 0, tmp;
while (bfs(s, t)) {
fill(all(it), 0);
while ((tmp = dfs(s, t, IINF)) > 0) {
ans += tmp;
}
}
return ans;
}
bool inScut(int u) { return dis[u] < IINF; }
};
void solve() {
int n, m; cin >> n >> m;
vector<int> hi(26, m), lo(26, 0);
vector no(26, vector<bool>(m, 0));
vector<bool> vis(m, 0);
auto yes = no;
rep (i, 0, n - 1) {
vector<int> g(26, 0), b(26, 0), y(26, 0);
vector<int> cnt(26, 0);
string s, t; cin >> s >> t;
rep (j, 0, m) {
if (t[j] == 'G') {
vis[j] = 1;
yes[s[j] - 'a'][j] = 1;
cnt[s[j] - 'a']++;
} else if (t[j] == 'B') {
no[s[j] - 'a'][j] = 1;
} else {
no[s[j] - 'a'][j] = 1;
cnt[s[j] - 'a']++;
}
}
rep (j, 0, 26) {
if (count(all(s), 'a' + j) != cnt[j]) {
lo[j] = hi[j] = cnt[j];
} else {
chmax(lo[j], cnt[j]);
}
}
}
Dinic<int> G(26 + m + 3);
int s = 26 + m, t = s + 1, s2 = t + 1;
int tot = 0;
rep (i, 0, 26) {
G.add_edge(s, i, lo[i]);
G.add_edge(s2, i, hi[i] - lo[i]);
tot += lo[i];
rep (j, 0, m) {
if (yes[i][j]) {
G.add_edge(i, 26 + j, 1);
continue;
}
if (no[i][j] || vis[j]) continue;
G.add_edge(i, 26 + j, 1);
}
}
rep (i, 0, m) G.add_edge(26 + i, t, 1);
G.add_edge(s, s2, m - tot);
G.flow(s, t);
string ans(m, '#');
rep (i, 0, 26) {
for (auto [v, r, rc] : G.adj[i]) {
if (v != s && v != s2 && rc == 0) ans[v - 26] = char('a' + i);
}
}
cout << ans << '\n';
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
Sign in with Wallet
Connect another wallet