这场比赛又只做出前两题......事后结合官方的教程学习了一番. # A. Oath of the Night's Watch 给一个长度为n的数列, 问多少个数满足至少有一个严格小于它, 同时至少有一个严格大于它.
7分钟之后才通过此题, 也许是理解题意花了些时间吧......唉, 慢就慢点吧.
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 1e5;
int a[MAX_N];
int main()
{
int n, mn, mx, ans = 0;
cin >> n >> a[0];
mn = mx = a[0];
for (int i = 1; i < n; ++i) {
cin >> a[i];
mn = min(mn, a[i]);
mx = max(mx, a[i]);
}
for (int i = 0; i < n; ++i)
ans += a[i] > mn && a[i] < mx;
cout << ans << endl;
return 0;
}B. Code For 1
按照这种方式展开一个序列: 将大于1的数x用
设
为[n]展开后1的个数, 则 , 也许会觉得这个式子很熟悉, 因为这就是从低位到高位读取二进制数的方法, 它的解是 . 同时, 我们也发现, [n]完全展开后的长度为大于它的最小的2的幂减去1, 因为递推式满足
, 还是在读二进制数, 只是把每一位都替换成了1.
所以可以类比在二叉树上求rank的过程, 求两个前缀和, 作差即得答案.
那么l, r为什么给的这么小呢? 官方教程中的解法是
#include <iostream>
using namespace std;
typedef long long ll;
ll cal(ll x, ll sz, ll k)
{
if (x <= 1)
return x;
ll y = x/2, s = sz/2;
if (k < s)
return cal(y, s, k);
if (k == s)
return y;
if (k == s+1)
return y + (x&1);
return y + (x&1) + cal(y, s, k-s-1);
}
int main()
{
ll n, l, r, s = 1;
cin >> n >> l >> r;
while (s < n)
s = (s << 1) | 1;
cout << cal(n, s, r) - (l > 1 ? cal(n, s, l-1) : 0) << endl;
return 0;
}C. Jon Snow and his Favourite Number
对长度为n的序列进行k次这样的操作: 排序, 将排在奇数位的数与x异或. 问结束后最大和最小数是什么. (1≤n≤10^5, 0≤k≤10^5, 0≤ai,x≤10^3)
企图观察性质的话......会发现有循环节, 或者像我一样GG.
然而这是一道暴力. ai, x都不超过10^3, 意味着序列中不会出现大于等于2^10=1024的数. 维护一下每种数有多少个就好. 10^8这个级别好像有点卡, 所以给了4s.
当时我的想法是, 把有序的数按位取反, 大小顺序会反过来. 异或是对特定的一些位取反, 是不是可以把这些位与其他位剥开看呢? 有没有可能只去追踪几个数的位置? 行不通......
启示: 题面中有哪些较小的数? 能否加以利用?
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
using namespace std;
typedef long long ll;
const int MAX_N = 1e5, MAX_X = 1<<10;
int a[MAX_N], b[MAX_N], c[MAX_N];
int main()
{
int n, k, x;
cin >> n >> k >> x;
Rep (i, 0, n) {
cin >> a[i];
++b[a[i]];
}
Rep (i, 0, k) {
copy(b, b + MAX_X, c);
int cnt = 0;
Rep (i, 0, MAX_X) {
int t = cnt & 1 ? c[i]/2 : (c[i]+1)/2;
b[i] -= t;
b[i^x] += t;
cnt += c[i];
}
}
int mn = 0, mx = MAX_X - 1;
while (!b[mn])
++mn;
while (!b[mx])
--mx;
cout << mx << " " << mn << endl;
return 0;
}D. Jon and Orbs
有k种宝珠, 最开始没有, 现在每天等概率生成一种, q个询问, 问至少多少天集齐k种的可能性不小于
如果理解了题意, 是一道DP. 设long double, 还想会不会需要取个对数之类的. 官方教程直接double......
由于最多问到1/2, 实验表明计算前7300天足够.
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
using namespace std;
typedef long double ld;
const int MAX_N = 7300, MAX_K = 1e3;
const ld eps = 1e-7;
ld f[MAX_N + 1][MAX_K + 1], g[MAX_N - MAX_K + 1];
int main()
{
int k, q, n;
cin >> k >> q;
f[1][1] = 1;
For (i, 2, MAX_N) {
For (j, 1, min(k, i))
f[i][j] = j*f[i-1][j]/k + (k-j+1)*f[i-1][j-1]/k;
if (f[i][k] > 0.501) {
n = i;
break;
}
}
For (i, k, n)
g[i-k] = f[i][k];
while (q--) {
int p;
cin >> p;
cout << upper_bound(g, g+n-k+1, (p-eps)/2000) - g + k << endl;
}
return 0;
}
int main()
{
int k, q, n;
cin >> k >> q;
f[1][1] = 1;
For (i, 2, MAX_N) {
For (j, 1, min(k, i))
f[i][j] = j*f[i-1][j]/k + (k-j+1)*f[i-1][j-1]/k;
if (f[i][k] > 0.501) {
n = i;
break;
}
}
For (i, k, n)
g[i-k] = f[i][k];
while (q--) {
int p;
cin >> p;
cout << upper_bound(g, g+n-k+1, (p-eps)/2000) - g + k << endl;
}
return 0;
}E. Game of Stones
n堆Nim游戏, 每堆si, 限制每堆不能同一规模多于一次, 问后手是否能赢. (1≤n≤10^6, 1≤si≤60)
算是我做的第一道游戏题. 重新看了一遍理论知识, 这题就是SG定理的应用. 但是它的SG函数非常有趣.
SG函数: SG(x) = mex { SG(y) | y是x的后继状态 } mex是不在集合中的最小自然数. 终态的SG函数值为0. 性质: x是必败状态 <=> SG(x) = 0 证明: 将所有状态拓扑排序, 运用数学归纳法. 1) 对于终止状态, 命题为真. 2) 如果x是必败状态, 那么它的后继都是必胜状态, 由归纳假设, 其SG值大于0, 所以SG(x)=0. 另一方面, 如果x是必胜状态, 那么它存在一个后继是必败状态, 其SG值等于0, 所以SG(x)<0.
SG定理: 游戏的和的SG函数值等于各个游戏SG值的Nim和 (异或和).
单堆Nim游戏的SG函数值等于石子数. Bouton定理可视为SG定理在Nim游戏中的直接应用.
于是, 本题可以算出在每一堆上游戏的SG函数值, 异或起来, 后手有必胜策略当且仅当异或和为0.
由于si很小, 而且满足两两不等的拆分也不多, 可以写个DP然后打表. 以 (石子数, 能用的规模) 为状态, 记忆化搜索即可. 实际能用的最大规模不超过石子数, 可以此减少状态数.
得到的结果很奇怪, 然后WA了.
单步运行了一下DP程序, 发现求mex那里写错了. 我排了个序, 处理重复的数那里出了点问题. 用布尔数组是更方便的选择.
正确的表是这样的: 0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, ...
尽管不清楚原理.
是不是很神奇呢?
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
using namespace std;
typedef long long ll;
typedef pair<int, ll> il;
const int inf = 1<<30;
map<il, int> f;
int sg(int x, ll S)
{
if (!x || !S)
return 0;
il p(x, S);
if (f.count(p))
return f[p];
vector<int> v;
For (i, 1, x) {
ll msk = 1LL << (i-1);
if (S & msk)
v.push_back(sg(x-i, S & ~msk & ((1LL << (x-i)) - 1)));
}
sort(v.begin(), v.end());
if (v[0])
return f[p] = 0;
int t = v.back() + 1;
Rep (i, 0, v.size() - 1)
if (v[i+1] - v[i] > 1) {
t = v[i] + 1;
break;
}
return f[p] = t;
}
int main()
{
For (i, 0, 60)
cout << sg(i, (1LL<<i) - 1) << ",";
return 0;
}#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
using namespace std;
const int sg[61] = {0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10};
int main()
{
int n, x = 0;
cin >> n;
Rep (i, 0, n) {
int s;
cin >> s;
x ^= sg[s];
}
cout << (x ? "NO" : "YES") << endl;
return 0;
}G. Barrels and boxes
f个一样的食物盒, w个一样的酒桶. 将它们摆成很多堆, 相同种类的堆不能相邻. Jon不喜欢一种摆法当且仅当存在高度 (即酒桶数目) 不超过h的酒堆, 每终摆法等可能, 输出他喜欢某种摆法的概率, 对(10^9+7)取模. (0≤f,w,h≤10^5)
把一个正整数n拆成有顺序的k个正整数之和的方案数是
由于1拆成1个部分的方案数是1, 所以规定
接下来可以枚举食物盒的堆数k, 然后讨论一下, 是k个, (k-1)个, 还是(k+1)个酒堆......
更优美的做法: 不要让它们竖着堆, 而是横着摆......所以分母是
一位外国友人发消息问 X 怎么计算 (大概是群发? ), 因为官方教程里用的是生成函数. 杀鸡不用宰牛刀啊. 于是提了一下 Generating Function 这个词和相关公式, 并解释了一下怎么从不定方程解的组数的角度看这个问题. 能帮到别人挺开心的~
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
using namespace std;
typedef long long ll;
const int MAX_N = 1e5, MOD = 1e9 + 7;
int n;
ll fac[2][MAX_N + 1];
ll inverse(int x)
{
return x == 1 ? 1 : MOD - MOD/x*inverse(MOD % x) % MOD;
}
void init()
{
fac[0][0] = fac[1][0] = 1;
For (i, 1, n)
fac[0][i] = fac[0][i-1] * i % MOD;
fac[1][n] = inverse(fac[0][n]);
Down (i, n-1, 1)
fac[1][i] = fac[1][i+1] * (i+1) % MOD;
}
inline ll C(ll n, ll k)
{
return n < 0 || k < 0 || k > n ? 0 : fac[0][n] * fac[1][k] % MOD * fac[1][n-k] % MOD;
}
int main()
{
ll f, w, h;
cin >> f >> w >> h;
if (!f) {
cout << (w > h) << endl;
return 0;
}
if (!w) {
cout << "1" << endl;
return 0;
}
n = max(f, w) - 1;
init();
ll p = 0, q = 0; // p/q
For (i, 1, f) {
ll t = C(f-1, i-1);
(q += t * (2*C(w-1, i-1) + C(w-1, i) + C(w-1, i-2))) %= MOD;
(p += t * (2*C(w-i*h-1, i-1) + C(w-(i+1)*h-1, i) + C(w-(i-1)*h-1, i-2))) %= MOD;
}
cout << p * inverse(q) % MOD << endl;
return 0;
}G. The Winds of Winter
一棵n个结点的有根树, 去掉某个结点, 则形成一片森林, 有一次改变某结点父亲的机会, 问去掉点i (i=1,2,..,n) 后森林里最大的树的最小结点数是多少. (1≤n≤10^5)
显然我们要将最大的树的某棵子树移植到最小的树上. 如果有多棵最大的树, 则任何移植都是无效的. 选择的子树过大, 小树会变得太大; 选择的子树过小, 大树仍然很大. 设大树的大小为M, 小树的大小为m, 则我们要最小化
所以, 现在的问题是维护去掉某个结点形成的每棵树的所有子树的大小, 支持lower_bound操作. 如果不考虑该结点上方那些就好搞了, 直接multiset启发式合并. (那就不会作为一场CF的G题了......)
据说, 遇到不会的题要使劲想, 没能解决的就是你该学的.
于是想了想......还是不知道怎样维护外面那些. 树上的一次转移似乎会使这个集合变化太多.
学了一下官方教程.
外面那些可以分为两类: parent和outer. 其中parent中存的大小要减去当前子树的大小才是真实值. outer定义为parent和当前子树的补集, 于是, 所有操作仅仅是在三个集合之间移动元素, 这和直接添加元素的时间复杂度是相同的.
写略复杂的DFS之前想清定义. 相当于隐含使用数学归纳法证明算法的正确性. 这里的定义是, 调用前, 全集U = parent + outer, 调用后, U = parent + outer + S, 集合两两不交. 如果调用后仅仅返回子树的一份拷贝而不修改outer, 会发现二分的时候需要将整棵子树从outer中去除, 这样时间复杂度是不对的.
multiset erase一个值会删除所有具有该值的元素, 所以得先find.
第一次提交没有将次大的儿子与外部的大小做比较. 维护了次大值的时候不要忘记啊. 还忘了一件事: 和std对拍, 没加srand......
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
#define ALL(s) s.begin(), s.end()
using namespace std;
const int MAX_N = 1e5;
typedef multiset<int> Set;
typedef Set::iterator iter;
int n, sz[MAX_N + 1], ans[MAX_N + 1];
vector<int> adj[MAX_N + 1];
Set s[MAX_N + 1], parent, outer;
void get_size(int u)
{
sz[u] = 1;
Rep (i, 0, adj[u].size()) {
int v = adj[u][i];
get_size(v);
sz[u] += sz[v];
}
}
inline bool get_big(int u, int& mx_sz, int& se_sz, int& mn_sz, int& big_ch)
{
se_sz = mx_sz = 0;
mn_sz = n + 1;
big_ch = -1;
int cnt = 1;
Rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (sz[v] > mx_sz) {
mx_sz = sz[v];
big_ch = v;
cnt = 1;
} else if (sz[v] == mx_sz)
++cnt;
mn_sz = min(mn_sz, sz[v]);
}
Rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (v != big_ch)
se_sz = max(se_sz, sz[v]);
}
return cnt != 1;
}
inline int get_ans(int mn, int mx, Set& S, int offset=0)
{
int ans = mx;
iter y = S.lower_bound((mx-mn+1)/2 - offset);
if (y != S.end())
ans = min(ans, mn + *y + offset);
if (y != S.begin())
ans = min(ans, mx - *--y - offset);
return ans;
}
inline void remove(Set& s, int v)
{
s.erase(s.find(v));
}
inline void remove(Set& s, Set& t)
{
for (iter i = t.begin(); i != t.end(); ++i)
remove(s, *i);
}
// before: U = parent + outer
// after: U = S + parent + outer
void dfs(int u, Set& S)
{
if (sz[u] == 1) {
remove(outer, sz[u]);
S.insert(sz[u]);
ans[u] = n-1;
return;
}
int mx, mn, se, big;
bool eq = get_big(u, mx, se, mn, big);
remove(outer, sz[u]);
parent.insert(sz[u]);
Rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (v != big) {
dfs(v, s[v]);
outer.insert(ALL(s[v]));
}
}
dfs(big, S);
remove(parent, sz[u]);
Rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (v != big)
remove(outer, s[v]);
}
if (mx == n-sz[u] || mx > n-sz[u] && eq)
ans[u] = mx;
else if (n-sz[u] > mx)
ans[u] = max(adj[u].size() == 1 ? 0 : mx, min(get_ans(mn, n-sz[u], outer), get_ans(mn, n-sz[u], parent, -sz[u])));
else // mx > n-sz[u] && !eq
ans[u] = max(adj[u].size() == 1 ? 0 : max(se, n-sz[u]), get_ans(min(mn, n-sz[u] ? n-sz[u] : n+1), mx, S));
Rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (v != big) {
S.insert(ALL(s[v]));
s[v].clear();
}
}
S.insert(sz[u]);
}
int main()
{
cin >> n;
Rep (i, 0, n) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
get_size(adj[0][0]);
For (i, 1, n)
outer.insert(sz[i]);
dfs(adj[0][0], s[1]);
For (i, 1, n)
cout << ans[i] << endl;
return 0;
}