11
13
2015
0

[BZOJ 1077] 天平

Description

你有n个砝码,均为1克,2克或者3克。你并不清楚每个砝码的重量,但你知道其中一些砝码重量的大小关系。你把其中两个砝码A和B放在天平的左边,需要另外选出两个砝码放在天平的右边。问:有多少种选法使得天平的左边重(c1)、一样重(c2)、右边重(c3)?(只有结果保证惟一的选法才统计在内)

暴力枚举,暴力判断

#include<cstdio>
#include<algorithm>
#include<cstring>
#define PROC "scale"
using namespace std;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
typedef long long LL;
int n, a, b;
const int maxn=52, inf=0x3f3f3f3f;
char mp[maxn][maxn];
int belong[maxn], bn;
struct yjq{
	int rel[maxn];
	bool able[4];
	yjq()
	{
		memset(able,true,sizeof(able));
		memset(rel,0x3f,sizeof(rel));
	}
};
yjq naive[maxn];
int fa[maxn];

int findfa(int son)
{
	if (son!=fa[son]) fa[son]=findfa(fa[son]);
	return fa[son];
}

void addfa(int s1, int s2)
{
	int f1=findfa(s1), f2=findfa(s2);
	fa[f2]=f1;
}

void init()
{
	bn=n;
	for (int i=1; i<=n; i++)
		fa[i]=i;
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=n; j++)
		{
			if (mp[i][j]=='=')
			{
				addfa(i,j);
			}
		}
	}
	for (int i=1; i<=n; i++)
		belong[i]=findfa(i);
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=n; j++)
		{
			if (mp[i][j]=='-')
			{
				naive[belong[i]].rel[belong[j]]=1;
				naive[belong[i]].able[3]=0;
				naive[belong[j]].rel[belong[i]]=-1;
				naive[belong[j]].able[1]=0;
			}
			else if (mp[i][j]=='+')
			{
				naive[belong[i]].rel[belong[j]]=-1;
				naive[belong[i]].able[1]=0;
				naive[belong[j]].rel[belong[i]]=1;
				naive[belong[j]].able[3]=0;
			}
		}
	}
	for (int i=1; i<=bn; i++)
	{
		for (int j=1; j<=bn; j++)
		{
			for (int k=1; k<=bn; k++)
			{
				if (naive[i].rel[j]==1&&naive[i].rel[j]==naive[j].rel[k])
				{
					naive[i].rel[k]=2;
					naive[i].able[2]=0;
					naive[k].rel[i]=-2;
					naive[k].able[2]=0;
				}
			}
		}
	}
}
int cnt[4];
int getres(int num1, int num2)
{
	if (num1>num2) return 1;
	if (num1<num2) return 3;
	return 2;
}

int st[5], sw[5];

bool illegal(int s1, int s2, int s3, int s4, int w1, int w2, int w3, int w4)
{
	st[1]=belong[s1];
	st[2]=belong[s2];
	st[3]=belong[s3];
	st[4]=belong[s4];
	sw[1]=w1;
	sw[2]=w2;
	sw[3]=w3;
	sw[4]=w4;
	for (int i=1; i<=4; i++)
	{
		if (!naive[st[i]].able[sw[i]]) return 1;
		for (int j=i+1; j<=4; j++)
		{
			if (st[i]==st[j]&&sw[i]!=sw[j]) return 1;
			int delta=naive[st[i]].rel[st[j]];
			if (delta==inf) continue;
			if (delta>0)
			{
				if (sw[i]+delta>sw[j]) return 1;
			}
			else
			{
				if (sw[i]+delta<sw[j]) return 1;
			}
		}
	}
	return 0;
}

void solve()
{
	for (int c=1; c<n; c++)
	{
		if (c==a||c==b) continue;
		for (int d=c+1; d<=n; d++)
		{
			if (d==a||d==b||d==c) continue;
			int res=0;
			for (int w1=1; w1<=3; w1++)
			{
				for (int w2=1; w2<=3; w2++)
				{
					for (int w3=1; w3<=3; w3++)
					{
						for (int w4=1; w4<=3; w4++)
						{
							if (illegal(a,b,c,d,w1,w2,w3,w4)) continue;
//							printf("%d:%d %d:%d %d:%d %d:%d\n",a,w1,b,w2,c,w3,d,w4);
							int back=getres(w1+w2,w3+w4);
							if (back!=res && res!=0)
							{
								res=-1;
								break;
							}
							if (!res) res=back;
						}
					}
				}
			}
			if (res!=-1)
				cnt[res]++;
		}
	}
}

int main()
{
//	freopen(PROC".in","r",stdin);
//	freopen(PROC".out","w",stdout);
	scanf("%d%d%d",&n,&a,&b);
	for (int i=1; i<=n; i++)
		scanf("%s",&mp[i][1]);
	init();
	solve();
	for (int i=1; i<=2; i++)
		printf("%d ",cnt[i]);
	printf("%d\n",cnt[3]);
	fclose(stdout);
	return 0;
}
Category: 黑暗算法 | Tags: 暴力
8
5
2015
0

[BZOJ 3170][TJOI 2013]松鼠聚会

首先造几组数据,可以发现把每个点按x+y排序后取中位数,然后在中位数左右的点枚举,随机数据是卡不到的,而且我感到要构造数据很麻烦,所以就这么写了。

#include<cstdio>
#include<algorithm>
using namespace std;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
typedef long long LL;
#define debug
const int maxn=100100, canshu=500;
int mid, n;
struct yjq{
    int x,y;
    void read()
    {
        scanf("%d%d",&x,&y);
    }
};
yjq poi[maxn];
LL ans;
 
inline bool cmpx(yjq ac, yjq ak)
{
    return ac.x<ak.x;
}
 
inline bool cmp(yjq ac, yjq ak)
{
    return ac.x+ac.y<ak.x+ak.y;
}
 
inline bool cmpy(yjq ac, yjq ak)
{
    return ac.y<ak.y;
}
 
inline int dist(yjq ac, yjq ak)
{
    return max(abs(ac.x-ak.x),abs(ac.y-ak.y));
}
 
inline LL calcans(yjq ac)
{
    LL nowans=0;
    for (int j=1; j<=n; j++)
        nowans+=dist(ac,poi[j]);
    return nowans;
}
 
void baoli()
{
    for (int i=1; i<=n; i++)
    {
        ans=min(ans,calcans(poi[i]));
    }
    printf(lld"\n",ans);
}
 
int main()
{
    scanf("%d",&n);
    mid=(n+1)>>1;
    for (int i=1; i<=n; i++)
        poi[i].read();
    ans=0x3f3f3f3f3f3f3f3fLL;
#ifdef debug
    if (n<=1000)
    {
        baoli();
        return 0;
    }
#endif
    sort(poi+1,poi+1+n,cmp);
    ans=min(ans,calcans(poi[mid]));
    for (int i=1; i<=300; i++)
    {
        ans=min(ans,calcans(poi[mid+i]));
        ans=min(ans,calcans(poi[mid-i]));
    }
    printf(lld"\n",ans);
    fclose(stdout);
    return 0;
}
Category: 黑暗算法 | Tags: 黑暗算法

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com