A. Extract Numbers
有一说一这题挺毒的，乍一看是个垃圾模拟其实要处理的东西还蛮多，而且我还决定了要边读入边处理，再加上 Vim 用的还不熟练，写着写着就写急躁了。因此我总共写了 17 分钟，换了两种写法才过。
一遍 AC。
#错误警示：心态很重要，细节也要想清楚。Think twice, code once.
const int MAXN = 1e5 + 10;
char ss[MAXN];
int n;
std::vector<std::string> nums;
std::vector<std::string> oths;
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> (ss + 1);
n = (int) strlen(ss + 1);
std::string s;
bool num = false;
bool lz = false;
bool others = false;
for (int i = 1; i <= n; ++i) {
if (ss[i] == ',' || ss[i] == ';') {
if (s.empty() || !num || others) oths.push_back(s);
else nums.push_back(s);
s.clear();
num = lz = others = false;
} else {
s += ss[i];
if (!isdigit(ss[i]) || others) {
num = false; others = true; continue;
}
if (num == false && others == false && isdigit(ss[i])) {
num = true;
if (ss[i] == '0') lz = true;
continue;
}
if (lz && isdigit(ss[i])) {
num = false; others = true; continue;
}
}
}
if (s.empty() || !num || others) oths.push_back(s);
else nums.push_back(s);
s.clear();
num = lz = others = false;
if (nums.size() != 0) {
cout << """;
forall (nums, i) {
cout << nums[i];
if (i != (int) nums.size() - 1) cout << ',';
}cout << """ << endl;
} else cout << "-" << endl;
if (oths.size() != 0) {
cout << """;
forall (oths, i) {
cout << oths[i];
if (i != (int) oths.size() - 1) cout << ',';
}cout << """ << endl;
} else cout << "-" << endl;
return 0;
}
B. Queries about less or equal elements
这题也是有非常严重的失误，最开始已经想到了最简单的做法：离线后排序 B 数组然后一个指针扫过去，但是不知道为啥还是决定手写二分，结果光荣写挂。瞪了一会未果决定换离散化 + 树状数组，然而还是挂在后面几个点。
又瞪了一会无果，打算随机改几个易错点，正好发现树状数组的最大长度可以达到二倍的 n，遂把数组开大两倍不放心又开个 long long，交一遍过了。但实际上是不用开 long long 的。
#错误警示：一定要稳扎稳打考虑好所有细节，比如最大数据范围到底能有多少，特别是 CP 这种争分夺秒的比赛欲速一定不达。
const int MAXN = 2e5 + 10;
int n, m;
lli aa[MAXN], bb[MAXN];
lli nums[MAXN * 2], cnt;
struct BIT {
lli ss[MAXN * 2];
void mod(int x) {
for (; x <= n + m; x += (x & (-x))) ++ss[x];
}
int qry(int x) {
int r = 0;for (; x; x -= (x & (-x))) r += ss[x];
return r;
}
} bt;
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
rep (i, 1, n) {
cin >> aa[i]; nums[++cnt] = aa[i];
}
rep (i, 1, m) {
cin >> bb[i]; nums[++cnt] = bb[i];
}
std::sort(nums + 1, nums + 1 + cnt);
cnt = (std::unique(nums + 1, nums + 1 + cnt) - nums - 1);
// DEBUG(cnt);
for (int i = 1; i <= n; ++i) {
aa[i] = (std::lower_bound(nums + 1, nums + 1 + cnt, aa[i]) - nums);
bt.mod(aa[i]);
// DEBUG(aa[i]);
}
rep (i, 1, m) bb[i] = (std::lower_bound(nums + 1, nums + 1 + cnt, bb[i]) - nums);
rep (i, 1, m) {
cout << bt.qry(bb[i]) << ' ';
// DEBUG(bb[i]);
} cout << endl;
return 0;
}
C. Make Palindrome
做法很显然了，就是修改所有出现奇数次的字符。然而我最开始光考虑到字典序最小的要求，于是把所有奇数次字母都找了一个修改成了 'a'，这个肯定是不符合修改次数最小的条件的，交上去就光荣 WA 了。瞪了一会无果，开始随机手造数据，结果第一发就把自己 hack 掉了，然后才意识到这个修改次数不是最小的，接着才想到正解。
结果交上去第二发还是 WA 了，发现自己只修改了长度为奇数的情况，偶数是一样的。然后才过掉了这题。
#错误警示：槽点太多不知从何说起，一定不要想当然，好好考虑一下贪心策略是不是对的、需不需要分类讨论。
const int MAXN = 2e5 + 10;
char ss[MAXN];
int n;
int cnt[27];
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> (ss + 1); n = (int) strlen(ss + 1);
for (int i = 1; i <= n; ++i) {
++cnt[ss[i] - 'a'];
}
if (n & 1) {
// at most one odd
std::vector<int> odds;
for (int i = 0; i < 26; ++i) {
if (cnt[i] & 1) {
odds.push_back(i);
}
}
std::reverse(ALL(odds));
for (int i = 0, siz = (int) odds.size(); i < siz / 2; ++i) {
--cnt[odds[i]]; ++cnt[odds[odds.size() - 1 - i]];
}
int fx = 0;
for (int i = 0; i < 26; ++i) {
if (cnt[i] & 1) fx = i;
for (int j = 1; j <= cnt[i] / 2; ++j) {
cout << (char) (i + 'a');
}
} cout << (char) (fx + 'a');
for (int i = 25; i >= 0; --i) {
for (int j = 1; j <= cnt[i] / 2; ++j) {
cout << (char) (i + 'a');
}
}
} else {
// no odd
std::vector<int> odds;
for (int i = 0; i < 26; ++i) {
if (cnt[i] & 1) {
odds.push_back(i);
}
}
std::reverse(ALL(odds));
for (int i = 0, siz = (int) odds.size(); i < siz / 2; ++i) {
--cnt[odds[i]]; ++cnt[odds[odds.size() - 1 - i]];
}
for (int i = 0; i < 26; ++i) {
for (int j = 1; j <= cnt[i] / 2; ++j) {
cout << (char) (i + 'a');
}
}
for (int i = 25; i >= 0; --i) {
for (int j = 1; j <= cnt[i] / 2; ++j) {
cout << (char) (i + 'a');
}
}
}
return 0;
}
D
计算几何……
E. Lomsat gelral
dsu on tree 板子题。后面会写专题题解。
const int MAXN = 1e5 + 10;
int n, col[MAXN];
std::vector<int> G[MAXN];
int siz[MAXN], heavy[MAXN];
void dfs(int u, int fa) {
siz[u] = 1;
for (auto v : G[u]) {
if (v == fa) continue;
dfs(v, u);
siz[u] += siz[v];
if (siz[v] > siz[heavy[u]]) heavy[u] = v;
}
}
lli cnt[MAXN], mxcnt, thisans, fson;
lli ans[MAXN];
void get(int u, int fa, int x) {
cnt[col[u]] += x;
if (cnt[col[u]] > mxcnt) mxcnt = cnt[col[u]], thisans = col[u];
else if (cnt[col[u]] == mxcnt) thisans += col[u];
for (auto v : G[u]) {
if (v == fa || v == fson) continue;
get(v, u, x);
}
}
void dfs2(int u, int fa, bool del) {
mxcnt = thisans = 0;
for (int v : G[u]) {
if (v == fa) continue;
if (v != heavy[u]) dfs2(v, u, true);
} if (heavy[u]) dfs2(heavy[u], u, false), fson = heavy[u];
get(u, fa, 1); fson = 0;
ans[u] = thisans;
if (del) { get(u, fa, -1); mxcnt = thisans = 0; }
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
rep (i, 1, n) cin >> col[i];
rep (i, 1, n - 1) {
int u, v; cin >> u >> v;
G[u].push_back(v); G[v].push_back(u);
}
dfs(1, 0);
dfs2(1, 0, true);
rep (i, 1, n) cout << ans[i] << ' ';
cout << endl;
return 0;
}
F
二分图相关……