比赛链接 http://codeforces.com/contest/1009
A.Game Shopping
这种题真是.. 打开网页 1min 读题 3min 思考 0min 写代码 0.5min..
- #include <cstdio>
- #include <cctype>
- #include <algorithm>
- #define gc() getchar()
- const int N=1e3+5;
- int n,m,cost[N],A[N];
- inline int read()
- {
- register int now=0;register char c=gc();
- for(;!isdigit(c);c=gc());
- for(;isdigit(c);now=now*10+c-'0',c=gc());
- return now;
- }
- int main()
- {
- n=read(), m=read();
- for(int i=1; i<=n; ++i) cost[i]=read();
- for(int i=1; i<=m; ++i) A[i]=read();
- int now=1,ans=0;
- for(int i=1; i<=n && now<=m; ++i)
- if(cost[i]<=A[now]) ++ans, ++now;
- printf("%d\n",ans);
- return 0;
- }
- B.Minimum Ternary String
- #include <cstdio>
- #include <cctype>
- #include <cstring>
- #include <algorithm>
- #define gc() getchar()
- const int N=1e5+7;
- int n;
- char s[N],ans[N];
- int main()
- {
- scanf("%s",s+1), n=strlen(s+1);
- int cnt[5],now;
- cnt[0]=cnt[1]=cnt[2]=0;
- for(now=1; now<=n; ++now)
- if(s[now]!='2') ++cnt[s[now]-'0'];
- else break;
- for(int i=1; i<=cnt[0]; ++i) ans[i]='0';
- for(int i=cnt[0]+1; i<=cnt[0]+cnt[1]; ++i) ans[i]='1';
- cnt[0]=cnt[1]=cnt[2]=0;
- for(int i=now; i<=n; ++i) ++cnt[s[i]-'0'];
- for(int i=now; i<now+cnt[1]; ++i) ans[i]='1';
- s[n+1]='3';
- for(int i=now+cnt[1]; i<=n; ++i)
- {
- while(s[now]=='1') ++now;
- ans[i]=s[now++];
- }
- puts(ans+1);
- return 0;
- }/*
- 102012012
- */
- C.Annoying Present
- #include <cstdio>
- #include <cctype>
- #include <algorithm>
- #define gc() getchar()
- #define eps 1e-8
- typedef long long LL;
- const int N=1e5+7;
- inline int read()
- {
- register int now=0,f=1;register char c=gc();
- for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
- for(;isdigit(c);now=now*10+c-'0',c=gc());
- return now*f;
- }
- int main()
- {
- int n=read(), m=read();
- LL sum=0, sumX=0, C1, C2=1ll*n*(n-1)>>1;//n/2 写成 n>>1 略显乱
- if(n&1) C1=1ll*(n>>1)*((n>>1)+1);
- else C1=1ll*(n>>1)*((n>>1)+1)-1ll*(n>>1);
- LL x,d;
- for(int i=1; i<=m; ++i)
- {
- x=read(), d=read(), sumX+=x;
- if(d>0) sum+=C2*d;
- else if(d<0) sum+=C1*d;
- }
- printf("%.8lf",1.0*(sum+1ll*n*sumX)/n);
- return 0;
- }
- D.Relatively Prime Graph
靠 欺负我读英文题目不仔细吗 图必须连通..
于是 WA*3. 看了数据才 A..
这破题 rank1000 + 了啊啊啊
而且这题 n^2 纯暴力都能过 太没意思了吧
- #include <cmath>
- #include <cstdio>
- #include <cctype>
- #include <algorithm>
- #define gc() getchar()
- #define pr std::pair<int,int>
- #define mp std::make_pair
- const int N=1e5+7;
- int n,m,cnt,P[N],fac[N],sum;
- pr A[3000005];
- bool not_P[N];
- int gcd(int x,int y){
- return y?gcd(y,x%y):x;
- }
- void Pre(int n)
- {
- for(int i=2; i<=n; ++i)
- {
- if(!not_P[i]) P[++cnt]=i;
- for(int j=1; j<=cnt&&i*P[j]<=n; ++j)
- {
- not_P[i*P[j]]=1;
- if(!(i%P[j])) break;
- }
- }
- for(int i=2; i<=n; ++i)
- if(!not_P[i]) fac[i]=i;
- else{
- for(int j=2; j<=i; ++j)
- if(!(i%j)) {fac[i]=j; break;}
- }
- }
- int main()
- {
- scanf("%d%d",&n,&m);// printf("%d\n",m);
- if(m<n-1) return puts("Impossible"),0;//...
- Pre(n);
- for(int i=2; i<=n && sum<m; ++i) A[++sum]=mp(1,i);
- for(int x=1; x<=cnt && sum<m; ++x)
- {
- int i=P[x];
- for(int j=i+1; j<=n && sum<m; )
- {
- int k=std::min(j+fac[i]-1,n+1);//n+1!
- for(int l=j; l<k && sum<m; ++l) A[++sum]=mp(i,l);
- j=k+1;
- }
- }
- for(int i=4; i<=n && sum<m; ++i)
- {
- if(!not_P[i]) continue;
- for(int j=i+1; j<=n && sum<m; )
- {
- int k=std::min(j+fac[i]-1,n+1);
- for(int l=j; l<k && sum<m; ++l)
- if(gcd(i,l)==1) A[++sum]=mp(i,l);
- j=k+1;
- }
- }
- if(sum<m) puts("Impossible");
- else
- {
- puts("Possible");
- for(int i=1; i<=m; ++i)
- printf("%d %d\n",A[i].first,A[i].second);
- }
- return 0;
- }
比赛结束后
来源: http://www.bubuko.com/infodetail-2685801.html