比赛的时候做了前四道, 然而第四道FST了, 原因是m,n搞反.
以下是A-F的题解. 6/7
最后一道题 (貌似是数位DP) 还没想通......脑子有点乱, 先放着吧. # A. A Serial Killer 一个杀手这样杀人: 从两名候选人中挑一个杀掉, 并另选一个人成为新的死亡候选人. 已知初始的两名候选人和n天里每天的死者和新候选人, 求(n+1)天里每天的两名死亡候选人. 没有人重名. (1≤n≤1000)
一开始读错题, 以为初始候选人是未知的. 如果已知, 那么模拟即可.
#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 s1, s2;
cin >> s1 >> s2;
cout << s1 << " " << s2 << endl;
int n;
cin >> n;
Rep (i, 0, n) {
string t1, t2;
cin >> t1 >> t2;
cout << t2 << " ";
if (s1 == t1) {
cout << s2 << endl;
s1 = t2;
} else {
cout << s1 << endl;
s2 = t2;
}
}
return 0;
}B. Sherlock and his girlfriend
给标号为2,3,4,...,n+1的n件珠宝染色, 一件珠宝不能和标号为它的质因子的珠宝同色, 求最小染色数和任意一种方案. (1≤n≤100000)
最小色数是NPC问题, 竞赛中出现, 一般来讲就得贪心了. 犯了一个方法论上的错误. 先试图证明 (看看它是不是无环, 然而并不) 而不是手算. 半天没搞出来, 翻了翻某群聊天记录, "质数输1, 合数输2". (算是开黑吧......)
??!
有道理啊......其实这就是贪心的策略. 但换种方式描述, 正确性就很显然了. 如果存在合数, 就至少得两种颜色. 这种构造说明2的下界是可以达到的.
特判n=1,2的情况.
#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 = 1e5;
bool f[MAX_N + 2];
int main()
{
int n;
cin >> n;
if (n <= 2)
cout << "1" << endl;
else
cout << "2" << endl;
For (i, 2, n+1) {
if (!f[i]) {
cout << "1 ";
for (int j = 2*i; j <= n+1; j += i)
f[j] = true;
} else
cout << "2 ";
}
cout << endl;
return 0;
}C. Molly's Chemicals
给一个长度为n的序列, 每个数的绝对值不超过10^9. 问有多少个区间的和等于整数k的自然数次幂. (1≤n≤10^5, 1≤|k|≤10)
这道题是最后做的. 开始没什么思路. 但是那么多人都过掉了, 说明它有一个简单的想法.
某次比赛的惨痛教训告诉我要看看什么数范围比较小, 也许能以此作为突破口. 这里k的范围比较小. 但是这是避免乘法溢出的吧. 所有数之和不超过10^14次方, long long足矣.
既然它会溢出, 说明增长得比较快. 咦, 岂不是可以枚举k的幂? 先差分, 然后把序列从左到右扫一遍, 维护自己和自己左边出现了哪些数, 丢到map里再查询即可.
想出来了略高兴, 而且时间不多了, 忘记了一个细节: 并非所有指数函数增长都比较快......|k|=1需特判. 被hack了一发. 其实挺感激的, 不然这场就FST两题了.
#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;
map<ll, int> cnt;
ll L[50];
int main()
{
int n, m = 0;
ll k, S = 0, ans = 0;
cin >> n >> k;
if (k != 1 && k != -1) {
for (ll x = 1; x <= 1e14; x *= k)
L[m++] = x;
} else {
L[m++] = 1;
if (k == -1)
L[m++] = -1;
}
++cnt[0];
For (i, 1, n) {
ll a;
cin >> a;
S += a;
Rep (j, 0, m)
if (cnt.count(S - L[j]))
ans += cnt[S - L[j]];
++cnt[S];
}
cout << ans << endl;
return 0;
}D. The Door Problem
n间房, m个开关, 每个开关可以控制多扇房门, 每间房恰好被两个开关控制. 按一次开关的效果是切换门的状态 (开/关). 已知每扇门的初始状态, 问能否使所有门都开. (2≤n≤10^5, 2≤m≤10^5)
先将问题数学化, 能列出一个模2的方程组. 可以转化为异或方程组 - 是否意味着可以高斯消元呢? 这个数据范围不允许.
换一种角度, 限制只能取0或1, 把这些变量之间的关系转化为相等和不等. 关押罪犯? 用虚点或带权并查集解决, 或者建图 - 2-SAT.
但是我一时忘记并查集究竟怎么搞了......虽然最终敲出了一个, 但是在m,n上翻车了.
结点和变量对应, 而不是和关系对应. 虽然通常用n表示点, m表示边.
| 带权并查集 不管相等还是不等, 一律合并, 表示两者关系已知. 每个点一个附加域, 表示与父亲的关系, 路径压缩的时候维护一下. 合并的时候将x, y的关系转化为x, y根结点的关系. |
| 虚点并查集 开2m个结点, 然后有两种理解: 与x相等的集合/与x不等的集合, x=0/x=1. 每一个关系合并两对集合. 必须合并两对, 不然有问题. 这一点用第二种解释更加明确. 之所以用并查集而非遇到不确定的填0, 就是因为这样可以同时枚举x=0,1的情况. 注意到合并的集合是对称的, 检查的时候看一种即可. |
注意到虚点并查集合并的集合跟2-SAT连的边是一致的. 相较2-SAT, 并查集的优势在于可以实时回答.
#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 = 1e5, MAX_M = 1e5;
vector<int> adj[MAX_N + 1];
int f[MAX_M*2 + 1], r[MAX_M*2 + 1], s[MAX_N + 1];
int F(int x)
{
return f[x] ? f[x] = F(f[x]) : x;
}
inline void merge(int x, int y)
{
if (x == y) return;
if (r[y] > r[x]) swap(x, y);
f[y] = x;
r[x] += x == y;
}
int main()
{
int n, m;
cin >> n >> m;
For (i, 1, n)
cin >> s[i];
For (i, 1, m) {
int k;
cin >> k;
For (j, 1, k) {
int u;
cin >> u;
adj[u].push_back(i);
}
}
bool ok = true;
For (i, 1, n) {
int x = F(adj[i][0]), y = F(adj[i][1]), ux = F(adj[i][0] + m), uy = F(adj[i][1] + m);
if (s[i]) { // eq
if (x == uy) {
ok = false;
break;
}
merge(x, y);
merge(ux, uy);
} else { // ueq
if (x == y) {
ok = false;
break;
}
merge(x, uy);
merge(y, ux);
}
}
puts(ok ? "YES" : "NO");
return 0;
}E. The Holmes Children
定义:
注意到
所以,
| 多重欧拉函数 去年APIO讲课为数不多的get到的知识点: |
所以暴力一番即可, 时间复杂度
单个欧拉函数值的求法 使用公式Pollard-Rho算法. 这里只要求做到 |
| 一个数的因子的数量是 |
| 模(10^9+7)可能是用来迷惑大众的吧...... |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
inline ll phi(ll n)
{
ll ans = n;
for (ll i = 2; i*i <= n; ++i) {
if (n % i == 0) {
ans = ans / i * (i-1);
do {
n /= i;
} while (n % i == 0);
}
}
return n > 1 ? ans / n * (n-1) : ans;
}
int main()
{
ll n, k;
cin >> n >> k;
ll ans = n;
k = (k+1)/2;
while (k && ans > 1) {
--k;
ans = phi(ans);
}
cout << ans % MOD << endl;
return 0;
}F. Sherlock's bet to Moriarty
一个n个点依次标号1,2,...,n的凸n边形和m条不在n边形内部相交的对角线, 形成的区域按照
为什么是20种不是k种? 可能跟2^20=1048576<100000有关. 建出平面图的对偶图, 发现是一棵树 (连通, 点数=边数+1). 尝试一条链的情形, 或许可以将链的中点填上1, 两边递归. 如点数N=7: 3 2 3 1 3 2 3. 显然链只需
树的重心 定义: 去掉该点形成的最大子树最小的点. 性质: 所有子树大小≤N/2. 证明: 反证. 如图, 设u满足重心的定义, v是最大子树, 然而size(v)>N/2. 现在来说明u不能是重心: size(x)<size(v), size(y)≤N/2<size(v).  推论: 一棵树只能有一个或两个重心, 并且它们只能相邻. 重心的求法: DFS. |
现在的问题是怎么建出这张图. 参考了一下官方教程. 将对角线(a,b)按照min(|a-b|, n-|a-b|)排序, 一层一层地拨开. 维护nxt指针, 表示轮廓线上某点的下一个点, 并记录一下这条边外面区域的编号. 特殊处理一下最里面的区域. 然后按照题意重新编号. 由于两个区域至多有两个公共点, 所以取区域的前三大顶点编号排序即可. 在有序的数组里二分寻找符合题意的编号.
#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 fst first
#define sec second
using namespace std;
typedef pair<int, int> ii;
const int MAX_N = 1e5, MAX_M = MAX_N - 3;
struct Diagonal {
int a, b, x;
bool operator<(const Diagonal& d)
{
return x < d.x;
}
} D[MAX_M];
struct Area {
int n, a, b, c;
} A[MAX_M + 1];
int nxt[MAX_N], mark[MAX_N], area[MAX_M];
vector<int> adj[MAX_M + 1];
void walk(int s, int t, int i)
{
static int v[MAX_N + MAX_M];
Area& ar = A[i];
int u = s;
while (u != t) {
if (mark[u] != -1)
area[mark[u]] = i;
v[ar.n++] = u;
u = nxt[u];
}
v[ar.n++] = t;
nxt[s] = t;
mark[s] = i;
sort(v, v+ar.n, greater<int>());
ar.a = v[0], ar.b = v[1], ar.c = v[2];
}
inline bool cmp(int i, int j)
{
return A[i].a < A[j].a || (A[i].a == A[j].a && ii(A[i].b, A[i].c) < ii(A[j].b, A[j].c));
}
void build(int n, int m)
{
Rep (i, 0, n-1) nxt[i] = i+1;
nxt[n-1] = 0;
fill_n(mark, n, -1);
int s = -1, t = -1;
Rep (i, 0, m) {
s = D[i].a, t = D[i].b;
walk(s, t, i);
}
walk(t, s, m);
area[m-1] = m;
static int o[MAX_M + 1];
Rep (i, 0, m+1) o[i] = i;
sort(o, o+m+1, cmp);
Rep (i, 0, m) {
int u = lower_bound(o, o+m+1, i, cmp) - o,
v = lower_bound(o, o+m+1, area[i], cmp) - o;
adj[u].push_back(v);
adj[v].push_back(u);
}
}
bool G[MAX_M + 1];
int parent[MAX_M + 1], color[MAX_M + 1], sz[MAX_M + 1];
ii get(int u, int p, int n)
{
ii ans(n, n);
sz[u] = 1;
int mx = 0;
Rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (v != p && !G[v]) {
ans = min(ans, get(v, u, n));
mx = max(mx, sz[v]);
sz[u] += sz[v];
}
}
mx = max(mx, n-sz[u]);
if (mx < ans.fst) {
parent[u] = p;
return ii(mx, u);
} else
return ans;
}
void dfs(int u, int p, int s, int c)
{
int g = get(u, p, s).sec;
G[g] = true;
color[g] = c;
Rep (i, 0, adj[g].size()) {
int v = adj[g][i];
if (!G[v])
dfs(v, g, v == parent[g] ? s - sz[g] : sz[v], c+1);
}
}
int main()
{
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
if (!m) {
cout << "1" << endl;
return 0;
}
Rep (i, 0, m) {
Diagonal& d = D[i];
int a, b;
cin >> a >> b;
--a, --b;
int mx = max(a, b), mn = min(a, b);
if (mx - mn < n - mx + mn)
d = (Diagonal){mn, mx, mx - mn};
else
d = (Diagonal){mx, mn, n - mx + mn};
}
sort(D, D+m);
build(n, m);
dfs(0, -1, m+1, 1);
Rep (i, 0, m+1)
cout << color[i] << " ";
cout << endl;
return 0;
}G. Sherlock and the Encrypted Data
待填.