第一题：Dragons
题意：一个有s点强壮值的战士，他要面对n条龙，龙有两个属性，x:只有当战士的强壮值大于x的时候才能打败这条龙，y:打败这条龙之后战士的强壮值可以增加y。龙的挑战顺序可以改变，问能否打败所有的龙。
题解：贪心。把龙按x的值从小到大排序，之后尝试累加即可。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
int x,y;
}num[1005];
bool cmp(const struct node &a,const struct node &b)
{
return a.x<b.x;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i)
scanf("%d%d",&num[i].x,&num[i].y);
sort(num,num+m,cmp);
bool flag=false;
for(int i=0;i<m;++i)
{
if(n>num[i].x)
n+=num[i].y;
else
{
flag=true;
break;
}
}
if(flag) puts("NO");
else puts("YES");
return 0;
}
第二题：T-primes
题意：给你n个数字xi(1<=xi<=10^12)，对于每个数字问它是否只有3个不同的因子。
题解：对于每个数xi，它必存在1和它本身两个不同的因子，可以得出第3个因子必是素数且它的平方等于xi。我们可以先打一张素数表，求得10^6以内的素数有哪些，再二分查找是否存在这样的素数。(枚举查找会超时的T^T)
代码：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define LL long long
LL prime[100000];
bool flag[1000005];
int idx;
void init()
{
int i,j;
idx=0;
memset(flag,false,sizeof(flag));
for(i=2; i<=1000000; ++i)
{
if(!flag[i])
{
prime[idx++]=i;
for(j=i+i; j<=1000000; j=j+i)
flag[j]=true;
}
}
}
int main()
{
int n;
LL num;
init();
scanf("%d",&n);
for(; n--;)
{
bool ans=false;
scanf("%I64d",&num);
int l=0,r=idx-1,mid;
for(;l<=r;)
{
mid=(l+r)>>1;
if(prime[mid]*prime[mid]==num)
{
ans=true;
break;
}
else if(prime[mid]*prime[mid]<num) l=mid+1;
else r=mid-1;
}
if(ans) puts("YES");
else puts("NO");
}
return 0;
}
第三题：Shifts
题意：一个n*m的01矩阵，对于每行可以进行循环左移或者循环右移操作，问最小需要几次操作可以使得01矩阵中存在全由1组成列。
题解：对于每行中的每个点，计算出由这行中最近1转移过来的步数，之后对于每列统计步数和，取最小值。
代码：
#include<cstdio>
#include<cstring>
using namespace std;
int mapt[105][10005];
int num[105][10005];
int main()
{
int n,m,idx,st;
bool flagt=false;
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)
{
bool flag=true;
getchar();
for(int j=0;j<m;++j)
{
mapt[i][j]=(getchar()=='1'?1:0);
if(mapt[i][j]==1) flag=false;
}
if(flag) flagt=true;
}
if(flagt) puts("-1");
else
{
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
if(mapt[i][j]==1)
{
st=j;
idx=j;
break;
}
num[i][st]=0;
for(int j=(st+1)%m;j!=st;j=(j+1)%m)
if(mapt[i][j]==1)
{
num[i][j]=0;
idx=j;
}
else
num[i][j]=(j-idx+m)%m;
idx=st;
for(int j=(st-1+m)%m;j!=st;j=(j-1+m)%m)
if(mapt[i][j]==1)
{
num[i][j]=0;
idx=j;
}
else if(num[i][j]>(idx-j+m)%m)
num[i][j]=(idx-j+m)%m;
}
int maxx=(1<<30)-1,summ=0;
for(int j=0;j<m;++j)
{
summ=0;
for(int i=0;i<n;++i)
summ+=num[i][j];
if(summ<maxx) maxx=summ;
}
printf("%d\n",maxx);
}
return 0;
}
第四题：
题意：
题解：
代码：
第五题：
题意：
题解：
代码：