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 題解