atCoder Regular Contest 117
A - God Sequence
贪心就行,先把多的输出了就好
int main() {
IOS; cin >> n >> m;
if (m >= n) {
rep (i, 1, m) cout << -i << ' ', k -= i;
rep (i, 1, n - 1) cout << i << ' ', k += i;
cout << -k;
} else {
rep (i, 1, n) cout << i << ' ', k += i;
rep (i, 1, m - 1) cout << -i << ' ', k -= i;
cout << -k;
}
return 0;
}
B - ARC Wrecker
肯定是要去重的, 每次操作是选大于等于自己的, 相同的数, 不可能最后值不一样
然后就是发现发操作, 其实实在修改自己和最近大于自己的数与自己的差距, 直接算即可, 记得加入默认0
int main() {
IOS; cin >> n; VI a(n); ll ans = 1;
for (auto &i : a) cin >> i; a.pb(0);
sort(all(a)); a.erase(unique(all(a)), a.end());
rep (i, 1, a.size() - 1) ans = ans * (a[i] - a[i - 1] + 1) % mod;
cout << ans;
return 0;
}
C - Tricolor Pyramid
首先建模, 发现把三个颜色映射成 \(0, 1, 2\)
每次合并就是把其下的两个数相减, 模 \(3\) 即可
最后就是算每个数对最后贡献了几次, 明显的杨辉三角模型
由于模数\(3\)较小, 需要\(Lucas\)算组合数
int C(int n, int m) { return m > n ? 0 : fac[n] * facinv[m] % 3 * facinv[n - m] % 3; }
int lucas(int n, int m) { return m ? C(n % 3,m % 3) * lucas(n / 3, m / 3) % 3 : 1; }
void init(int n) {
fac[0] = fac[1] = facinv[0] = facinv[1] = inv[0] = inv[1] = 1;
rep (i, 2, n)
fac[i] = fac[i - 1] * i % 3,
inv[i] = inv[3 % i] * (3 - 3 / i) % 3,
facinv[i] = facinv[i - 1] * inv[i] % 3;
}
int main() {
IOS; cin >> n >> s; --n; init(2);
rep (i, 0, n) {
int c = s[i] == 'B' ? 0 : s[i] == 'W' ? 1 : 2;
m = (m + lucas(n, i) * c % 3) % 3;
}
if (n & 1) m = (3 - m) % 3;
cout << (m == 0 ? 'B' : m == 1 ? 'W' : 'R');
return 0;
}
D - Miracle Tree
明细是找直径, 然后先处理分支(先处理直径则所有分支都要加上剩余直径的长直接爆炸)
int d[N], s, t, pre[N], a[N];
VI h[N];
bool v[N];
void dfs(int x, int fa, int &s) {
pre[x] = fa; d[x] = d[fa] + 1; if (d[x] > d[s]) s = x;
for (auto &y : h[x]) if (y ^ fa) dfs(y, x, s);
}
void dfs(int x, int fa) {
a[x] = ++k;
for (auto &y : h[x]) if ((y ^ fa) && (!v[y])) dfs(y, x);
for (auto &y : h[x]) if ((y ^ fa) && v[y]) dfs(y, x);
++k;
}
int main() {
IOS; cin >> n;
rep (i, 2, n) { int u, v; cin >> u >> v; h[u].pb(v); h[v].pb(u); }
dfs(1, 0, s); dfs(s, 0, t); for (int i = t; i; i = pre[i]) v[i] = 1;
dfs(s, 0); rep (i, 1, n) cout << a[i] << ' ';
return 0;
}