首页 > 代码库 > 洛谷11月月赛round.1

洛谷11月月赛round.1

太感动了
#2 thwfhk 240 (801ms) 100 100 40
 
又一张明信片,话说10月的怎么还没收到
 



 

P2246 SAC#1 - Hello World(升级版)

题目背景

一天,智障的pipapi正在看某辣鸡讲义学程序设计。

题目描述

在讲义的某一面,他看见了一篇文章。这篇文章由英文字母(大小写均有)、数字、和空白字符(制表/空格/回车)构成。

pipapi想起了他最近刚刚学会写的Hello World程序。他非常好奇,这篇文章中,“HelloWorld”作为子序列到底出现过多少次呢?

由于papapi是个智障,大小写对于他而言毫无区别;因此,“hEllOWorLD”这样的子序列也是可以接受的。O和W之间的空格是也是可以少的;也就是说,“HelloWorld”是可以的。根据标程的意思,就是没有空格,不用考虑空格的情况。

两个子序列相同当且仅当它们每一个字符所在的位置都相同。

由于答案可能很大,请输出结果对1000000007(10^9+7)的余数。

输入输出格式

输入格式:

 

输入包含若干行。这些行的内容共同构成一篇文章。

文章以EOF(文件结尾)结束。

 

输出格式:

 

输出仅包含一个整数,表示这篇文章中“Hello World”出现的次数。 

 

输入输出样例

输入样例#1:
HhEeLlLlOoWwOoRrLlDd
输出样例#1:
1536
输入样例#2:
Gou Li Guo Jia Sheng Si YiQi Yin Huo Fu Bi Qu ZhiRiver can feed peopleAlso can race boatsHall Ellen Ok Words locked 
输出样例#2:
273

说明

记n为输入的文章的长度(字符数)。

对于20%的数据,n <= 20。

对于50%的数据,n <= 500。

对于所有的数据,15 <= n <= 500000。


 

直接秒掉,f[i][j]前i个0到j匹配方案数,滚掉第一维

 

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int N=5e5+5,MOD=1e9+7;int n,m,p,mp[300];char c;int f[12];int main(){    char s[12]="helloworld";    for(int i=0;i<10;i++) mp[s[i]]=1;    while((c=getchar())!=EOF){    if((c>=A&&c<Z)||(c>=a&&c<=z)){        if(c<a) c+=a-A;        if(!mp[c]) continue;        //printf("%c\n",c);        if(c==h) f[1]++;        else if(c==e) f[2]+=f[1],f[2]%=MOD;        else if(c==l){            f[4]+=f[3],f[4]%=MOD;            f[3]+=f[2],f[3]%=MOD;            f[9]+=f[8],f[9]%=MOD;        }else if(c==o){            f[5]+=f[4],f[5]%=MOD;            f[7]+=f[6],f[7]%=MOD;        }else if(c==w) f[6]+=f[5],f[6]%=MOD;        else if(c==r) f[8]+=f[7],f[8]%=MOD;        else if(c==d) f[10]+=f[9],f[10]%=MOD;            }    }    printf("%d",f[10]);}

 

 




P2247 SAC#1 - ACOJ云评测计划

题目背景

本题由世界上最蒟蒻最辣鸡最撒比的SOL提供。

寂月城网站是完美信息教室的官网。地址:http://191.101.11.174/mgzd 。

题目描述

ACOJ的服务器简直是差到了一个令人发指的地步。于是SAC的出题人,也就是傻逼SOL,不得不强制要求每一个通过下载ACOJ软件包而搭建的分站,都为主站启动云端评测服务。

云评测服务是由网络来连接的。这样的网络连接是双向的;但是由于地理位置等因素的限制,并不是任意两台服务器都可以直接相连。ACOJ主站已经得到了可以直连的服务器的表,其中包含n个分站(包括主站)以及它们的m条连接情况,可以根据这个来分配各个分站的任务。

有一些分站的服主是SOL的脑残粉。他们会无条件地将他们的服务器提供给SOL。这些ACOJ分站称作“好站”。但是还有一些分站的服主是SOL黑。他们虽然拿到了ACOJ的服务端,但是并不愿意为SOL提供资源,于是利用黑科技关掉了云服务。也就是说,虽然主站仍然认为这些站点存在,但是它们不会起到任何作用——既不能传递通信,也不能进行评测。它们称作“坏站”。

经过千辛万苦的调查,SOL确定了ACOJ云评测系统中有最多k个坏站存在,而且这k个坏站似乎会使得ACOJ的云网络不再联通!大危机!

但是SOL太弱智了,并不能确定是哪k个。于是他请你来帮他找出任意一组可能会使得网络不再联通的k个站点,以便加强防范。

输入输出格式

输入格式:

 

输入包含m+1行。

第1行3个整数n、m、k。

接下来m行,每行两个整数a、b,表示标号为a和b的站点可以直接相连。

 

输出格式:

 

输出包含1行。

不超过k个整数,表示能够将原图割开的任意一组节点组合。

因为使用了Special Judge,所以节点的顺序并不用担心。只需要满足能够割开原图即可。

如果不存在这样的站点集合,输出“How oversuspicious you are, SOL!”;如果网络不存在任何坏站时本来就无法连通,输出“Poor SOL!”。

 

输入输出样例

输入样例#1:
4 4 21 22 33 44 1
输出样例#1:
1 3
输入样例#2:
4 6 21 22 33 44 11 32 4 
输出样例#2:
How oversuspicious you are, SOL!
输入样例#3:
4 0 2
输出样例#3:
Poor SOL!

说明

对于20%的数据,n <= 15。

对于另外20%的数据,n <= 100,k=1。

对于另外20%的数据,n <= 100,k=2。

对于100%的数据,3 <= n <= 500,k <= 3,n-k >= 2,云网络不存在自环和重边。


枚举再求割点

 也可以每次重构图

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;const int N=505;inline int read(){    char c=getchar();int x=0,f=1;    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,m,k,a,b;struct edge{    int v,w,ne;}e[N*N<<1];int h[N],cnt=0;inline void ins(int u,int v){    cnt++;    e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;    cnt++;    e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;}int dfn[N],low[N],dfc,scc,iscut[N],cv,nc;void init(){	for(int i=0;i<=n;i++) dfn[i]=low[i]=iscut[i]=0;	dfc=scc=cv=0;}void dfs1(int u,int fa){ nc++;	dfn[u]=low[u]=++dfc;	int child=0;	for(int i=h[u];i;i=e[i].ne){		int v=e[i].v;		if(!dfn[v]){			child++;			dfs1(v,u);			low[u]=min(low[u],low[v]);			if(low[v]>=dfn[u]) iscut[u]=1;		}else if(v!=fa) low[u]=min(low[u],dfn[v]);	}	if(fa==0&&child==1) iscut[u]=0;	if(iscut[u]) cv=u;}void dfs2(int u,int fa,int del){	dfn[u]=low[u]=++dfc;	int child=0;	for(int i=h[u];i;i=e[i].ne){		int v=e[i].v; if(v==del) continue;		if(!dfn[v]){			child++;			dfs2(v,u,del);			low[u]=min(low[u],low[v]);			if(low[v]>=dfn[u]) iscut[u]=1;		}else if(v!=fa) low[u]=min(low[u],dfn[v]);	}	if(fa==0&&child==1) iscut[u]=0;	if(iscut[u]) cv=u;}void dfs3(int u,int fa,int del1,int del2){	dfn[u]=low[u]=++dfc;	int child=0;	for(int i=h[u];i;i=e[i].ne){		int v=e[i].v; if(v==del1||v==del2) continue;		if(!dfn[v]){			child++;			dfs3(v,u,del1,del2);			low[u]=min(low[u],low[v]);			if(low[v]>=dfn[u]) iscut[u]=1;		}else if(v!=fa) low[u]=min(low[u],dfn[v]);	}	if(fa==0&&child==1) iscut[u]=0;	if(iscut[u]) cv=u;}int main(){	n=read();m=read();k=read();	for(int i=1;i<=m;i++){a=read();b=read();ins(a,b);}		dfs1(1,0);	if(nc<n) {puts("Poor SOL!");return 0;}	else if(cv) {printf("%d",cv);return 0;}		init();	if(k==2){		dfs2(2,0,1);		if(cv){printf("%d %d",1,cv);return 0;}				for(int i=2;i<=n;i++){			init();			dfs2(1,0,i);			if(cv){printf("%d %d",i,cv);return 0;} 		}	}else if(k==3){		dfs3(3,0,1,2);		if(cv){printf("%d %d %d",1,2,cv);return 0;}		for(int i=3;i<=n;i++){			init();			dfs3(2,0,1,i);			if(cv){printf("%d %d %d",1,i,cv);return 0;}		}		for(int i=2;i<=n;i++)			for(int j=i+1;j<=n;j++){				init();				dfs3(1,0,i,j);				if(cv){printf("%d %d %d",i,j,cv);return 0;} 			}	}	puts("How oversuspicious you are, SOL!");	return 0;}

 




 

P2248 分段

题目描述

给定你n个数技术分享,要求将它们分成若干连续的段。

要求:

  1. 有m对给定的数不能被分到同一段。

  2. 分出一个段的代价是技术分享,其中K和S均为给定的常数,而P则是该段中所有数的最大值,Q是该段中所有数的最小值。

  3. 要求你求出每段代价之和最小的分段方案。

输入输出格式

输入格式:

 

第一行两个正整数n和m,表示数的个数和不能共存的m对数。

第二行两个非负整数K和S,含义见题面。

第三行n个非负整数,即给定的n个数。

接下来m行每行2个数技术分享技术分享,表示技术分享技术分享这两个编号的数不能共存。(编号从1开始)

 

输出格式:

 

输出仅一行,表示最小的每段代价之和。

 

输入输出样例

输入样例#1:
5 23 12 3 12 14 162 33 1
输出样例#1:
11

说明

对于10%的数据,技术分享

对于30%的数据,技术分享

对于另外10%的数据,技术分享

对于另外30%的数据,技术分享

对于100%的数据,1≤m,n≤100000,0≤K,S,a_i≤100000,1≤pi,qi≤n,pi≠qi。

 


 

想了个O(n^2)的DP就打上了,特判了一下S==0,好像没什么用

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int N=1e5+5;const ll INF=1e18;inline int read(){    char c=getchar();int x=0,f=1;    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,m,K,S,a[N],pos[N],p,q;int mx[N][17],mn[N][17];void initRMQ(){    for(int i=1;i<=n;i++) mx[i][0]=mn[i][0]=a[i];        for(int j=1;j<=16;j++)        for(int i=1;i+(1<<j)-1<=n;i++)            mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]),            mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);}int rmq(int l,int r){    int k=log(r-l+1)/log(2);    return max(mx[l][k],mx[r-(1<<k)+1][k])-min(mn[l][k],mn[r-(1<<k)+1][k]);}ll f[N];void dp(){    for(int i=1;i<=n;i++){        f[i]=INF;int p=pos[i];        for(int j=i-1;j>=p;j--){            f[i]=min(f[i],f[j]+K+(ll)S*(ll)rmq(j+1,i));            p=max(p,pos[j]);        }    }}struct range{    int a,b;    bool operator <(const range &r)const{return b<r.b;}}d[N];void sol(){    int cnt=0;    for(int i=1;i<=n;i++) if(pos[i]) d[++cnt]=(range){pos[i],i};        sort(d+1,d+1+cnt);    int last=0,ans=0;    for(int i=1;i<=cnt;i++){        if(d[i].a<=last) continue;        last=d[i].b;        ans++;    }    printf("%d",ans*K+K);}int main(){    n=read();m=read();K=read();S=read();    for(int i=1;i<=n;i++) a[i]=read();    for(int i=1;i<=m;i++){        p=read();q=read();        if(p>q) swap(p,q);        pos[q]=max(pos[q],p);    }    if(S==0){        sol();    }else{            initRMQ();        dp();        printf("%lld",f[n]);    }}

 

洛谷11月月赛round.1