第一题：Shooshuns
and Sequence
题意：给你一个数字序列，有一个操作，1）把第k个数字复制一份放到序列最后。2）删除第1个数字。问要执行多少次操作使得数字序列里的数字都相同，如果不能输出-1
题解：由题目可知，如果原数字序列在第k个数字之后出现不同的数字则不可能通过操作使得数字相同。如果可以使数字都相同，操作数可以通过判断从第i位之后所有数都相同中最小的i即为操作数。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int num[100005];
int main()
{
int n,k;
bool flag=false;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
scanf("%d",num+i);
for(int i=n;i>k;--i)
if(num[i]!=num[k])
{
flag=true;
break;
}
if(flag) printf("-1\n");
else
{
int idx=0;
for(int i=n;i>=1;--i)
if(num[i]!=num[k])
{
idx=i;
break;
}
printf("%d\n",idx);
}
return 0;
}
第二题： Cosmic
Tables
题意：一个矩阵，会有交换行或列，以及询问第i行第j列是什么数字的询问。
题解：交换行或列的时候只要交换行列的小标即可，询问就没啥难度了。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int mat[1005][1005];
int row[1005],col[1005];
int main()
{
int n,m,k;
char s[5];
int a,b,temp;
memset(mat,0,sizeof(mat));
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&mat[i][j]);
for(int i=1;i<=n;++i)
row[i]=i;
for(int i=1;i<=m;++i)
col[i]=i;
for(;k--;)
{
scanf("%s%d%d",s,&a,&b);
if(s[0]=='c')
{
temp=col[a];
col[a]=col[b];
col[b]=temp;
}
else if(s[0]=='r')
{
temp=row[a];
row[a]=row[b];
row[b]=temp;
}
else
{
printf("%d\n",mat[row[a]][col[b]]);
}
}
return 0;
}
第三题： Reducing
Fractions
题意：对于一个分数，为了不让别人很直观的知道是什么，我们把分子用它的几个因子相乘表示，分母也是如此。题目给一个上面提到的那个形式表示的分数，要求对其约分，再通过上面提到的形式把约分后的分数表示出来。
题解：千万不要傻傻的把输入乘起来然后求gcd约分（我比赛时就这样的T^T），这样做不仅数据要超long long而且还费时间。因为题目给的就是分子分母的因子，我们可以在这个基础上继续求因子，同时统计分子和分母的素数因子分别有哪些以及其个数，之后就在各自的素数因子的基础上再约分。这样最后输出的时候也方便快捷。
代码：
#include<cstdio>
#include<cstring>
using namespace std;
int prime[10000005]={0};
int a[100005],b[100005];
int ap[10000005],bp[10000005];
void check(int *x,int *y,int len)//分解因子
{
for(int i=0;i<len;++i)
for(int j=x[i];j>1;j/=prime[j])
y[prime[j]]++;//因子数+1
}
void print(int *x,int *y,int len)
{
int cnt;
for(int i=0;i<len;++i)
{
cnt=1;
for(int j=x[i];j>1;j/=prime[j])
if(y[prime[j]]>0) y[prime[j]]--;
else cnt*=prime[j];
if(i==0) printf("%d",cnt);
else printf(" %d",cnt);
}
puts("");
}
int main()
{
int n,m;
prime[2]=0;
for(int i=2;i<=10000000;++i)
if(!prime[i])
{
prime[i]=i;
for(int j=2*i;j<=10000000;j+=i)
prime[j]=i;
}
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i) scanf("%d",a+i);
for(int i=0;i<m;++i) scanf("%d",b+i);
check(a,ap,n);check(b,bp,m);
printf("%d %d\n",n,m);
print(a,bp,n);print(b,ap,m);
return 0;
}
第四题： Olympiad
题意：有一个n个人参加的比赛，同时Vasya也参加了这个比赛，现在知道第一轮的分数和第二轮的分数，但是不知道这些分数是属于哪个选手的，同时知道Vasya至少获得的分数和k，问Vasya可能的最好名次和最差名次。
题解：题目保证存在分数和大于k，所以Vasya最好成绩就是取分数和最大的第一轮和第二轮分数，即第一名。最差成绩就是第一轮分数和第二轮分数搭配，使得大于等于k的数最多，最差成绩就是取大于等于k中的最小数。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
int a[100005],b[100005];
int main()
{
int n,k,t=1;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i) scanf("%d",a+i);
for(int i=1;i<=n;++i) scanf("%d",b+i);
sort(a+1,a+1+n);
sort(b+1,b+1+n,greater<int>());
for(int i=1;i<=n;++i)
if(a[i]+b[t]>=k) ++t;
printf("%d %d\n",1,t-1);
return 0;
}
第五题： Decoding
Genome
题意：有个由m中字符组成的长度为n的DNA串，同时告诉你k个不能出现的情况，就是字母b不能接在字母a的后面等等。问符合题目条件的DNA串有多少种，答案对1000000007求余
题解：构造矩阵，直接快速幂就行了。
代码：
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 55
#define mod 1000000007
#define LL long long
typedef struct node
{
LL matrix[MAX][MAX];
} Matrix;
Matrix x,y,z;
LL n;//题目的n特别大，必须用long long
int m,k;
int check(char c)
{
if('a'<=c&&c<='z') return c-'a';
else return c-'A'+26;
}
Matrix mul(Matrix a,Matrix b)//矩阵乘法
{
Matrix c;
for(int i=0;i<m;++i)
for(int j=0;j<m;++j)
{
c.matrix[i][j]=0;
for(int k=0;k<m;++k)
c.matrix[i][j]=(c.matrix[i][j]+(a.matrix[i][k]*b.matrix[k][j])%mod)%mod;
}
return c;
}
Matrix cal(LL exp)//矩阵幂
{
Matrix p,q;
p=x;
q=z;//单位矩阵
for(;exp>1;)
{
if(exp&1)
{
exp--;
q=mul(p,q);
}
else
{
exp>>=1;
p=mul(p,p);
}
}
p=mul(p,q);
return p;
}
int main()
{
char a[5];
scanf("%I64d%d%d",&n,&m,&k);
for(int i=0;i<m;++i)
for(int j=0;j<m;++j)
{
x.matrix[i][j]=1;
z.matrix[i][j]=(i==j);
}
for(;k--;)
{
scanf("%s",a);
x.matrix[check(a[0])][check(a[1])]=0;
}
if(n==1) y=z;
else y=cal(n-1);
LL ans=0;
for(int i=0;i<m;++i)
for(int j=0;j<m;++j)
ans=(ans+y.matrix[i][j])%mod;
printf("%I64d\n",ans);
return 0;
}