Codeforces Round #137 (Div. 2)

不是很难的一场~~~

A. Shooshuns and Sequence

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

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

B. Cosmic Tables

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

C. Reducing Fractions

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

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

[cpp]
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#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<N;i++){
        if(prime[i]) continue;
        for(int j=2;j*i<N;j++)
            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<<i<<" "<<c[i]<<endl;
        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<n;i++){
            scanf("%d",&a[i]);
            split(a[i],c1);
        }
        for(int i=0;i<m;i++){
            scanf("%d",&b[i]);
            split(b[i],c2);
        }
        for(int i=2;i<N;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<n;i++)
            print(a[i],c1);
        printf("\n");
        for(int i=0;i<m;i++)
            print(b[i],c2);
        printf("\n");
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#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<N;i++){
  if(prime[i]) continue;
  for(int j=2;j*i<N;j++)
   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<<i<<" "<<c[i]<<endl;
  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<n;i++){
   scanf("%d",&a[i]);
   split(a[i],c1);
  }
  for(int i=0;i<m;i++){
   scanf("%d",&b[i]);
   split(b[i],c2);
  }
  for(int i=2;i<N;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<n;i++)
   print(a[i],c1);
  printf("\n");
  for(int i=0;i<m;i++)
   print(b[i],c2);
  printf("\n");
}
return 0;
}
D. Olympiad

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

E. Decoding Genome

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

[cpp]
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set> &

补充：软件开发 , C++ ,