T1
模拟
#include <algorithm> #include <cstring> #include <cstdio> #define N 100005 struct node { int x,y; bool operator<(node a)const { return x<a.x; } }pp[N]; int len,sum,tot=1; char str[N]; int main(int argc,char *argv[]) { freopen("cross.in","r",stdin); freopen("cross.out","w",stdout); scanf("%s",str+1); len=strlen(str+1); for(register int i=0;i<=25;++i) { for(register int j=1;j<=len;++j) { if(i==str[j]-'a') { if(pp[tot].y) pp[++tot].x=j; else { if(!pp[tot].x) pp[tot].x=j; else pp[tot].y=j; } } } } std::sort(pp+1,pp+1+tot); for(register int i=1;i<=tot;++i) { int x1=pp[i].x,y1=pp[i].y; for(register int j=i+1;j<=tot;++j) { int x2=pp[j].x,y2=pp[j].y; if(x2>y1) break; if((x2>x1&&x2<y1&&y2>y1)) sum++; } } printf("%d ",sum); fclose(stdin); fclose(stdout); return 0; }
T2
二分+dijkstra 85分
正解不知道是啥
#include <cstring> #include <cstdio> #include <queue> #define N 4005 #define inf 0x3f3f3f3f using namespace std; bool vis[N<<1],tp[505][505]; int n,m,q,k,cnt,ans=inf,far[N],to[N<<1],pre[N],head[N<<1],nextt[N<<1],val[N<<1],opt[N<<1]; struct node { int x,y; bool operator<(node a)const { return y>a.y; } }; priority_queue<node>Q; inline int min(int a,int b) {return a>b?b:a;} bool check(int x) { int use=0; for(register int i=1;i<=n;++i) vis[i]=false,far[i]=inf; far[1]=0; Q.push((node){1,far[1]}); for(node now;!Q.empty();) { now=Q.top();Q.pop(); if(vis[now.x]) continue; vis[now.x]=true; for(register int i=head[now.x];i;i=nextt[i]) { int v=to[i]; if(far[v]>far[now.x]+val[i]&&opt[i]==1) { far[v]=far[now.x]+val[i]; pre[v]=now.x; if(!vis[v]) Q.push((node){v,far[v]}); } else if(far[v]>far[now.x]+val[i]&&opt[i]==2&&val[i]<=x) { far[v]=far[now.x]+val[i]; pre[v]=now.x; if(!vis[v]) Q.push((node){v,far[v]}); } } } for(register int i=n;pre[i];i=pre[i]) if(tp[pre[i]][i]) use++; if(use<=k) {ans=min(ans,far[n]);return true;} return false; } int main(int argc,char *argv[]) { freopen("move.in","r",stdin); freopen("move.out","w",stdout); scanf("%d%d%d%d",&n,&m,&q,&k); for(int u,v,w;m--;) { scanf("%d%d%d",&u,&v,&w); nextt[++cnt]=head[u];to[cnt]=v;val[cnt]=w; head[u]=cnt;opt[cnt]=1; } for(int u,v,w;q--;) { scanf("%d%d%d",&u,&v,&w); nextt[++cnt]=head[u];to[cnt]=v;val[cnt]=w; head[u]=cnt;opt[cnt]=2; tp[u][v]=1; } if(!k) {check(0) ;printf("%d ",ans);return 0;} int l=0,r=inf; for(register int mid;l<=r;) { mid=(l+r)>>1; if(check(mid)) l=mid+1; else r=mid-1; } printf("%d ",ans); fclose(stdin);fclose(stdout); return 0; }
#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <queue> #include <vector> using namespace std; namespace Solve { typedef pair<int,int> Node; const int MAXN = 500 + 10, MAXM = 2000 + 10, INF = 0x7fffffff/2; int n, m, q, k; int nodes[MAXN][MAXN], nop; int head[MAXN*MAXN], next[MAXN*MAXM*2], to[MAXN*MAXM*2], w[MAXN*MAXM*2], op; int dis[MAXN*MAXN]; void build(int a, int b, int x) { next[++op]=head[a];head[a]=op;to[op]=b;w[op]=x; } int dijkstra(int s, int t, int n) { priority_queue<Node, vector<Node>, greater<Node> > que; for(int i=1;i<=n;i++) dis[i] = INF; dis[s] = 0; que.push(Node(dis[s], s)); while(!que.empty()) { Node u = que.top(); que.pop(); if (dis[u.second] != u.first) continue; for(int pos=head[u.second]; pos; pos=next[pos]) { if (u.first + w[pos] < dis[to[pos]]) { dis[to[pos]] = u.first + w[pos]; que.push(Node(dis[to[pos]], to[pos])); } } } return dis[t] == INF ? -1 : dis[t]; } void solve() { scanf("%d%d%d%d", &n, &m, &q, &k); k = min(k, n); nop = 0; for(int i=0;i<=k;i++) for(int u=1;u<=n;u++) nodes[i][u] = ++nop; for(int i=1;i<=m;i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); for(int j=0;j<=k;j++) build(nodes[j][u], nodes[j][v], w); } for(int i=1;i<=q;i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); for(int j=0;j<k;j++) build(nodes[j][x], nodes[j+1][y], z); } for(int i=0;i<k;i++) build(nodes[i][n], nodes[i+1][n], 0); cout << dijkstra(nodes[0][1], nodes[k][n], nop) << endl; } } int main() { freopen("move.in", "r", stdin); freopen("move.out", "w", stdout); Solve::solve(); return 0; }
T3
20分乱搞
正解树形dp
#include <cstring> #include <cstdio> #include <set> #define N 5005 #define Mod 786433 using namespace std; set<int>se; struct node { int x,y; }e[N]; bool V[N<<1],fw[N]; int n,k,cnt=1,tim,tot,ans,num[N<<1],id[N<<1],fa[N],to[N<<1],siz[N<<1],head[N],nextt[N<<1]; void Dfs1(int x,int pre) { siz[x]=1; fw[x]=true; for(int i=head[x];i;i=nextt[i]) { int v=to[i]; if(v==pre||fw[v]) continue; Dfs1(v,x); siz[x]+=siz[v]; } } void Dfs2(int x,int pre) { fw[x]=true; for(int i=head[x];i;i=nextt[i]) { int v=to[i]; if(siz[v]>=k&&!V[id[i^1]]&&!V[id[i]]) num[++tot]=id[i],V[id[i]]=true,V[id[i^1]]=true; if(v==pre||fw[v]) continue; Dfs2(v,x); } } int find_(int x) {return x==fa[x]?x:fa[x]=find_(fa[x]);} bool check() { int Size[N]; for(int i=1;i<=n;++i) fa[i]=i,Size[i]=0; for(int i=1;i<n;++i) { if(se.find(i)!=se.end()) continue; fa[find_(e[i].y)]=find_(e[i].x); } for(int i=1;i<=n;++i) Size[fa[find_(i)]]++; for(int i=1;i<=n;++i) if(Size[fa[find_(i)]]<k) return false; return true; } void Dfs3(int p) { if(p>tot) return; if(check()) ans=(ans+1)%Mod; for(int i=p+1;i<=tot;++i) { se.insert(num[i]); Dfs3(i); se.erase(num[i]); } } inline void swap(int &m,int &n) { int tmp=n; n=m; m=tmp; } int main(int argc,char *argv[]) { freopen("cut.in","r",stdin); freopen("cut.out","w",stdout); scanf("%d%d",&n,&k); for(int u,v,i=1;i<n;++i) { scanf("%d%d",&u,&v); if(u>v) swap(u,v); nextt[++cnt]=head[u];to[cnt]=v;head[u]=cnt;id[cnt]=i; nextt[++cnt]=head[v];to[cnt]=u;head[v]=cnt;id[cnt]=i; e[i]=(node){u,v}; } Dfs1(1,0); memset(fw,0,sizeof(fw)); Dfs2(1,0); Dfs3(0); printf("%d ",ans); fclose(stdin); fclose(stdout); return 0; }
#include<cstdio> #include<cstdlib> #define N 5555 #define M 786433 using namespace std; typedef long long LL; struct edge { int t,n; }e[N*2]; LL h[N],size[N],f[N][N],g[N],cnt[N]; int n,K,tote; void add(int u,int v) { e[++tote].t=v; e[tote].n=h[u]; h[u]=tote; return ; } void dfs(int u,int fa) { size[u]++; f[u][1]=1; for (int i=h[u];i;i=e[i].n) { int v=e[i].t; if (v==fa) continue; dfs(v,u); for (int j=1;j<=size[u]+size[v];j++) g[j]=0; for (int j=1;j<=size[u];j++) g[j]=cnt[v]*f[u][j]%M; for (int j=1;j<=size[u];j++) for (int k=1;k<=size[v];k++) g[j+k]=(g[j+k]+f[u][j]*f[v][k]%M)%M; for (int j=1;j<=size[u]+size[v];j++) f[u][j]=g[j]; size[u]+=size[v]; } for (int i=K;i<=size[u];i++) cnt[u]=(cnt[u]+f[u][i])%M; return ; } int main() { freopen("cut.in","r",stdin); freopen("cut.out","w",stdout); scanf("%d %d",&n,&K); for (int i=1;i<n;i++) { int u,v; scanf("%d %d",&u,&v); add(u,v); add(v,u); } dfs(1,1); printf("%d ",cnt[1]); fclose(stdin); fclose(stdout); return 0; }