賣書

?

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 1000010 using namespace std; int n,a[maxn],cnt1,cnt2; int qread(){int i=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch<='9'&&ch>='0'){i=i*10+ch-'0';ch=getchar();}return i; } int main(){freopen("book.in","r",stdin);freopen("book.out","w",stdout); // freopen("Cola.txt","r",stdin);scanf("%d",&n);for(int i=1;i<=n;i++)a[i]=qread();for(int i=1;i<=n;i++){if(a[i]==5)cnt1++;if(a[i]==10){if(cnt1==0){puts("NO");return 0;}else {cnt2++;cnt1--;}}if(a[i]==20){if(cnt1==0||(cnt2==0&&cnt1<3)){puts("NO");return 0;}if(cnt2){cnt2--;cnt1--;}else{cnt1-=3;}}}puts("YES");return 0; } 100分 貪心

?

?

?

寫代碼

?

#include<iostream> #include<cstdio> #include<cstring> #define maxn 1000010 using namespace std; int n,a[maxn],s1[maxn],s2[maxn],top1,top2,m,sid1[maxn],sid2[maxn],b[maxn]; bool ex[maxn]; void out(){for(int i=1;i<=n;i++){if(b[i]==1)printf("+%d ",a[i]);else printf("-%d ",a[i]);} } int main(){freopen("program.in","r",stdin);freopen("program.out","w",stdout); // freopen("Cola.txt","r",stdin);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);scanf("%d",&m);int x;for(int i=1;i<=m;i++){scanf("%d",&x);ex[x]=1;}for(int i=1;i<=n;i++){if(ex[i]){top2+=1;s2[top2]=a[i];b[i]=-1;sid2[top2]=i;while(top2){if(s2[top2]==s1[top1]){b[sid2[top2]]=-1;b[sid1[top1]]=1;top1-=1;top2-=1;}else{sid2[top2+1]=sid1[top1];top2+=1;s2[top2]=s1[top1];top1-=1;}if(top1<0){puts("NO");return 0;}}}else{top1+=1;s1[top1]=a[i];sid1[top1]=i;}}if(top1==0&&top2==0){out();return 0;}while(top1){s2[++top2]=s1[top1];sid2[top2]=sid1[top1];top1--;while(top2){if(s2[top2]==s1[top1]){b[sid2[top2]]=-1;b[sid1[top1]]=1;top1--;top2--;}else{sid2[top2+1]=sid1[top1];s2[++top2]=s1[top1--];}if(top1<0){puts("NO");return 0;}}}out();return 0; } 100分 括號匹配

?

?

?

?

?

迷宮

?

#include<iostream> #include<cstdio> #include<vector> #define maxn 110 using namespace std; int n,m,num,head[maxn],q,s,t,st[maxn],top; struct node{int to,pre,v; }e[maxn*maxn*5]; void Insert(int from,int to,int v){e[++num].to=to;e[num].v=v;e[num].pre=head[from];head[from]=num; } bool vis[maxn],flag; void dfs(int now){if(now==t&&top==0){flag=1;return;}if(flag)return;vector<int>zu;for(int i=1;i<=top;i++)zu.push_back(st[i]);for(int i=head[now];i;i=e[i].pre){int to=e[i].to;if(vis[to])continue;else{vis[to]=1;if(e[i].v==0){dfs(to);top=0;for(int j=0;j<zu.size();j++)st[++top]=zu[j];vis[to]=0;continue;}for(int j=1;j<=10;j+=2){if(e[i].v>0){for(int k=1;k<=j;k++){top=top+1;st[top]=e[i].v;}dfs(to);if(flag)return;top=0;for(int k=0;k<zu.size();k++)top=top+1,st[top]=zu[k];}if(e[i].v<0){top-=j-1;if(st[top]!=-e[i].v||top<1)break;else top-=1;dfs(to);top=0;for(int k=0;k<zu.size();k++)st[++top]=zu[k];}}vis[to]=0;}} } int main(){freopen("maze.in","r",stdin);freopen("maze.out","w",stdout); // freopen("Cola.txt","r",stdin);scanf("%d%d",&n,&m);int x,y,z;for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);Insert(x,y,z);Insert(y,x,z);}scanf("%d",&q);while(q--){flag=0;top=0;scanf("%d%d",&s,&t);vis[s]=1;dfs(s);vis[s]=1;if(flag)puts("YES");else puts("NO");}return 0; } 5分 暴力

?

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> using namespace std; int n,m,g[105][105][40],q[105*105*40][3],t,x,y,z; int main(){ // freopen("maze.in","r",stdin);freopen("maze.out","w",stdout);freopen("maze20.in","r",stdin);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);if(z!=0){if(z<0)z=abs(z);else z+=10;g[x][y][z]=1;g[y][x][z]=1;}else{g[x][y][z]=1;g[y][x][z]=1;t++;q[t][0]=x;q[t][1]=y;q[t][2]=0;t++;q[t][0]=y;q[t][1]=x;q[t][2]=0;}}for(int i=1;i<=n;i++){g[i][i][0]=1;t++;q[t][0]=i;q[t][1]=i;q[t][2]=0;}for(int s=1;s<=t;s++){int x=q[s][0],y=q[s][1],sta=q[s][2];if(sta!=0){for(int i=1;i<=n;i++){if(g[i][x][sta-10]==1){if(g[i][y][0]==0){g[i][y][0]=1;t++;q[t][0]=i;q[t][1]=y;q[t][2]=0;}}}}else{for(int i=1;i<=n;i++){if(g[i][x][0]==1&&g[i][y][0]==0){g[i][y][0]=1;t++;q[t][0]=i;q[t][1]=y;q[t][2]=0;}if(g[y][i][0]==1&&g[x][i][0]==0){g[x][i][0]=1;t++;q[t][0]=x;q[t][1]=i;q[t][2]=0;}for(int j=1;j<=10;j++){if(g[y][i][j]==1&&g[x][i][j+20]==0){g[x][i][j+20]=1;t++;q[t][0]=x;q[t][1]=i;q[t][2]=j+20;}}}}}int tt=0;scanf("%d",&tt);for(;tt;tt--){scanf("%d%d",&x,&y);if(g[x][y][0]==1)puts("YES");else puts("NO");} } 100分 動態規劃

?

?

?

?

預計得分100+80+0 實際得分100+100+5 T1較簡單，是以前做過的原題。T2看到函數遞歸就覺得應該和棧有關系，仔細研究，這不就是個括號序列嗎，一開始以為要用雙向鏈表，后來發現加個數組記錄一下id，再加一個棧模擬退棧就好了，雖然和標解不太一樣，但是A了。T3我思索良久，想過建分層圖，但復雜度太高，正確性也很玄學，所以就寫了個dfs，才搜了5分 今天的題都是關于棧的，發揮的還好，但我覺得T3的dfs應該再優化一下，盡量拿到更多部分分 小結

?

轉載于:https://www.cnblogs.com/thmyl/p/7770860.html

總結

以上是生活随笔為你收集整理的清北刷题冲刺 11-02 a.m的全部內容，希望文章能夠幫你解決所遇到的問題。

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