把莫斯科时间当成北京时间, 于是错过了这一场......题目不难, 唉, 一个涨rating的机会...... 以下是题解: 6/6 会发现是贪心专场. 10的yp同学rank 30+ Orz
A. Pupils Redistribution
A, B两组, 每组n个学生, 每个学生有一个1~5的整数权值, 现用交换操作调整分组, 使得两组拥有权值w(w=1,...,5)的学生数量 (记为cnt[A/B][w]) 相等, 最小化交换次数, 或报告无解. (n ≤ 100)
如果某一权值学生总数为奇数, 则无解. 反之, 让A中多出来的到B去, B中多出来的到A去, 则cnt[A][w] = cnt[B][w] (w=1,..,5), A, B人数相等, 因此, A中到B去的和B中到A去的人数相等, 任意配对即为交换方案.
综上, 无解当且仅当存在cnt[A][w]+cnt[B][w]为奇数. 如果有解, A中要到B去的人数即为答案.
#include <bits/stdc++.h>
using namespace std;
int cnt[2][6];
int main()
{
int n;
cin >> n;
Rep (i, 0, 2) {
Rep (j, 0, n) {
int x;
cin >> x;
++cnt[i][x];
}
}
For (i, 1, 5) {
if ((cnt[0][i] + cnt[1][i]) % 2) {
cout << "-1" << endl;
return 0;
}
}
int ans = 0;
For (i, 1, 5) {
if (cnt[0][i] < cnt[1][i])
ans += (cnt[1][i] + cnt[0][i])/2 - cnt[0][i];
}
cout << ans << endl;
return 0;
}B. Weird Rounding
给两个数n, k, 问n的十进制表示中至少去掉多少个数字, 才能使得到的数能被10^k整除. 允许得到0. 不允许前导0. 保证有解且输入不含前导0. (0≤n≤2*10^9, 1≤k≤9)
一个数能被10^k整除, 当且仅当 1)它是0 或者 2) 末尾至少有k个连续的0.
先考虑 2), 从低尾向高位贪心, 如果现在不满足条件, 又遇到了非0数, 则删掉它. 做完一遍后仍不满足条件, 则只可能是 1), 由于题目保证有解, 输出(n的十进制表示的长度-1).
#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;
int main()
{
string s;
int k;
cin >> s >> k;
if (s == "0") {
cout << "0" << endl;
return 0;
}
int cnt = 0, ans = 0;
Down (i, s.size()-1, 1) {
if (s[i] == '0')
++cnt;
else
++ans;
if (cnt == k)
break;
}
cout << (cnt == k ? ans : s.size()-1) << endl;
return 0;
}C. Dishonest Sellers
某兄要买n件物品, 减价前至少买k件. 现给出n件物品减价前后的价格, 求最小花费. (1≤n≤2*10^5, 0≤k≤n, 1≤价格≤10^4)
DP可以解决这个问题, 然而数据范围不允许. 发现可以贪心. 先假设全都减价后买, 然后将减价前后价格之差从小到大排序, 先取前k件减价前购买, 后面的如果差是负数也在减价前购买.
#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;
int main()
{
string s;
int k;
cin >> s >> k;
if (s == "0") {
cout << "0" << endl;
return 0;
}
int cnt = 0, ans = 0;
Down (i, s.size()-1, 1) {
if (s[i] == '0')
++cnt;
else
++ans;
if (cnt == k)
break;
}
cout << (cnt == k ? ans : s.size()-1) << endl;
return 0;
}D. String Game
一个字符串t, 要删去一些字符得到字符串p. 一个小朋友按照某种顺序删掉所有的字符, 她的哥哥要在她删掉第x个字符后阻止她, 自己上, 以达成目标. 问x最大是多少. (1≤|p|≤|t|≤200000)
x可行当且仅当剩下的字符含有子序列p. 纠结了一会儿, 想枚举x, 却不知怎样快速地判定. 突然想到二分 (不知道是不是受到昨天某群有人说 "第一眼sb题, 第二眼二分, 但不知道怎么判定" 的启发), 于是成功了一半.
然而......不知道哪里想岔了, 误认为要判断是否含有子串p. KMP有点生疏, 开始抄书, 样例不对, 才发现错误. 实际上贪心地验证即可.
这题花了40min, 于是这场就GG了. TAT
#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;
const int MAX_N = 2e5;
string p, t;
int a[MAX_N];
bool check(int x)
{
static bool b[MAX_N];
string s;
fill_n(b, p.size(), false);
Rep (i, x, p.size())
b[a[i]] = true;
Rep (i, 0, p.size()) {
if (b[i])
s.push_back(p[i]);
}
int j = 0;
Rep (i, 0, s.size()) {
if (s[i] == t[j])
++j;
if (j == (int)t.size())
return true;
}
return false;
}
int main()
{
cin >> p >> t;
Rep (i, 0, p.size()) {
cin >> a[i];
--a[i];
}
int l = 0, r = p.size(); // [l, r)
while (r-l > 1) {
int m = (l+r)/2;
if (check(m))
l = m;
else
r = m;
}
cout << l << endl;
return 0;
}E. Bitwise Formula
输入n个定义语句和正整数m, 每句是如下两种之一: 1) var_name := binary_number_of_exactly_m_bits 2) vat_name := x op y (x, y is either the name of variable defined before or symbol '?', op in {AND, OR, XOR} ) 每个变量只定义一次, '?'是某个m位二进制数 (所有的'?'都是这一个数). 位运算和平时所理解的一样. 求最小的使得变量之和最小的二进制数, 和最小的使得变量之和最大的二进制数. (1≤n≤5000, 1≤m≤1000)
和 NOI <起床困难综合症> 相似, 按位贪心. 具体地, 枚举第i位是0, 1, 比较所得答案, 取符合题意的那个. 时间复杂度
35min写完这题对于一个码力低下的选手有点难......还剩3min时写完, 然而样例不对......于是这场只完成A~D.
为什么不对呢? i和j打反. 改过来就能AC吗? 不, TLE. 关闭iostream流同步后多过了几组, 然而还是T.
我们要将
#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;
const int MAX_N = 5e3, MAX_M = 1e3;
typedef bitset<MAX_M> Bitset;
typedef map<string, Bitset> Map;
Map V[2];
int main()
{
ios::sync_with_stdio(false);
V[0]["?"] = Bitset();
V[1]["?"] = Bitset().set();
int n, m;
cin >> n >> m;
Rep (i, 0, n) {
string var, t, o, s;
cin >> var >> t >> s;
if (isdigit(s[0]))
V[0][var] = V[1][var] = Bitset(s);
else {
cin >> o >> t;
For (j, 0, 1) {
const Bitset& x = V[j][s], & y = V[j][t];
switch (o[0]) {
case 'A':
V[j][var] = x & y; break;
case 'O':
V[j][var] = x | y; break;
default:
V[j][var] = x ^ y;
}
}
}
}
Bitset ans[2];
Rep (i, 0, m) {
int cnt[2] = {0, 0};
For (j, 0, 1) {
for (Map::iterator ix = V[j].begin(); ix != V[j].end(); ++ix)
if (ix->first[0] != '?')
cnt[j] += ix->second[i];
}
ans[0][i] = cnt[1] < cnt[0]; // min
ans[1][i] = cnt[1] > cnt[0]; // max
}
For (i, 0, 1) {
Down (j, m-1, 0)
cout << ans[i][j];
cout << endl;
}
return 0;
}F. Peterson Polyglot
一棵Trie树, 将第p层和第(p+1)层合并, 并合并分支产生一棵新的Trie树, 最小化新的Trie树的结点数, 并输出最小的p. (n≤3*10^5)
开始在想是不是要用到SAM之类的姿势. 否则, 怎样合并呢? 这里并没有合并两个东西产生一个新东西的模式啊.
参考了一下Tag. brute force, dfs and similar, dsu, hashing, trees. 并且, 它是Div. 1的C题, 所以不会太难. 果然是乱搞啊......
那就让我来brute force一番. 对于每一个结点u, 删掉它连向儿子的边, 并计算合并后的大小. 合并两棵Trie跟合并两棵线段树类似 - Trie的形态是相似的. 将y并到x上, 只用遍历y. 似乎应该把小的往大的上合. 虽然这里合并的结果不用上传.
每一层合并后的大小之和加上该层上方的结点数目即为该层的答案.
我也说不清启发式合并是不是必须的 (貌似不是), 因为线段树合并是均摊
另外, 本题不用考虑合并后单词消失的bug.
| 线段树合并复杂度的证明 假设这些线段树叶子的总数是 |
| 这个想法是我在WZH学长学习永无乡新姿势时产生的. 对于这份复杂度不明的代码跑得这么快我不服气, 试图构造数据卡掉 QAQ 合并(n-1)次满二叉树不就是 |
UPDATE 2017.3.8 线段树合并复杂度的简单证明 每次合并, 访问到的点相当于被删除了. 总点数是
就本题的时间复杂度询问了一下出题人niyaznigmatul, 得到回复如下: > Because dfs visits vertex for the first time if it's in both subtrees, that are being merged. Every next time the vertex is visited, it appears again in a new subtree. It means vertex is visited k - 1 times, if it appeared in k subtrees. So, consider biggest subtree and for every vertex this - 1 from k - 1 means "we don't visit biggest subtree".
和我先前对线段树合并复杂度的证明类似. 给树上的路径染色, 会合并在一起的染同一种颜色. 某种颜色出现在k个不同的子树中, 意味着这些颜色的结点总共访问(k-1)次. 考虑出现在最大子树中的颜色. 每个结点访问的次数比出现的次数少1, 不妨把这少访问的一次看作从不访问最大子树.
也就是说, 以下我的代码可以省去找最大子树的部分.
我直接在原树上合并, 再把加上的边清除. 官方教程也提供了另一种做法: 通过新建一棵树, 合并除最大子树外的其他子树, 再减掉它和最大子树的交.
希望没人告诉我Tag, 没人告诉我某题能做, 我也能做出它. 有时如果不事先知道题目在我的能力范围内, 会产生思维上的惰性.
#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;
const int MAX_N = 3e5, SIGMA = 26;
typedef pair<int, int> ii;
int adj[MAX_N + 1][SIGMA], d[MAX_N + 1], ans[MAX_N + 1], cnt[MAX_N + 1], sz[MAX_N + 1];
queue<ii> Q;
int merge(int x, int y)
{
int ret = 0;
Rep (i, 0, SIGMA) {
int& u = adj[x][i], v = adj[y][i];
if (!v) continue;
if (u)
ret += merge(u, v);
else {
u = v;
Q.push(ii(x, i));
ret += sz[v];
}
}
return ret;
}
void retrace()
{
while (!Q.empty()) {
ii p = Q.front();
Q.pop();
adj[p.first][p.second] = 0;
}
}
void dfs(int u)
{
int big = 0, mx = 0;
sz[u] = 1;
++cnt[d[u]];
Rep (i, 0, SIGMA) {
int v = adj[u][i];
if (!v) continue;
d[v] = d[u] + 1;
dfs(v);
sz[u] += sz[v];
if (sz[v] > mx) {
mx = sz[v];
big = v;
}
}
if (!big) {
++ans[d[u]];
return;
}
int s = mx;
Rep (i, 0, SIGMA) {
int v = adj[u][i];
if (v && v != big)
s += merge(big, v);
}
ans[d[u]] += s;
retrace();
}
int main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
Rep (i, 0, n-1) {
int u, v;
char x;
cin >> u >> v >> x;
adj[u][x - 'a'] = v;
}
d[1] = 1;
dfs(1);
int max_d = *max_element(d+1, d+n+1);
For (i, 2, max_d-1) {
cnt[i] += cnt[i-1];
ans[i] += cnt[i-1];
}
int* x = min_element(ans+1, ans+max_d);
cout << *x << endl << x - ans << endl;
return 0;
}