「CF332X」Codeforces Round #193 (Div. 2)
A. Down the Hatch!
阅读+模拟题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define N 100005 #define pa pair<int,int> #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,ans,len; char a[2005]; int main() { n=read(); scanf("%s",a); len=strlen(a); for(int i=n;i<len;i+=n) if(a[i-3]==a[i-2]&&a[i-2]==a[i-1])ans++; printf("%d\n",ans); return 0; } |
B. Maximum Absurdity
每K个的和求出来以后，就是找距离超过K的两个数相加的最大值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define N 100005 #define pa pair<int,int> #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,K,A,B; int a[200005]; ll ans,b[200005],c[200005]; int main() { n=read();K=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=K;i++) b[n-K+1]+=a[n-i+1]; for(int i=n-K;i;i--) b[i]=b[i+1]+a[i]-a[i+K]; for(int i=n-K+1;i;i--) { c[i]=i; if(b[c[i+1]]>b[c[i]])c[i]=c[i+1]; } ll mx=0; for(int i=1;i<=n-2*K+1;i++) { if(b[i]>b[mx])mx=i; if(b[mx]+b[c[i+K]]>b[A]+b[B])A=mx,B=c[i+K]; } printf("%d %d\n",A,B); return 0; } |
C. Students’ Revenge
http://m.blog.csdn.net/blog/u010638776/10044315
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define N 100005 #define pa pair<int,int> #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,p,K; vector<int>ans; struct data{ int a,b,id,val; }a[100005]; bool cmpa(data a,data b) { if(a.a==b.a&&a.b==b.b)return a.val<b.val; if(a.a==b.a)return a.b>b.b; return a.a>b.a; } bool cmpb(data a,data b) { if(a.a==b.a&&a.b==b.b)return a.id<b.id; if(a.b==b.b)return a.a<b.a; return a.b>b.b; } int main() { n=read();p=read();K=read(); for(int i=1;i<=n;i++) a[i].a=read(),a[i].b=read(),a[i].id=i; sort(a+1,a+n+1,cmpb); for(int i=1;i<=n;i++) a[i].val=i; sort(a+1,a+n-(p-K)+1,cmpa); int mx=0; for(int i=1;i<=K;i++) { ans.push_back(a[i].id); mx=max(mx,a[i].val); } sort(a+1,a+n+1,cmpb); for(int i=mx+1;i<=n&&ans.size()<p;i++) ans.push_back(a[i].id); for(int i=0;i<ans.size();i++) printf("%d ",ans[i]); return 0; } |
D. Theft of Blueprints
wmd神犇：http://blog.csdn.net/wmdcstdio/article/details/44755115
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<map> #include<set> #include<cmath> #include<deque> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll n,K,ans,f[2005],w[2005]; int main() { n=read();K=read(); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { int x=read(); if(x>=0)f[i]+=x,f[j]+=x,w[i]++,w[j]++; } if(K==2) { for(int i=1;i<=n;i++) ans+=f[i]*(w[i]-1); ans=2*ans/n/(n-1); } else { for(int i=1;i<=n;i++) ans+=f[i]; ans/=n; } cout<<ans<<endl; return 0; } |
E. Binary Key
枚举串中1的个数记忆化搜索
字符可以是空格QAQ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include<map> #include<set> #include<cmath> #include<deque> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char p[1000005],s[205]; int a,b,K,cnt; int vis[2005][205]; char ch[2005],ans[2005]; bool flag; bool check(int x,int k) { while(x<=a&&k<=b) { if(p[x]!=s[k])return 0; x+=K;k+=cnt; } if(x<=a||k<=b)return 0; return 1; } bool dfs(int x,int k) { if(k>cnt) { for(int i=x;i<=K;i++)ch[i]='0'; return 1; } if(x>K||vis[x][k]==cnt)return 0; vis[x][k]=cnt; if(dfs(x+1,k)) { ch[x]='0'; return 1; } else if(check(x,k)) { ch[x]='1'; if(dfs(x+1,k+1))return 1; ch[x]='0'; } return 0; } int main() { gets(p+1);a=strlen(p+1); gets(s+1);b=strlen(s+1); K=read(); ans[1]='z'; int t1=a/K+1,t2=a/K; for(cnt=1;cnt<=b;cnt++) { if(b<cnt*t2||b>cnt*t1)continue; if(dfs(1,1)&&strcmp(ch+1,ans+1)<0) { flag=1; copy(ch+1,ch+K+1,ans+1); } } if(!flag)puts("0"); else for(int i=1;i<=K;i++)printf("%c",ans[i]); return 0; } |
Subscribe
计数器 9786070
OI 课件=>
OI 课件=>