叉叉
题目描述
现在有一个字符串，每个字母出现的次数均为偶数。接下来我们把第一次出现的字母a和第二次出现的a连一条线，第三次出现的和四次出现的字母a连一条线，第五次出现的和六次出现的字母a连一条线...对其他25个字母也做同样的操作。
现在我们想知道有多少对连线交叉。交叉的定义为一个连线的端点在另外一个连线的内部，另外一个端点在外部。
下图是一个例子，共有三对连线交叉（我们连线的时候，只能从字符串上方经过）。
输入格式
一行一个字符串。保证字符串均由小写字母组成，且每个字母出现次数为偶数次。
输出格式
一个整数，表示答案。
样例输入
abaazooabz
样例输出
3
数据范围
对于30% 的数据，字符串长度不超过50。
对于100% 的数据，字符串长度不超过100,000。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int top,ans,cnt[27],pos[27],num[27],a[100010]; char s[100010]; int main(){ freopen("cross.in","r",stdin);freopen("cross.out","w",stdout); //freopen("Cola.txt","r",stdin); scanf("%s",s); int len=strlen(s); memset(pos,0x3f,sizeof(pos)); for(int i=0;i<len;i++){ int now=s[i]-'a'; num[now]++; if(num[now]%2==0){ ans+=cnt[now]; for(int j=0;j<26;j++){ if(j==now)continue; if(pos[j]<pos[now])cnt[j]--; } pos[now]=0x7fffffff; cnt[pos[now]]=0; } else { a[top]=now; pos[now]=top; cnt[now]=0; top++; for(int j=0;j<26;j++){ if(j==now)continue; if(pos[j]<pos[now])cnt[j]++; } } } printf("%d",ans); }
跳跳虎回家
#include<iostream> #include<cstdio> #include<cmath> #include<queue> #include<cstring> #define maxn 501 using namespace std; int n,m,p,k,num,head[maxn],f[501][2001]; struct node{int to,pre,v,mark;}e[2000+2001]; struct Node{ int id,cnt,dis; bool operator < (const Node b)const{ return dis>b.dis; } }; Node make_Node(int id,int cnt,int dis){ Node res; res.id=id;res.cnt=cnt;res.dis=dis; return res; } void Insert(int from,int to,int v,int mark){ e[++num].to=to; e[num].v=v; e[num].mark=mark; e[num].pre=head[from]; head[from]=num; } priority_queue<Node>q; void Dij(){ q.push(make_Node(1,0,0)); memset(f,0x3f,sizeof(f));f[1][0]=0; while(!q.empty()){ Node now=q.top();int point=now.id,d=now.dis,c=now.cnt; q.pop(); for(int i=head[point];i;i=e[i].pre){ int to=e[i].to; if(e[i].mark==0&&f[to][c]>f[point][c]+e[i].v){ f[to][c]=f[point][c]+e[i].v; q.push(make_Node(to,c,f[to][c])); } if(c<k&&e[i].mark==1&&f[to][c+1]>f[point][c]+e[i].v){ f[to][c+1]=f[point][c]+e[i].v; q.push(make_Node(to,c+1,f[to][c+1])); } } } } int main(){ //freopen("Cola.in","r",stdin); freopen("move.in","r",stdin);freopen("move.out","w",stdout); scanf("%d%d%d%d",&n,&m,&p,&k); int x,y,z; for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); Insert(x,y,z,0); } for(int i=1;i<=p;i++){ scanf("%d%d%d",&x,&y,&z); Insert(x,y,z,1); } Dij(); int ans=0x7fffffff; for(int i=0;i<=min(k,p);i++){ ans=min(ans,f[n][i]); } if(ans>20000000){puts("-1");return 0;} printf("%d",ans); }
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #define maxn 5010 using namespace std; int n,m,p,k,l,r,mid; int num,head[maxn],num2,head2[maxn],dis[maxn]; bool vis[maxn],ok[maxn],flag; struct node{ int to,pre,v,mark; }e[maxn],e2[maxn]; void Insert(int from,int to,int v,int mark){ e[++num].to=to; e[num].v=v; e[num].pre=head[from]; e[num].mark=mark; head[from]=num; } void Insert2(int from,int to,int v,int mark){ e2[++num2].to=to; e2[num2].v=v; e2[num2].pre=head2[from]; e2[num2].mark=mark; head2[from]=num2; } void Spfa(){ queue<int>q; memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); vis[1]=1;dis[1]=0; q.push(1); while(!q.empty()){ int now=q.front();q.pop();vis[now]=0; for(int i=head[now];i;i=e[i].pre){ if(e[i].mark)continue; int to=e[i].to; if(dis[to]>dis[now]+e[i].v){ dis[to]=dis[now]+e[i].v; if(!vis[to])vis[to]=1,q.push(to); } } } } void dfs(int now,int d,int t){ if(t>k)return; if(d>mid)return; if(now==n){flag=1;return;} if(flag)return; for(int i=head[now];i;i=e[i].pre){ int to=e[i].to; if(!ok[to])continue; if(!vis[to]){ vis[to]=1; dfs(to,d+e[i].v,t+e[i].mark); vis[to]=0; } } } bool check(){ flag=0; memset(vis,0,sizeof(vis)); vis[1]=1; dfs(1,0,0); if(flag)return 1; else return 0; } void bfs(){ queue<int>q; q.push(n);ok[n]=1; while(!q.empty()){ int now=q.front();q.pop(); for(int i=head2[now];i;i=e2[i].pre){ int to=e2[i].to; if(!ok[to]){ ok[to]=1; q.push(to); } } } } int main(){ //freopen("Cola.txt","r",stdin); freopen("move.in","r",stdin);freopen("move.out","w",stdout); scanf("%d%d%d%d",&n,&m,&p,&k); int x,y,z; for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); Insert(x,y,z,0); Insert2(y,x,z,0); r+=z; } for(int j=1;j<=p;j++){ scanf("%d%d%d",&x,&y,&z); Insert(x,y,z,1); Insert2(y,x,z,1); r+=z; } if(k==0){ Spfa(); if(dis[n]>=20000000){puts("-1");return 0;} printf("%d",dis[n]);return 0; } else { bfs(); if(!ok[1]){puts("-1");return 0;} int ans=-1; while(l<=r){ mid=(l+r)>>1; if(check())ans=mid,r=mid-1; else l=mid+1; } printf("%d",ans); } }
#include<iostream> #include<cstdio> #include<cmath> #include<queue> #include<cstring> #define maxn 501 using namespace std; int n,m,p,k,num,head[maxn],f[501][2001]; bool vis[maxn][2001]; struct node{int to,pre,v,mark;}e[2001+2001]; struct Node{ int id,cnt,dis; bool operator < (const Node b)const{ return dis>b.dis; } }; Node make_Node(int id,int cnt,int dis){ Node res; res.id=id;res.cnt=cnt;res.dis=dis; return res; } void Insert(int from,int to,int v,int mark){ e[++num].to=to; e[num].v=v; e[num].mark=mark; e[num].pre=head[from]; head[from]=num; } priority_queue<Node>q; void Dij(){ q.push(make_Node(1,0,0)); memset(f,0x3f,sizeof(f));f[1][0]=0; while(!q.empty()){ Node now=q.top();int point=now.id,d=now.dis,c=now.cnt; if(point==n)break;//非常有用的一句话 q.pop(); for(int i=head[point];i;i=e[i].pre){ int to=e[i].to; if(e[i].mark==0&&f[to][c]>f[point][c]+e[i].v){ f[to][c]=f[point][c]+e[i].v; q.push(make_Node(to,c,f[to][c])); } if(c<k&&e[i].mark==1&&f[to][c+1]>f[point][c]+e[i].v){ f[to][c+1]=f[point][c]+e[i].v; q.push(make_Node(to,c+1,f[to][c+1])); } } } } int main(){ //freopen("Cola.in","r",stdin); freopen("move.in","r",stdin);freopen("move.out","w",stdout); scanf("%d%d%d%d",&n,&m,&p,&k); int x,y,z; for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); Insert(x,y,z,0); } for(int i=1;i<=p;i++){ scanf("%d%d%d",&x,&y,&z); Insert(x,y,z,1); } Dij(); int ans=0x7fffffff; for(int i=0;i<=min(k,p);i++){ ans=min(ans,f[n][i]); } if(ans>20000000){puts("-1");return 0;} printf("%d",ans); }
秀秀和哺噜国
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define maxn 5010 #define mod 786433 using namespace std; int n,k,num,head[maxn],fal[maxn],sz[maxn],ans,can[maxn],c; bool vis[maxn],v[maxn]; struct node{ int to,pre,v; }e[maxn]; void Insert(int from,int to,int id){ e[id].to=to; e[id].pre=head[from]; head[from]=id; num=max(num,id); } void Dfs(int now,int father){ sz[now]=1; for(int i=head[now];i;i=e[i].pre){ int to=e[i].to; if(to==father)continue; fal[to]=i; Dfs(to,now); sz[now]+=sz[to]; } } int bfs(int x){ int res=1; queue<int>q; q.push(x); vis[x]=1; while(!q.empty()){ int now=q.front();q.pop(); for(int i=head[now];i;i=e[i].pre){ if(e[i].v!=0)continue; int to=e[i].to; if(!vis[to]){ vis[to]=1; q.push(to); res++; } } } return res; } bool check(){ memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ if(!vis[i]){ if(bfs(i)<k)return 0; } } return 1; } void dfs(int pos){ if(pos>c){ //for(int i=1;i<=num;i++)cout<<i<<' '<<e[i].v<<endl;cout<<endl; if(check()){ ans++; if(ans>=mod)ans-=mod; } return; } dfs(pos+1); int w=(can[pos]>=n?(can[pos]-n+1):(can[pos]+n-1)); e[can[pos]].v=1; e[w].v=1; dfs(pos+1); e[can[pos]].v=0; e[w].v=0; } int main(){ //freopen("Cola.in","r",stdin); freopen("cut.in","r",stdin);freopen("cut.out","w",stdout); scanf("%d%d",&n,&k); int x,y; for(int i=1;i<n;i++){ scanf("%d%d",&x,&y); Insert(x,y,i);Insert(y,x,i+n-1); } Dfs(1,0); int sum=0; for(int i=1;i<=n;i++) if(sz[i]<k){ //e[fal[i]].v=1; int w=(fal[i]>=n?fal[i]-n+1:fal[i]+n-1); //e[w].v=1; v[fal[i]]=v[w]=1; sum++; } for(int i=1;i<=num;i++){ if(v[i]==0){ can[++c]=i; int w=(i>=n?i-n+1:i+n-1); v[w]=1; v[i]=1; } } dfs(1); printf("%d",ans); 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\n",cnt[1]); fclose(stdin); fclose(stdout); return 0; }