这场edu我原本以为能清真一点……
后来发现不仅是七题
还有各种奇奇怪怪的骚操作……
A.
随便枚举
#include<bits/stdc++.h> using namespace std; int n; int main(){ scanf("%d",&n);int x=1; for(;n/(x*10);x*=10); printf("%d ",n/x*x+x-n); }
B.
xjb按照定义分一下就行了
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,k,m,a[200010]; double ans; int main(){ cin>>n>>k;ll i; for(i=1;i<=n;i++)cin>>a[i]; for(i=1;i<=n;i++)ans+=a[i]*min(min(i,n-i+1),min(k,n-k+1)); ans/=(n-k+1); printf("%16.15f",ans); }
C.
将茶杯排序，然后从后往前贪心地构造就行了。
#include<bits/stdc++.h> using namespace std; int a[1010],b[1010],n,w; 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();w=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++){b[i]=(a[i]+1)>>1;w-=b[i];} if(w<0){puts("-1");return 0;} while(w){ int minv=0; for(int i=1;i<=n;i++)if((!minv||a[i]>=a[minv])&&a[i]>b[i])minv=i; int x=min(a[minv]-b[minv],w); b[minv]+=x;w-=x; } for(int i=1;i<=n;i++)printf("%d ",b[i]); }
D.
求出前缀和，二分下标。
#include<bits/stdc++.h> using namespace std; int a[1010],b[1010],n,w; 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();w=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++){b[i]=(a[i]+1)>>1;w-=b[i];} if(w<0){puts("-1");return 0;} while(w){ int minv=0; for(int i=1;i<=n;i++)if((!minv||a[i]>=a[minv])&&a[i]>b[i])minv=i; int x=min(a[minv]-b[minv],w); b[minv]+=x;w-=x; } for(int i=1;i<=n;i++)printf("%d ",b[i]); }
E.
大数据版01背包……
不知道正解是啥，我sort一下+鬼畜剪枝玄学过去……
#include<bits/stdc++.h> #define N 1000005 using namespace std; typedef long long ll; int w[N],c[N],rk[N]; int n,m; ll f[N],p[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; } bool cmp(int x,int y){return p[x]<p[y];} int main(){ n=read();m=read(); for(int i=1;i<=n;i++){ w[i]=read();c[i]=read();p[i]=c[i]*6LL/w[i];rk[i]=i; } sort(rk+1,rk+n+1,cmp);int s=0; for(int i=n;i;i--){ int ww=w[rk[i]],cc=c[rk[i]]; s+=ww; for(int j=s;j>=max(ww,s-50);j--)f[j]=max(f[j],f[j-ww]+cc); } for(int i=1;i<=m;i++)f[i]=max(f[i],f[i-1]); cout<<f[m]<<endl; }
F.
本场最恶心的题……
首先线性筛出素数，这个不用说。
其次有个显然的单调性。那么我们可以对等级二分答案。
这类问题很模型化，任取两个数不能为素数，那么我们考虑怎样才一定取不出素数。
问题其实也就是一个二分匹配问题，左集合全部为奇数（我们暂时先不考虑1的问题），右集合全部为偶数，那么只有从左边取一个数或者从右边取一个数才可能构成素数。
那么这里就构成了一个二分图模型。
我们考虑建图：
①建立源点，连入各个奇数，流为各个奇数其本身的价值。
②建立汇点，将各个偶数连入汇点，流为各个偶数其本身的价值。
③对应遍历各个奇数，如果其右边有偶数和其相加能够构成素数，那么将其连入那个点，流为INF.
那么我们跑出的最大流就是最小割，也就是最小花费，同样可以理解为最小抛掉的点的价值总和。
那么我们此时最优选取方案的价值和就是Sum-maxlfow.这里Sum就是能够选择的数的价值总和。
于是就这么恶心的写完了……
#include<bits/stdc++.h> #define N 200005 #define inf 1000000007 using namespace std; int n,m,opt[N],e,s,t,vis[N];int prime[N],cnt=0; struct Data{int p,c,l;}a[N]; //////////////////////////////////////////////////////////////////////////////////////////////////////////// inline void calcpri(){ memset(vis,1,sizeof(vis)); for(int i=2;i<=N;i++){ if(vis[i]){prime[++cnt]=i;} for(int j=1;j<=cnt;j++){ int t=i*prime[j];if(t>N)break; vis[t]=0; if(i%prime[j]==0)break; } } } ////////////////////////////////////////////////////////////////////////////////////////////////////////// namespace Maxflow{ struct Edge{int u,v,f,next;}G[N<<1]; int head[4*N],tot=0; inline void addedge(int u,int v,int f){ G[tot].u=u;G[tot].v=v;G[tot].f=f;G[tot].next=head[u];head[u]=tot++; G[tot].u=v;G[tot].v=u;G[tot].f=0;G[tot].next=head[v];head[v]=tot++; } int level[N]; bool bfs(int s,int t){ memset(level,0,sizeof(level)); queue<int>q;q.push(s);level[s]=1; while(!q.empty()){ int u=q.front();q.pop(); if(u==t)return 1; for(int i=head[u];~i;i=G[i].next){ int v=G[i].v,f=G[i].f; if(f&&!level[v])level[v]=level[u]+1,q.push(v); } } return 0; } int dfs(int u,int maxf,int t){ int ret=0;if(u==t)return maxf; for(int i=head[u];~i;i=G[i].next){ int v=G[i].v,f=G[i].f; if(f&&level[v]==level[u]+1){ f=dfs(v,min(maxf-ret,f),t); ret+=f;G[i].f-=f;G[i^1].f+=f; } } if(!ret)level[u]=inf; return ret; } inline void init(){memset(head,-1,sizeof(head));tot=0;} inline int dinic(int s,int t){ int ans=0; while(bfs(s,t))ans+=dfs(s,inf,t); return ans; } } /////////////////////////////////////////////////////////////////////////////////////////////////////////// bool check(int x){ int k=0;for(int i=1;i<=n;i++)if(a[i].l<=x)if(a[i].c==1&&a[i].p>a[k].p)k=i; Maxflow::init(); int s=0,t=n+1; int sum=0; for(int i=1;i<=n;i++)if(a[i].l<=x){ if(a[i].c==1&&i!=k)continue; sum+=a[i].p;if(a[i].c&1)Maxflow::addedge(s,i,a[i].p); else Maxflow::addedge(i,t,a[i].p); } for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(vis[a[i].c+a[j].c]){ if(a[i].c&1)Maxflow::addedge(i,j,inf); else Maxflow::addedge(j,i,inf); } return (sum-Maxflow::dinic(s,t)>=m); } 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();calcpri(); for(int i=1;i<=n;i++)a[i].p=read(),a[i].c=read(),a[i].l=read(); int l=1,r=0,ret=0; for(int i=1;i<=n;i++)r=max(r,a[i].l);ret--; while(l<=r){ int mid=(l+r)>>1; if(check(mid))ret=mid,r=mid-1; else l=mid+1; } printf("%d ",ret); }
G.
一个挺妙的dp。
记录dp[i],表示到了位置i最多的出现次数。
cnt[i]，表示最后一次出现的 B 以 i 结尾 0-i中最多能出现几次B
首先dp[i]初始为dp[i-1]
接着用kmp，O(m)求出可以从之前的哪个位置转移
求和之后比较即可。
#include<bits/stdc++.h> #define N 100005 using namespace std; char s[N],p[N]; int nxt[N],dp[N],cnt[N]; void calcnext(char *s,int len,int *nxt){ int i=0,j;nxt[0]=j=-1; while(i<len){ while(j!=-1&&s[i]!=s[j])j=nxt[j]; nxt[++i]=++j; } } int main(){ scanf("%s",s);scanf("%s",p); calcnext(p,strlen(p),nxt);int slen=strlen(s),plen=strlen(p); //for(int i=0;i<plen;i++)printf("%d ",nxt[i]);puts(""); if(plen>slen){puts("0");return 0;} else{ memset(cnt,0,sizeof(cnt));memset(dp,0,sizeof(dp)); for(int i=plen-1;i<slen;i++){ bool sqc=1; for(int k=0;k<plen;k++) if(s[i-k]!=p[plen-1-k]&&s[i-k]!='?'){sqc=0;break;} dp[i]=dp[i-1]; if(sqc){ cnt[i]=dp[i-plen]; for(int k=nxt[plen];~k;k=nxt[k])cnt[i]=max(cnt[i],cnt[i-(plen-k)]); cnt[i]++; dp[i]=max(dp[i],cnt[i]); } } printf("%d ",dp[slen-1]); } }
这场没有DS题好差评……
不过有几道好题真是不错的呀。