【bestcoder#35】AB問題解

DZY Loves Balls  
 Accepts: 371
 
 Submissions: 988
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
問題の説明

      
    
     n
        
    
     m
       。  DZY             ，  
    
     n+m
      ，    。DZY                01 
    
     S[1⋯(n+m)]
    。  DZY 
    
     i
             ，  
    
     S[i]=1
    ，      ，  
    
     S[i]=0
    。
DZY     ，'01' 
    
     S
             。

説明の入力

         。 (
    
     TestCase≤150
    )
      , 
    
     n
    , 
    
     m(1≤n,m≤12)
    

出力の説明

        ，      ，   
    
     p/q
    (
    
     p,q
      )。

入力サンプル

1 1
2 3

出力サンプル

1/2
6/5

Hint

Case 1: S='01' or S='10',        = 1/2
Case 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)
問題の説明

                   ，            
    
     (u→v)
       
    
     u
       
    
     v
    ，   
    
     u
           
    
     v
      。
  ，DZY        (DAG)。       
    
     k
        ，            。

説明の入力

       。 (
    
     TestCase≤5
    )
   ，      
    
     n,m,k(1≤n,m≤105,0≤k≤m)
    .
   
    
     m
     ，        
    
     u,v(u≠v,1≤u,v≤n)
    ,        
    
     (u→v)
    .

出力の説明

        ，              。

入力サンプル

5 5 2
1 2
4 5
2 4
3 4
2 3
3 2 0
1 2
1 3

出力サンプル

5 3 1 2 4
1 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 0x3f3f3f3f
using 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("
");
	}
	return 0;
}