万里无云，又是平静的一天。
3843. 寻找羔羊(agnus) (Standard IO)
Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits
Goto ProblemSetOn遍历串，找到s就判一下是否形成agnus，如果形成就统计（乘法原理）。
1 #include<bits/stdc++.h> 2 using namespace std; 3 char c[30010]; 4 bool isagnus(int i){ 5 return (c[i-4]=='a'&&c[i-3]=='g'&&c[i-2]=='n'&&c[i-1]=='u'); 6 } 7 int nxt; 8 long long ans; 9 int main(){ 10 cin>>c; 11 nxt=-1; 12 int len=strlen(c); 13 for(int i=0;i<len;i++){ 14 if(c[i]=='s'){ 15 if(isagnus(i)){ 16 ans+=(i-4-nxt)*(len-i); 17 nxt=i-4; 18 } 19 } 20 } 21 printf("%d",ans); 22 return 0; 23 }
3844. 统计损失(count) (Standard IO)
Time Limits: 1000 ms Memory Limits: 524288 KB Detailed Limits
Goto ProblemSet考虑dp，用f[i][0/1]分别表示从以i为根节点的子树中，经过点i而是否上去的路径答案。
发现处理f[i][0]时复杂度似乎太高，考虑优化：
用v表示f[v][1]：
这样就能在线维护了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 int x=0,f=1; 5 char c=getchar(); 6 while(!isdigit(c)){ 7 if(c=='-') f=-1; 8 c=getchar(); 9 } 10 while(isdigit(c)){ 11 x=(x<<1)+(x<<3)+(c^48); 12 c=getchar(); 13 } 14 return x*f; 15 } 16 typedef long long ll; 17 const int N=1e5+10; 18 const int p=10086; 19 ll val[N]; 20 ll f[N][2]; 21 int n; 22 struct edge{ int to,nxt; }e[N<<1]; 23 int head[N<<1],cnt; 24 void addedge(int from,int to){e[++cnt]=(edge){to,head[from]};head[from]=cnt;} 25 void dfs(int u,int fa){ 26 f[u][1]=(val[u])%p; 27 ll tot=0,sum=0; 28 for(int i=head[u];i;i=e[i].nxt){ 29 int v=e[i].to; 30 if(v==fa) continue; 31 dfs(v,u); 32 tot=f[v][1]; 33 f[u][0]=(f[u][0]+tot*sum*val[u])%p; 34 sum=(sum+tot)%p; 35 f[u][1]=(f[u][1]+f[v][1]*val[u])%p; 36 } 37 } 38 int main(){ 39 n=read(); 40 for(int i=1;i<=n;i++) val[i]=read(); 41 for(int i=1,x,y;i<n;i++){ 42 x=read(),y=read(); 43 addedge(x,y); 44 addedge(y,x); 45 } 46 dfs(1,0); 47 ll ans=0; 48 for(int i=1;i<=n;i++){ 49 ans=(ans+f[i][0]+f[i][1])%p; 50 } 51 printf("%lld",ans); 52 return 0; 53 }
3845. 简单题(simple) (Standard IO)
Time Limits: 1000 ms Memory Limits: 524288 KB Detailed Limits
Goto ProblemSet分析题。
发现如果存在一个图满足条件，那么它一定是一条编号连续的链，用一些边将其中的点连接。
又发现这道题不用图论，直接dp即可（找的就是不相交线段条数）。
1 #include<bits/stdc++.h> 2 #pragma GCC optimize(3) 3 using namespace std; 4 int read(){ 5 int x=0,f=1; 6 char c=getchar(); 7 while(!isdigit(c)){ 8 if(c=='-') f=-1; 9 c=getchar(); 10 } 11 while(isdigit(c)){ 12 x=(x<<1)+(x<<3)+(c^48); 13 c=getchar(); 14 } 15 return x*f; 16 } 17 const int N=2e5+10; 18 int n,m; 19 int f[N]; 20 int l[N]; 21 int main(){ 22 n=read();m=read(); 23 for(register int i=1;i<=m;i++){ 24 int ll=read(),rr=read(); 25 if(ll>rr) swap(ll,rr); 26 if(ll<rr-1){ 27 l[rr]=max(l[rr],ll); 28 } 29 } 30 for(register int i=1;i<=n;i++){ 31 if(l[i]) f[i]=max(f[i-1],f[l[i]]+1); 32 else f[i]=f[i-1]; 33 } 34 printf("%d",f[n]+n-1); 35 return 0; 36 }