以后不放水题了
C.NN and the Optical Illusion
复习一下高中数学即可
$\frac{ans}{ans+r}=\sin \frac{\pi}{n}$
解方程
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double pai=acos(-);
int n,d; double a;
int main()
{
scanf("%d%d",&n,&d),a=pai/n;
printf("%f",sin(a)*d/(-sin(a)));
return ;
}
D.Dasha and Chess
先走到中间，然后背对着车最少的那个角落走，根据咕咕原理可知这边最少有 666*3/4=499.5— —也就是500 只车，而走过去只需要499步，所以一定能被将到；总步数最多499+499步
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
pair<int,int> rook[N];
int t1,t2,t3,kx,ky,mini;
int ocp[N][N],cnt[][];
void Check()
{
if(t1<=) exit();
}
void Move(int xx,int yy)
{
kx+=xx,ky+=yy;
if(ocp[kx][ky]) kx-=xx;
printf("%d %d\n",kx,ky),fflush(stdout);
scanf("%d%d%d",&t1,&t2,&t3),Check();
int rx=rook[t1].first,ry=rook[t1].second;
ocp[rx][ry]=false,rook[t1]=make_pair(t2,t3),ocp[t2][t3]=true;
}
int main()
{
scanf("%d%d",&kx,&ky),mini=1e9;
for(int i=;i<=;i++)
{
scanf("%d%d",&t1,&t2);
rook[i]=make_pair(t1,t2),ocp[t1][t2]=true;
}
while(kx<) Move(,);
while(kx>) Move(-,);
while(ky<) Move(,);
while(ky>) Move(,-);
for(int i=;i<=;i++)
for(int j=;j<=;j++)
if(ocp[i][j]) cnt[i>][j>]++;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
if(cnt[i][j]<mini) mini=cnt[i][j];
for(int i=;i<=;i++)
for(int j=;j<=;j++)
if(cnt[i][j]==mini)
while(true) Move(i?-:,j?-:);
return ;
}
E.Andrew and Taxi
首先一定有解，构造方法是所有边都是小编号指向大编号，那么二分答案对大于答案的边跑拓扑排序检验即可
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
struct a
{
int u,v,w;
}edg[N];
int p[N],noww[N],goal[N];
int deg[N],idx[N],que[N],outp[N];
int n,m,f,b,t1,t2,t3,cnt,num,ans;
void Link(int f,int t)
{
noww[++cnt]=p[f],p[f]=cnt;
goal[cnt]=t,deg[t]++;
}
bool Nocir(int x)
{
num=,cnt=,f=,b=-;
memset(p,,sizeof p);
memset(deg,,sizeof deg);
for(int i=;i<=m;i++)
if(edg[i].w>x)
Link(edg[i].u,edg[i].v);
for(int i=;i<=n;i++)
if(!deg[i]) que[++b]=i;
while(f<=b)
{
int tn=que[f++]; idx[tn]=++num;
for(int i=p[tn];i;i=noww[i])
if(!(--deg[goal[i]]))
que[++b]=goal[i];
}
for(int i=;i<=n;i++)
if(deg[i]) return false;
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&t1,&t2,&t3);
edg[i]=(a){t1,t2,t3},ans=max(ans,t3);
}
int l=,r=ans;
while(l<=r)
{
int mid=(l+r)/;
if(Nocir(mid)) r=mid-,ans=mid;
else l=mid+;
}
Nocir(ans);
for(int i=;i<=m;i++)
if(edg[i].w<=ans&&idx[edg[i].u]>idx[edg[i].v])
outp[++outp[]]=i;
printf("%d %d\n",ans,outp[]);
for(int i=;i<=outp[];i++)
printf("%d ",outp[i]);
return ;
}
F.Ivan and Burgers
恭喜出题人获得了“出到原题”成就
然后就被踩标算了。。。
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,K=;
vector<pair<int,int> > ve[N];
vector<pair<int,int> > ::iterator it;
int n,m,t1,t2,val[N],ans[N],bas[K],pos[K];
void Insert(int x,int y)
{
for(int i=;~i;i--)
if(x&(<<i))
{
if(!bas[i])
{
bas[i]=x,pos[i]=y;
return;
}
if(y>pos[i])
swap(x,bas[i]),swap(y,pos[i]);
x^=bas[i];
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&val[i]);
scanf("%d",&m);
for(int i=;i<=m;i++)
{
scanf("%d%d",&t1,&t2);
ve[t2].push_back(make_pair(t1,i));
}
for(int i=;i<=n;i++)
{
Insert(val[i],i);
for(it=ve[i].begin();it!=ve[i].end();it++)
{
int lef=it->first,idx=it->second;
for(int j=;~j;j--)
if(pos[j]>=lef&&(ans[idx]^bas[j])>ans[idx])
ans[idx]^=bas[j];
}
}
for(int i=;i<=m;i++)
printf("%d\n",ans[i]);
return ;
}