比完小結(jié)

今年的題目出的有點(diǎn)詭異，難度跨越有點(diǎn)大

入門 to 普及- to(注意：前方東非大裂谷，請(qǐng)小心慢行) 提高+/省選- to 提高+/省選-

不過實(shí)際上沒有這么難

T3、T4 一個(gè)DP 一個(gè)暴力（雖然不是正解） 也就可以過了

扯入正題

T1 標(biāo)題統(tǒng)計(jì)

這道題十分的水，沒有什么技術(shù)含量，隨便怎么搞都可以過。

下面是我直接放代碼了。。。

#include<bits/stdc++.h> using namespace std;char t; int ans(0);int main(){freopen( "title.in", "r", stdin );freopen( "title.out", "w", stdout );while( ( t = getchar() ) != EOF )if ( t != ' ' && t != '\n' && t != '\r' ) ans++;printf( "%d", ans ); return 0; }

T2 龍虎斗

這道題沒話說，只是題目長了點(diǎn)，好好理解一下也是不難的。
我們可以預(yù)處理出兩邊陣營的氣勢(shì)和（別忘了加上“某一刻天降神兵”）然后枚舉每個(gè)兵營，把你的兵加進(jìn)去，算出之后兩個(gè)陣營最終的氣勢(shì)，然后選出氣勢(shì)之差絕對(duì)值最小的哪個(gè)陣營就可以了。
C++內(nèi)置的函數(shù)abs由于老是忘掉是什么類型的，所以干脆手打算了。。。
話不多說，直接上代碼（普及- 及以下難度的不用具體講吧？）。還有注意要開 long long。（死了也別忘記）據(jù)說沒開long long只能得70左右。

#include<bits/stdc++.h> using namespace std;typedef long long LL;LL n, m, p1, s1, s2; LL s[166666]; LL L, R; LL ans(-1), q(0x7f7f7f7f7f7f7f7f);LL Abs( LL x ){return x >= 0 ? x : -x; }int main(){freopen( "fight.in", "r", stdin );freopen( "fight.out", "w", stdout );scanf( "%lld", &n );for ( int i = 1; i <= n; ++i ) scanf( "%lld", &s[i] );scanf( "%lld%lld%lld%lld", &m, &p1, &s1, &s2 );s[p1] += s1;for ( int i = 1; i <= n; ++i ){if ( i < m ) L += ( m - i ) * s[i];if ( i > m ) R += ( i - m ) * s[i];}for ( int i = 1; i <= n; ++i ){LL tL(L), tR(R), c;if ( i < m ) tL += ( m - i ) * s2;if ( i > m ) tR += ( i - m ) * s2;c = Abs( tL - tR );if ( c < q ) ans = i, q = c;}printf( "%lld\n", ans );return 0; }

T3 擺渡車

看這道題的時(shí)候，我（相信大家也是這樣）最先想到的是貪心，但是從數(shù)據(jù)范圍可以看出，如果是貪心題，數(shù)據(jù)范圍不會(huì)那么小（相信NOIP不會(huì)和Luogu月賽一樣，2018 11月月賽 搞個(gè)幾百大小數(shù)據(jù)騙我們用DP，結(jié)果是貪心）。有些人會(huì)想(including me)，是不是在有人到達(dá)時(shí)才能發(fā)車呢？？？沒想清楚就下手的話，就會(huì)浪費(fèi)好多時(shí)間。仔細(xì)想想，很容易發(fā)現(xiàn)不一定要有人到達(dá)時(shí)發(fā)車，比如有時(shí)候，bus一回來，有個(gè)人等了2分鐘，后面那個(gè)人還有INF(hh) min 才會(huì)來，如果有人到達(dá)時(shí)才能發(fā)車，那么bus將在INF min后才等到一個(gè)人，原來等了2分鐘的那個(gè)人與司機(jī)等得花都謝了，所以這時(shí)候肯定是一回來就發(fā)車，雖然沒有人剛好到達(dá)。

當(dāng)然，我們先排序。（DP，從排序做起）。

我們用f[i]表示i min 時(shí)發(fā)一輛車，ps[i]表示1 ~ i 的人數(shù)，ts[i]表示1 ~ i 所有人開始等的時(shí)間之和。
設(shè)上一次發(fā)車是jmin時(shí)，那么j min及以前的人都已經(jīng)滾粗了，我們要求j + 1 ~ i所有人等待時(shí)間之和。
等待時(shí)間之和為Σ(i - t[k]) 可以簡化為 i * 人數(shù) - Σ(t[k])， 人數(shù)、Σ(t[k])可以用前綴和來維護(hù)（即前面提到的ps、ts數(shù)組）。
然后就可以得到轉(zhuǎn)移方程——

( 0 <= i < m ) f[i] = ps[i] * i - ts[i] ( i > m ) f[i] = min{ f[j] + ( ps[i] - ps[j] ) * i - ( ts[i] - ts[j] ) }( 0 <= j <= i - m )

藍(lán)鵝，這樣的復(fù)雜度達(dá)到了O(MAXT ^ 2)!!!這是遠(yuǎn)遠(yuǎn)不行的。所以我們要進(jìn)行優(yōu)化~

優(yōu)化I

對(duì)于兩個(gè)人a、b( ta < tb,b = a + 1) 如果 tb - ta >= 2 * m 可以從中間斷開

如果用work( l, r )表示對(duì)l、r區(qū)間范圍內(nèi)進(jìn)行一次DP work( ls, ta ), ls = tb;

很容易解釋，因?yàn)槿绻麅蓚€(gè)人之間時(shí)間間隔不小于2m的話，他們是完全可以分兩趟車走的。因?yàn)閍最遲走的時(shí)間為ta + m - 1，車回來的時(shí)間為ta + 2m - 1,如果tb >= ta + 2m - 1，剛好可以直接粗發(fā)QAQ。(或者理解為b可以作為起點(diǎn))

優(yōu)化II

i - 2* m + 1 <= j <= i - m

不難理解，每兩趟車之間間隔不會(huì)超過或等于2m（否則中間為什么不再來一趟呢？？？）

實(shí)際上，這已經(jīng)滿足題目的時(shí)間復(fù)雜度要求，但是還有一個(gè)亂搞優(yōu)化。(在考場(chǎng)上想到的)

優(yōu)化III

if ps[i] == ps[i - 1]

? j = i - m

解釋這個(gè)優(yōu)化要從貪心的角度考慮。

回到原來那個(gè)問題:是不是在有人到達(dá)時(shí)才能發(fā)車呢？？？

前面已經(jīng)解釋了答案是否定的。這從一個(gè)側(cè)面告訴我們，如果不是在有人到達(dá)時(shí)才發(fā)車，肯定是由于車來不及回來。

所以，在最優(yōu)方案中，那趟車一定會(huì)在剛好回來時(shí)發(fā)車。也就是說，i min時(shí)車剛好回來，上一次發(fā)車是在 i - m min時(shí)。

真是玄之又玄。

最終的程序不是在考場(chǎng)中寫的，因?yàn)榭紙?chǎng)中 優(yōu)化I 采用了路徑壓縮的方法，但是出現(xiàn)一些問題，被卡掉20分。

算法的復(fù)雜度也是在O(nm)級(jí)別，但常數(shù)要比Sooke大佬的代碼大一些。

然后上代碼！（雖然不是最好的解，但87ms也湊合吧。）

#include<bits/stdc++.h> using namespace std; #define MAXN 505 #define MAXM 205int n, m, mm, ans; int t[MAXN], ps[MAXM * MAXN], ts[MAXM * MAXN]; int f[MAXM * MAXN];void work( int l, int r ){memset( ps, 0, sizeof ps ), memset( ts, 0, sizeof ts ), memset( f, 0, sizeof f );for ( int i = l + 1; i <= r; ++i ){t[i] -= t[l]; ps[t[i]]++; ts[t[i]] += t[i];}t[l] = 0; ps[0]++;for ( int i = 1; i < t[r] + m; ++i ) ps[i] += ps[i - 1], ts[i] += ts[i - 1];for ( int i = 1; i < t[r] + m; ++i ){if ( i < m ){ f[i] = ps[i] * i - ts[i]; continue; }if ( ps[i] == ps[i - 1] ){ f[i] = f[i - m] + ( ps[i] - ps[i - m] ) * i - ( ts[i] - ts[i - m] ); continue; }f[i] = INT_MAX;for ( int j = max( 0, i - mm + 1 ); j <= i - m; ++j ) f[i] = min( f[i], f[j] + ( ps[i] - ps[j] ) * i - ( ts[i] - ts[j] ) );}int cur(INT_MAX);for ( int i = t[r]; i < t[r] + m; ++i ) cur = min( cur, f[i] );ans += cur; }int main(){scanf( "%d%d", &n, &m ); mm = m << 1;for ( int i = 1; i <= n; ++i ) scanf( "%d", &t[i] );sort( t + 1, t + n + 1 );int ls(1);for ( int i = 1; i < n; ++i )if ( t[i + 1] - t[i] >= mm ) work( ls, i ), ls = i + 1;work( ls, n );printf( "%d\n", ans );return 0; }

非常抱歉，雖然這個(gè)代碼通過了一些民間數(shù)據(jù)，但CCF的數(shù)據(jù)實(shí)在太強(qiáng)，把我原來的代碼卡到了80分，以上代碼70分，具體錯(cuò)誤還不清楚，所以就暫時(shí)留坑QAQ。
updata 2018/11/30 23:03: 總算填好坑了QAQ

T4 對(duì)稱二叉樹

這道題我也不知道正解是什么。我直接暴力+剪枝也跑過了所有測(cè)試點(diǎn)（數(shù)據(jù)太水？）

我們可以考慮當(dāng)將一棵樹所有節(jié)點(diǎn)的左右子樹交換，那么搜索的順序左變右，右變左。

即原來對(duì)于節(jié)點(diǎn)P，從根節(jié)點(diǎn)到P的路徑是左右左左右，那么反轉(zhuǎn)后根節(jié)點(diǎn)到P'的位置的路徑就是右左右右左。

我們直接枚舉每個(gè)子樹的根節(jié)點(diǎn)，把原來的點(diǎn)、翻轉(zhuǎn)后的點(diǎn)一一對(duì)應(yīng)就可以了。

實(shí)現(xiàn)起來也不難。注意加點(diǎn)剪枝（不解釋剪枝原理了）。

#include<bits/stdc++.h> using namespace std;const int MAXN = 1000000 + 0xac;//AC萬歲！！！int n, v[MAXN], d[MAXN], s[MAXN]; unsigned long long M1[MAXN], M2[MAXN], M3[MAXN]; int L[MAXN], R[MAXN];void DFS( int x, int dep ){s[x] = 1; M1[x] = v[x]; M2[x] = v[x]; M3[x] = dep * v[x];if ( L[x] != -1 ) DFS( L[x], dep + 1 ), s[x] += s[L[x]], M1[x] *= M1[L[x]], M2[x] += M2[L[x]], M3[x] += M3[L[x]];d[x] = dep;if ( R[x] != -1 ) DFS( R[x], dep + 1 ), s[x] += s[R[x]], M1[x] *= M1[R[x]], M2[x] += M2[R[x]], M3[x] += M3[R[x]]; }bool check( int x, int y ){if ( v[x] != v[y] || s[x] != s[y] || M1[x] != M1[y] || M2[x] != M2[y] || M3[x] != M3[y] ) return 0;if ( L[x] > 0 || R[y] > 0 ){if ( L[x] < 0 || R[y] < 0 ) return 0;if ( !check( L[x], R[y] ) ) return 0;}if ( R[x] > 0 || L[y] > 0 ){if ( R[x] < 0 || L[y] < 0 ) return 0;if ( !check( R[x], L[y] ) ) return 0;}return 1; }bool cmp( int x, int y ){return s[x] > s[y]; }int main(){freopen( "tree.in", "r", stdin );freopen( "tree.out", "w", stdout );scanf( "%d", &n );for ( int i = 1; i <= n; ++i ) scanf( "%d", &v[i] );for ( int i = 1; i <= n; ++i ) scanf( "%d%d", &L[i], &R[i] );DFS( 1, 1 );int ans(1);for ( int i = 1; i <= n; ++i )if ( s[i] > ans && check( i, i ) ) ans = max( ans, s[i] );printf( "%d\n", ans );return 0; }

鳴謝

感謝葉康杰童鞋的審核。
感謝CCF提供的數(shù)據(jù)（尤其是把我T3卡掉了的那些QAQ）。

轉(zhuǎn)載于:https://www.cnblogs.com/louhancheng/p/10023188.html

總結(jié)

以上是生活随笔為你收集整理的NOIP 2018 普及组 解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。