Codeforces 456 Div2

（写到一半突然断电。。。。。无力，原谅我不写题意了）

B:

很显然，如果$k=1$，答案就是n
若$k≥2$，答案就是n的第一个1开始，将后面所有位全部转换为1后的值。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 1010
using namespace std;
long long x,y;
int main(){SF("%I64d%I64d",&x,&y);if(y==1)PF("%I64d",x);else{long long ans=1;while(x){ans<<=1ll;x>>=1ll;}PF("%I64d",ans-1);}
}

C:

本来之前写了一个很详细的题意。。。呵呵呵呵呵呵呵呵呵呵

用一个set存储所有生命值在攻击限度内的敌人，当某个敌人将要超出限度时，统计一次答案。
特殊处理regen为0的，以及max_health小于等于damage的敌人，因为它们永远不可能通过自己恢复生命来超出攻击范围。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
long long x,y,dem,sumy,s1;
int n,m;
bool ign[MAXN],ini[MAXN];
struct node{long long st,k,tim;int id;bool operator < (const node &a) const {return (dem-st)/k+tim<(dem-a.st)/a.k+a.tim;}node () {}node (long long st1,long long k1,long long tim1,int id1):st(st1),k(k1),tim(tim1),id(id1) {}
};
long long endtime (node x){return (dem- x.st)/(x.k)+ x.tim;
}
struct que{long long tim,x,y;bool operator < (const que &a) const {return tim<a.tim;}que () {}que (long long tim1,long long x1,long long y1):tim(tim1),x(x1),y(y1) {}
}Query[MAXN];
multiset<node> s;
long long stx[MAXN],kx[MAXN],timx[MAXN],las[MAXN],che,sta,inc,ans;
int main(){SF("%d%d",&n,&m);SF("%I64d%I64d%I64d",&sta,&inc,&dem);for(int i=1;i<=n;i++){SF("%I64d%I64d%I64d",&che,&stx[i],&kx[i]);if(inc!=0&&che<=dem){PF("-1");return 0;}if(stx[i]<=dem){if(kx[i]==0||che<=dem){sumy++;ini[i]=1;}elses.insert(node(stx[i],kx[i],0,i));}if(kx[i]==0||che<=dem){ign[i]=1;}}for(int i=1;i<=m;i++){SF("%I64d%I64d%I64d",&Query[i].tim,&Query[i].x,&Query[i].y);}sort(Query+1,Query+1+m);int top=1;while(s.size()||top<=m){while(s.size()==0&&top<=m){ans=max(ans,1ll*((Query[top].tim-1ll)*inc+sta)*sumy);long long x=Query[top].x;las[x]=Query[top].tim;stx[x]=Query[top].y;top++;if(ign[x]==1){if(ini[x]==1&&stx[x]>dem){sumy--;ini[x]=0;}if(ini[x]==0&&stx[x]<dem){sumy++;ini[x]=1;}continue;}if(stx[x]<=dem)s.insert(node(stx[x],kx[x],las[x],x));}if(s.size()==0&&top>m)break;while(1){if(top>m)break;if(s.size()!=0){multiset<node>::iterator it=s.begin();if(endtime(*it)<Query[top].tim)break;}s1=s.size()+sumy;ans=max(ans,1ll*((Query[top].tim-1ll)*inc+sta)*s1);long long x=Query[top].x;if(ign[x]==1){las[x]=Query[top].tim;stx[x]=Query[top].y;if(ini[x]==1&&stx[x]>dem){sumy--;ini[x]=0;}if(ini[x]==0&&stx[x]<=dem){sumy++;ini[x]=1;}top++;continue;}multiset<node>::iterator it=s.find(node(stx[x],kx[x],las[x],x));if(it!=s.end())s.erase(it);las[x]=Query[top].tim;stx[x]=Query[top].y;if(stx[x]<=dem)s.insert(node(stx[x],kx[x],las[x],x));top++;}if(s.size()==0&&top>m)break;multiset<node>::iterator itx=s.begin();long long t1=endtime(*itx);//PF("{%I64d}",t1);s1=s.size()+sumy;ans=max(ans,1ll*(t1*inc+sta)*s1);s.erase(itx);}if(inc!=0&&sumy!=0)PF("-1");else{if(sumy!=0)ans=max(ans,sumy*sta);PF("%I64d",ans);}
}

D:

算了不粘图片了，反正没人会看。

为了使每条鱼的贡献尽量大，我们肯定希望一条鱼能被尽量多的网给覆盖，所以按照这个原则BFS贪心就可以了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#define SF scanf
#define PF printf
#define MAXN 1010
using namespace std;
long long n,m,r,k,ans;
long long w[4][3]={
   {
   1ll,0ll},{
   0ll,1ll},{-1ll,0ll},{
   0ll,-1ll}};
struct node{long long dix,x,y;bool operator < (const node &a) const {return dix<a.dix;}node () {}node (long long dix1,long long x1,long long y1):dix(dix1),x(x1),y(y1) {}
};
map<pair<int,int> ,int> used;
priority_queue<node>q;
long long dis(long long x,long long y){long long x1=min(r,x)+min(r,n-x+1ll)-r;long long y1=min(r,y)+min(r,m-y+1ll)-r;return x1*y1;
}
void bfs(){int sum=0;while(!q.empty()){node nex=q.top();sum++;if(sum>k)return ;q.pop();ans+=nex.dix;long long x1=nex.x;long long y1=nex.y;for(int i=0;i<4;i++){long long x2=x1+w[i][0];long long y2=y1+w[i][1];if(x2>0&&y2>0&&x2<=n&&y2<=m&&used[make_pair(x2,y2)]==0){used[make_pair(x2,y2)]=1;q.push(node(dis(x2,y2),x2,y2));}}}}
int main(){SF("%I64d%I64d%I64d%I64d",&n,&m,&r,&k);long long stx=(n+1ll)>>1ll;long long sty=(m+1ll)>>1ll;q.push(node(dis(stx,sty),stx,sty));used[make_pair(stx,sty)]=1;bfs();double t1=ans;double t2=double(n-r+1)*double(m-r+1);PF("%.10lf",t1/t2);
}

E:

首先跑一个暴力，发现其实能组成的数个数并不是很多，即使是最大的情况（即最小的16个质数），我们也能通过将其拆分为2组，（即2,5,11,17…为一组，3,7,13,19…为一组），这样每组的能组成的数约为1000000个左右，所以再套个二分，处理从这两组中之积小于等于某个值的组合数，就可以得到答案了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 20
#define MAXM 1500000
using namespace std;
long long prim[MAXN],maxl,cnt[2];
int n;
long long res[2][MAXM],k;
void dfs(long long sum,int k,int flag){if(flag==1)res[k%2][++cnt[k%2]]=sum;if(k>n)return ;if(sum<=maxl/prim[k])dfs(sum*prim[k],k,1);dfs(sum,k+2,0);
}
bool check(long long x){long long j=cnt[1];long long ans=0;for(int i=1;i<=cnt[0];i++){while(j!=0&&res[0][i]>x/res[1][j])j--;ans+=1ll*j;}return ans>=k;
}
int main(){SF("%d",&n);maxl=1;for(int i=1;i<=18;i++)maxl*=10ll;for(int i=1;i<=n;i++)SF("%I64d",&prim[i]);SF("%I64d",&k);sort(prim+1,prim+1+n);dfs(1,1,1);dfs(1,2,1);sort(res[0]+1,res[0]+cnt[0]+1);sort(res[1]+1,res[1]+cnt[1]+1);/*for(int i=1;i<=cnt[0];i++)PF("[%I64d]\n",res[0][i]);for(int i=1;i<=cnt[1];i++)PF("{%I64d}\n",res[1][i]);*///dfs(1,2);long long l=1,r=maxl,ans;while(l<=r){long long mid=(l+r)>>1ll;if(check(mid)){ans=mid;r=mid-1ll;}elsel=mid+1ll;}PF("%I64d",ans);
}