A
区间DP
#include<stdio.h> #include<string.h> #include<algorithm> #include<string> #include<iostream> using namespace std; #define MAXN 1009 #define inf 10007 typedef __int64 ll; char s[MAXN]; int dp[MAXN][MAXN]; int main() { int t,ca; scanf("%d",&t); ca=1; while(t--) { scanf("%s",s+1); int len=strlen(s+1); for(int i=1;i<=len;i++) dp[i][i]=1; for(int l=1;l<=len;l++) { for(int j=1;j+l-1<=len;j++) { int en=j+l-1; dp[j][en]=(dp[j+1][en]+dp[j][en-1]-dp[j+1][en-1]+inf)%inf; if(s[j]==s[en]) dp[j][en]=(dp[j][en]+dp[j+1][en-1]+1)%inf; } } printf("Case %d: %d ",ca++,dp[1][len]); } return 0; }
D
强连通 有一点点逆向思维 去掉的边 是缩点 的入度或者出度为0 num[i]*(n-num[i]) 最小
#include<stdio.h> #include<string.h> #include<algorithm> #include<string> #include<iostream> #include<stack> using namespace std; #define MAXN 100109 #define inf 1e12+7 typedef __int64 ll; int head[MAXN],dfn[MAXN],low[MAXN],fa[MAXN],c1[MAXN],in[MAXN],out[MAXN]; int k,cnt,num; bool vis[MAXN]; stack<int>s; struct node { int next,v,u; }edge[MAXN]; void add(int u,int v) { edge[cnt].v=v; edge[cnt].u=u; edge[cnt].next=head[u]; head[u]=cnt++; } void dfs(int u) { low[u]=dfn[u]=k++; vis[u]=1; s.push(u); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(!dfn[v]) { dfs(v); low[u]=min(low[u],low[v]); } else if(vis[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { num++; while(!s.empty()) { int now=s.top(); s.pop(); vis[now]=0; fa[now]=num; c1[num]++; if(now==u) break; } } } int main() { int t; scanf("%d",&t); int ca=1; while(t--) { int n,m; scanf("%d%d",&n,&m); memset(head,-1,sizeof(vis)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(vis,0,sizeof(vis)); memset(c1,0,sizeof(c1)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); cnt=0; for(int i=1;i<=m;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); } num=0; k=1; for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i); printf("Case %d: ",ca++); if(num==1) printf("-1 "); else { for(int i=0;i<cnt;i++) { if(fa[edge[i].u]!=fa[edge[i].v]) { in[fa[edge[i].v]]++; out[fa[edge[i].u]]++; } } ll mx=0; //printf("%d ",num); for(int i=1;i<=num;i++) { //printf("in %d out %d ",in[i],out[i]); if(in[i]==0||out[i]==0) { mx=max(mx,(ll)n*(n-1)-m-(ll)c1[i]*(n-c1[i])); } } printf("%I64d ",mx); } } return 0; }
G
线段树维护 第i个位子的 是否能成一个组
新来的 那么 1 那么 大一的 小1的更新为 0 求和 离线
#include<stdio.h> #include<string.h> #include<algorithm> #include<string> #include<iostream> #include<stack> using namespace std; #define MAXN 100010 #define inf 1e12+7 typedef __int64 ll; int z[MAXN]; struct node { int l,r,w; }tree[MAXN<<2]; struct p1 { int l,r,id; }x[MAXN]; bool cmp(p1 a,p1 b) { return a.r<b.r; } void Build(int l,int r,int a) { tree[a].l=l; tree[a].r=r; tree[a].w=0; if(l==r) return ; int mid=(l+r)>>1; Build(l,mid,a<<1); Build(mid+1,r,a<<1|1); } void update(int l,int r,int ind,int w,int a) { if(l==r) { tree[a].w+=w; return ; } int mid=(l+r)>>1; if(ind<=mid) update(l,mid,ind,w,a<<1); else update(mid+1,r,ind,w,a<<1|1); tree[a].w=tree[a<<1].w+tree[a<<1|1].w; } int Ques(int l,int r,int a1,int b1,int a) { if(a1<=l&&r<=b1) return tree[a].w; int mid=(l+r)>>1; int ans=0; if(a1<=mid) ans=ans+Ques(l,mid,a1,b1,a<<1); if(b1>mid) ans=ans+Ques(mid+1,r,a1,b1,a<<1|1); return ans; } int pos[MAXN]; int ans[MAXN]; int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&z[i]); pos[z[i]]=i; } for(int i=1;i<=m;i++) { scanf("%d%d",&x[i].l,&x[i].r); x[i].id=i; } sort(x+1,x+m+1,cmp); int cnt=1; Build(1,n,1); for(int i=1;i<=n;i++) { update(1,n,i,1,1); if(z[i]-1>0&&pos[z[i]-1]<i) update(1,n,pos[z[i]-1],-1,1); if(z[i]+1<=n&&pos[z[i]+1]<i) update(1,n,pos[z[i]+1],-1,1); while(cnt<=m&&x[cnt].r<=i) { ans[x[cnt].id]=Ques(1,n,x[cnt].l,i,1); cnt++; } } for(int i=1;i<=m;i++) printf("%d ",ans[i]); } return 0; }
H
斐波那契
#include<stdio.h> #include<string.h> #include<algorithm> #include<string> #include<iostream> using namespace std; #define MAXN 10090 #define inf 10007 typedef __int64 ll; char z[MAXN]; int f[MAXN]; int main() { int t; scanf("%d",&t); int ca=1; f[0]=f[1]=1; for(int i=2;i<MAXN;i++) { f[i]=(f[i-1]+f[i-2])%inf; } while(t--) { scanf("%s",z); int ans=1; int len=strlen(z); int cnt=0; for(int i=1;i<len;i++) { if(z[i]=='e'&&z[i-1]=='h') { cnt++; i++; } else { ans=(ans*f[cnt])%inf; cnt=0; } } ans=(ans*f[cnt])%inf; printf("Case %d: %d ",ca++,ans); } return 0; }
K
最后一个数的 奇偶
#include<stdio.h> #include<string.h> #include<algorithm> #include<string> #include<iostream> using namespace std; #define MAXN 10090 #define inf 10007 typedef __int64 ll; int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); int a; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&a); } } if(a) printf("Alice "); else printf("Bob "); } return 0; }