ARC211A
考虑这样一个性质就是在不考虑 \(5\) 的情况下，答案是什么，当且仅当只有一对 \(i\) 和 \(10 - i\) 都存在的，答案才会加 \(1\)。
考虑有 \(5\) 的情况就是不能有相邻的，这个也是好说的，然后感觉就做完了。
点击查看代码
//これも運命じゃないか
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define double long double
#define Air
namespace io{inline int read(){int f = 1, t = 0; char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}while(ch >= '0' && ch <= '9'){t = t * 10 + ch - '0'; ch = getchar();}return t * f;}inline void write(int x){if(x < 0){putchar('-'); x = -x;}if(x >= 10){write(x / 10);}putchar(x % 10 + '0');}
}
using namespace io;
int n;
int a[10];
void work(){n = 9;int tot = 0;for(int i = 1; i <= n; i++){a[i] = read();if(i != 5)tot += a[i];}int ans = 0;ans += max(0ll, a[5] - tot - 1);int cnt = 0;for(int i = 1; i <= 4; i++){if(a[i] && a[10 - i]){cnt ++;}else{if(a[i] || a[10 - i]){cnt = -1;}}}if(a[5]){cnt = -1;}if(cnt == 1){ans ++;}cout << ans << '\n';
}
signed main() {
#ifndef Airfreopen(".in","r",stdin);freopen(".out","w",stdout);
#endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int TCS = read();while(TCS--){work();} return 0;
}
ARC211B
神秘构造，我们考虑答案一定 \(\le 1\) 先特判掉 \(x = y\) 可能等于 \(0\) 的情况，然后就这样构造：
\[s1: \ x 个 0，\ y - x 个 1
\]
\[s2: \ z 个 0
\]
\[s3: \ z 个 0 + s1
\]
正确性感觉很显然，然后就没了吧。
点击查看代码
//これも運命じゃないか
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define double long double
#define Air
namespace io{inline int read(){int f = 1, t = 0; char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}while(ch >= '0' && ch <= '9'){t = t * 10 + ch - '0'; ch = getchar();}return t * f;}inline void write(int x){if(x < 0){putchar('-'); x = -x;}if(x >= 10){write(x / 10);}putchar(x % 10 + '0');}
}
using namespace io;
int x, y, z;
void work(){x = read();y = read();z = read();if(x == y){cout << y << ' ';for(int i = 1; i <= y; i++){cout << '0' << ' ';}cout << '\n';cout << z << ' ';for(int i = 1; i <= z; i++){cout << '0' << ' ';}cout << '\n';cout << z << ' ';for(int i = 1; i <= z; i++){cout << '0' << ' ';}cout << '\n';return ;}cout << y << ' ';for(int i = 1; i <= x; i++){cout << '0' << ' ';}for(int i = 1; i <= y - x; i++){cout << '1' << ' ';}cout << '\n';cout << z << ' ';for(int i = 1; i <= z; i++){cout << '0' << ' ';}cout << '\n';cout << y + z << ' ';for(int i = 1; i <= z; i++){cout << '0' << ' ';}for(int i = 1; i <= x; i++){cout << '0' << ' ';}for(int i = 1; i <= y - x; i++){cout << '1' << ' ';}cout << '\n';
}
signed main() {
#ifndef Airfreopen(".in","r",stdin);freopen(".out","w",stdout);
#endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int TCS = 1;while(TCS--){work();} return 0;
}
ARC211C
我们考虑一个事情就是我们肯定不会出现一次消掉有大于等于两个的极长连续段。
之后考虑每一个相邻连续段就是考察他旁边的两个点，然后贪心的看目前能决策的是不是全局最大值，然后就做完了。
点击查看代码
//これも運命じゃないか
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define double long double
#define Air
namespace io{inline int read(){int x; cin >> x; return x;}inline void write(int x){if(x < 0){putchar('-'); x = -x;}if(x >= 10){write(x / 10);}putchar(x % 10 + '0');}
}
using namespace io;
int n;
const int N = 2e5 + 10;
int a[N];
string s;
struct Data{int l, r;
};
vector<Data> dat;
int sum[N];
int totmx = 0;
void work(){n = read();cin >> s;s = ' ' + s + '#';for(int i = 1; i <= n; i++){a[i] = read();}int last = 0;for(int i = 1; i <= n + 1; i++){if(s[i] == '#'){if(i != 1 && s[i - 1] != '#'){dat.push_back({last + 1, i - 1});}last = i;}}int idl = 0, idr = 0;for(int i = 1; i <= n; i++){if(s[i] == '.'){idl = i;break;}}for(int i = n; i >= 1; i--){if(s[i] == '.'){idr = i;break;}}for(int i = idl; i <= idr; i++){totmx = max(totmx, a[i]);}int tot = 0;for(auto y: dat){int maxx = 0;for(int i = y.l; i <= y.r; i++){maxx = max(maxx, a[i]);}for(int i = y.l; i <= y.r; i++){sum[tot] += (a[i] == maxx);}tot ++;} int ans = 0;for(int i = 0; i < dat.size() - 1; i++){int maxx = 0;for(int j = dat[i].l; j <= dat[i + 1].r; j++){maxx = max(maxx, a[j]);}int flag = (maxx == totmx);ans += sum[i] * sum[i + 1] * flag;// cerr << sum[i] * sum[i + 1] << ' ';}cout << ans << '\n';
}
signed main() {
#ifndef Airfreopen(".in","r",stdin);freopen(".out","w",stdout);
#endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int TCS = 1;while(TCS--){work();} return 0;
}
ARC211D
考虑什么时候不合法，一定是断开某条割边后 \(1, 2\) 在同一连通块，然后我们直接大力 \(dfs\) 每次断掉 \(dfs\) 树上的边就是对的。
点击查看代码
//これも運命じゃないか
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define double long double
#define Air
namespace io{inline int read(){int f = 1, t = 0; char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}while(ch >= '0' && ch <= '9'){t = t * 10 + ch - '0'; ch = getchar();}return t * f;}inline void write(int x){if(x < 0){putchar('-'); x = -x;}if(x >= 10){write(x / 10);}putchar(x % 10 + '0');}
}
using namespace io;
int n, m;
const int N = 2e5 + 10;
vector<int>e[N], v[N];
int id[N];
bool flag[N * 3];
int ans[N][2];
bool vis[N][2];
void dfs(int now, int fa, int op){ans[now][op] = fa;vis[now][op] = 1;for(int i = 0; i < e[now].size(); i++){int y = e[now][i], z = v[now][i];if(vis[y][op]) continue;if(flag[z]){continue;}flag[z] = 1;dfs(y, now, op);}
}
signed main() {
#ifndef Airfreopen(".in","r",stdin);freopen(".out","w",stdout);
#endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);n = read();m = read();for(int i = 1; i <= m; i++){int x = read(), y = read();e[x].push_back(y);e[y].push_back(x);v[x].push_back(i);v[y].push_back(i + m);}memset(ans, -1, sizeof ans);dfs(1, 0, 0);dfs(2, 0, 1);bool flag = 0;for(int i = 1; i <= n; i++){flag |= (ans[i][0] == -1);flag |= (ans[i][1] == -1);}if(flag){cout << "No\n";return 0;}cout << "Yes\n";for(int i = 1; i <= n; i++){if(ans[i][0]){cout << ans[i][0] << ' ';}if(ans[i][1]){cout << ans[i][1] << ' ';}cout << '\n';}return 0;
}