并不对劲的noip2018
day1
road
題意
有n（\(n \leq 10^5\)）個數(shù)\(a_1,a_2,...,a_n\)排成一排，每次可以選擇一段大于零的數(shù)減一，問最少幾次把所有數(shù)減為0。
題解
先想到一個簡單的策略：當處理到區(qū)間\([l,r]\)時，找出其中的最小值出現(xiàn)的位置\(k\)，對這個區(qū)間進行\(a_k\)次區(qū)間減一，再分別處理\([l,k-1]\)和\([k+1,r]\)。
但是區(qū)間\([l,r]\)要是有很多個最小值，出現(xiàn)位置為\(k_1,k_2,\)...\(,k_p\)，該怎么辦？想必是沒什么影響的。對這個區(qū)間進行最小值次區(qū)間減一后，\(k_1,k_2,\)...\(,k_p\)上的數(shù)都變成0，選其中的哪一個作為斷點都沒什么區(qū)別。
要想維護區(qū)間最值，用st表就行了。
代碼
#include<algorithm> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<iomanip> #include<iostream> #include<map> #include<stack> #include<vector> #include<queue> #define rep(i,x,y) for(int i=(x);i<=(y);++i) #define dwn(i,x,y) for(int i=(x);i>=(y);--i) #define maxn 100010 using namespace std; int read() {int x=0,f=1;char ch=getchar();while(!isdigit(ch)&&ch!='-')ch=getchar();if(ch=='-')f=-1,ch=getchar();while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x*f; } void write(int x) {if(x==0){putchar('0'),putchar('\n');return;}if(x<0){putchar('-'),x=-x;}char ch[20];int f=0;while(x)ch[++f]=x%10+'0',x/=10;while(f)putchar(ch[f--]);putchar('\n'); } int n,d[maxn],st[20][maxn],lg[maxn],ans=0; int MIN(int l,int r) {int len=r-l+1;return d[st[lg[len]][l]]<=d[st[lg[len]][r-(1<<lg[len])+1]]?st[lg[len]][l]:st[lg[len]][r-(1<<lg[len])+1]; } void work(int l,int r,int lst) {int minx=MIN(l,r);ans+=(d[minx]-lst);if(l<=minx-1)work(l,minx-1,d[minx]);if(minx+1<=r)work(minx+1,r,d[minx]);return; } int main() {n=read();rep(i,1,n)d[i]=read(),st[0][i]=i;lg[0]=-1;rep(i,1,n)lg[i]=lg[i>>1]+1;rep(k,1,lg[n])for(int i=1;i+(1<<k)-1<=n;i++)st[k][i]=d[st[k-1][i]]<=d[st[k-1][i+(1<<(k-1))]]?st[k-1][i]:st[k-1][i+(1<<(k-1))];work(1,n,0);write(ans);return 0; }money
題意
有\(n\)（\(n\leq 100\)）個數(shù)\(a_1,a_2,\)...\(,a_n\)(\(\forall i\in[1,n],a_i\leq25000\))。
定義“湊出”是：當存在一個\(n\)個數(shù)的數(shù)列\(t_1,t_2,\)...\(,t_n\)使\(\sum_{i=1}^n a_i*t_i \space= k\)時，k能被這n個數(shù)湊出。
求最小的數(shù)\(m\)，使存在m個數(shù)\(b_1,\)...\(,b_m\)，這些數(shù)能湊出\(a_1,\)...\(,a_n\)能湊出的所有數(shù)，湊不出\(a_1,\)...\(,a_n\)湊不出的所有數(shù)。
共\(T\)(\(T\leq20\))組輸入。
題解
把這\(n\)個數(shù)中所有能被\(n\)個數(shù)中的其它數(shù)湊出的刪掉。
正確性：假設數(shù)\(x\)能被\(n\)個數(shù)中的其它數(shù)湊出，那么\(x\)能湊出的數(shù)一定能被湊出\(x\)的數(shù)湊出，刪掉\(x\)后，原來能湊出的數(shù)還能被湊出。
最優(yōu)性：那么這個可以用反證法來證明，假設存在一種刪去了p個數(shù)，又添加了q（q<p）個數(shù)的方法比只刪數(shù)更優(yōu)。為了讓方法更優(yōu)，添加的數(shù)一定不能被未刪除的數(shù)湊出。但是，這樣添加的數(shù)就是原來湊不出的數(shù)，現(xiàn)在能湊出了，與題意不符。所以添加數(shù)不會使答案更優(yōu)，只刪掉能被湊出的數(shù)就行了。
需要判斷每個數(shù)能否被湊出，這是個完全背包問題。
代碼
#include<algorithm> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<iomanip> #include<iostream> #include<map> #include<stack> #include<vector> #include<queue> #define rep(i,x,y) for(int i=(x);i<=(y);++i) #define dwn(i,x,y) for(int i=(x);i>=(y);--i) #define maxk 25010 #define maxn 110 using namespace std; int read() {int x=0,f=1;char ch=getchar();while(!isdigit(ch)&&ch!='-')ch=getchar();if(ch=='-')f=-1,ch=getchar();while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x*f; } void write(int x) {if(x==0){putchar('0'),putchar('\n');return;}if(x<0){putchar('-'),x=-x;}char ch[20];int f=0;while(x)ch[++f]=x%10+'0',x/=10;while(f)putchar(ch[f--]);putchar('\n'); } int yes[maxk],t,maxpos,a[maxn],n,ans,maxlim; int main() {t=read();while(t--){n=read(),ans=n;maxlim=maxpos=0;rep(i,1,n)a[i]=read(),maxlim=max(maxlim,a[i]);rep(i,1,maxlim)yes[i]=0;yes[0]=1;sort(a+1,a+n+1);rep(i,1,n){if(yes[a[i]]){ans--;continue;}rep(j,0,maxpos){if(j+a[i]>maxlim)break;if(yes[j])yes[j+a[i]]=1,maxpos=max(maxpos,j+a[i]);}}write(ans);}return 0; }track
題意
有一棵有\(n\)（\(n\leq5*10^4\)）的樹，有邊權。
要把這棵樹拆成\(m\)條鏈，鏈之間可以有公共點，但不能有公共邊。
求一種拆分方案，使邊權和最小的鏈邊權和最大。
題解
“最大值最小”顯然是需要二分的，然后就是判斷這棵樹能否拆成不少于m條邊權和大于等于k的鏈。
這樣問題就轉換成：對于每個點，選若干對兒子，使得每一對中，兩個兒子向下連的直鏈長度，加上該點到兩個兒子的邊大于等于\(k\)，在剩下兒子中選擇向下的直鏈長度加該點到這個兒子的邊長度最長的作為該點向下的直鏈。需要找出一種方法使選出的兒子對的個數(shù)盡可能多，在此基礎上，該點向下的直鏈長度盡可能長。
\(l_i\)表示在處理完\(i\)的子樹后，點\(i\)向下連的鏈最長有多長。
在計算完點\(u\)的所有兒子\(v_i\)的\(l_{v_i}\)后，將所有兒子按\(l_{v_i}+i到這個兒子的距離\)排序，第\(j\)個記作\(a_j\)。
這樣問題就變成在單調不降數(shù)列\(a_1,\)...\(,a_p\)中，選出若干對數(shù)，同一個數(shù)只能被選一次，使每一對的和大于等于\(k\)，選出的數(shù)對的個數(shù)盡可能多，在此基礎上，剩下的數(shù)中最大的數(shù)盡可能大。
如果只用考慮數(shù)對個數(shù)最多，就可以這樣：找出位置\(q\)使\(k\leq a_q+a_{q+1}\)且\(k\geq a_{q-1}+a_q\)，那么對于小于\(a_q\)的數(shù)，只有在大于\(a_q\)的數(shù)中才能找到與它相加大于\(k\)的。那么就可以從\(a_{q-1}\)到\(a_1\)，判斷是否存在\(i\)使\(a_i\)未被選且\(當前數(shù)+a_i\geq k\)，如果有，就取符合條件的最小的\(a_i\)。判斷完所有小于\(a_q\)的數(shù)后，未被選的大于等于\(a_q\)的數(shù)直接兩兩配對就行了。以上過程的時間復雜度是\(O(n)\)的，可以維護一個指針\(i\)，初始位置為\(q\)，每當\(當前數(shù)+a_i\leq k\)時，右移\(i\)，因為隨著當前數(shù)減小，符合條件的與它配對的數(shù)是不斷增大的。
那要是要考慮在選出數(shù)對個數(shù)最多的基礎上，剩下的數(shù)的最大值盡可能大呢？看上去沒有簡單的貪心策略。先有個暴力的想法：枚舉最后剩下的數(shù)中的最大值，求刪掉枚舉的數(shù)后的數(shù)列中最多能選出多少對。會發(fā)現(xiàn)刪掉較大的數(shù)后的答案肯定不會比刪掉較小的數(shù)的答案更大，也就是有單調性。那么只要先二分出剩下的數(shù)的最大值，再貪心求出刪掉該數(shù)后最多能湊出幾對就行了。
代碼
#include<algorithm> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<iomanip> #include<iostream> #include<map> #include<stack> #include<vector> #include<queue> #define rep(i,x,y) for(int i=(x);i<=(y);++i) #define dwn(i,x,y) for(int i=(x);i>=(y);--i) #define maxn 50010 #define maxm 100010 using namespace std; int read() {int x=0,f=1;char ch=getchar();while(!isdigit(ch)&&ch!='-')ch=getchar();if(ch=='-')f=-1,ch=getchar();while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x*f; } void write(int x) {if(x==0){putchar('0'),putchar('\n');return;}if(x<0){putchar('-'),x=-x;}char ch[20];int f=0;while(x)ch[++f]=x%10+'0',x/=10;while(f)putchar(ch[f--]);putchar('\n'); } int num,ans,mid,n,m,fa[maxn],fir[maxn],nxt[maxm],v[maxm],w[maxm],sons; int tofa[maxn],son[maxn],tmp[maxn],tn,mk[maxn],len[maxn],L=10001,R,cnt,tmpnum; void ade(int u1,int v1,int w1){v[cnt]=v1,w[cnt]=w1,nxt[cnt]=fir[u1],fir[u1]=cnt++;} int getx(int u){return len[u]+tofa[u];} bool cmp(int x,int y){return getx(x)<getx(y);} void check(int lim) {tmpnum=tn=0;int pos=0;rep(i,1,sons)if(i!=lim)tmp[++tn]=son[i];rep(i,1,tn-1)if(getx(tmp[i])+getx(tmp[i+1])>=mid){pos=i;break;}if(pos==0){return;}else{rep(i,1,tn)mk[i]=0;int b=pos+1,c=0;dwn(a,pos,1){if(b>tn)break;while(b<tn&&getx(tmp[a])+getx(tmp[b])<mid)b++;if(getx(tmp[a])+getx(tmp[b])>=mid)mk[a]=mk[b]=1,b++,tmpnum++;else break;} rep(i,pos+1,tn)if(!mk[i])c++;tmpnum+=c/2;} } void getans(int u) {for(int k=fir[u];k!=-1;k=nxt[k])if(v[k]!=fa[u]){getans(v[k]);}sons=0;for(int k=fir[u];k!=-1;k=nxt[k])if(v[k]!=fa[u]){if(getx(v[k])>=mid)num++;else son[++sons]=v[k];}if(sons==0){len[u]=0;return;}sort(son+1,son+sons+1,cmp);int pos=0;rep(i,1,sons-1)if(getx(son[i])+getx(son[i+1])>=mid){pos=i;break;}if(pos==0){len[u]=getx(son[sons]);return;}else{int l=1,r=sons,ansnum=0,anslen=0;check(0);ansnum=tmpnum;while (l<=r){int mi=(l+r)>>1;check(mi);if(tmpnum>ansnum||(tmpnum==ansnum&&getx(son[mi])>anslen))ansnum=tmpnum,anslen=getx(son[mi]),l=mi+1;else r=mi-1; }num+=ansnum,len[u]=anslen; }return; } int check() {num=0;rep(i,1,n)len[i]=0;getans(1);if(num>=m)return 1;else return 0; } void getfa(int u) {for(int k=fir[u];k!=-1;k=nxt[k])if(v[k]!=fa[u])tofa[v[k]]=w[k],fa[v[k]]=u,getfa(v[k]); } int main() {n=read(),m=read();memset(fir,-1,sizeof(fir));rep(i,1,n-1){int x=read(),y=read(),z=read();ade(x,y,z),ade(y,x,z);L=min(L,z),R+=z;}getfa(1);while(L<=R){mid=((L+R)>>1);int f=check();if(f)ans=max(mid,ans),L=mid+1;else R=mid-1;}write(ans);fclose(stdout);return 0; }day2
travel
題意
有一棵有\(n\)(\(n\leq 5000\))個點的樹或基環(huán)外向樹。
每個點只能走一次，求字典序最小的DFS序。
題解
如果是樹，就貪心地先走編號更小的兒子。
有環(huán)的話，就枚舉刪掉環(huán)上的哪條邊，變成樹。
需要注意的是，要在枚舉刪邊之前將每個點的兒子排序。要不然\(O(n^2 log n)\)會被卡。
代碼
#include<algorithm> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<iomanip> #include<iostream> #include<map> #include<queue> #include<set> #include<stack> #include<vector> #define rep(i,x,y) for(register int i=(x);i<=(y);++i) #define dwn(i,x,y) for(register int i=(x);i>=(y);--i) #define maxn 5010 using namespace std; int read() {int x=0,f=1;char ch=getchar();while(!isdigit(ch)&&ch!='-')ch=getchar();if(ch=='-')f=-1,ch=getchar();while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x*f; } void write(int x) {if(x==0){putchar('0'),putchar(' ');return;}int f=0;char ch[20];if(x<0)putchar('-'),x=-x;while(x)ch[++f]=x%10+'0',x/=10;while(f)putchar(ch[f--]);putchar(' ');return; } int to[maxn][maxn],tl[maxn],qx[maxn],qy[maxn],num,n,m,nox,noy,vis[maxn],ans[maxn],tmp[maxn],tmpn,cntq,yes; void work(int u) {vis[u]=1,tmp[++tmpn]=u;rep(k,1,tl[u])if(!vis[to[u][k]]&&(u!=nox||to[u][k]!=noy)&&(u!=noy||to[u][k]!=nox))work(to[u][k]); } void getcir(int u,int fa) {vis[u]=1;rep(k,1,tl[u]){if(to[u][k]!=fa){if(vis[to[u][k]]){yes=1;qx[++cntq]=u,qy[cntq]=to[u][k];return;}else{getcir(to[u][k],u);if(yes==1){if(u==qy[1])yes=-1;qx[++cntq]=u,qy[cntq]=to[u][k];return; }if(yes)return;}}} } void upd() {if(ans[1]!=0){rep(i,1,n){if(tmp[i]<ans[i])break;if(tmp[i]>ans[i])return;}}rep(i,1,n)ans[i]=tmp[i];return; } int main() {n=read(),m=read();rep(i,1,m){int x=read(),y=read();to[x][++tl[x]]=y,to[y][++tl[y]]=x;}rep(i,1,n)sort(to[i]+1,to[i]+tl[i]+1);if(n-1==m){work(1);rep(i,1,n)write(tmp[i]);return 0;}getcir(1,0);rep(i,1,cntq){nox=qx[i],noy=qy[i];tmpn=0;rep(i,1,n)vis[i]=0;work(1);upd();}rep(i,1,n)write(ans[i]);return 0; }game
自閉了，不寫。
defence
自閉了，不寫。
總結
爆零就完事兒了
我記得有一次我接了個任務：砍五只大野豬
我想：我都是個上位獵人了，單挑火龍一家、兩只雷狼都不帶掉血的，五只大野豬算什么？
于是拿著古結云大劍，啥都沒穿，啥都沒拿就去了
結果被秋名山豬神安排得明明白白的，雖然完成了，但是過程不太愉快
可能有一些方面是因為輕敵，但主要還是走位不夠靈活、預判不夠精準及時、對地形的運用不夠好導致的
活用道具、合理配置裝備，確實是比較重要的
但要想在技術上更進一步，就必須嘗試脫離這些東西，只靠自己的腦子和手戰(zhàn)斗
在這種情況下能夠通關后，也該嘗試著在通關速度上更進一步，或者用不常使用的武器（大劍、片手以外的所有武器。。。）通關
\(\color{white}{\text{事實上，這個任務上位獵人拿腳玩都沒問題……所以，你知道我只是在比喻，對吧？}}\)
我什么時候才能成為能裸裝零針迅龍的大劍使呢？
轉載于:https://www.cnblogs.com/xzyf/p/9997668.html
總結
以上是生活随笔為你收集整理的并不对劲的noip2018的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
