C - Many Balls
初始数字为 \(0\)， 你可以选择对这个数进行两种操作：\(A : +1\) 、\(B: *2\)，给出一组到达 \(n\) 的操作序列（长度最大 \(120\))。
转化成从 \(n\) 做 \(-1\) 和 \(/2\) 到 \(0\), 偶数做 \(/2\), 奇数做 \(-1\), \(log(10^{18}) \approx 60\), 操作数最多不会超过 \(120\)
Sample Code (C++)
int main()
{
IOS; LL n; cin >> n;
vector<char> v;
while(n)
{
if(n & 1) v.push_back(‘A‘), n -= 1;
else v.push_back(‘B‘), n /= 2;
}
reverse(v.begin(), v.end());
for(auto c : v) cout << c;
cout << endl;
return 0;
}
D - Pair of Balls
\(n\) 种颜色的球，每种有两个，按一定顺序放在 \(m\) 个瓶子中，若某两个瓶子最上方的两个球颜色相同，则可以同时取掉，问是否可以把球取完。
每种颜色转化成一个点，然后做有向图拓扑判环即可
Sample Code (C++)
int n, m;
vector<int> G[N];
int d[N];
int main()
{
IOS; cin >> n >> m;
for(int i = 1; i <= m; ++ i)
{
int k, pre = 0; cin >> k;
for(int j = 1; j <= k; ++ j)
{
int x; cin >> x;
if(pre) G[pre].push_back(x), d[x] ++;
pre = x;
}
}
queue<int> q;
for(int i = 1; i <= n; ++ i)
if(!d[i]) q.push(i);
int res = 0;
while(!q.empty())
{
int u = q.front(); q.pop(); res ++;
for(auto v : G[u])
{
d[v] --;
if(!d[v]) q.push(v);
}
}
if(res == n) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
E - Amusement Park
\(n\) 个数，取 \(k\) 次，每个数取完之后 \(-1\) , 求可以取得的最大值。
贪心从最大的开始取，将 \(a\) 从大到小排序后，判断剩余次数是否够前 \(i\) 个 \(a_i\) 取至 \(a_{i + 1}\) , 分类讨论即可
Sample Code (C++)
LL n, m, a[N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> a[i];
LL res = 0;
sort(a + 1, a + n + 1); reverse(a + 1, a + n + 1);
for(int i = 1; i <= n; ++ i)
{
if((a[i] - a[i + 1]) * i <= m)
{
res += (a[i] + a[i + 1] + 1) * (a[i] - a[i + 1]) / 2 * i;
m -= (a[i] - a[i + 1]) * i;
}
else
{
int t = m / i;
res += t * (a[i] + a[i] - t + 1) / 2 * i;
res += (m % i) * (a[i] - t);
break;
}
}
cout << res << endl;
return 0;
}
F - Max Sum Counting
给长度为 \(n\) 的序列 \(A = (A_1, A_2, ..., A_n)\), \(B = (B_1, B_2, ... , B_n)\), 求集合 \(S\) 的方案数，使得：\(\max\limits_{i \in S}A_i\ge \sum\limits_{i \in S}B_i\)
将 \(A\) 按升序排序，每次将当前 \(A_i\) 作为最大的 \(A_i\), 对 \(B\) 做背包统计方案数
Sample Code (C++)
int n;
PII a[N];
int dp[N];
int main()
{
IOS; cin >> n;
for(int i = 1; i <= n; ++ i) cin >> a[i].fi;
for(int i = 1; i <= n; ++ i) cin >> a[i].se;
sort(a + 1, a + n + 1);
int res = 0;
dp[0] = 1;
for(int i = 1; i <= n; ++ i)
{
for(int j = a[i].se; j <= a[i].fi; ++ j)
{
res += dp[j - a[i].se];
if(res > P) res -= P;
}
for(int j = 5000; j >= a[i].se; -- j)
{
dp[j] += dp[j - a[i].se];
if(dp[j] > P) dp[j] -= P;
}
}
cout << res << endl;
return 0;
}
G - 01Sequence
构造长度为 \(n\) 的 \(01\) 串， 满足 \(m\) 个 \((l, r, x)\) 的限制，即区间 \([l, r]\) 至少有 \(x\) 个 \(1\), 构造一种 \(1\) 最少的方案。
贪心按照右端点排序，并从右端点开始填 \(1\) , 使得填上的 \(1\) 尽可能同时满足多个限制，结合树状数组统计区间 \(1\) 的个数，并查集找最靠右端点的下一个可填 \(1\) 的位置，复杂度 \(O(nlogn)\)
Sample Code (C++)
int n, m, a[N];
struct Node
{
int l, r, x;
bool operator < (const Node& t) const
{
return r < t.r;
}
}q[N];
int fa[N], tr[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int lowbit(int x) { return x & -x; }
void add(int x) { for(int i = x; i <= n; i += lowbit(i)) tr[i] ++; }
int sum(int x)
{
int res = 0;
for(int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
IOS; cin >> n >> m;
for(int i = 1; i <= n; ++ i) fa[i] = i;
for(int i = 1; i <= m; ++ i) cin >> q[i].l >> q[i].r >> q[i].x;
sort(q + 1, q + m + 1);
for(int i = 1; i <= m; ++ i)
{
int one = q[i].x - (sum(q[i].r) - sum(q[i].l - 1));
for(int j = 1; j <= one; ++ j)
{
int now = find(q[i].r);
add(now);
a[now] = 1;
fa[now] = find(now - 1);
}
}
for(int i = 1; i <= n; ++ i) cout << a[i] << " ";
cout << endl;
return 0;
}