这场edu蛮简单的……
连道数据结构题都没有……
A.随便质因数分解凑一下即可。
#include<bits/stdc++.h> #define N 100005 using namespace std; int a[N],cnt,k,x,n; int main(){ scanf("%d%d",&n,&k); for(int i=2;k>1&&n>1;i++) for(;k>1&&n%i==0;--k,n/=i)a[++cnt]=i; if(n==1){puts("-1");return 0;} for(int i=1;i<=cnt;i++)printf("%d ",a[i]); printf("%d ",n); }
B.读入的时候贪心选一下即可。
#include<bits/stdc++.h> #define inf 1000000007 using namespace std; int n,q,ans,mmp=inf; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ int x;scanf("%d",&x); if(x>0)ans+=x; if(x%2!=0)mmp=min(abs(x),mmp); } if(ans%2==0)ans-=mmp; printf("%d ",ans); }
C.贪心
#include<bits/stdc++.h> #define N 100010 using namespace std; char a[N],t[N],ans[N],s[N],minv[N]; int main(){ scanf("%s",s);int len=strlen(s),m=0,k=0; minv[len]='z'+1;minv[len-1]=s[len-1]; for(int i=len-2;i>=0;i--)minv[i]=min(minv[i+1],s[i]); for(int i=0;i<len;i++){ t[m++]=s[i]; while(m&&t[m-1]<=minv[i+1])ans[k++]=t[--m]; } ans[k]=0; printf("%s ",ans); }
D.扫一下树，计算可能的出现次数（值域过大用map比较好）
然后总共的减去sum即为答案。
#include<bits/stdc++.h> #define N 100010 #define inf 2147483640 using namespace std; int n,val[N],lc[N],rc[N],fa[N],ans; map<int,int> mp; void dfs(int u,int ql,int qr){ if(u==-1)return;if(ql>qr)return; if(ql<=val[u]&&val[u]<=qr)ans+=mp[val[u]]; dfs(lc[u],ql,min(val[u]-1,qr)); dfs(rc[u],max(val[u]+1,ql),qr); } inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } int main(){ n=read(); for(int i=1;i<=n;i++){ val[i]=read();lc[i]=read();rc[i]=read(); mp[val[i]]++;fa[lc[i]]=fa[rc[i]]=i; } for(int i=1;i<=n;i++)if(!fa[i])dfs(i,0,inf); printf("%d ",n-ans); }
E.正解应该是dp，然而记忆化搜索还是能水过去……
#include<bits/stdc++.h> #define N 100010 using namespace std; int n,a[N],f[500][N]; inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } int dfs(int u,int k){ if(u>n)return 0; if(k>400)return dfs(u+a[u]+k,k)+1; if(f[k][u])return f[k][u]; else return f[k][u]=dfs(u+a[u]+k,k)+1; } int main(){ n=read();for(int i=1;i<=n;i++)a[i]=read(); int q=read(); while(q--){ int u=read(),v=read(); printf("%d ",dfs(u,v)); } }
F.比较裸的单调队列优化。
#include<bits/stdc++.h> #define inf 1000000000000000000ll #define N 5005 using namespace std; typedef long long ll; int n,m,sum,a[N],q[N],l,r; ll dp[N][N],s[N]; struct Node{int x,y;}b[N]; bool operator <(Node a,Node b){return a.x<b.x;} inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } int main(){ n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(),dp[0][i]=inf; sort(a+1,a+n+1); for(int i=1;i<=m;i++){b[i].x=read();b[i].y=read();sum+=b[i].y;} if(sum<n){puts("-1");return 0;}sort(b+1,b+m+1); for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++)s[j]=s[j-1]+abs(a[j]-b[i].x); l=1;r=0; for(int j=0;j<=n;j++){ if(l<=r&&q[l]<j-b[i].y)l++; while(l<=r&&dp[i-1][j]-s[j]<=dp[i-1][q[r]]-s[q[r]])r--; q[++r]=j;if(l<=r)dp[i][j]=dp[i-1][q[l]]-s[q[l]]+s[j]; else dp[i][j]=inf; } } cout<<dp[m][n]<<endl; }
总结：这场题目其实没多大意思……但是思维题比较多。