叉叉
|
题目名称 |
叉叉 |
|
程序文件名 |
cross |
|
输入文件名 |
cross.in |
|
输出文件名 |
cross.out |
|
每个测试点时限 |
1秒 |
|
内存限制 |
128MB |
|
测试点数目 |
10 |
|
每个测试点分值 |
10 |
|
是否有部分分 |
无 |
|
试题类型 |
传统 |
题目描述
现在有一个字符串，每个字母出现的次数均为偶数。接下来我们把第一次出现的字母a和第二次出现的a连一条线，第三次出现的和四次出现的字母a连一条线，第五次出现的和六次出现的字母a连一条线...对其他25个字母也做同样的操作。
现在我们想知道有多少对连线交叉。交叉的定义为一个连线的端点在另外一个连线的内部，另外一个端点在外部。
下图是一个例子，共有三对连线交叉（我们连线的时候，只能从字符串上方经过）。
输入格式
一行一个字符串。保证字符串均由小写字母组成，且每个字母出现次数为偶数次。
输出格式
一个整数，表示答案。
样例输入
abaazooabz
样例输出
3
数据范围
对于30% 的数据，字符串长度不超过50。
对于100% 的数据，字符串长度不超过100,000。
思路：模拟
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; char s[100010]; int len,ans; int pos[28],vis[28]; int main(){ freopen("cross.in","r",stdin); freopen("cross.out","w",stdout); scanf("%s",s+1); len=strlen(s+1); for(int i=1;i<=26;i++){ int flag=0,num=0; memset(vis,0,sizeof(vis)); memset(pos,-1,sizeof(pos)); for(int j=1;j<=len;j++){ int x=s[j]-'a'+1; if(s[j]-'a'+1==i&&flag){ ans+=num;flag=0;num=0; } else if(s[j]-'a'+1==i&&flag==0){ flag=j; } else if(flag){ if(vis[s[j]-'a'+1]){ vis[s[j]-'a'+1]=0; if(pos[s[j]-'a'+1]<flag){ num++;pos[s[j]-'a'+1]=-1; } else{ num--;pos[s[j]-'a'+1]=-1; } } else{ num++;vis[s[j]-'a'+1]=1;pos[s[j]-'a'+1]=j; } } else if(flag==0){ if(vis[s[j]-'a'+1]) vis[s[j]-'a'+1]=0,pos[s[j]-'a'+1]=-1; else vis[s[j]-'a'+1]=1,pos[s[j]-'a'+1]=j; } } } cout<<ans/2; } /* aaaaaaaa 0 abababab 2 fgshahafgs 4 agafsdgfsd 7 abaazooabz 3 fgsgsfsdaads 1 abcdacdbcabdacbd 9 absbsbsbsddaskaksa 4 abaaaaaaaabbbbbbbbab 3 ghdgahsgdhasgdhasghdgasgdashgdhasgdgshs 37 */
思路：
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 20010 using namespace std; int n,m,q,k; int tot,tot1; int ans=0x7f7f7f7f; int dis[MAXN],vis[MAXN]; int dis1[MAXN],vis1[MAXN]; int to[MAXN],net[MAXN],cap[MAXN],head[MAXN]; int to1[MAXN],net1[MAXN],cap1[MAXN],head1[MAXN]; struct nond{ int x,y,z; }edge[MAXN]; void add(int u,int v,int w){ to[++tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot; } void add1(int u,int v,int w){ to1[++tot1]=v;cap1[tot1]=w;net1[tot1]=head1[u];head1[u]=tot1; } void spfa(int s){ queue<int>que; memset(vis,0,sizeof(vis)); memset(dis,0x7f,sizeof(dis)); que.push(s); dis[s]=0;vis[s]=1; while(!que.empty()){ int now=que.front(); que.pop(); vis[now]=0; for(int i=head[now];i;i=net[i]) if(dis[to[i]]>dis[now]+cap[i]){ dis[to[i]]=dis[now]+cap[i]; if(!vis[to[i]]){ vis[to[i]]=1; que.push(to[i]); } } } } void spfaa(int s){ queue<int>qu; memset(vis1,0,sizeof(vis1)); memset(dis1,0x7f,sizeof(dis1)); qu.push(s); dis1[s]=0;vis1[s]=1; while(!qu.empty()){ int now=qu.front(); qu.pop(); vis1[now]=0; for(int i=head1[now];i;i=net1[i]) if(dis1[to1[i]]>dis1[now]+cap1[i]){ dis1[to1[i]]=dis1[now]+cap1[i]; if(!vis1[to1[i]]){ vis1[to1[i]]=1; qu.push(to1[i]); } } } } int main(){ freopen("move.in","r",stdin); freopen("move.out","w",stdout); scanf("%d%d%d%d",&n,&m,&q,&k); for(int i=1;i<=m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); add1(v,u,w); } for(int i=1;i<=q;i++) scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z); if(k==0){ spfa(1); if(dis[n]==2139062143){ cout<<"-1"; return 0; } else cout<<dis[n]; } else if(k==1){ spfa(1); spfaa(n); ans=dis[n]; if(dis[n]==2139062143){ cout<<"-1"; return 0; } for(int i=1;i<=q;i++){ if(dis[edge[i].x]==2139062143) continue; if(dis[edge[i].y]==2139062143) continue; ans=min(ans,dis[edge[i].x]+dis1[edge[i].y]+edge[i].z); } cout<<ans; } else if(k>=q){ for(int i=1;i<=q;i++) add(edge[i].x,edge[i].y,edge[i].z); spfa(1); if(dis[n]==2139062143){ cout<<"-1"; return 0; } cout<<dis[n]; } else{ spfa(1); cout<<dis[n]-100; } } /* 5 5 2 1 1 2 1 1 3 2 2 4 2 3 4 3 4 5 4 1 4 1 2 5 1 */
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 20010 using namespace std; int n,m,q,k; int tot,tot1; int ans=0x7f7f7f7f; int dis[MAXN],vis[MAXN]; int dis1[MAXN],vis1[MAXN]; int to[MAXN],net[MAXN],cap[MAXN],head[MAXN]; int to1[MAXN],net1[MAXN],cap1[MAXN],head1[MAXN]; struct nond{ int x,y,z; }edge[MAXN]; void add(int u,int v,int w){ to[++tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot; } void add1(int u,int v,int w){ to1[++tot1]=v;cap1[tot1]=w;net1[tot1]=head1[u];head1[u]=tot1; } void spfa(int s){ queue<int>que; memset(vis,0,sizeof(vis)); memset(dis,0x7f,sizeof(dis)); que.push(s); dis[s]=0;vis[s]=1; while(!que.empty()){ int now=que.front(); que.pop(); vis[now]=0; for(int i=head[now];i;i=net[i]) if(dis[to[i]]>dis[now]+cap[i]){ dis[to[i]]=dis[now]+cap[i]; if(!vis[to[i]]){ vis[to[i]]=1; que.push(to[i]); } } } } void spfaa(int s){ queue<int>qu; memset(vis1,0,sizeof(vis1)); memset(dis1,0x7f,sizeof(dis1)); qu.push(s); dis1[s]=0;vis1[s]=1; while(!qu.empty()){ int now=qu.front(); qu.pop(); vis1[now]=0; for(int i=head1[now];i;i=net1[i]) if(dis1[to1[i]]>dis1[now]+cap1[i]){ dis1[to1[i]]=dis1[now]+cap1[i]; if(!vis1[to1[i]]){ vis1[to1[i]]=1; qu.push(to1[i]); } } } } int main(){ freopen("move.in","r",stdin); freopen("move.out","w",stdout); scanf("%d%d%d%d",&n,&m,&q,&k); for(int i=1;i<=m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); add1(v,u,w); } for(int i=1;i<=q;i++) scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z); if(k==0){ spfa(1); if(dis[n]==2139062143){ cout<<"-1"; return 0; } else cout<<dis[n]; } else if(k==1){ spfa(1); spfaa(n); ans=dis[n]; if(dis[n]==2139062143){ cout<<"-1"; return 0; } for(int i=1;i<=q;i++){ if(dis[edge[i].x]==2139062143) continue; if(dis[edge[i].y]==2139062143) continue; ans=min(ans,dis[edge[i].x]+dis1[edge[i].y]+edge[i].z); } cout<<ans; } else{ for(int i=1;i<=q;i++) add(edge[i].x,edge[i].y,edge[i].z); spfa(1); if(dis[n]==2139062143){ cout<<"-1"; return 0; } cout<<dis[n]; } } /* 5 5 2 1 1 2 1 1 3 2 2 4 2 3 4 3 4 5 4 1 4 1 2 5 1 */
正解：dp
#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; }
思路：树形DP
设dp[i][j]表示在i的子树中j所在的联通块的大小 为dp[i][j],其他联通块大小均符合要求的删边方案数
然后
求助大佬翻译一下题解：
考虑用树形dp来解决这道问题。 设f[i][j] 表示在i的子树中j所在的连通块大小为f[i][j]，且其他连通块大小均符合要求的删边方案数 对于每个点??我们一棵一棵地将其子树加进来，设新加入子树的根为?? 若删除??与??之间的边，则用??[??][??] * sum(??[??][??]) s in [k,n] 去更新??[??][??] 若不删??与??之间的边，则枚举??所在连通块的大小??，并更新??[??][??+??] 时间复杂度 O(n^3) ？ 考虑一个优化：每次新加一颗子树时，??只需枚举到前面已经加进来的子树大小之和，??也只需枚举到新子树的大小 这只是一个常数优化？其实每个点对相当于只在??????处被算了一次 故优化后的时间复杂度是O（n^2)的,本题得以解决。
#include<cstdio> #include<cstdlib> #define MAXN 5555 #define mod 786433 using namespace std; int n,K,tot; long long f[MAXN][MAXN]; int to[MAXN*2],net[MAXN*2],head[MAXN]; long long size[MAXN],g[MAXN],cnt[MAXN]; void add(int u,int v){ to[++tot]=v;net[tot]=head[u];head[u]=tot; to[++tot]=u;net[tot]=head[v];head[v]=tot; } void dfs(int now,int fa){ size[now]++; f[now][1]=1; for(int i=head[now];i;i=net[i]) if(to[i]!=fa){ dfs(to[i],now); for(int j=1;j<=size[now]+size[to[i]];j++) g[j]=0; for(int j=1;j<=size[now];j++) g[j]=cnt[to[i]]*f[now][j]%mod; for(int j=1;j<=size[now];j++) for(int k=1;k<=size[to[i]];k++) g[j+k]=(g[j+k]+f[now][j]*f[to[i]][k]%mod)%mod; for(int j=1;j<=size[now]+size[to[i]];j++) f[now][j]=g[j]; size[now]+=size[to[i]]; } for(int i=K;i<=size[now];i++) cnt[now]=(cnt[now]+f[now][i])%mod; 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); } dfs(1,1); printf("%d ",cnt[1]); return 0; }