DZY Loves Balls
Accepts: 371
Submissions: 988
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
一个盒子里有。DZY现在想知道，’01’在串中出现的期望次数。
输入描述
输入有多组测试数据。 ()每行两个整数,
输出描述
对于每个测试数据，输出一行答案，格式为(互质)。
输入样例
1 12 3
输出样例
1/26/5
Hint
Case 1: S=’01’ or S=’10’, 所以期望次数 = 1/2Case 2: S=’00011′ or S=’00101′ or S=’00110′ or S=’01001′ or S=’01010′ or S=’01100′ or S=’10001′ or S=’10010′ or S=’10100′ or S=’11000′,所以期望次数 = (1+2+1+2+2+1+1+1+1+0)/10 = 12/10 = 6/5
排列组合。
一共有C(n+m,n)种排列。
01出现的次数：枚举01的位置然后计算其他位置的摆放方案数(n+m-1)*C(n+m-2,n-1)
期望(n+m-1)*C(n+m-2,n-1)/C(n+m,n)=(n*m)/(n+m)
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;int main(){int n,m;while (scanf("%d%d",&n,&m)!=EOF){int k=__gcd(n*m,n+m);cout<<n*m/k<<"/"<<(n+m)/k<<endl;}return 0;}
DZY Loves Topological Sorting
Accepts: 112
Submissions: 586
Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 131072/131072 K (Java/Others)
问题描述
一张有向图的拓扑序列是图中点的一个排列，满足对于图中的每条有向边之前。现在，DZY有一张有向无环图(DAG)。你要在最多删去条边之后，求出字典序最大的拓扑序列。
输入描述
输入有多组数据。 ()第一行，三个正整数 .接下来.
输出描述
对于每组测试数据，输出一行字典序最大的拓扑序列。
输入样例
5 5 21 24 52 43 42 33 2 01 21 3
输出样例
5 3 1 2 41 3 2
Hint
数据1. 删除(2->3),(4->5)两条边，可以得到字典序最大的拓扑序列：(5,3,1,2,4).
（思路并不难的一道题，可是我在结束的前15分钟才想出来正解。。写出来了没调对。。）
首先计算出每个点的度数。
使拓扑序最大的数字就是当前度数<=k的最大数字，k-=他的度数，他所连得点度数减1。
然后重复这个过程。
问题就变成了查找<=k的最大数字，，在线段树中维护区间最小值，直接二分就可以了。
修改的复杂度是O(mlogn)，查询的复杂度是O(nlogn)，总复杂度O((m+n)logn)
注意：此题不写读入优化就TLE了。。
#include <iostream>#include <cstring>#include <algorithm>#include <cstdio>#include <cstdlib>#include <cmath>#define inf 0x3f3f3f3fusing namespace std;int cnt,tot,h[150005],d[150005],n,m,k;struct edge{int y,ne;}e[150005];struct Segtree{int l,r,m;}a[500000];void read(int &tmp){tmp=0;int fu=1;char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar())if (ch=='-') fu=-1;for (;ch>='0'&&ch<='9';ch=getchar())tmp=tmp*10+ch-'0';tmp*=fu;}void Addedge(int x,int y){e[++tot].y=y;e[tot].ne=h[x];h[x]=tot;d[y]++;}void P(int x){if (a[x<<1].m<a[(x<<1)+1].m) a[x].m=a[x<<1].m;else a[x].m=a[(x<<1)+1].m;}void Build(int x,int l,int r){a[x].l=l,a[x].r=r;if (l==r){a[x].m=d[l];return;}int m=(l+r)>>1;Build(x<<1,l,m);Build((x<<1)+1,m+1,r);P(x);}int Find(int x,int k){if (a[x].l==a[x].r)return a[x].l;if (a[(x<<1)+1].m<=k) return Find((x<<1)+1,k);return Find(x<<1,k);}void M(int x,int y,int k){if (a[x].l==a[x].r){a[x].m+=k;return;}int m=(a[x].l+a[x].r)>>1;if (y<=m) M(x<<1,y,k);else M((x<<1)+1,y,k);P(x);}int main(){while (scanf("%d%d%d",&n,&m,&k)!=EOF){tot=0;for (int i=1;i<=n;i++)d[i]=0,h[i]=0;int x,y;for (int i=1;i<=m;i++){read(x),read(y);Addedge(x,y);}Build(1,1,n);for (int i=1;i<=n;i++){x=Find(1,k);k-=d[x];M(1,x,inf);d[x]=inf;if (i==1) printf("%d",x);else printf(" %d",x);for (int j=h[x];j;j=e[j].ne)if (d[e[j].y]!=inf)M(1,e[j].y,-1),d[e[j].y]–;}printf("\n");}return 0;}
积极思考造成积极人生，消极思考造成消极人生。
