概述
A Ginkgo Numbers
直接暴力查找(m,n)是否为(p,q)的因子
1<m^2+n^2<20000 所以直接来个142x142的循环就行
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
int main()
{
int t,i,j,p,q,x,y,f;
RD(t);
while(t--)
{
scanf("%d%d",&p,&q);
x=p*p+q*q;
if(x<=1)
{
printf("Cn");
}
else
{
f=0;
for(i=-142; i<=142; ++i)
{
for(j=-142; j<=142; ++j)
{
y=i*i+j*j;
if(y==0||y==1)
{
continue;
}
if((abs(i)==abs(p)&&abs(j)==abs(q))||(abs(i)==abs(q)&&abs(j)==abs(p)))
{
continue;
}
if((i*p+j*q)%y==0&&(i*q-j*p)%y==0)
{
f=1;
break;
}
}
if(f==1)
{
break;
}
}
if(f==1)
{
printf("Cn");
}
else
{
printf("Pn");
}
}
}
return 0;
}
B One-Dimensional Cellular Automaton
一道数论题,直接写TLE无疑,只能YY了一下。各种数组保存。。。写得都晕了,居然1A。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,i) for(i=a;i<b;++i)
#define For(a,b,i) for(i=a;i<=b;++i)
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
int s[51],f[51][51][51],q[51][51],tx[51];
int main()
{
int n,m,a,b,c,t,i,j,k,l,p,tt;
while(1)
{
RD(n);
RD(m);
RD(a);
RD(b);
RD(c);
RD(t);
if(n==0&&m==0&&a==0&&b==0&&c==0&&t==0)
{
break;
}
For(1,n,i)
{
RD(s[i]);
}
if(t==0)//等于0时没有变化,直接输出
{
FOR(1,n,i)
{
OT(s[i]);
printf(" ");
}
OT(s[n]);
printf("n");
}
else
{
For(1,n,i)//三维数组保存
{
f[0][i-1][i]=a;
f[0][i][i]=b;
f[0][i+1][i]=c;
}
p=0;
while(t>1)//转化为2进制进行操作
{
tx[++p]=t%2;
t=t/2;
}
For(1,p/2,i)
{
tt=tx[i];
tx[i]=tx[p-i+1];
tx[p-i+1]=tt;
}
For(1,p,l)
{
For(1,n,i)
{
For(1,n,j)
{
f[l][i][j]=0;
}
}
For(1,n,k)
{
For(1,n,i)
{
For(1,n,j)
{
f[l][i][j]=(f[l][i][j]+f[l-1][i][k]*f[l-1][k][j])%m;
}
}
}
if(tx[l]==1)
{
For(1,n,i)
{
For(1,n,j)
{
q[i][j]=f[l][i][j];
f[l][i][j]=0;
}
}
For(1,n,k)
{
For(1,n,i)
{
For(1,n,j)
{
f[l][i][j]=(f[l][i][j]+q[i][k]*f[0][k][j])%m;
}
}
}
}
}
mem(q,0);
For(1,n,k)
{
For(1,n,i)
{
For(1,n,j)
{
q[i][j]=(q[i][j]+s[k]*f[p][k][j])%m;
}
}
}
FOR(1,n,i)
{
OT(q[1][i]);
printf(" ");
}
OT(q[1][n]);
printf("n");
}
}
return 0;
}
并查集维护+压缩路径水题。。。int直接能过
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
int fa[100001],s[100001];
int n;
void init()//初始化
{
mem(s,0);
int i;
for(i=1;i<=n;++i)
{
fa[i]=i;
}
}
int f(int x)//并查集
{
if(fa[x]==x)
{
return x;
}
int xx=f(fa[x]);
s[x]+=s[fa[x]];
fa[x]=xx;
return xx;
}
int main()
{
int m,i,j,a,b,w,p,q;
char c;
while(1)
{
RD(n);
RD(m);
if(n==0&&m==0)
{
break;
}
init();
while(m--)
{
scanf("%c",&c);
RD(a);
RD(b);
if(c=='!')
{
RD(w);
p=f(a);
q=f(b);
fa[p]=q;
s[p]=s[b]-s[a]+w;
}
else if(c=='?')
{
if(f(a)==f(b))
{
printf("%dn",s[a]-s[b]);
}
else
{
printf("UNKNOWNn");
}
}
}
}
return 0;
}
H Beautiful Spacing
寻找最短空隙组中的最长空隙,二分+判断
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
int w,n;
int a[50001],s[50001],g[50001],h[50001];
bool f(int x)
{
int i,px=0,py=1,dx;
mem(g,0);
g[0]=1;
h[0]=1;
for(i=2;i<=n;++i)
{
while(px<py&&(s[i]+i-h[px]-s[h[px]-1])>w)
{
px++;
}
if(px<py)
{
if(h[px]!=i)
{
dx=(w-s[i]+s[h[px]-1]+i-h[px]-1)/(i-h[px]);
if(dx<=x)
{
g[i]=1;
h[py]=i+1;
py++;
}
}
}
}
for(i=n;i>=0;--i)
{
if(g[i]==1&&(s[n]-s[i]+n-i)<=w)
{
return true;
}
}
return false;
}
int main()
{
int m,i,j,l,r;
while(1)
{
RD(w);
RD(n);
if(w==0&&n==0)
{
break;
}
s[0]=0;
for(i=1;i<=n;++i)
{
RD(a[i]);
s[i]=s[i-1]+a[i];
}
l=0;
r=w;
while(l+1<r)
{
m=(l+r)/2;
if(f(m)==true)
{
r=m;
}
else
{
l=m;
}
}
OT(r);
printf("n");
}
return 0;
}
最后
以上就是典雅宝贝为你收集整理的130811个人赛练习BNU-Regionals 2012, Asia - Tokyo的全部内容,希望文章能够帮你解决130811个人赛练习BNU-Regionals 2012, Asia - Tokyo所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复