反思:

我考得最炸的一次

怎么說呢?簡單的兩個題0分,稍難(我還不敢說難,肯定又有人噴我)42分

前10分鐘看T1,不會,覺得不可做,完全不可做,把它跳了

最后10分鐘看T1,發現一個有點用的性質,仍然認為不可實現

0分

所以T1是什么樣的難題呢

即使暴力也有60分,但我楞沒想出來暴力怎么打

然后我就掛掉了

?t2又是什么樣難題

大多數人秒切一個小時切兩道,

但這次考試給了我很大啟迪,也正是這次考試我才開始使勁剛T1

其實大多數T1都是比較簡單的,并沒有想象中那么難,這次考試對我來說意義很大

(就在模擬測試21我也認為T1很難堅持剛其實T1還是很簡單的)

count

題解

一共有多少種方案可以把這棵樹分成大小相同的幾塊

題干簡潔明了,

性質:我們如果能分成大小相同全為$size$大小的幾塊,那么只有一種方案分成大小全為$size$

有了這條性質我們就可以愉快的打了

枚舉所有n的約數打了就$AC$了(還有不要暴力枚舉約數,先根號n求一下約數)

實現,假設當前我們發現這個子樹累計$size$達到了約數就剪掉這個枝條

若減不掉就累加到父親上,如果父親減不掉且$size$已經比當前枚舉約數大了,那么當前方案不可行,否則方案$++$

?

例如我們枚舉約數3,我們在3減不掉,5減不掉,累加到2,2判斷size大了所以不可行

bool dfs(ll x,ll pre,ll num){sz[x]=1;for(ll i=head[x];i;i=nxt[i]){ll y=ver[i];if(y==pre) continue;if(!dfs(y,x,num)) return 0;sz[x]+=sz[y];if(sz[x]>num) return 0;} // printf("sz=%lld \n",sz[x]);if(sz[x]==num) sz[x]=0;return 1; }

代碼

#include<bits/stdc++.h> using namespace std; #define ll int #define A 2999989 ll sz[A],ver[A],nxt[A],head[A]; ll ans=2,tot=1,n,m; vector<ll> woshishabi; void add(ll x,ll y){ver[++tot]=y,nxt[tot]=head[x],head[x]=tot; } inline ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return f*x; } bool dfs(ll x,ll pre,ll num){sz[x]=1;for(ll i=head[x];i;i=nxt[i]){ll y=ver[i];if(y==pre) continue;if(!dfs(y,x,num)) return 0;sz[x]+=sz[y];if(sz[x]>num) return 0;} // printf("sz=%lld \n",sz[x]);if(sz[x]==num) sz[x]=0;return 1; } int main(){n=read();for(ll i=1,a,b;i<n;i++){a=read(),b=read();add(a,b);add(b,a);}for(ll i=2;i<=sqrt(n);i++){if(n%i==0){if(i*i==n) woshishabi.push_back(i);elsewoshishabi.push_back(i),woshishabi.push_back(n/i);}}for(ll i=0;i<woshishabi.size();i++){if(dfs(1,0,woshishabi[i])){ans++;} // printf("=%lld ans=%lld\n",woshishabi[i],ans); }cout<<ans<<endl; }

dinner

題解

不錯的題意轉化

分成個數最少的環,每個環總權值最大的最小

最大的最小??

二分答案

一個很好的二分答案題,讓我明白了我們枚舉其實可以拿分塊優化一下

暴力應該都會打吧

枚舉圈的數量,這里講一下$check$

我采取的是首先找到一個圈,找到最左可以到達的值,以及到達最左后到達右面節點,這已經$1$個圈了

每次枚舉剩下的值,若當前符合直接返回,不符合最左指針$++$,右面指針跟著移動,進行操作知道最左達到$n+1$

這樣一般過不了(然而我暴力$nian$標算了)我打法玄學

while(now<=tim){tl--;now+=a[tl];}now-=a[tl],tl++;while(now<=tim){tr++;now+=a[tr];}now-=a[tr],tr--;//一個完美的閉合回路while(tl!=n+2){cnt=2;tot=0; // printf("tl=%lld tr=%lld \n",tl,tr);//除了當前滿足的tl,tr之外的圈的另一半for(LL j=tr+1;j<=tl+n-1;j++){if(tot>tim)tot=a[j],cnt++;if(cnt>m){cnt=m+10;break;}} // printf("cnt=%lld\n",cnt);if(cnt<=m)return 1;now-=a[tl];tl++;while(now<=tim){tr++;now+=a[tr];}now-=a[tr],tr--;}return 0; }

主要講剪枝

就一句話特別簡單

if(j+t<=tl+n-1&&sum[j+t]-sum[j-1]+tot<=tim){tot+=(sum[j+t]-sum[j-1]);j+=t;continue;}

能t加就加t,一句小的剪枝讓你從$T60$分到$100$分,從$3000$-->$200$(雖然我暴力跑了$100$)

方法簡單,

一定要掌握這種思想

代碼

#include<bits/stdc++.h> using namespace std; #define LL long long #define A 1010101 LL a[A],sum[A]; LL n,m,ans,avg,mx=-1,t; LL check(LL tim){LL now=0,tl=n+1,tr=n+1,tot,cnt=0;now=a[n+1]; // printf("now=%lld\n",now);while(now<=tim){tl--;now+=a[tl];}now-=a[tl],tl++;while(now<=tim){tr++;now+=a[tr];}now-=a[tr],tr--;//一個完美的閉合回路while(tl!=n+2){cnt=2;tot=0; // printf("tl=%lld tr=%lld \n",tl,tr);//除了當前滿足的tl,tr之外的圈的另一半for(LL j=tr+1;j<=tl+n-1;j++){if(j+t<=tl+n-1&&sum[j+t]-sum[j-1]+tot<=tim){tot+=(sum[j+t]-sum[j-1]);j+=t;continue;}tot+=a[j];if(tot>tim)tot=a[j],cnt++;if(cnt>m){cnt=m+10;break;}} // printf("cnt=%lld\n",cnt);if(cnt<=m)return 1;now-=a[tl];tl++;while(now<=tim){tr++;now+=a[tr];}now-=a[tr],tr--;}return 0; } int main(){scanf("%lld%lld",&n,&m);t=sqrt(n);for(LL i=1;i<=n;i++){scanf("%lld",&a[i]);a[i+n]=a[i];mx=max(mx,a[i]);}for(LL i=1;i<=2*n;i++)sum[i]=sum[i-1]+a[i];LL l=mx,r=sum[n];while(l<=r){LL mid=(l+r)>>1;if(check(mid)) r=mid-1,ans=mid;else l=mid+1;}printf("%lld\n",ans); }

chess

題解

知道了正解也難以實現打了$4$個小時,我最后還是頹了標程,然而剛看$10$秒就明白怎么做并用$10$分鐘$AC$

首先我們要掌握一種科技最短路計數

然而敵軍不能對方案造成影響,考慮縮邊

那么題解中說縮邊縮邊,怎么縮啊

我嘗試跑兩遍$spfa$(偽縮邊)然而只有$20$分

嘗試$tarjan$(偽縮邊)然而只有$0$分

嘗試對拍小點全對,大點全錯

好難實現,考慮每個點$dfs?$

能過?,能過最多每個點搜每個點一遍善用復雜度分析$2500^2$

那么$dfs$搜些什么,

既然敵軍不能對方案造成影響,遇到敵軍往下搜但不建邊,遇到空格return并且建邊

建單向邊,這樣我們就縮邊了

很巧妙不是嗎?

注意答案可能很大開0x7ffffffffffffffffffff

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define A 51000 ll head[A],nxt[A],ver[A],way[A],dis[A],G[51][51],mzz[51][51]; ll F[58][58]; ll qix,qiy,zhongx,zhongy; bool flag[A]; ll tot=0,n,m; ll id(ll x,ll y){return (x-1)*m+y; } void jb(ll x,ll y){//建邊 // printf("jbjbjbjbx=%lld y=%lld\n",x,y);nxt[++tot]=head[x],head[x]=tot,ver[tot]=y; } const ll nowx[9]={0,2,2,1,-1,-2,-2,1,-1}; const ll nowy[9]={0,1,-1,2,2,1,-1,-2,-2}; void dfs(ll root,ll x,ll y){G[x][y]=1; // printf("x=%lld y=%lld\n",x,y);for(ll i=1;i<=8;i++){ll x1=nowx[i]+x,y1=nowy[i]+y; // printf("x=%lld y=%lld x1=%lld y1=%lld\n",x,y,x1,y1);if(x1<1||x1>n||y1<1||y1>m||G[x1][y1]) continue;if(F[x1][y1]==1)dfs(root,x1,y1);else G[x1][y1]=1,jb(root,mzz[x1][y1]);} } /*void spfa(ll w){deque<ll>q;memset(dis,0x3f,sizeof(dis));memset(flag,0,sizeof(flag));dis[w]=0;q.push_back(w);while(!q.empty()){ll x=q.front();q.pop_front();flag[x]=0;for(ll i=head[x];i;i=nxt[i]){ll y=ver[i];if(dis[y]>dis[x]+edge[i]){if(edge[i]==0)choose[y]=x;dis[y]=dis[x]+edge[i]; // printf("x=%lld y=%lld dx=%lld dy=%lld\n",x,y,dis[x],dis[y]); // if(x==59||y==59){ // printf("***********\n"); // }if(!flag[y]){q.push_back(y);flag[y]=1;}}}} }*/ void spfa2(ll w){deque<ll>q;memset(dis,0x7f,sizeof(dis));memset(flag,0,sizeof(flag));dis[w]=0;q.push_back(w);while(!q.empty()){ll x=q.front();q.pop_front();flag[x]=0; // printf("x=%lld\n",x);for(ll i=head[x];i;i=nxt[i]){ll y=ver[i];if(dis[y]>dis[x]+1){way[y]=way[x];dis[y]=dis[x]+1;if(!flag[y]){q.push_back(y);flag[y]=1;}}else if(dis[y]==dis[x]+1){way[y]+=way[x];}}} } int main(){scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++){mzz[i][j]=id(i,j); // printf("mzz[%lld][%lld]=%lld\n",i,j,mzz[i][j]); }for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++){scanf("%lld",&F[i][j]); if(F[i][j]==3)qix=i,qiy=j;else if(F[i][j]==4)zhongx=i,zhongy=j;}for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++){if(F[i][j]==0||F[i][j]==3){memset(G,0,sizeof(G));dfs(mzz[i][j],i,j);}} /* for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++){ if(F[i][j]==2) continue;for(ll k=1;k<=8;k++){ll x1=i+nowx[k],y1=j+nowy[k];ll idpre=id(i,j),idnow=id(x1,y1);if(x1<1||x1>n||y1<1||y1>m) continue;if(F[x1][y1]==2) continue;if(!G[idpre][idnow]){if(F[x1][y1]==1||F[x1][y1]==4)jb(idpre,idnow,0),G[idpre][idnow]=1;elsejb(idpre,idnow,1),G[idpre][idnow]=1;}}if(F[i][j]==3)qix=i,qiy=j;else if(F[i][j]==4)zhongx=i,zhongy=j;} */ way[mzz[qix][qiy]]=1; // printf("%lld\n%lld\n",dis[id(zhongx,zhongy)],way[id(zhongx,zhongy)]); spfa2(mzz[qix][qiy]);if(dis[mzz[zhongx][zhongy]]>1e8) printf("-1\n");elseprintf("%lld\n%lld\n",dis[mzz[zhongx][zhongy]]-1,way[mzz[zhongx][zhongy]]); }

?

轉載于:https://www.cnblogs.com/znsbc-13/p/11366081.html

總結

以上是生活随笔為你收集整理的NOIP模拟测试19「count·dinner·chess」的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。