这场edu我原本以为能清真一点……
后来发现不仅是七题
还有各种奇奇怪怪的骚操作……
A.
随便枚举
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
scanf("%d",&n);int x=;
for(;n/(x*);x*=);
printf("%d\n",n/x*x+x-n);
}
B.
xjb按照定义分一下就行了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,m,a[];
double ans;
int main(){
cin>>n>>k;ll i;
for(i=;i<=n;i++)cin>>a[i];
for(i=;i<=n;i++)ans+=a[i]*min(min(i,n-i+),min(k,n-k+));
ans/=(n-k+);
printf("%16.15f",ans);
}
C.
将茶杯排序，然后从后往前贪心地构造就行了。
#include<bits/stdc++.h>
using namespace std;
int a[],b[],n,w;
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
int main(){
n=read();w=read();
for(int i=;i<=n;i++)a[i]=read();
for(int i=;i<=n;i++){b[i]=(a[i]+)>>;w-=b[i];}
if(w<){puts("-1");return ;}
while(w){
int minv=;
for(int i=;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=;i<=n;i++)printf("%d ",b[i]);
}
D.
求出前缀和，二分下标。
#include<bits/stdc++.h>
using namespace std;
int a[],b[],n,w;
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
int main(){
n=read();w=read();
for(int i=;i<=n;i++)a[i]=read();
for(int i=;i<=n;i++){b[i]=(a[i]+)>>;w-=b[i];}
if(w<){puts("-1");return ;}
while(w){
int minv=;
for(int i=;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=;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=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
bool cmp(int x,int y){return p[x]<p[y];}
int main(){
n=read();m=read();
for(int i=;i<=n;i++){
w[i]=read();c[i]=read();p[i]=c[i]*6LL/w[i];rk[i]=i;
}
sort(rk+,rk+n+,cmp);int s=;
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-);j--)f[j]=max(f[j],f[j-ww]+cc);
}
for(int i=;i<=m;i++)f[i]=max(f[i],f[i-]);
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=;
struct Data{int p,c,l;}a[N];
////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline void calcpri(){
memset(vis,,sizeof(vis));
for(int i=;i<=N;i++){
if(vis[i]){prime[++cnt]=i;}
for(int j=;j<=cnt;j++){
int t=i*prime[j];if(t>N)break;
vis[t]=;
if(i%prime[j]==)break;
}
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////
namespace Maxflow{ struct Edge{int u,v,f,next;}G[N<<];
int head[*N],tot=;
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=;G[tot].next=head[v];head[v]=tot++;
}
int level[N];
bool bfs(int s,int t){
memset(level,,sizeof(level));
queue<int>q;q.push(s);level[s]=;
while(!q.empty()){
int u=q.front();q.pop();
if(u==t)return ;
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]+,q.push(v);
}
}
return ;
}
int dfs(int u,int maxf,int t){
int ret=;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]+){
f=dfs(v,min(maxf-ret,f),t);
ret+=f;G[i].f-=f;G[i^].f+=f;
}
}
if(!ret)level[u]=inf;
return ret;
}
inline void init(){memset(head,-,sizeof(head));tot=;}
inline int dinic(int s,int t){
int ans=;
while(bfs(s,t))ans+=dfs(s,inf,t);
return ans;
} }
///////////////////////////////////////////////////////////////////////////////////////////////////////////
bool check(int x){
int k=;for(int i=;i<=n;i++)if(a[i].l<=x)if(a[i].c==&&a[i].p>a[k].p)k=i;
Maxflow::init();
int s=,t=n+;
int sum=;
for(int i=;i<=n;i++)if(a[i].l<=x){
if(a[i].c==&&i!=k)continue;
sum+=a[i].p;if(a[i].c&)Maxflow::addedge(s,i,a[i].p);
else Maxflow::addedge(i,t,a[i].p);
}
for(int i=;i<=n;i++)for(int j=;j<=n;j++)if(vis[a[i].c+a[j].c]){
if(a[i].c&)Maxflow::addedge(i,j,inf);
else Maxflow::addedge(j,i,inf);
}
return (sum-Maxflow::dinic(s,t)>=m);
} inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
} int main(){
n=read();m=read();calcpri();
for(int i=;i<=n;i++)a[i].p=read(),a[i].c=read(),a[i].l=read();
int l=,r=,ret=;
for(int i=;i<=n;i++)r=max(r,a[i].l);ret--;
while(l<=r){
int mid=(l+r)>>;
if(check(mid))ret=mid,r=mid-;
else l=mid+;
}
printf("%d\n",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=,j;nxt[]=j=-;
while(i<len){
while(j!=-&&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("");return ;}
else{
memset(cnt,,sizeof(cnt));memset(dp,,sizeof(dp));
for(int i=plen-;i<slen;i++){
bool sqc=;
for(int k=;k<plen;k++)
if(s[i-k]!=p[plen--k]&&s[i-k]!='?'){sqc=;break;}
dp[i]=dp[i-];
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\n",dp[slen-]);
}
}
这场没有DS题好差评……
不过有几道好题真是不错的呀。