Codeforces Round #138 (Div. 一)

Codeforces Round #138 (Div. 1)

转载请注明出处，谢谢http://blog.****.net/acm_cxlove/article/details/7854526 by---cxlove

再一次在DIV1中怒跪~~~果断应该回到DIV2历练历练

A. Bracket Sequence

找出一个子串，而且它的括号匹配是规范的，要求里面的"[]"对数最多，输出任意一解

其实嘛，括号匹配就是一个堆栈模拟，可以想着想着就觉得有好多细节需要考虑，一直不想写

到了最后才写了枚举+栈模拟的，噗。。。结果必要没过嘛

其实没有那么复杂，记录从头到当前位置的[]个数，而且记录堆栈内每一个字符在串中的位置

当出现括号匹配，也就是弹出堆栈的时候就更新一下，注意堆栈为空的情况

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#define inf 110000000
#define M 10005
#define N 100005
#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(a))
#define LL long long
using namespace std;
char str[N];
int sum[N];
int main(){
   while(scanf("%s",str)!=EOF){
        stack<int>s;
        int l=strlen(str);
		int ans=0,x,y;
		sum[0]=(str[0]=='[');s.push(0);
		for(int i=1;i<l;i++){
			sum[i]=sum[i-1]+(str[i]=='[');
			if(!s.empty()){
				char ch=str[s.top()];
				if((ch=='('&&str[i]==')')||(ch=='['&&str[i]==']')){
					s.pop();
					if(s.empty()&&sum[i]>ans){
						ans=sum[i];
						x=0;y=i;
					}
					else if(!s.empty()&&ans<sum[i]-sum[s.top()]){
						ans=sum[i]-sum[s.top()];
						x=s.top()+1;
						y=i;
					}
				}
				else s.push(i);
			}
			else s.push(i);
		}
		printf("%d\n",ans);
		if(ans){
			for(int i=x;i<=y;i++)
				printf("%c",str[i]);
			puts("");
		}
   }
   return 0;
}

B. Two Strings

给出两个串a,b。问a中的每一个字符是否都出现在a的与b相同的子串中。

哎，被詹姐教育了番。。。

计算第一个字符，向前向后能匹配到的最远位置，看看之和是否大于模式串的长度

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#define inf 110000000
#define M 10005
#define N 200005
#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(a))
#define LL long long
#define MOD 1000000007
using namespace std;
int front[N],back[N];
char a[N],b[N];
int pos[200];
int main(){
	while(scanf("%s%s",a+1,b+1)!=EOF){
		int l1=strlen(a+1),l2=strlen(b+1);
		mem(pos,0);
		int j=1;
		for(int i=1;i<=l1;i++){
			if(j<=l2&&a[i]==b[j]){
				pos[a[i]]=j;
				j++;
			}
			front[i]=pos[a[i]];
		}
		mem(pos,0);
		j=l2;
		for(int i=l1;i>0;i--){
			if(j>0&&a[i]==b[j]){
				pos[a[i]]=l2-j+1;
				j--;
			}
			back[i]=pos[a[i]];
		}
		bool flag=true;
		for(int i=1;i<=l1&&flag;i++)
			if(front[i]+back[i]<=l2)
				flag=false;
		puts(flag?"Yes":"No");
	}
	return 0;
}

C. Partial Sums

给出一个序列，用这个序列的前i项和替换原来的序列，执行K次，输出最后的结果

其实可以YY出一个序列，表示当前这个数，是由多少个ai组成的。

比如当N=4，K=3的时候

4 1

10 4 1

20 10 4 1

只需要得到这个矩阵就可以了，可以发现是一个组合数C(i+k,i)

比如20=C(6,3) 10=C(5,2) 4=C(4,1) 1=C(3,0)

但是我当时傻叉地把组合数搞错了，我连C(N,M)=C(N,N-M)都没反应过来

哭瞎~~~~这里可以先预处理好这些组合数，组合数就暴力求就行了，不过需要逆元

又学到了新的姿势，不过2000个数，可以直接快速幂来求

inv[i]表示i对于MOD的逆元

则 inv[i]=(-MOD/i*inv[MOD%i]); 这样通过递推O(1)就能求出每一个的逆元

从zhou神那得到了证明，其实就是证明这个的正确性

两边同时乘以i

inv[i]*i=i*(-MOD/i*inv[MOD%i]); (由逆元性质我们知道，a*inv[a]%MOD=1)

i*(-MOD/i) == (MOD%i)%MOD

-(MOD-MOD%i) == (MOD%i)%MOD

这是显然成立的，得证

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#define inf 110000000
#define M 10005
#define N 2005
#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(a))
#define LL long long
#define MOD 1000000007
using namespace std;
LL inv[N],c[N],a[N];
LL slove(int n,int m){
	LL ans=1;
	for(int i=1;i<=m;i++)
		ans=((ans*inv[i])%MOD*(n-i+1))%MOD;
	return ans;
}
int main(){
	int n,k;
	while(scanf("%d%d",&n,&k)!=EOF){
		for(int i=0;i<n;i++)
			scanf("%I64d",&a[i]);
		if(k==0){
			for(int i=0;i<n;i++) printf("%I64d ",a[i]);
			printf("\n");continue;
		}
		inv[0]=inv[1]=1;
		for(int i=2;i<N;i++)
			inv[i]=((-MOD/i*inv[MOD%i])%MOD+MOD)%MOD;
		for(int i=0;i<n;i++)
			c[i]=slove(i+k-1,i);
		for(int i=0;i<n;i++){
			LL ans=0;
			for(int j=0;j<=i;j++)
				ans=(ans+a[j]*c[i-j])%MOD;
			printf("%I64d ",ans);
		}
		puts("");
	}
	return 0;
}

Codeforces Round #138 (Div. 一)

相关推荐