首页 > 其他 > 详细

codeforces#324(div2)

时间:2015-10-07 14:44:47      阅读:721      评论:0      收藏:0      [点我收藏+]

codeforces#324(div2) 

A题:水题。没注意10的时候特判WA了一次。

技术分享
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=1000100;
const int INF=(1<<29);

int n,t;

int main()
{
    while(cin>>n>>t){
        if(t==10){
            if(n==1){
                puts("-1");
                continue;
            }
            REP(i,1,n-1) printf("1");
            puts("0");
        }
        else{
            REP(i,1,n) printf("%d",t);
            puts("");
        }
    }
    return 0;
}
View Code

B题:水题。没注意取模的时候负数WA了一次。

技术分享
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=(1<<29);
const ll p=1e9+7;

int n;
ll x3[maxn],x7[maxn];

int main()
{
    x3[0]=x7[0]=1;
    REP(i,1,maxn-1) x3[i]=(x3[i-1]*3)%p,x7[i]=(x7[i-1]*7)%p;
    while(cin>>n){
        printf("%I64d\n",(x3[n*3]+7*p-x7[n])%p);
    }
    return 0;
}
View Code

D题:把一个奇数分解成三个质数的和。先找最接近n的尽可能大的质数a(因为质数频率很高,所以复杂度不会高),然后n-a为偶数,由歌德巴赫猜想,任何一个偶数可以分解成两个质数的和,n-a很小,直接暴力就行了。判大素数可以分解质因数,看质因子个数是否为1。

技术分享
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))

using namespace std;

typedef long long ll;
const int maxn=10001000;
const int INF=(1<<29);

ll n;
vector<int> prime;
bool isprime[maxn];

void getPrime()
{
    memset(isprime,1,sizeof(isprime));
    isprime[1]=0;
    REP(i,2,maxn-1){
        if(!isprime[i]) continue;
        for(int j=i+i;j<maxn;j+=i){
            isprime[j]=0;
        }
    }
    REP(i,1,maxn-1) if(isprime[i]) prime.push_back(i);
}

bool IsPrime(ll n)
{
    int cnt=0;
    ll t;
    for(int i=0;i<prime.size();i++){
        t=prime[i];
        if(t*t>=n) break;
        while(n%t==0) n/=t,cnt++;
    }
    while(n%t==0) n/=t,cnt++;
    if(n!=1) cnt++;
    return cnt==1;
}

int main()
{
    getPrime();
    while(cin>>n){
        ll p;
        for(p=n;;p--){
            if(IsPrime(p)) break;
        }
        ll a=p;
        n-=p;
        if(n==0){
            printf("1\n%I64d\n",a);continue;
        }
        if(IsPrime(n)){
            printf("2\n%I64d %I64d\n",a,n);continue;
        }
        ll b,c;
        for(b=2;b<n-1;b++){
            c=n-b;
            if(IsPrime(b)&&IsPrime(c)){
                break;
            }
        }
        printf("3\n%I64d %I64d %I64d\n",a,b,c);
    }
    return 0;
}
View Code

这场C题题意理解错实在可惜,,,C题是说相同位置的不同字符,我理解成了把所有的字符拿出来去掉都有的字符剩下的不同字符,然后浪费了一个小时写C。。。。还好过了D,避免掉分。。

不过A题没注意测边缘数据,B题没注意负数取模,D题没过样例就交确实是不应该。。。话说回来,如果C不理解错题意,应该可以在40min左右过,D题可以在1h左右过,这样又一个小时4题,就重回1700了。。。不过这不是重点,重点是补完这场的C和E然后滚回实验室刷紫书。。。队友都刷到第7章了。。

 

codeforces#324(div2)

原文:http://www.cnblogs.com/--560/p/4858654.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!