2018 CCF NOIP Junior 题解

标题统计

洛谷自测 P5015

牛客网自测 277A

给定一个字元串, 统计其中除空格和换行符之外, 有多少个字元

输入只有一行, 包含: 大小写字母, 数字, 空格和最后的换行符

我们可以直接读入一行, 然后统计其中空格之外的字元总数

也可以循环读入单个字元直到换行符停止, 累加非空格字元的数量

也可以循环读入字元串直到EOF, 把字元串长度累加

#include <cstdio> #include <cstring>

int main()
{
// 循环读入字元串应该是最简便的写法了
// 因为scanf("%s")以空格分割, 累加字元串长度作为答案, 读入直到EOF即可
// 或者用 cin 和 string 也可以
char s[10]; // 字元串长度不超过5
int ans = 0;
while (scanf("%s", s) != EOF)
ans += strlen(s);
printf("%d", ans);
return 0;
}

龙虎斗

洛谷自测 P5016

牛客网自测 277B

s1位工兵派往p1之后, 我们计算出这时的两方势力

如果两方势力相同, 那么手中的s2位需要派往m 如果不同, 那么这s2位要派往弱势一方的阵营或m 枚举派往哪个兵营即可

注意一下数据范围, 80分很容易拿到

最后的20分, 肯定会超过int, 然后会不会超过long long呢?

令 n = 100000, m = 99999, ci = 10^9, s1 = 10^9, p1 = 1

这时可以算得左方势力可能的最大值: 4999949999000000000 并不会超过long long的最大值 9223372036854775808 庆幸, 并不需要写高精度 (在考场上未必需要这么判断, 先把long long打上去, 稳拿80分 最后有时间再判断要不要写高精度 切忌一开始就写高精度)

最后, 不要使用abs()求绝对值, 而是用llabs()

如果是在考场上, 还是自己手写一个函数取绝对值比较稳妥

(CCF官方测评环境貌似用不了llabs()?)

#include <cstdio> #include <cmath> typedef long long int_t;

// 自始至终使用 long long, 避免中间运算溢出
int_t n, m, s1, p1, s2, p2;
int_t c[100005];

int main()
{
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", c + i);
scanf("%lld%lld%lld%lld", &m, &p1, &s1, &s2);

c[p1] += s1; // 将s1的兵放到p1兵营中

// 计算左右两边的势力
int_t L = 0, R = 0;
for (int_t i = 1; i < m; i++)
L += c[i]*(m-i); // |m-i|即距离
for (int_t i = m+1; i <= n; i++)
R += c[i]*(i-m);

if (L == R)
p2 = m; // 势力已经相等, 所以放到中立地点m
else if (L < R) { // 左方势力较小, 所以要放到1~m的某个位置
p2 = 1; // 假定要派往1
int_t nowd = llabs(R-L-s2*(m-1)); // 派往p2时的势力差距
for (int_t i = 2; i <= m; i++) { // 枚举2~m
int_t d = llabs(R-L-s2*(m-i)); // 派往i时的势力差距
if (d < nowd) {
p2 = i; // 如果派往i会让势力差距更小, 就选择i
nowd = d;
}
}
}
else if (L > R) {
p2 = m;
int_t nowd = L - R;
for (int_t i = m+1; i <= n; i++) {
int_t d = llabs(L-R-s2*(i-m));
if (d < nowd) {
p2 = i;
nowd = d;
}
}
}

printf("%lld", p2);
return 0;
}

摆渡车

洛谷自测 P5017

牛客网自测 277C

这道题目是dp, 我是按照时间点做的, 正解应该是按照人

如果ti有人到达, 那么这个人的发车时间是ti~ti+m-1 设定状态: f[i]表示在时间点i发车, 此时前面的人等待的时间之和 f[i] = f[j] + w[j+1, i] w[j+1, i]表示这一段时间内等待的人等待时间总和不需要从0~i-m+1枚举j, 只需要从i-2m~i-m+1枚举j即可

不过这个演算法是O(mT), 4kw, 在超时的边缘

luogu上是80分, 牛客网是70分

不过把luogu上的数据下载下来, 本地(i5-8550u)用时2.124s

在ccf官方测评下, 有可能会通过

#include <string> #include <cstdio> #include <cstring> #include <algorithm> using namespace std;

#define MAXT 4000005
#define INF 0x3f3f3f3f

int n, m, maxt, mint = MAXT;
int t[505];
int cnt[MAXT]; // cnt[i]表示时间点i的人数
int f[MAXT+100]; // f[i]表示在时间点i发车

int getint() {
int x = 0;
char c = getchar();
while (!isdigit(c)) c = getchar();
while ( isdigit(c)) x = x*10+c-48, c = getchar();
return x;
}

int main()
{
n = getint();
m = getint();
for (int i = 0; i < n; i++) {
t[i] = getint();
maxt = max(maxt, t[i]);
mint = min(mint, t[i]);
}

// 把所有时间点往前移动一下
maxt -= mint;
for (int i = 0; i < n; i++) {
cnt[t[i]-mint]++;
}

memset(f, INF, sizeof(f));

// 预处理f[0]~f[m-1], 这段时间只能发一车
f[0] = 0;
int num = cnt[0]; // num表示等车的人数
for (int i = 1; i < m; i++) {
f[i] = f[i-1] + num;
num += cnt[i];
}

for (int i = m; i <= maxt+m-1; i++) {
// f[i]由f[i-2m]~f[i-m]转移而来
int tj = 0;
// tj先计算i-m+1~i-1这段时间的人的等待时间总和
for (int j = i-1; j >= 0 && j >= i-m+1; j--)
tj += (i-j)*cnt[j];

// tj表示j+1~i这段时间等车的人的时间总和
for (int j = i-m; j > i-m*2 && j >= 0; j--) {
f[i] = min(f[i], f[j] + tj);
tj += (i-j)*cnt[j];
}
}

int ans = INF;
for (int i = maxt; i <= maxt+m-1; i++)
ans = min(ans, f[i]);
printf("%d", ans);
return 0;
}

对称二叉树

洛谷自测 P5018

牛客网自测 277D

整体思路是
求出dfs序列(过程中需要添加虚拟节点) 对dfs序列计算manacher演算法的len数组利用len数组判断每一个节点的子树的dfs序列是否回文的

对称二叉树有两个要求: 权值对称和结构对称

我们先假定结构对称, 看看怎么判断权值对称:

如果一颗子树权值对称, 那么它的dfs序列是回文串

这时应该想到manacher演算法: 求一个字元串的最长回文子串 但是我们不能求出来整棵树的dfs序列然后直接跑manacher, 返回答案 这样连样例2都过不了, 列出它的dfs序列你就明白了 我们需要利用manacher的len数组判断一颗子树的dfs序列是否回文串所以是求出整棵树的dfs序列, 计算出manacher演算法中的len数组

这时, 我们解决了权值对称, 那么这样能解决结构对称吗?

不能, 仅仅这样连样例1都过不了, 发现样例1在结构不对称的情况下满足子树的dfs序列是回文串 结构对称不太容易判断, 我在思考时也走了一些弯路(维护size等) 因为在每个节点都只有一个子节点时, dfs序列是回文的, 但是很容易结构不对称 其实, 我们只需要添加一些虚拟节点就可以把结构不对称的情况过滤掉了如果一个节点只有一个子节点, 那么在空的那个子树添加一个节点, 权值设定为原树中未出现过的 (实现时, 直接判断如果一边子树为空就添加, 即叶子节点下也会添加两个, 不过不影响答案)

#include <cstdio> #include <cstring> #include <algorithm> using namespace std;

#define MAXN 2000005
#define INF 0x3f3f3f3f

int n, v[MAXN], lc[MAXN], rc[MAXN];

int fir[MAXN]; // fir[i]表示点i在dfs序列中第一次出现的位置
int siz[MAXN]; // siz[i]表示点i子树大小
int siz2[MAXN]; // siz2[i]表示点i的子树中有多少个是虚拟节点
int cnt, seq[MAXN*2];
int cntm, seqm[MAXN*4]; // seq是dfs序列, seqm是马拉车演算法扩展之后的, 下标都从0开始用
int len[MAXN*4]; // len[i]表示seqm[i]为中心的最长的回文串, 右端点到i的字元个数

// 生成dfs序列
// 添加虚拟节点并不需要改变lc/rc数组, 只需要在dfs序列中添加即可
void dfs(int rt) {
siz[rt] = 1;
fir[rt] = cnt;
seq[cnt++] = v[rt];

if (lc[rt] > 0) {
dfs(lc[rt]);
siz[rt] += siz[lc[rt]];
siz2[rt] += siz2[lc[rt]];
} else { // 子树为空则添加虚拟节点
siz[rt]++;
siz2[rt]++;
seq[cnt++] = INF*2;
seq[cnt++] = INF*2;
}
if (rc[rt] > 0) {
dfs(rc[rt]);
siz[rt] += siz[rc[rt]];
siz2[rt] += siz2[rc[rt]];
} else {
siz[rt]++;
siz2[rt]++;
seq[cnt++] = INF*2;
seq[cnt++] = INF*2;
}

seq[cnt++] = v[rt];
}

// manacher演算法, 求出来len数组即可
void Manacher() {
// 预处理, 将seq序列扩展
seqm[cntm++] = INF;
for (int i = 0; i < cnt; i++) {
seqm[cntm++] = seq[i];
seqm[cntm++] = INF;
}

// 演算法流程, 求出来len数组
int pos = 0, R = 0;
for (int i = 0; i < cntm; i++) {
if (i < R)
len[i] = min(len[2*pos-i], R-i);
else
len[i] = 1;
while (i - len[i] >= 0 &&
i + len[i] < cntm &&
seqm[i-len[i]] == seqm[i+len[i]])
len[i]++;

if (len[i] + i - 1 > R) {
R = len[i] + i - 1;
pos = i;
}
}
}

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", v + i);
for (int i = 1; i <= n; i++)
scanf("%d%d", lc + i, rc + i);

dfs(1); // 求出dfs序列
Manacher(); // 处理出len数组, 利用len数组判断某棵子树是否回文

int ans = 1;
for (int i = 1; i <= n; i++) {
// 依次判断每一棵子树是否回文
// 找到这个子树的dfs序列对应的seqm序列的位置
// 判断中点的len值是否超过右端点即可
// seq[i]*2+1 -> seqm[]的位置
int l = fir[i] * 2 + 1;
int r = (fir[i] + siz[i]*2 - 1) * 2 + 1;
int mid = (l + r) / 2;
if (r-mid+1 <= len[mid])
ans = max(ans, siz[i]-siz2[i]); // 别忘了减去虚拟节点的个数
}

printf("%d", ans);
return 0;
}

2018 CCF NOIP Junior 题解