2022-2023 ACM-ICPC German Collegiate Programming Contest
===
比賽鏈結
---
https://codeforces.com/gym/104059
比賽影片
---
{%youtube Ha2ssG90SQo%}
記分板
---
題解
---
### A. Alternative Architecture
---
#### 題目摘要
給樂高的長寬，問可以擺出多少不同方向，擺放的方位必須讓樂高角角的圓對到後面超大樂高的圓
#### 想法
就是兩邊要做出相似直角三角形，直接報搜，注意邊長矩形的，三角形的斜邊要減1
:::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++)
map<ll, bool> mp;
void solve() {
ll a, b;
cin >> a >> b;
a--, b--;
ll g=__gcd(a, b);
if (a<b) swap(a, b);
ll aa=a/g, bb=b/g;
for(ll i=1;i<=a;i++) mp[i*i]=1;
ll ans=0;
for(ll i=1;i<=b;i++){
ll c=b*b-i*i;
if (mp[c]){
c=sqrtl(c);
if ((i%bb==0)&&(c%bb==0)){
ll ii=i/bb*aa;
ll cc=c/bb*aa;
if (ii*ii+cc*cc==a*a) ans++;
}
}
}
ans++;
if (a!=b) ans<<=1;
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### B. Breeding Bugs
---
#### 題目摘要
給一堆數字，找到一個集合使當中兩兩元素和不為質數
#### 想法
去除掉$1 + 1 = 2$的case，發現可以奇偶建二分圖，最大獨立集 = N - 最小點覆蓋，最小點覆蓋又等於最大匹配，因此跑一次最大匹配就好，至於1的case可以選擇在一堆1中只留下一個1建圖
實作寫了一般圖最大匹配，但其實不需要
:::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 int ll
struct Matching {
int n, tk;
vector<vector<int>> g;
vector<int> fa, pre, match, s, t;
queue<int> q;
int find(int u) {
return u == fa[u] ? fa[u] : fa[u] = find(fa[u]);
}
int lca(int a, int b) {
tk++;
a = find(a), b = find(b);
for (;;swap(a, b)) {
if (a != n) {
if (t[a] == tk) return a;
t[a] = tk;
a = find(pre[match[a]]);
}
}
}
void blossom(int x, int y, int l) {
while (find(x) != l) {
pre[x] = y;
y = match[x];
if (s[y] == 1) q.push(y), s[y] = 0;
if (fa[x] == x) fa[x] = 1;
if (fa[y] == y) fa[y] = 1;
x = pre[y];
}
}
bool bfs(int r) {
iota(all(fa), 0);
fill(all(s), -1);
while (!q.empty()) q.pop();
q.push(r);
s[r] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int u : g[x]) {
if (s[u] == -1) {
pre[u] = x;
s[u] = 1;
if (match[u] == n) {
for (int a = u, b = x, last; b != n; a = last, b = pre[a]) {
last = match[b], match[b] = a, match[a] = b;
}
return true;
}
q.push(match[u]);
s[match[u]] = 0;
} else if (!s[u] && find(u) != find(x)) {
int l = lca(u, x);
blossom(x, u, l);
blossom(u, x, l);
}
}
}
return false;
}
int solve() {
int res = 0;
for (int x = 0; x < n; x++) {
if (match[x] == n) res += bfs(x);
}
return res;
}
void add_edge(int u, int v) {
g[u].pb(v);
g[v].pb(u);
}
Matching (int _n) : n(_n), tk(0), g(n), fa(n + 1), pre(n + 1, n), match(n + 1, n), s(n + 1), t(n) {}
};
const int N=2e7+10;
bool isp[N];
vector<int> prime;
void solve() {
for(int i=2;i<=20000000;i++){
if (!isp[i]) prime.push_back(i);
for(auto x:prime){
if (x*i>20000000) break;
isp[x*i]=1;
if (i % x==0) break;
}
}
int n; cin >> n;
vector<int> p;
int one = 0;
rep (i, 0, n) {
int a; cin >> a;
if (a == 1 && one) continue;
p.pb(a);
if (a == 1) one = 1;
}
n = p.size();
vector<vector<int>> adj(n);
Matching G(n);
rep (i, 0, n) {
rep (j, i + 1, n) {
if (!isp[p[i] + p[j]]) {
G.add_edge(i, j);
}
}
if (p[i] == 1) one = 1;
}
cout << n - G.solve() << '\n';
}
main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### C. Chaotic Construction
---
#### 題目摘要
給一環狀區間，有兩種操作
1. 把某個點破壞或回複
2. 詢問兩個位置是不是連通的
#### 想法
將每個點設為1，用BIT單點修改區間詢問
檢查順著跑或逆著跑有沒有區間和等於區間長度就好
:::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 int MAXN = 1e5 + 5;
int n;
int BIT[MAXN];
void mod(int x, int val) {
while (x <= n) {
BIT[x] += val;
x += x & -x;
}
}
int query(int x) {
int res = 0;
while (x) {
res += BIT[x];
x -= x & -x;
}
return res;
}
void solve() {
int m; cin >> n >> m;
rep (i, 0, n) mod(i + 1, 1);
while (m--) {
char c; cin >> c;
if (c == '?') {
int a, b; cin >> a >> b;
if (a > b) swap(a, b);
int ch = query(b) - query(a - 1), ch2 = query(n) - query(b - 1) + query(a);
if (ch == b - a + 1 || ch2 == n - (b - a + 1) + 2) cout << "possible\n";
else cout << "impossible\n";
} else {
int a; cin >> a;
mod(a, c == '+' ? 1 : -1);
}
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### D. Diabolic Doofenshmirtz
---
#### 題目摘要
互動題，每次詢問n會回傳n除以x的餘數，求x
(詢問最多42次，詢問的點要遞增)
#### 想法
42好log，來二分搜
二分搜$x$，若沒有要遞增，直接搜到第一個$n \ \% \ x\not=n$的$n$就好
然而要遞增，可以再每次$n \ \% \ x\not=n$時，將新的起點設成$b=n-(n \ \% \ x)$，每次再檢查$b+mid$是否為$b+((b+mid) \ \% \ x)$就好
:::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++)
ll query(ll x){
cout << "? " << x << endl;
ll res;
cin >> res;
return res;
}
void solve() {
ll l=1, r=1e12+1;
ll b=0;
while(l<r){
ll m=(l+r>>1);
ll x=query(b+m);
if (b+x!=b+m) r=m ,b=b+m-x;
else l=m+1;
}
cout << "! " << l << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### E. Enjoyable Entree
---
#### 題目摘要
有A湯與B湯，第一天A湯有100，B湯0，第二天A湯有0，B湯100，之後兩湯的量是前一天湯加前二天湯的平均，求第$n$天兩碗湯分別的量
#### 想法
兩湯和為100，所以只要做一邊
A湯的遞迴是為
\begin{cases}
F(1)=100\\
F(2)=0\\
F(n)=\frac{F(n-1)+F(n-2)}{2}\ (n>2)
\end{cases}
注意到$n$到$10^6$時已經收斂了，只要遞迴跑到$10^6$，剩下都是$\frac{100}{3}$，B湯就是100-A湯
:::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 int N=1e6+10;
long double f[N];
void solve() {
ll n; cin >> n;
f[1]=100, f[2]=0;
for(int i=3;i<=1000000;i++){
f[i]=(f[i-1]+f[i-2])/2;
}
cout << fixed << setprecision(10);
if (n>1000000){
cout << 100.0/3 << ' ' << 200.0/3 << '\n';
}else{
cout << f[n] << ' ' << 100.0-f[n] << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### F. Formula Flatland
---
#### 題目摘要
找所有點度數不小於3的圖的最小環
#### 想法
每次從度數最小點建外指的邊能構出出入不大於5的DAG，並且環的可能答案只有3、4、5(我也不知道為什麼QAQ)，找出3環4環的所有case再做有限bfs就好
:::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, m; cin >> n >> m;
rep (i, 0, n) {
int x, y; cin >> x >> y;
}
vector<vector<int>> tmp(n), adj(n);
vector<pii> edge;
vector<int> deg(n, 0);
rep (i, 0, m) {
int a, b; cin >> a >> b;
a--, b--;
edge.pb({a, b});
tmp[a].pb(i);
tmp[b].pb(i);
deg[a]++;
deg[b]++;
}
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<bool> vis(m, 0);
rep (i, 0, n) pq.push({deg[i], i});
while (!pq.empty()) {
auto [d, i] = pq.top();
pq.pop();
if (d != deg[i] || d == 0) continue;
for (int id : tmp[i]) {
if (vis[id]) continue;
vis[id] = 1;
int v = (i ^ edge[id].F ^ edge[id].S);
adj[i].pb(v);
deg[v]--;
if (deg[v]) pq.push({deg[v], v});
}
deg[i] = 0;
}
vector dis(n, vector<int>(4, 0));
int ans = 5;
rep (i, 0, n) {
queue<pii> q;
set<int> reach;
q.push({i, 0});
dis[i][0] = 1;
reach.insert(i);
while (!q.empty()) {
auto [u, d] = q.front();
q.pop();
for (int v : adj[u]) {
reach.insert(v);
rep (k, 1, 4) if (dis[v][k]) {
chmin(ans, d + 1 + k);
}
dis[v][d + 1] = 1;
if (d < 2) q.push({v, d + 1});
}
}
for (int v : reach) rep (j, 0, 4) dis[v][j] = 0;
}
set<pii> st;
rep (i, 0, n) {
int sz = adj[i].size();
rep (j, 0, sz) rep (k, 0, j) {
if (st.count({minmax(adj[i][j], adj[i][k])})) {
chmin(ans, 4);
}
st.insert(minmax(adj[i][j], adj[i][k]));
}
}
cout << ans << '\n';
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
### G. Guessing Game
---
#### 題目摘要
題目狗幹長，總之有$n$個人，有七天每天有$d_i$場比賽，每個人會對每天的其中一場比賽做出預測(yes or no)，猜對會得一分，你會預測最後兩天的各一場比賽，問你有沒有機會贏其他人。
#### 想法
首先先觀察到我要贏的話要讓兩場都猜對，那麼代表其他人的答對題數不能超過一場，因此會發現這是一個2-SAT問題。
對於每一個人，要求其不能贏超過一場，意思就是他猜的七場中任兩場取反的or不能是0也就是：
$\Rightarrow\bigwedge\limits_{1\le i<j\le7}(\neg P_i \ \vee \ \neg P_j)$
那整個題目加上一定要取那兩個的條件就可以寫成：
$\Rightarrow P_1 \ \wedge \ P_2 \wedge \bigwedge\limits_{k=1}^n\bigwedge\limits_{i=1}^7\bigwedge\limits_{j=i+1}^7(\neg P_{ki} \ \vee \ \neg P_{kj})$
根據2-SAT的概念來建圖跑SCC就好。
其中一定要取的那兩個點可以用$(P_1 \vee P_1) \wedge (P_2 \vee P_2)$來表示
:::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<int> d(8, 0);
rep (i, 1, 8) cin >> d[i];
rep (i, 1, 8) d[i] += d[i - 1];
int m = d[7];
auto op = [&](int x) -> int {
return x >= m ? x - m : x + m;
};
vector b(n, vector<int>(7));
rep (i, 0, n) {
rep (j, 0, 7) {
cin >> b[i][j];
if (b[i][j] < 0) b[i][j] = -b[i][j] + m;
b[i][j]--;
b[i][j] += d[j];
}
}
vector<vector<int>> adj(m << 1);
int px, py; cin >> px >> py;
if (px < 0) px = -px + m;
px--;
px += d[5];
if (py < 0) py = -py + m;
py--;
py += d[6];
adj[op(px)].pb(px);
adj[op(py)].pb(py);
rep (i, 0, n) {
int pre = 0;
rep (j, 0, 7) rep (k, 0, 7) if (j != k) {
adj[b[i][j]].pb(op(b[i][k]));
}
}
int cnt = 0, sccid = 0;
vector<int> dfn(m << 1, 0), low(m << 1, 0), scc(m << 1, 0);
vector<bool> inst(m << 1, 0);
stack<int> st;
auto dfs = [&](auto self, int u) -> void {
st.push(u);
inst[u] = true;
dfn[u] = low[u] = ++cnt;
for(int v : adj[u]){
if(!inst[v] && dfn[v]) continue;
if(!dfn[v]) self(self, v);
chmin(low[u], low[v]);
}
if(low[u] == dfn[u]){
sccid++;
while(st.top() != u){
inst[st.top()] = false;
scc[st.top()] = sccid;
st.pop();
}
scc[u] = sccid;
inst[u] = false;
st.pop();
}
};
rep(i, 0, m << 1){
if(!dfn[i]) dfs(dfs, i);
}
rep (i, 0, m) {
if (scc[i] == scc[i + m]) {
cout << "impossible\n";
return;
}
}
cout << "possible\n";
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
### H. Hardcore Hangman
---
#### 題目摘要
有一個答案字串，由小寫字母組成，可以做7次詢問，每次可以詢問多個字母，會給你出現的位置，猜答案算是一個操作
#### 想法
有點分治的概念，可以用交集來找出現的數字，然後不斷的往下切，可以參考一下圖片。
但賽中debug太慢，哭了
`後來發現可以好好的切塊(用bit看)，不用用我的怪切法`
:::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++)
set<int> st1[26], st2[26], st3[26], st4[26];
void solve() {
int n;
cout << "? abcdefghijklvwx" << endl;
cin >> n;
rep(i,0,n){
int a; cin >> a; a--;
st1[0].insert(a);
}
cout << "? ghijklmnopqr" << endl;
cin >> n;
rep(i,0,n){
int a; cin >> a; a--;
if(st1[0].find(a)!=st1[0].end()){
st1[0].erase(a);
st1[1].insert(a);
}else{
st1[2].insert(a);
}
}
cout << "? defghi" << endl;
cin >> n;
rep(i,0,n){
int a; cin >> a;a--;
if(st1[0].find(a)!=st1[0].end()){
st2[1].insert(a);
st1[0].erase(a);
}else{
st2[2].insert(a);
st1[1].erase(a);
}
}
for(auto v : st1[0]) st2[0].insert(v);
for(auto v : st1[1]) st2[3].insert(v);
cout << "? pqrstuvwx" << endl;
cin >> n;
rep(i,0,n){
int a; cin >> a;a--;
if(st1[2].find(a)!=st1[2].end()){
st2[5].insert(a);
st1[2].erase(a);
}else{
st2[6].insert(a);
}
}
for(auto v : st1[2]) st2[4].insert(v);
vector<int> todel;
for(auto v : st2[6]){
if(st2[0].find(v)!=st2[0].end()){
st2[0].erase(v);
todel.push_back(v);
st2[7].insert(v);
}
}
for(auto v : todel){
st2[6].erase(v);
}
// rep(i,0,8){
// for(auto v : st2[i]) cout << v << ' ';
// cout << '\n';
// }
// good above
cout << "? bcefhiklnoqrtuwxz" << endl;
cin >> n;
rep(i,0,n){
int a; cin >> a;
a--;
if(st2[0].find(a)!=st2[0].end()){
st2[0].erase(a);
st3[1].insert(a);
}else if(st2[1].find(a)!=st2[1].end()){
st2[1].erase(a);
st3[3].insert(a);
}else if(st2[2].find(a)!=st2[2].end()){
st2[2].erase(a);
st3[5].insert(a);
}else if(st2[3].find(a)!=st2[3].end()){
st2[3].erase(a);
st3[7].insert(a);
}else if(st2[4].find(a)!=st2[4].end()){
st2[4].erase(a);
st3[9].insert(a);
}else if(st2[5].find(a)!=st2[5].end()){
st2[5].erase(a);
st3[11].insert(a);
}else if(st2[6].find(a)!=st2[6].end()){
st2[6].erase(a);
st3[13].insert(a);
}else if(st2[7].find(a)!=st2[7].end()){
st2[7].erase(a);
st3[15].insert(a);
}else{
st4[25].insert(a);
}
}
rep(i,0,8){
for(auto v : st2[i]) {st4[i*3].insert(v);}
}
// rep(i,0,18){
// cout << 30+i << ' ';
// for(auto v : st3[i]){
// cout << v << ' ';
// }
// cout << '\n';
// }
cout << "? behknqtwy" << endl;
cin >> n;
rep(i,0,n){
int a; cin >> a;
a--;
if(st3[1].find(a)!=st3[1].end()){
st3[1].erase(a);
st4[1].insert(a);
}else if(st3[3].find(a)!=st3[3].end()){
st3[3].erase(a);
st4[4].insert(a);
}else if(st3[5].find(a)!=st3[5].end()){
st3[5].erase(a);
st4[7].insert(a);
}else if(st3[7].find(a)!=st3[7].end()){
st3[7].erase(a);
st4[10].insert(a);
}else if(st3[9].find(a)!=st3[9].end()){
st3[9].erase(a);
st4[13].insert(a);
}else if(st3[11].find(a)!=st3[11].end()){
st3[11].erase(a);
st4[16].insert(a);
}else if(st3[13].find(a)!=st3[13].end()){
st3[13].erase(a);
st4[19].insert(a);
}else if(st3[15].find(a)!=st3[15].end()){
st3[15].erase(a);
st4[22].insert(a);
}else{
st4[24].insert(a);
}
}
int cnt =1;
rep(i,1,16){
for(auto v : st3[i]) {st4[i+cnt].insert(v);}
i+=1;
cnt++;
}
vector<int> ans(100000,-1);
// rep(i,0,26){
// for(auto v : st4[i]){
// cout << v << ' ';
// }
// cout << '\n';
// }
rep(i,0,26){
for(auto v: st4[i]){
ans[v]=i;
}
}
cout << "! ";
for(auto v:ans){
if(v==-1) break;
cout << char('a'+v);
}
cout << endl;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
// 4 2 5 6 7
// 4 1 3 4 6
// 2 2 6
// 3 1 3 4
// 1 2
// 2 2 8
```
:::
### I. Improving IT
---
#### 題目摘要
有$n$個月，每個月會有一個CPU能買，在$m$個月內要賣出(不含買它的月)，若要買新的CPU要先把手上的賣掉再買，第$n+1$個月會賣出手上的CPU。你每個月都要有一個CPU，求最小成本
#### 想法
先設$a_{i,\ j}$為第$i$個CPU買後$j$月的售價，當$j=0$時是買入價格，$dp_{i}$為第$i$的最小成本，能列出轉移式
\begin{equation}
dp_{i}=\min\limits_{max(1,\ i-m)\le j<i}dp_{j}-a_{i,\ i-j}+a_{i,\ 0}
\end{equation}
跑完在把第$n+1$月賣掉就好
:::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 LINF=1e18+10;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<ll>> a(n+1, vector<ll>(m+1));
for(int i=1;i<=n;i++){
cin >> a[i][0];
for(int j=1;j<=min(m, n-i+1);j++){
cin >> a[i][j];
}
}
vector<ll> dp(n+1, LINF);
dp[1]=a[1][0];
for(int i=2;i<=n;i++){
for(int j=max(1, i-m);j<i;j++){
dp[i]=min(dp[i], dp[j]-a[j][i-j]);
}
dp[i]+=a[i][0];
}
ll ans=LINF;
for(int j=max(1, n+1-m);j<n+1;j++){
ans=min(ans, dp[j]-a[j][n-j+1]);
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### J. Jesting Jabberwocky
---
#### 題目摘要
給長度為$N$的字串，有四種花色，你要做些交換讓他一樣花色的都排在一起，排序的方法是把一個花色拿出來移動到任意位置，求最小交換次數
#### 想法
由於花色沒有大小之分，可以把每一種排列都枚舉過一次
要最小交換次數，可以觀察到等於最大化不需要移動的點，也就是非嚴格的LIS
答案就會是最小的N-LIS
:::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 int ll
const int MAXN = 1e5 + 5;
const ll LINF = 1e18 + 5;
string t = "hdsc";
void solve() {
string s; cin >> s;
int n = s.size();
vector<int> rk(4);
iota(all(rk), 0);
map<char, int> mp;
ll ans = LINF;
do {
rep (i, 0, 4) mp[t[i]] = rk[i];
vector<int> lis;
rep (i, 0, n) {
auto it = upper_bound(all(lis), mp[s[i]]);
if (it == lis.end()) lis.pb(mp[s[i]]);
else *it = mp[s[i]];
}
ans = min(ans, n - (int)lis.size());
} while (next_permutation(all(rk)));
cout << ans << '\n';
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### K. K.O. Kids
---
#### 題目摘要
給你一個2xn的矩陣，每個矩陣只有一個是安全(可能左邊或右邊)，每次都會走另外一邊，除非他不安全就繼續往前，如果有一個人失敗就換下一個，給你安全的路徑，問一開始先選左邊的話會有幾個小孩安全過去。
#### 想法
直接實作，想清楚下一次的case就好。
:::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 n,k;
void solve() {
string s;
cin >> n >> k >> s;
char now = 'L'; int cnt = 0;
for(auto c : s){
if(now=='L'){
if(c=='R'){
cnt++;
now='L';
}else{
now='R';
}
}else{
if(c=='L'){
cnt++;
now='R';
}else{
now='L';
}
}
}
k<cnt?cout<<0:cout<<k-cnt;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### L. Lots of Land
---
#### 題目摘要
$ℓ\times w$的土地要平均分給$n$人，求其中一組解，若無解輸出IMPOSSIBLE
#### 想法
先判$ℓ\times w$是否整除$n$，若否則無解。再求$ℓ與n的gcd$，代表$ℓ$要放多少人，$\frac{n}{gcd}$的部分是$w$要放多少人，因此只要讓$n$個人都有$\frac{ℓ}{gcd}\times \frac{w}{\frac{n}{gcd}}$面積就好
:::spoiler 實作
```cpp=
```
:::
### M. Mirror Madness
---
#### 題目摘要
給一個多邊形，它的每條邊都是平行$x$軸或$y$軸，並且邊上點的數量不超過$10^6$。給一個起點(保證在邊上)，你會往$(1,\ 1)$的方向射光線，當碰到邊就會反射，題目保證光線不會碰到多邊形角落，問前$m$次碰到邊的點為何
#### 想法
光束只會有$x+y=k與x-y=k$的形式，並且一碰到牆就會換成另一種直線，可以讓每條線記錄所有在這條邊上的多邊形上的點(因為最多只有$10^6$個)並排序，接下來直接從起點直接跑就好。對於一條線從一個點下一次撞牆的點要算一下，當我目前位置是那條線的奇數項(0-base)，我下一個點是我前一位，反之後一位
:::spoiler 實作
```cpp=
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define F first
#define S second
const int N=4e6+10, B=2000000;
vector<int> v1[N], v2[N];
pii p[500005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i=0;i<n;i++) cin >> p[i].F >> p[i].S;
for(int i=0;i<n;i++){
int j=(i+1)%n;
if (p[i].F==p[j].F){
int d=(p[i].S<p[j].S)?1:-1;
for(int k=p[i].S;k!=p[j].S;k+=d){
v1[p[i].F-k+B].push_back(p[i].F);
v2[p[i].F+k+B].push_back(p[i].F);
}
}else{
int d=(p[i].F<p[j].F)?1:-1;
for(int k=p[i].F;k!=p[j].F;k+=d){
v1[k-p[i].S+B].push_back(k);
v2[k+p[i].S+B].push_back(k);
}
}
}
for(int i=0;i<=4000000;i++){
sort(v1[i].begin(), v1[i].end());
sort(v2[i].begin(), v2[i].end());
}
int x, y;
cin >> x >> y;
for(int i=0;i<m;i++){
if (i&1){
int tmp=x+y+B;
int j=lower_bound(v2[tmp].begin(), v2[tmp].end(), x)-v2[tmp].begin();
if (j&1) j--;
else j++;
x=v2[tmp][j];
y=tmp-x-B;
}else{
int tmp=x-y+B;
int j=lower_bound(v1[tmp].begin(), v1[tmp].end(), x)-v1[tmp].begin();
if (j&1) j--;
else j++;
x=v1[tmp][j];
y=x+B-tmp;
}
cout << x << ' ' << y << '\n';
}
}
```
:::
Sign in with Wallet
Connect another wallet