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; }
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; }
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; }
这场C题题意理解错实在可惜,,,C题是说相同位置的不同字符,我理解成了把所有的字符拿出来去掉都有的字符剩下的不同字符,然后浪费了一个小时写C。。。。还好过了D,避免掉分。。
不过A题没注意测边缘数据,B题没注意负数取模,D题没过样例就交确实是不应该。。。话说回来,如果C不理解错题意,应该可以在40min左右过,D题可以在1h左右过,这样又一个小时4题,就重回1700了。。。不过这不是重点,重点是补完这场的C和E然后滚回实验室刷紫书。。。队友都刷到第7章了。。
原文:http://www.cnblogs.com/--560/p/4858654.html