2018 CCF NOIP Junior 题解
标题统计
给定一个字符串, 统计其中除空格和换行符之外, 有多少个字符
输入只有一行, 包含: 大小写字母, 数字, 空格和最后的换行符
我们可以直接读入一行, 然后统计其中空格之外的字符总数
也可以循环读入单个字符直到换行符停止, 累加非空格字符的数量
也可以循环读入字符串直到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;
}
龙虎斗
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;
}
摆渡车
这道题目是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;
}
对称二叉树
整体思路是
求出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;
}
