Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:

Posted by ACAccepted at 2019-02-11 18:10:50 on Problem 1632
In Reply To:过是过了,不过代码太长,问下800K的代码怎么写? Posted by:zjmwqx at 2009-06-19 11:34:55
#include <cstdio>
#include <bitset>
using namespace std;

int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-48;c=getchar();}
	return x*f;
}

const int MAXN=40; 
int n;
bitset<MAXN> g[MAXN];
bitset<MAXN> down;

void init()
{
	for (int i=1;i<=36;i++)g[i].reset();
	int a,b; 
	n=read();
	for (int i=1;i<=n;i++)
	{
		a=read();b=read();
		g[a].set(b);
	}
}

bool dfs(int vis,int now,int need,bitset<MAXN> down)
{
	if (down.count()<need)return false;
	if (now==need)return true;
	if (now+36-vis<need)return false;
	return (dfs(vis+1,now,need,down)||dfs(vis+1,now+1,need,down&g[vis]));
}

void work()
{
	down.set();
	int i;
	for (i=2;i*i<=n;i++)if (!dfs(1,0,i,down))break;
	printf("%d\n",i-1);
}

int main()
{
	int cas;cas=read();
	while (cas--)
	{
		init();
		work();
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator