TCO 2015 Round 1A DIV1

2015年4月15日34,0340

250：

枚举l-r的数，爆搜，统计数位，用map存一下T T

实际上对于每个数小范围暴力即可T T

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long 
using namespace std;
int mx=0;
map<string,bool> mp;
class Similars{
public:
	void dfs(string a,int x,int tot,bool flag){
		if(x==0){
			if(flag==1)
			{
				if(mp[a])mx=max(mx,tot);
			}
			else mp[a]=1;
			return;
		}
		int t=x%10;x/=10;
		dfs(a,x,tot,flag);
		a[t]++;if(a[t]=='1')tot++;
		dfs(a,x,tot,flag);
	}
	int maxsim(int L, int R){
		string a="0000000000";
		for(int i=L;i<=R;i++)
		{
			dfs(a,i,0,1);
			dfs(a,i,0,0);
		}
		return mx;
	}
};

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

int mx=0;

map<string,bool> mp;

class Similars{

public:

void dfs(string a,int x,int tot,bool flag){

if(x==0){

if(flag==1)

{

if(mp[a])mx=max(mx,tot);

}

else mp[a]=1;

return;

}

int t=x%10;x/=10;

dfs(a,x,tot,flag);

a[t]++;if(a[t]=='1')tot++;

dfs(a,x,tot,flag);

}

int maxsim(int L, int R){

string a="0000000000";

for(int i=L;i<=R;i++)

{

dfs(a,i,0,1);

dfs(a,i,0,0);

}

return mx;

}

};

500：

暴力走min(n^2,K)次，预处理出哪些不能同时取。。。

再暴搜+快速幂算方案TAT

结果有个点T了。。。

正解

假如k步之前在一起了，那么k步的时候一定在一起了
所以如果我们能求出k步的状态，就可以用每个数出现的次数+1的乘积作为答案（可以选择任意数量的放，也可以不放）

所以暴力求状态后乘起来就行了。。。我是SB

暴力

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long 
using namespace std;
int mx=0;
map<string,bool> mp;
class Similars{
public:
	void dfs(string a,int x,int tot,bool flag){
		if(x==0){
			if(flag==1)
			{
				if(mp[a])mx=max(mx,tot);
			}
			else mp[a]=1;
			return;
		}
		int t=x%10;x/=10;
		dfs(a,x,tot,flag);
		a[t]++;if(a[t]=='1')tot++;
		dfs(a,x,tot,flag);
	}
	int maxsim(int L, int R){
		string a="0000000000";
		for(int i=L;i<=R;i++)
		{
			dfs(a,i,0,1);
			dfs(a,i,0,0);
		}
		return mx;
	}
};

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

int mx=0;

map<string,bool> mp;

class Similars{

public:

void dfs(string a,int x,int tot,bool flag){

if(x==0){

if(flag==1)

{

if(mp[a])mx=max(mx,tot);

}

else mp[a]=1;

return;

}

int t=x%10;x/=10;

dfs(a,x,tot,flag);

a[t]++;if(a[t]=='1')tot++;

dfs(a,x,tot,flag);

}

int maxsim(int L, int R){

string a="0000000000";

for(int i=L;i<=R;i++)

{

dfs(a,i,0,1);

dfs(a,i,0,0);

}

return mx;

}

};

正解。。。其实就是暴力。。。

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define mod 1000000007
#define ll long long 
using namespace std;
int n;ll ans=1;
int to[105],cnt[105];
class Autogame{
public:
	int wayscnt(vector <int> a, int K){
		n=a.size();K=min(K,n*n);
		for(int i=0;i<n;i++)
			to[i+1]=a[i];
		for(int i=1;i<=n;i++)
		{
			int x=i;
			for(int j=1;j<=K;j++)
				x=to[x];
			cnt[x]++;
		}
		for(int i=1;i<=n;i++)
			ans=(ans*(cnt[i]+1))%mod;
		printf("%lld",ans);
		return ans;
	}
};

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define mod 1000000007

#define ll long long

using namespace std;

int n;ll ans=1;

int to[105],cnt[105];

class Autogame{

public:

int wayscnt(vector <int> a, int K){

n=a.size();K=min(K,n*n);

for(int i=0;i<n;i++)

to[i+1]=a[i];

for(int i=1;i<=n;i++)

{

int x=i;

for(int j=1;j<=K;j++)

x=to[x];

cnt[x]++;

}

for(int i=1;i<=n;i++)

ans=(ans*(cnt[i]+1))%mod;

printf("%lld",ans);

return ans;

}

};

1000

由于不存在完备匹配

根据hall定理

一定存在一个X的子集S，使得S的邻集大小小于S的大小

求出删去邻集每个元素的代价，删最小的几个

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long 
using namespace std;
int n,ans=inf;
int mp[25][25],v[25];
bool sel[25];
void cal()
{
	memset(v,0,sizeof(v));
	int tot=n+1,sum=0;
	for(int i=1;i<=n;i++)
		if(sel[i])
		{
			tot--;
			for(int j=1;j<=n;j++)
				v[j]+=mp[i][j];
		}
	if(tot>n)return;
	sort(v+1,v+n+1);
	for(int i=1;i<=tot;i++)
		sum+=v[i];
	ans=min(ans,sum);
}
void dfs(int x)
{
	if(x==n+1)
	{
		cal();
		return;
	}
	sel[x]=0;
	dfs(x+1);
	sel[x]=1;
	dfs(x+1);
}
class Revmatching{
public:
	int smallest(vector <string> A){
		n=A.size();
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				mp[i+1][j+1]=A[i][j]-'0';
		dfs(1);
		return ans;
	}
};

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

int n,ans=inf;

int mp[25][25],v[25];

bool sel[25];

void cal()

{

memset(v,0,sizeof(v));

int tot=n+1,sum=0;

for(int i=1;i<=n;i++)

if(sel[i])

{

tot--;

for(int j=1;j<=n;j++)

v[j]+=mp[i][j];

}

if(tot>n)return;

sort(v+1,v+n+1);

for(int i=1;i<=tot;i++)

sum+=v[i];

ans=min(ans,sum);

}

void dfs(int x)

{

if(x==n+1)

{

cal();

return;

}

sel[x]=0;

dfs(x+1);

sel[x]=1;

dfs(x+1);

}

class Revmatching{

public:

int smallest(vector <string> A){

n=A.size();

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

mp[i+1][j+1]=A[i][j]-'0';

dfs(1);

return ans;

}

};

« 「CF534X」Codeforces Round #298 (Div. 2) 「BZOJ2770」YY的Treap »

hzwer.com _ Home | http://hzwer.com

TCO 2015 Round 1A DIV1

分类目录

热门文章

Myfriends

近期评论