Codeforces Round #137 (Div. 2) - c++编程基础

不是很难的一场~~~

A. Shooshuns and Sequence

随便YY下吧，首先必须从k个之后，都是相同的，否则不管怎么样，都不会完成

然后就需要看k之前连续相同的有几个

B. Cosmic Tables

直接搞，两个数组分别记录每一行当前的位置，以及每一列当前的位置

C. Reducing Fractions

分解质因子之后，不要将质因子组合，那样容易出错，一个是容易出上界，二个容易个数过多

显然新分数是将原分数约分得到的，所以个数不变，我们保留剩下的因子即可

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 1<<27
#define M 100005
#define N 10000005
#define Min(a,b) ((a)<(b) (a):(b))
#define Max(a,b) ((a)>(b) (a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(b))
#define LL long long
using namespace std;
int prime[N]={0},c1[N],c2[N];
int n,m,a[M],b[M];
void Prime(){
for(int i=2;i if(prime[i]) continue;
for(int j=2;j*i prime[i*j]=1;
}
}
void split(int num,int c[]){
for(int i=2;i*i<=num&&prime[num];i++){
while(num%i==0){
c[i]++;
num/=i;
}
}
if(num>1) c[num]++;
}
void print(int num,int c[]){
int tmp=1;
for(int i=2;i*i<=num&&prime[num];i++){
// cout< while(num%i==0){
if(c[i]){c[i]--;tmp*=i;}
num/=i;
}
}
if(num>1&&c[num]){c[num]--;tmp*=num;}
printf("%d ",tmp);
}
int main(){
Prime();
while(scanf("%d%d",&n,&m)!=EOF){
mem(c1,0);mem(c2,0);
for(int i=0;i scanf("%d",&a[i]);
split(a[i],c1);
}
for(int i=0;i scanf("%d",&b[i]);
split(b[i],c2);
}
for(int i=2;i int mm=min(c1[i],c2[i]);
c1[i]-=mm;c2[i]-=mm;
}
printf("%d %d\n",n,m);
for(int i=0;i print(a[i],c1);
printf("\n");
for(int i=0;i print(b[i],c2);
printf("\n");
}
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#define inf 1<<27
#define M 100005
#define N 10000005
#define Min(a,b) ((a)<(b) (a):(b))
#define Max(a,b) ((a)>(b) (a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(b))
#define LL long long
using namespace std;
int prime[N]={0},c1[N],c2[N];
int n,m,a[M],b[M];
void Prime(){
for(int i=2;i if(prime[i]) continue;
for(int j=2;j*i prime[i*j]=1;
}
}
void split(int num,int c[]){
for(int i=2;i*i<=num&&prime[num];i++){
while(num%i==0){
c[i]++;
num/=i;
}
}
if(num>1) c[num]++;
}
void print(int num,int c[]){
int tmp=1;
for(int i=2;i*i<=num&&prime[num];i++){
// cout< while(num%i==0){
if(c[i]){c[i]--;tmp*=i;}
num/=i;
}
}
if(num>1&&c[num]){c[num]--;tmp*=num;}
printf("%d ",tmp);
}
int main(){
Prime();
while(scanf("%d%d",&n,&m)!=EOF){
mem(c1,0);mem(c2,0);
for(int i=0;i scanf("%d",&a[i]);
split(a[i],c1);
}
for(int i=0;i scanf("%d",&b[i]);
split(b[i],c2);
}
for(int i=2;i int mm=min(c1[i],c2[i]);
c1[i]-=mm;c2[i]-=mm;
}
printf("%d %d\n",n,m);
for(int i=0;i print(a[i],c1);
printf("\n");
for(int i=0;i print(b[i],c2);
printf("\n");
}
return 0;
}
D. Olympiad

readforces~~~~看懂之后，排序直接贪心，题目说一定有一组相加大于k，所以最优为1

E. Decoding Genome

简单题~~构造矩阵，快速幂乘

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 1<<27
#define M 100005
#define N 55
#define Min(a,b) ((a)<(b) (a):(b))
#define Max(a,b) ((a)>(b) (a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(b))
#define LL long long
#define MOD 1000000007
using na

Codeforces Round #137 (Div. 2) (一)