2020-2021 ACM-ICPC Nordic Collegiate Programming Contest
===
比賽鏈結
---
https://codeforces.com/gym/105444/
比賽影片
---
{%youtube_w-7YBJZHdA%}
記分板
---
題解
---
### A. Array of Discord
---
#### 題目摘要
給一組非嚴格遞增的序列，問能不能改變一個數字的一個位數使得序列不非嚴格遞增並輸出解
#### 想法
$n^2$枚舉長度相同的數字，在枚舉位數看能不能讓兩個大小關係改變
:::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++)
int len(ll x){
int res=0;
while(x){
res++;
x/=10;
}
return res;
}
void solve() {
int n; cin >> n;
vector<ll> a(n);
for(auto &x:a) cin >> x;
for(int i=0;i<n;i++) for(int z=i-1;~z;--z){
if (len(a[i])<=1&&len(a[z])<=1){
if (a[z]!=0){
for(int k=0;k<n;k++){
if (i==k) cout << 0 << ' ';
else cout << a[k] << ' ';
}
cout << '\n';
return;
}else if (a[i]!=9){
for(int k=0;k<n;k++){
if (z==k) cout << 9 << ' ';
else cout << a[k] << ' ';
}
cout << '\n';
return;
}
continue;
}
if (len(a[i])==len(a[z])){
int m=len(a[i]);
ll div=10;
for(int j=0;j<m;j++){
ll tmp1=a[z]%div;
ll tmp2=a[i]%div;
tmp1/=(div/10);
tmp2/=(div/10);
tmp1*=(div/10);
tmp2*=(div/10);
if (tmp1!=0){
ll tmp=a[i]-tmp2+tmp1-(div/10);
if (len(tmp)!=m) continue;
if (tmp<a[z]){
for(int k=0;k<n;k++){
if (k==i) cout << tmp << ' ';
else cout << a[k] << ' ';
}
cout << '\n';
return;
}
}else if (tmp2!=9*(div / 10)){
ll tmp=a[z]-tmp1+tmp2+(div/10);
if (len(tmp)!=m) continue;
if (tmp>a[i]){
for(int k=0;k<n;k++){
if (k==z) cout << tmp << ' ';
else cout << a[k] << ' ';
}
cout << '\n';
return;
}
}
div*=10;
}
}
}
cout << "impossible\n";
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### B. Big Brother
---
#### 題目摘要
求半平面交面積和
#### 想法
套模板
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll __int128
#define rep(a, b, c) for(int a = b; a < c; a++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define double long double
const ll LINF = 1e18 + 5;
struct pt {
ll x, y;
};
struct Line {
pt a, b;
};
pt operator + (pt a, pt b) {
return {a.x + b.x, a.y + b.y};
}
pt operator - (pt a, pt b) {
return {a.x - b.x, a.y - b.y};
}
ll operator ^ (pt a, pt b) {
return a.x * b.y - a.y * b.x;
}
ll operator * (pt a, pt b) {
return a.x * b.x + a.y * b.y;
}
pair<ll, ll> ap(Line a, Line b) {
return {(a.b - a.a) ^ (b.a - a.a), (a.b - a.a) ^ (b.b - a.a)};
}
bool isin(Line l0, Line l1, Line l2) {
auto [a02x, a02y] = ap(l0, l2);
auto [a12x, a12y] = ap(l1, l2);
if (a12x - a12y < 0) a12x *= -1, a12y *= -1;
return a02y * a12x - a02x * a12y > 0;
}
const double eps = 1e-9;
int sign(double x) {
return fabs(x) <= eps ? 0 : (x > 0 ? 1 : -1);
}
int pos(pt a) {
return sign(a.y) == 0 ? sign(a.x) < 0 : a.y < 0;
}
int ori(pt o, pt a, pt b) {
return sign((o - a) ^ (o - b));
}
vector<Line> HPI(vector<Line> arr) {
sort(all(arr), [&](Line a, Line b) {
pt A = a.b - a.a, B = b.b - b.a;
if (pos(A) != pos(B)) return pos(A) < pos(B);
if (sign(A ^ B) != 0) return sign(A ^ B) > 0;
return ori(a.a, a.b, b.b) < 0;
});
deque<Line> dq(1, arr[0]);
auto same = [&](pt a, pt b) {
return sign(a ^ b) == 0 && pos(a) == pos(b);
};
for (auto p : arr) {
if (same(dq.back().b - dq.back().a, p.b - p.a)) continue;
while (dq.size() >= 2 && !isin(p, dq.end()[-2], dq.back())) dq.pop_back();
while (dq.size() >= 2 && !isin(p, dq[0], dq[1])) dq.pop_front();
dq.pb(p);
}
while (dq.size() >= 3 && !isin(dq[0], dq.end()[-2], dq.back())) dq.pop_back();
while (dq.size() >= 3 && !isin(dq.back(), dq[0], dq[1])) dq.pop_front();
return vector<Line>(all(dq));
}
void solve() {
int n; cin >> n;
vector<pt> p(n);
for (auto &[x, y] : p) {
int a, b; cin >> a >> b;
x = a, y = b;
}
vector<Line> li;
rep (i, 0, n) {
if (p[i].x == p[(i - 1 + n) % n].x && p[i].y == p[(i - 1 + n) % n].y) continue;
li.pb({p[i], p[(i - 1 + n) % n]});
}
if (li.size() <= 2) {
cout << "0.00000\n";
return;
}
// cout << li.size() << '\n';
auto hull = HPI(li);
// for (auto l : hull) cout << l.a.x << ' ' << l.a.y << " & " << l.b.x << ' ' << l.b.y << '\n';
double A = 0;
int sz = hull.size();
auto calc = [&](Line x, Line y) -> pair<double, double> {
if (x.a.x == x.b.x) {
double m2 = 1.0 * (y.a.y - y.b.y) / (y.a.x - y.b.x);
double k2 = y.a.y - m2 * y.a.x;
return {x.a.x, m2 * x.a.x + k2};
}
if (y.a.x == y.b.x) {
double m = 1.0 * (x.a.y - x.b.y) / (x.a.x - x.b.x);
double k = x.a.y - m * x.a.x;
return {y.a.x, m * y.a.x + k};
}
double m = 1.0 * (x.a.y - x.b.y) / (x.a.x - x.b.x);
double m2 = 1.0 * (y.a.y - y.b.y) / (y.a.x - y.b.x);
double k = x.a.y - m * x.a.x;
double k2 = y.a.y - m2 * y.a.x;
double X = 1.0 * (k - k2) / (m2 - m);
double Y = m * X + k;
return {X, Y};
};
vector<pair<double, double>> P;
rep (i, 0, sz) {
auto [x, y] = calc(hull[i], hull[(i + 1) % sz]);
P.pb({x, y});
// cout << x << ' ' << y << '\n';
}
rep (i, 0, sz) {
auto [x, y] = P[i];
auto [x2, y2] = P[(i + 1) % sz];
A += x * y2 - x2 * y;
}
A = fabs(A);
cout << fixed << setprecision(10) << 1.0 * A / 2 << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### C. Coin Stacks
---
#### 題目摘要
給很多疊硬幣，每次可以選不同的兩疊各移除掉一個，問最後是否能移除全部，並輸出步驟
#### 想法
優先取現在能取的最大跟次大，這樣是好的，但我不會證明
小心他給你一疊大小為0的
:::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 pb push_back
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
void solve() {
int n; cin >> n;
vector<int> a(n);
rep (i, 0, n) cin >> a[i];
vector<pii> ans;
priority_queue<pii> pq;
rep (i, 0, n) {
if (a[i]) {
pq.push({a[i], i});
}
}
while (pq.size() > 1) {
auto [b, i] = pq.top();
pq.pop();
auto [b2, i2] = pq.top();
pq.pop();
ans.pb({i, i2});
b--, b2--;
if(b) pq.push({b, i});
if (b2) pq.push({b2, i2});
}
if (pq.empty()) {
cout << "yes\n";
for(auto [a, b] : ans) cout << min(a, b) + 1 << ' ' << max(a, b) + 1 << '\n';
} else {
cout << "no\n";
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### D. Dams in Distress
---
#### 題目摘要
#### 想法
:::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 pb push_back
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
const ll LINF = 1e18 + 5;
void solve() {
int n; ll w; cin >> n >> w;
n++;
vector<vector<int>> adj(n);
vector<ll> d(n, 0), c(n, 0);
c[0] = w;
rep (i, 1, n) {
int p; cin >> p >> c[i] >> d[i];
adj[p].pb(i);
}
vector<ll> mx(n, 0), sum(n, 0);
mx[0] = w;
auto dfs = [&](auto self, int u) -> void {
for (int v : adj[u]) {
mx[v] = max(mx[u] - d[v], c[v] - d[v]);
self(self, v);
}
};
dfs(dfs, 0);
ll ans = LINF;
rep (i, 0, n) {
ans = min(ans, mx[i]);
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### E. Exhaustive Experiment
---
#### 題目摘要
#### 想法
將他給的範圍x擴大兩倍，發現他就是一個轉置45度後的四個象限，先處理一下變成熟悉的象限。
:::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; }
void solve() {
int n; cin >> n;
vector<tuple<ll, ll, int>> pt(n);
for (auto &[x, y, t] : pt) {
ll X, Y; char c; cin >> X >> Y >> c;
X *= 2;
x = Y - X, y = X + Y;
t = (isupper(c) ? (c == 'P' ? 1 : -1) : 0);
}
sort(all(pt));
ll ln = LINF;
map<pll, int> no;
for (auto [x, y, t] : pt) {
if (t == 1) {
if (ln <= y) {
cout << "impossible\n";
return;
}
} else if (t == -1) {
chmin(ln, y);
} else {
if (y >= ln) {
no[{x, y}] = 1;
}
}
}
sort(all(pt), greater<tuple<ll, ll, int>>());
ll hp = -LINF, ans = 0, hnt = -LINF;
for (auto [x, y, t] : pt) {
if (t == 1) {
if (chmax(hp, y)) {
ans++;
chmax(hp, hnt);
}
} else if (t == 0 && !no[{x, y}]) {
chmax(hnt, y);
}
}
cout << ans << '\n';
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
### F. Film Critics
---
#### 題目摘要
給長度$n$的序列$a$，可以任意排列$a$，並有一套評分系統，若在第$i$項之前的分數平均小於$a_i$會得到$0$分，否則得到$m$分，問能不能找到一組排列能拿到恰$k$分
#### 想法
先判掉$k$不是$m$的倍數，並將$p$設成$\frac{k}{m}$。
先將評分系統改成問$i\times a_i$(0-base)是否大於等於$i$之前的分數和，再觀察$a$，能發現會得到$m$分的要是前$p$大的數(若比較小的數在某位置能得到$m$分，那比較大的數在相同位置也能得到$m$分)，並將$a_i$分成兩組，前$p$大要從小到大排序，前$(n-p)$小是由大到小，最後再從位置由小到大跑，並記錄這位置之前的分數和，若能放下前$p$大的就放，否則就放前$(n-p)$小的，若連前$(n-p)$小的也放不下的就無解
前$p$大能由小到大排序：
假設有兩數$a_k與a_{k+1},\ a_k<a_{k+1}$並兩數都屬於前$p$大，倘若$a_{k+1}放在p_1,\ a_k放在p_2且p_1<p_2$，則$\exists p_3\in (p_1,\ p2),\ p_4\in (p_3, p_2]$使條件滿足，因為$p_4$有機率比$p_2$小，所以從小到大的排序比較好
:::spoiler 實作
```cpp=
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second
void _solve(){
int n, m, k;
cin >> n >> m >> k;
set<pii> st;
vector<int> a(n+1);
vector<pii> vec(n);
for(int i=1;i<=n;i++){
cin >> a[i];
vec[i-1]={a[i], i};
}
if (k%m!=0){
cout << "impossible\n";
return;
}
sort(vec.begin(), vec.end(), greater<pii>());
vector<pii> g1, g2;
k/=m;
for(int i=0;i<k;i++) g1.push_back(vec[i]);
for(int i=k;i<n;i++) g2.push_back(vec[i]);
sort(g1.begin(), g1.end(), greater<pii>());
sort(g2.begin(), g2.end());
int d=0;
vector<int> ans(n);
for(int i=0;i<n;i++){
if (!g1.empty()&&i*g1.back().F>=d){
ans[i]=g1.back().S;
g1.pop_back();
d+=m;
}else{
if (g2.empty()||i*g2.back().F>=d){
cout << "impossible\n";
return;
}
ans[i]=g2.back().S;
g2.pop_back();
}
}
for(int i=0;i<n;i++) cout << ans[i] << ' ';
cout << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int _t=1;
//cin >> _t;
while(_t--) _solve();
}
```
:::
### G. Gig Combinatorics
---
#### 題目摘要
給一序列元素只有1, 2, 3，問有多少子序列滿足頭是1，尾是3，且中間數字都是2
#### 想法
先算頭是1尾是3且中間可以有2或沒2的數量，再減掉頭1尾3中間沒東西的數量就好
:::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++)
const ll mod=1e9+7;
void solve() {
int n; cin >> n;
vector<int> a(n+1, 0);
for(int i=1;i<=n;i++) cin >> a[i];
ll ans=0, sum=0;
for(int i=1;i<=n;i++){
if (a[i]==1){
sum=(sum+1)%mod;
}else if (a[i]==2){
sum=sum*2%mod;
}else{
ans=(ans+sum)%mod;
}
}
sum=0;
for(int i=1;i<=n;i++){
if (a[i]==1){
sum=(sum+1)%mod;
}else if (a[i]==3){
ans=(ans-sum+mod)%mod;
}
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### H. Hiring and Firing
---
#### 題目摘要
每天都有一個HR員工開除人或招募人，為避免尷尬不能讓HR員工開除他招募的人，問在開除順序是後招募先開除的情況下，最少需要多少位HR員工
#### 想法
:::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; }
void solve() {
int n; cin >> n;
vector<vector<int>> adj(n), adj2(n);
vector<int> st;
vector<int> h(n);
rep (i, 0, n) {
int f; cin >> f >> h[i];
while (f) {
int tmp = min(f, h[st.back()]);
f -= tmp;
h[st.back()] -= tmp;
adj[st.back()].pb(i);
adj2[st.back()].pb(i);
adj2[i].pb(st.back());
if (h[st.back()] == 0) st.pop_back();
}
if (h[i]) st.pb(i);
}
auto check_one = [&]() -> bool {
bool f = 1;
rep (i, 0, n) f &= adj[i].empty();
if (f) {
cout << 1 << '\n';
rep (i, 0, n) cout << 1 << ' ';
return true;
}
return false;
};
auto check_two = [&]() -> bool {
vector<int> col(n, -1);
bool f = 0;
auto dfs = [&](auto self, int u, int pa) -> void {
for (int v : adj2[u]) {
if (v == pa) continue;
if (col[v] == -1) {
col[v] = col[u] ^ 1;
self(self, v, u);
} else if (col[v] == col[u]) f = 1;
}
};
rep (i, 0, n) if (col[i] == -1) {
col[i] = 0;
dfs(dfs, i, -1);
if (f) return false;
}
cout << 2 << '\n';
rep (i, 0, n) cout << col[i] + 1 << ' ';
return true;
};
if (check_one()) return;
if (check_two()) return;
vector<int> col(n, -1), it(n);
rep (i, 0, n) it[i] = adj[i].size() - 1;
auto work = [&](auto self, int st) -> void {
while (it[st] >= 0) {
int nxt = adj[st][it[st]];
if (col[nxt] == -1) {
if (it[nxt] >= 0 && col[adj[nxt][it[nxt]]] != -1) {
col[nxt] = ((col[st] + 1) ^ (col[adj[nxt][it[nxt]]] + 1)) - 1;
if (col[nxt] == -1) {
col[nxt] = (col[st] + 1) % 3;
}
} else {
col[nxt] = (col[st] + 1) % 3;
}
}
it[st]--;
self(self, nxt);
}
};
rep (i, 0, n) if (col[i] == -1) {
if (it[i] >= 0 && col[adj[i][it[i]]] != -1) {
col[i] = (col[adj[i][it[i]]] + 1) % 3;
} else {
col[i] = 0;
}
work(work, i);
}
cout << 3 << '\n';
rep (i, 0, n) cout << col[i] + 1 << ' ';
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
### I. Infection Estimation
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### J. Joining Flows
---
#### 題目摘要
#### 想法
:::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 pb push_back
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
const ll LINF = 1e18 + 5;
void solve() {
int n;
cin >> n;
vector<tuple<ll, ll, ll>> v(n);
for(auto &[t, a, b]:v) cin >> t >> a >> b;
int q;
cin >> q;
vector<tuple<ll, ll, int>> qry(q);
for(int i=0;i<q;i++){
auto &[b, a, c]=qry[i];
cin >> a >> b;
a*=b;
c=i;
}
sort(qry.begin(), qry.end());
vector<ll> ans(q);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq2;
priority_queue<pair<ll, ll>> pq;
for (auto [t, a, b] : v) {
pq.push({t, b - a});
pq2.push({t, b - a});
}
ll F = 0, L = 0, R = 0, mxxxxf = 0;
for (auto [t, a, b] : v) {
L += t * a;
R += t * a;
mxxxxf += b;
F += a;
}
for(auto [f, t, idx]:qry){
if (f < F || F > mxxxxf) {
ans[idx] = 0;
continue;
}
ll d=f-F, tmp = d;
while(!pq.empty() && tmp){
auto [t, l] = pq.top();
pq.pop();
ll mi = min(l, tmp);
R += t * mi;
tmp -= mi;
l -= mi;
if (l) pq.push({t, l});
}
tmp = d;
while(!pq2.empty() && tmp) {
auto [t, l] = pq2.top();
pq2.pop();
ll mi = min(l, tmp);
L += t * mi;
tmp -= mi;
l -= mi;
if (l) pq2.push({t, l});
}
ans[idx] = (t >= L && t <= R);
F=f;
}
rep (i, 0, q) cout << (ans[i] ? "yes\n" : "no\n");
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### K. Keep Calm And Carry Off
---
#### 題目摘要
給兩大數，問讓兩數加減$X$使得最後兩數相加不進位的最小$X$
#### 想法
找到被進位影響的最高位，將小於等於最高位的位數都設0，最高位數+1的數+1，在用大數減法求$X$，兩個大數都做一遍取min
:::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; }
void solve() {
string a, b; cin >> a >> b;
reverse(all(a));
reverse(all(b));
while (a.size() < b.size()) a.pb('0');
while (b.size() < a.size()) b.pb('0');
int n = a.size();
string ans = "";
rep (PEPPA, 0, 2) {
int car = n;
for (int i = n - 1; i >= 0; --i) {
if (a[i] - '0' + b[i] - '0' >= 10) {
car = i;
break;
}
}
if (car == n) {
cout << '0' << '\n';
return;
}
while (car + 1 < n && a[car + 1] - '0' + b[car + 1] - '0' == 9) car++;
string sub(car + 1, '0'), res = "";
if (car == n - 1) sub.pb('1');
else sub.pb(a[car + 1] + 1);
rep (i, car + 2, n) sub.pb(a[i]);
int carry = 0;
rep (i, 0, n) {
if (sub[i] - a[i] - carry < 0) res.pb(sub[i] - a[i] - carry + 10 + '0'), carry = 1;
else res.pb(sub[i] - a[i] - carry + '0'), carry = 0;
}
while (res.back() == '0') res.pop_back();
reverse(all(res));
if (ans.empty()) ans = res;
else {
if (res.size() < ans.size()) ans = res;
else if (res.size() == ans.size()) {
rep (i, 0, res.size()) {
if (res[i] != ans[i]) {
ans = (res[i] < ans[i] ? res : ans);
break;
}
}
}
}
swap(a, b);
}
cout << ans << '\n';
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
### L. Language Survey
---
#### 題目摘要
給一個n\*m的圖，有三種顏色，若圖上的點為1，代表他要恰被一個顏色塗；若為2，代表他要被至少兩個顏色塗，並且每個顏色塗過的區域要洽為一個連通塊，輸出著色方法
#### 想法
考慮另一個問題：能不能將這張圖切成三個顏色的連通塊，並且沒有一個點的周圍沒有與自己顏色不同的點。
假設能做到這個問題，那麼原來的問題就變很簡單了。
將那張圖畫上去，對於一個2的點，去找他四周其中一個與他顏色不同的點將那個顏色塗到這個點，因為這張的圖的性質因此一定找的到一個點，如此一來就結束了。
要能構造上面的圖，也許有很多方法，總之我跟官解一樣。先特判n = 1或m = 1，將最左邊一列塗上A，將B指在右上角， C指在右下角，開始繞一個螺旋，特別注意要好好繞，不要讓邊邊疊兩行一樣顏色的爛掉
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(X, a, b) for(int X = a; X < b; ++X)
int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
void solve() {
int n, m; cin >> n >> m;
vector<string> g(n);
vector<vector<string>> G(3, vector<string>(n, string(m, '.')));
rep (i, 0, n) cin >> g[i];
if (n == 1) {
int cnt = 0;
rep (i, 0, m) {
if (g[0][i] == '2' && (i == 0 || g[0][i - 1] == '1')) cnt++;
if (cnt >= 3) break;
if (g[0][i] == '2') G[cnt][0][i] = 'A' + cnt;
G[0][0][i] = 'A';
}
if ((cnt == 0 && n * m < 3) || cnt >= 3) {
cout << "impossible\n";
return;
}
if (cnt == 0) {
G[1][0][0] = 'B';
G[2][0][1] = 'C';
G[0][0][0] = G[0][0][1] = '.';
} else if (cnt == 1) {
rep (i, 0, m) if (g[0][i] == '2') {
G[1][0][i] = 'B';
G[2][0][i] = 'C';
}
}
rep (i, 0, 3) {
rep (j, 0, n) cout << G[i][j] << '\n';
cout << '\n';
}
return;
}
if (m == 1) {
int cnt = 0;
rep (i, 0, n) {
if (g[i][0] == '2' && (i == 0 || g[i - 1][0] == '1')) cnt++;
if (cnt >= 3) break;
if (g[i][0] == '2') G[cnt][i][0] = 'A' + cnt;
G[0][i][0] = 'A';
}
if ((cnt == 0 && n * m < 3) || cnt >= 3) {
cout << "impossible\n";
return;
}
if (cnt == 0) {
G[1][0][0] = 'B';
G[2][1][0] = 'C';
G[0][0][0] = G[0][1][0] = '.';
} else if (cnt == 1) {
rep (i, 0, n) if (g[i][0] == '2') {
G[1][i][0] = 'B';
G[2][i][0] = 'C';
}
}
rep (i, 0, 3) {
rep (j, 0, n) cout << G[i][j] << '\n';
cout << '\n';
}
return;
}
rep (i, 0, n) G[2][i][0] = 'C';
rep (i, 1, m) G[0][0][i] = 'A';
rep (i, 1, n) G[1][i][m - 1] = 'B';
int x = 1, y = m - 1, cur = 0;
vector<int> d(2);
d[0] = m - 3, d[1] = n - 3;
while (d[0] > 0 || d[1] > 0) {
rep (i, 0, d[cur & 1]) {
x += dx[cur];
y += dy[cur];
G[1][x][y] = 'B';
}
d[cur & 1] -= 2;
cur = (cur + 1) % 4;
}
rep (i, 0, n) rep (j, 0, m) if (G[1][i][j] == '.' && G[2][i][j] == '.') G[0][i][j] = 'A';
rep (i, 0, n) rep (j, 0, m) if (g[i][j] == '2') {
rep (k, 0, 4) {
int nx = i + dx[k], ny = j + dy[k];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
rep (l, 0, 3) if (G[l][i][j] == '.' && G[l][nx][ny] != '.') {
G[l][i][j] = 'A' + l;
}
}
}
rep (i, 0, 3) {
rep (j, 0, n) cout << G[i][j] << '\n';
cout << '\n';
}
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
### M. Methodic Multiplication
---
#### 題目摘要
x\*S(y) = S(y\*x)，x+S(y) = S(x+y)
#### 想法
觀察水題，每\*一次會複製一次x或y，加法會把兩邊的S()數量加在一起形成一坨S()，所以總共會有x數量\*y數量個S()
:::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++)
string a, b;
int cnt1 =0, cnt2=0, cnt;
void solve() {
cin >> a >> b;
rep(i,0,a.size()){
if(a[i]=='S'){
cnt1++;
i++;
}else if(a[i]==0){
break;
}
}
rep(i,0,b.size()){
if(b[i]=='S'){
cnt2++;
i++;
}else if(b[i]==0){
break;
}
}
if(cnt1 > cnt2) swap(cnt1,cnt2);
cnt2*=cnt1;
rep(i,0,cnt2) cout << "S(";
cout << 0;
rep(i,0,cnt2) cout << ")";
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
Sign in with Wallet
Connect another wallet