今天早上打了一下, 只做出了前三道简单题......TAT 还以为自己想到了E题的正解, 没过样例, 我把题目看错了......真是太不冷静了. QAQ (不过在一个没有空调的小房间里呆上一个半小时确实让人很难冷静) 度娘告诉我这是个经典问题, 然而我孤陋寡闻......涨知识了. D题也不难, 然而我读不懂题啊......QAQ 题解: 5/5 # A. Sagheer and Crossroads 十字路口, 判断是否撞车. 根据题意模拟即可.
B. Sagheer, the Hausmeister
n层楼, 每层楼有走廊, 走廊上m个房间, 走廊两端是通向上一层的楼梯. 楼梯只能向上走. 每段路 (上楼, 左右移动) 的长度均为1个单位. 从第一层左侧的楼梯口出发, 有一些房间必去, 终止位置任意, 求最短总路径. (1≤n≤15, 1≤m≤100)
先求出终点所在的楼层, 然后做DP: (i, 0/1)表示清理完前i层后到达第i层左/右侧的最短路.
有些疑惑, 这数据范围怎么这么小......呃, 出题人说2^n枚举就行了......
这道题花的时间有点久......在细节的处理上有点纠结......也是没有Think twice, code once吧.
const int N = 15, M = 100;
char s[M+3];
int dp[2][N], l[N], r[N];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
per (i, n-1, 0) {
scanf("%s", s);
rep (j, 1, m+1) {
if (s[j] == '0') continue;
l[i] = j;
r[i] = max(r[i], m+1-j);
}
}
while (n && !l[n-1]) --n;
if (!n) return puts("0"), 0;
else if (n == 1) return printf("%d\n", l[0]), 0;
dp[0][0] = 2*l[0];
dp[1][0] = m+1;
rep (i, 0, n-2) {
dp[0][i+1] = 1 + min(dp[0][i] + 2*l[i+1], dp[1][i] + m + 1);
dp[1][i+1] = 1 + min(dp[1][i] + 2*r[i+1], dp[0][i] + m + 1);
}
printf("%d\n", 1 + min(dp[0][n-2] + l[n-1], dp[1][n-2] + r[n-1]));
return 0;
}C. Sagheer and Nubian Market
买
typedef long long ll;
const int N = 1e5;
int n, a[N];
ll b[N];
ll cal(ll k)
{
rep (i, 0, n) b[i] = a[i] + (i+1) * k;
sort(b, b+n);
ll cost = 0;
rep (i, 0, k) cost += b[i];
return cost;
}
int main()
{
int S;
scanf("%d%d", &n, &S);
rep (i, 0, n) scanf("%d", a+i);
int l = 0, r = n+1;
while (r-l > 1) { // [l, r)
int m = (l+r)/2;
if (cal(m) <= S) l = m;
else r = m;
}
printf("%d %d\n", l, (int)cal(l));
return 0;
}D. Sagheer and Kindergarten
题面略长, 转化成图论模型后是这样的: n个点的有根树森林, q个询问: 加入一条边后, 是否形成环? 如果是, 有多少个点在环上或者能到达这个环? (1≤n,q≤10^5)
先DFS求出每个点所在连通块的根和DFS序. 新加入x->y, 如果y在x的子树中, 输出以y为根的子树大小; 否则, 输出0.
几乎猜到了题意, 但是没考虑能到达这个环的点. TAT
有点像[NOI 2009] 植物大战僵尸. 做那道题的时候也没有考虑环外的点......要吃一堑长一智啊......
const int N = 1e5, M = 1e5;
int dfn, cur[M+1], in[N+1], pre[N+1], fin[N+1], r[N+1], sz[N+1];
vector<int> adj[N+1];
int dfs(int u, int a)
{
sz[u] = 1;
r[u] = a;
pre[u] = ++dfn;
for (auto v : adj[u]) sz[u] += dfs(v, a);
fin[u] = ++dfn;
return sz[u];
}
int main()
{
int n, m, k, q;
scanf("%d%d%d%d", &n, &m, &k, &q);
rep (i, 0, k) {
int a, b;
scanf("%d%d", &a, &b);
if (cur[b]) {
++in[a];
adj[cur[b]].push_back(a);
}
cur[b] = a;
}
rep (i, 1, n+1)
if (!in[i])
dfs(i, i);
rep (i, 0, q) {
int x, y;
scanf("%d%d", &x, &y);
y = cur[y];
if (r[x] == r[y] && pre[y] > pre[x] && fin[y] < fin[x])
printf("%d\n", sz[x]);
else
puts("0");
}
return 0;
}E. Sagheer and Apple Tree
n个点的有根树上的点i有ai个苹果. 这棵树的所有叶子结点的深度的奇偶性相同. 两人轮流操作: 选一个点, 取走至少1个苹果, - 如果该点是叶子, 吃掉苹果 - 否则, 把这些苹果移到该点的某个儿子上
不能操作者输. 问有多少个点对(u,v) (u!=v), 使得交换u,v后先手必败. (u,v)和(v,u)视为等同的. (2≤n≤10^5, 1≤ai≤10^7)
读题的时候还记得, 读完后却认为每次只能取1个苹果......
能取多个苹果好像不太好做啊. 和Nim有点像, 但是丢掉的果子会到另一堆中. 大概还是得从SG定理入手, 那把什么当成小游戏呢? 这个深度条件是做什么用的呢?
去学习了一下知识, 便找到了以下经典问题.
| Staircase Nim n级台阶, 每级上有0或多个硬币, 每次可以把某级台阶上的一些硬币推到下一级台阶上, 两人轮流操作, 不能操作者输. |
| 如果不能把偶数级台阶上的硬币推走, 这就是奇数级台阶的Nim. 现在可以把偶数级台阶上的硬币推走, 它还是奇数级台阶的Nim. |
| 假设你是先手. 称奇数级台阶Nim和为0的状态为A状态. |
| - 你处于A状态. 如果推偶数台阶上的硬币, 对方可以把这些硬币再往下推一级; 如果推奇数台阶上的硬币, 根据Nim游戏的结论, 对方同样可以通过操作奇数台阶上的硬币, 使Nim和为0. 因此, 无论怎么操作, 对方都可以使你保持A状态. - 你不在A状态. 只要按照Nim游戏的最优策略, 可以使对方进入A状态. - 终态是A状态. |
| 由以上可以推出, 先手必败 <=> Nim和为0. |
上面的一切对于所有叶子结点的奇偶性相同的树也是成立的. 设叶子结点的奇偶性为t, 则SG值等于所有深度的奇偶性为t的结点上苹果数的Nim和.
C++11的语法糖和哈希表好评~
// c++11 required
#define LLFORMAT "I64"
using namespace std;
typedef long long ll;
const int N = 1e5;
int D, a[N], d[N];
vector<int> adj[N];
unordered_map<int, int> cnt;
void dfs(int u)
{
D = max(D, d[u]);
for (auto v : adj[u]) d[v] = d[u] + 1, dfs(v);
}
int main()
{
int n, s = 0;
scanf("%d", &n);
rep (i, 0, n) scanf("%d", a+i);
rep (i, 1, n) {
int p;
scanf("%d", &p);
adj[p-1].push_back(i);
}
dfs(0);
D &= 1;
ll t = 0;
rep (i, 0, n) {
d[i] &= 1;
if (d[i] == D) {
s ^= a[i];
++cnt[a[i]];
++t;
}
}
ll ans = s ? 0 : 1LL*n*(n-1)/2 - t*(n-t);
rep (i, 0, n)
if (d[i] != D)
if (cnt.count(s ^ a[i]))
ans += cnt[s ^ a[i]];
printf("%" LLFORMAT "d\n", ans);
return 0;
}