2023-2024 ICPC Southwestern European Regional Contest
===
比賽鏈結
---
https://codeforces.com/gym/104945
比賽影片
---
{%youtube nOVCjYJf_yg %}
記分板
---
題解
---
### A. Card game
---
#### 題目摘要
有五種花色的牌，每種花色都會被分配$1到N$的數字，你會有$N$張牌，你想讓同花色的牌聚集在一起並以升序的方式排列，並且花色C必須放到最後，問最少理牌(將一張卡抽起來並插到一個空隙中)數
#### 想法
對花色(不含C)做排列得到每張牌的優先次序後，再把答案跟$N-LIS$取min，
:::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()
typedef pair<int, int > pii;
const int N=1e5+10;
string s[N];
void solve() {
int n; cin >> n;
for(int i=0;i<n;i++) cin >> s[i];
vector<char> v;
v.push_back('S');
v.push_back('W');
v.push_back('E');
v.push_back('R');
sort(v.begin(), v.end());
int ans=0;
do{
cout << '\n';
int tot=0;
vector<pii> tmp(n, {0, 0});
for(int j=0;j<4;j++){
for(int i=0;i<n;i++){
if (s[i][0]==v[j]){
int x=0;
int sz=s[i].size();
for(int k=1;k<sz;k++){
x*=10;
x+=s[i][k]-'0';
}
tmp[i]={j, x};
}
}
}
for(int i=0;i<n;i++){
if (s[i][0]=='C'){
int x=0;
int sz=s[i].size();
for(int k=1;k<sz;k++){
x*=10;
x+=s[i][k]-'0';
}
tmp[i]={4, x};
}
}
vector<pii> dp;
for(int i=0;i<n;i++){
int j=upper_bound(dp.begin(), dp.end(), tmp[i])-dp.begin();
if (j>=dp.size()){
dp.push_back(tmp[i]);
}else{
dp[j]=tmp[i];
}
}
ans=max(ans, (int)dp.size());
}while(next_permutation(v.begin(), v.end()));
cout << n-ans << '\n';
}
int main() {
solve();
}
```
:::
### B. Supporting everyone
---
#### 題目摘要
有$N$個國家，可以直接買國家旗幟或自己買顏色做，買旗幟或顏色(顏色買一次就能用到所有需要這顏色的國家)都花費1點，問要表示所有國家的最少花費
#### 想法
最小點覆蓋 = 最大匹配，顏色連國家，跑一次最大流解決
:::spoiler 實作
```cpp=
#pragma GCC optimize("Ofast")
#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 pii pair<int, int>
#define pb push_back
#define lpos pos << 1
#define rpos pos << 1 | 1
const int IINF = 1e9 + 7;
struct Dinic {
struct edge {
int v, r; ll 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, ll 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;
}
ll dfs(int u, int t, ll cap) {
if (u == t || cap == 0) return cap;
for (int &i = it[u]; i < adj[u].size(); i++) {
auto &[v, r, rc] = adj[u][i];
if (dis[v] != dis[u] + 1) continue;
ll tmp = dfs(v, t, min(cap, rc));
if (tmp > 0) {
rc -= tmp;
adj[v][r].rc += tmp;
return tmp;
}
}
return 0;
}
ll flow(int s, int t) {
ll ans = 0, tmp;
while (bfs(s, t)) {
fill(all(it), 0);
while ((tmp = dfs(s, t, IINF)) > 0) {
ans += tmp;
}
}
return ans;
}
};
void solve() {
int n, m; cin >> n >> m;
Dinic G(n + m + 2);
int s = n + m, t = s + 1;
rep (i, 0, m) {
G.add_edge(s, i, 1);
}
rep (i, 0, n) {
G.add_edge(m + i, t, 1);
int k; cin >> k;
rep (j, 0, k) {
int c; cin >> c;
c--;
G.add_edge(c, m + i, IINF);
}
}
int ans = m;
cout << G.flow(s, t) << '\n';
// cout << max(0LL, ans - G.flow(s, t)) << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### C. Metro quiz
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### D. Flag performance
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### E. Nicest view
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
#pragma GCC optimize("Ofast")
#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 pii pair<int, int>
#define pb push_back
#define lpos pos << 1
#define rpos pos << 1 | 1
const int IINF = 1e9 + 7;
void solve() {
int n; cin >> n;
vector<ll> h(n);
rep (i, 0, n) cin >> h[i];
vector<pii> see;
rep (i, 0, n) see.pb({h[i], i});
sort(all(see), greater<pii>());
set<int> st;
ll N = 0, D = 1;
for (auto [v, id] : see) {
auto r = st.upper_bound(id);
auto l = st.lower_bound(id);
if (l != st.begin() && *l != id - 1) {
ll dis = id - (*l + 1) + 1;
dis *= 1000;
ll y = h[*l] - h[*l + 1], y2 = v - h[*l + 1];
ll N2 = dis * y + y2, D2 = y;
ll g = __gcd(N2, D2);
N2 /= g, D2 /= g;
if (N2 * D > D2 * N) {
N = N2;
D = D2;
}
}
if (r != st.end() && *r != id + 1) {
ll dis = *r - 1 - id + 1;
dis *= 1000;
ll y = h[*r] - h[*r - 1], y2 = v - h[*r - 1];
ll N2 = dis * y + y2, D2 = y;
ll g = __gcd(N2, D2);
N2 /= g, D2 /= g;
if (N2 * D > D2 * N) {
N = N2;
D = D2;
}
}
st.insert(id);
}
D *= 1000;
ll g = __gcd(N, D);
N /= g, D /= g;
if (D == 1) cout << N << '\n';
else cout << N << '/' << D << '\n';
}
```
:::
### F. Programming-trampoline-athlon!
---
#### 題目摘要
#### 想法
:::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 pii pair<int, int>
#define pb push_back
void solve() {
int n; cin >> n;
vector<string> s(n);
vector<int> pt(n, 0);
vector<pii> ans;
rep (i, 0, n) {
cin >> s[i];
int c; cin >> c;
vector<int> e(6);
rep (j, 0, 6) cin >> e[j];
sort(all(e));
pt[i] = c * 10;
rep (j, 1, 5) pt[i] += e[j];
ans.pb({pt[i], i});
}
sort(all(ans), [&](auto a, auto b) {
if (a.first != b.first) return a.first > b.first;
else return a.second < b.second;
});
int last = 0, cnt = 0;
while (last != n - 1) {
if (ans[last].first > ans[last + 1].first) cnt++;
if (ans[last + 1].first != ans[last].first && last > 1) break;
last++;
}
// cout << last + 1 << '\n';
rep (i, 0, last + 1) {
auto [a, b] = ans[i];
cout << s[b] << ' ' << a << '\n';
}
}
int main() {
solve();
}
```
:::
### G. Favourite dish
---
#### 題目摘要
給N道菜，每道菜有兩個值$t_i, p_i$，有M個人要對N道菜評分，每個人有兩個值$T_i, P_i$，第i個人對第j道菜的評分標準是$\frac{t_j \times T_i + p_j \times P_i}{T_i + P_i}$，對每個人求最大評分的菜，若一樣就找index最小的
#### 想法
:::spoiler 實作
```cpp=
#pragma GCC optimize("Ofast")
#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 pii pair<int, int>
#define pb push_back
#define lpos pos << 1
#define rpos pos << 1 | 1
#define pll pair<ll, ll>
#define F first
#define S second
const int IINF = 1e9 + 7;
const ll LINF = 1e18 + 5;
struct info {
ll x, y, id;
};
ll cross(info a, info b) {
return a.x * b.y - a.y * b.x;
}
void solve() {
int n, m; cin >> n >> m;
vector<info> a(n), b(m);
rep (i, 0, n) {
auto &[x, y, id] = a[i];
cin >> x >> y;
id = i;
}
rep (i, 0, m) {
auto &[x, y, id] = b[i];
cin >> x >> y;
id = i;
}
sort(all(a), [&](info a, info b) {
if (cross(a, b) != 0) return cross(a, b) > 0;
return a.x < b.x;
});
sort(all(b), [&](info a, info b) {
if (cross(a, b) != 0) return cross(a, b) > 0;
return a.x < b.x;
});
vector<pll> ans(m, {0, LINF});
auto calc = [&](int i, int j) -> ll {
return a[i].x * b[j].x + a[i].y * b[j].y;
};
auto dc = [&](auto self, int l, int r, int ql, int qr) -> void {
if (l > r) return;
if (ql == qr) {
rep (i, l, r + 1) {
if (ans[b[i].id].F < calc(ql, i)) ans[b[i].id] = {calc(ql, i), a[ql].id};
else if (ans[b[i].id].F == calc(ql, i)) ans[b[i].id].S = min(ans[b[i].id].S, a[ql].id);
}
return;
}
int mid = l + r >> 1, opt;
rep (i, ql, qr + 1) {
if (ans[b[mid].id].F < calc(i, mid)) ans[b[mid].id] = {calc(i, mid), a[i].id}, opt = i;
else if (ans[b[mid].id].F == calc(i, mid)) {
if (a[i].id < ans[b[mid].id].S) {
ans[b[mid].id].S = a[i].id;
opt = i;
}
}
}
self(self, l, mid - 1, ql, opt);
self(self, mid + 1, r, opt, qr);
};
dc(dc, 0, m - 1, 0, n - 1);
rep (i, 0, m) cout << ans[i].S + 1 << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### H. Break a leg!
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### I. Throwing dice
---
#### 題目摘要
#### 想法
:::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()
typedef pair<int, int > pii;
const int N=1e5+10;
void solve() {
int n,m; cin >> n >> m;
ll asum=n, bsum=m,a;
rep(i,0,n) {cin >> a; asum+=a;}
rep(i,0,m) {cin >> a;bsum+=a;}
if(asum > bsum) cout << "ALICE\n";
else if(asum==bsum) cout << "TIED";
else cout << "BOB";
}
int main() {
solve();
}
```
:::
### J. Olympic goodies
---
#### 題目摘要
有一棵樹邊權和為$P$，你要任意邊權使最大邊權路徑的值最小
#### 想法
將邊權都丟到接到度數1的邊(假設為$m$個)上，其他邊權是0，所以只要看$P\% m是0、1、或2以上就好$，注意特判$N$是2的情況
:::spoiler 實作
```cpp=
#pragma GCC optimize("Ofast")
#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 pii pair<int, int>
const int N=1e5+10;
int in[N];
void solve(){
int n, p;
cin >> n >> p;
for(int i=1;i<n;i++){
int a, b;
cin >> a >> b;
in[a]++;
in[b]++;
}
if (n==1){
cout << 0 << '\n';
return;
}
if (n==2){
cout << p << '\n';
return;
}
int cnt=0;
for(int i=0;i<n;i++) cnt+=(in[i]==1);
if (p%cnt>=2){
cout << (2*((p/cnt)+1)) << '\n';
}else if (p%cnt==1){
cout << (2*(p/cnt)+1) << '\n';
}else{
cout << (2*(p/cnt)) << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### K. Team selection
---
#### 題目摘要
有$N人編號1到N$，並有$\frac{N}{2}$個操作，操作有$a_i、b_i$，意即將第$a_i$位的人移除後丟到$A$陣列，再將$b_i$位的人移除後丟$B$，輸出$A$與$B$
#### 想法
樹上二分搜(pbds會被卡)
:::spoiler 實作
```cpp=
#pragma GCC optimize("Ofast")
#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 pii pair<int, int>
#define pb push_back
#define lpos pos << 1
#define rpos pos << 1 | 1
const int MAXN = 4e6 + 5;
int tree[MAXN << 2];
void build(int pos, int l, int r) {
if (l == r) {
tree[pos] = 1;
return;
}
int mid = l + r >> 1;
build(lpos, l, mid);
build(rpos, mid + 1, r);
tree[pos] = tree[lpos] + tree[rpos];
}
void mod(int pos, int l, int r, int id, int v) {
if (l == r) {
tree[pos] = 0;
return;
}
int mid = l + r >> 1;
if (id <= mid) mod(lpos, l, mid, id, v);
else mod(rpos, mid + 1, r, id, v);
tree[pos] = tree[lpos] + tree[rpos];
}
int query(int pos, int l, int r, int k) {
if (l == r) return l;
int mid = l + r >> 1;
if (tree[lpos] >= k) return query(lpos, l, mid, k);
else return query(rpos, mid + 1, r, k - tree[lpos]);
}
void solve() {
int n; cin >> n;
vector<int> a(n);
vector<int> b(n);
rep (i, 0, n / 2) cin >> a[i];
rep (i, 0, n / 2) cin >> b[i];
build(1, 1, n);
vector<int> aa, bb;
rep (i, 0, n / 2) {
int A = query(1, 1, n, a[i]);
aa.pb(A);
mod(1, 1, n, A, 0);
int B = query(1, 1, n, b[i]);
bb.pb(B);
mod(1, 1, n, B, 0);
}
rep (i, 0, n / 2) cout << aa[i] << ' ';
cout << '\n';
rep (i, 0, n / 2) cout << bb[i] << ' ';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### L. Broken trophy
---
#### 題目摘要
給$K$種矩形邊長做多是3，用那些矩形構出$3\times N$的矩形(保證有解)
#### 想法
因為題目保證有解，只要先做完最棘手的矩形就好，而麻煩的矩形有$2\times 2$及$2\times 1$(邊長有3的擺完後還是矩形，而$1\times 1$找空隙擺就好)，但這兩種矩形可以合起來變成一個$3\times 2$，所以這要討論剩下的矩形要如何和其他種搭配：
1. 剩$2\times 1$：可以先三個搭配起來變成$3\times 2$，剩下的再和$1\times 1$搭配
2. 剩$2\times 2$：先用三個$2\times 2$搭配兩個$3\times 1$形成$3\times 6$，再看能不能用兩$2\times 2$個、一個$3\times 1$及一個$1\times 1$形成$3\times 4$，最後再做$2\times 2$與$1\times 1$的就好
剩下的矩形只要好好擺就好
:::spoiler 實作
```cpp=
#pragma GCC optimize("Ofast")
#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()
/*
0->3*1
1->3*2
2->3*3
3->2*1
4->2*2
5->1*1
*/
const int N=1e5+10;
int ans[5][N];
int a[N<<2], b[N<<2];
vector<int> cnt[10];
void solve() {
int k, n;
cin >> k >> n;
for(int i=1;i<=k;i++) cin >> a[i];
for(int i=1;i<=k;i++) cin >> b[i];
for(int i=1;i<=k;i++){
if (a[i]<b[i]) swap(a, b);
if (a[i]==3){
cnt[b[i]-1].push_back(i);
}else if(a[i]==2){
cnt[b[i]+2].push_back(i);
}else{
cnt[5].push_back(i);
}
}
int idx=0;
for(;cnt[3].size()&&cnt[4].size();idx+=2){
ans[0][idx]=ans[0][idx+1]=cnt[3].back();
ans[1][idx]=ans[1][idx+1]=ans[2][idx]=ans[2][idx+1]=cnt[4].back();
cnt[3].pop_back();
cnt[4].pop_back();
}
if (!cnt[3].empty()){
while(cnt[3].size()>=3){
ans[0][idx]=ans[0][idx+1]=cnt[3].back();
cnt[3].pop_back();
ans[1][idx]=ans[1][idx+1]=cnt[3].back();
cnt[3].pop_back();
ans[2][idx]=ans[2][idx+1]=cnt[3].back();
cnt[3].pop_back();
idx+=2;
}
while(!cnt[3].empty()){
ans[0][idx]=ans[1][idx]=cnt[3].back();
cnt[3].pop_back();
ans[2][idx]=cnt[5].back();
cnt[5].pop_back();
idx++;
}
}else{
while(cnt[4].size()>=3&&cnt[0].size()>=2){
ans[0][idx]=ans[1][idx]=ans[0][idx+1]=ans[1][idx+1]=cnt[4].back();
cnt[4].pop_back();
ans[0][idx+2]=ans[1][idx+2]=ans[0][idx+3]=ans[1][idx+3]=cnt[4].back();
cnt[4].pop_back();
ans[0][idx+4]=ans[1][idx+4]=ans[0][idx+5]=ans[1][idx+5]=cnt[4].back();
cnt[4].pop_back();
ans[2][idx]=ans[2][idx+1]=ans[2][idx+2]=cnt[0].back();
cnt[0].pop_back();
ans[2][idx+3]=ans[2][idx+4]=ans[2][idx+5]=cnt[0].back();
cnt[0].pop_back();
idx+=6;
}
if (cnt[4].size()>=2&&cnt[0].size()==1){
ans[0][idx]=ans[1][idx]=ans[0][idx+1]=ans[1][idx+1]=cnt[4].back();
cnt[4].pop_back();
ans[0][idx+2]=ans[1][idx+2]=ans[0][idx+3]=ans[1][idx+3]=cnt[4].back();
cnt[4].pop_back();
ans[2][idx]=ans[2][idx+1]=ans[2][idx+2]=cnt[0].back();
cnt[0].pop_back();
ans[2][idx+3]=cnt[5].back();
cnt[5].pop_back();
idx+=4;
}
while(!cnt[4].empty()){
ans[0][idx]=ans[1][idx]=ans[0][idx+1]=ans[1][idx+1]=cnt[4].back();
cnt[4].pop_back();
ans[2][idx]=cnt[5].back();
cnt[5].pop_back();
ans[2][idx+1]=cnt[5].back();
cnt[5].pop_back();
idx+=2;
}
}
while(!cnt[0].empty()){
ans[0][idx]=ans[1][idx]=ans[2][idx]=cnt[0].back();
cnt[0].pop_back();
idx++;
}
while(!cnt[1].empty()){
ans[0][idx]=ans[1][idx]=ans[2][idx]=cnt[1].back();
ans[0][idx+1]=ans[1][idx+1]=ans[2][idx+1]=cnt[1].back();
cnt[1].pop_back();
idx+=2;
}
while(!cnt[2].empty()){
ans[0][idx]=ans[1][idx]=ans[2][idx]=cnt[2].back();
ans[0][idx+1]=ans[1][idx+1]=ans[2][idx+1]=cnt[2].back();
ans[0][idx+2]=ans[1][idx+2]=ans[2][idx+2]=cnt[2].back();
cnt[2].pop_back();
idx+=3;
}
while(!cnt[5].empty()){
ans[0][idx]=cnt[5].back();
cnt[5].pop_back();
ans[1][idx]=cnt[5].back();
cnt[5].pop_back();
ans[2][idx]=cnt[5].back();
cnt[5].pop_back();
idx++;
}
for(int i=0;i<3;i++){
for(int j=0;j<n;j++){
cout << ans[i][j] << ' ';
}
cout << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### M. In-order
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
Sign in with Wallet
Connect another wallet