首页 > 代码库 > 洛谷11月月赛round.1
洛谷11月月赛round.1
#2 thwfhk 240 (801ms) 100 100 40
P2246 SAC#1 - Hello World（升级版）
题目背景
一天，智障的pipapi正在看某辣鸡讲义学程序设计。
题目描述
在讲义的某一面，他看见了一篇文章。这篇文章由英文字母（大小写均有）、数字、和空白字符（制表/空格/回车）构成。
pipapi想起了他最近刚刚学会写的Hello World程序。他非常好奇，这篇文章中，“HelloWorld”作为子序列到底出现过多少次呢？
由于papapi是个智障，大小写对于他而言毫无区别；因此，“hEllOWorLD”这样的子序列也是可以接受的。O和W之间的空格是也是可以少的；也就是说，“HelloWorld”是可以的。根据标程的意思，就是没有空格，不用考虑空格的情况。
两个子序列相同当且仅当它们每一个字符所在的位置都相同。
由于答案可能很大，请输出结果对1000000007(10^9+7)的余数。
输入输出格式
输入格式：
输入包含若干行。这些行的内容共同构成一篇文章。
文章以EOF（文件结尾）结束。
输出格式：
输出仅包含一个整数，表示这篇文章中“Hello World”出现的次数。
输入输出样例
HhEeLlLlOoWwOoRrLlDd
1536
Gou Li Guo Jia Sheng Si YiQi Yin Huo Fu Bi Qu ZhiRiver can feed peopleAlso can race boatsHall Ellen Ok Words locked
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!”。
输入输出样例
4 4 21 22 33 44 1
1 3
4 6 21 22 33 44 11 32 4
How oversuspicious you are, SOL!
4 0 2
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个数，要求将它们分成若干连续的段。
要求：
有m对给定的数不能被分到同一段。
分出一个段的代价是
，其中K和S均为给定的常数，而P则是该段中所有数的最大值，Q是该段中所有数的最小值。
- 要求你求出每段代价之和最小的分段方案。
输入输出格式
输入格式：
第一行两个正整数n和m，表示数的个数和不能共存的m对数。
第二行两个非负整数K和S，含义见题面。
第三行n个非负整数，即给定的n个数。
接下来m行每行2个数和
，表示
和
这两个编号的数不能共存。（编号从1开始）
输出格式：
输出仅一行，表示最小的每段代价之和。
输入输出样例
5 23 12 3 12 14 162 33 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