月度归档:2015年03月

UOJ 2 【NOI2014】起床困难综合症

21 世纪,许多人得了一种奇怪的病:起床困难综合症,其临床表现为:起床难,起床后精神不佳。作为一名青春阳光好少年,atm 一直坚持与起床困难综合症作斗争。通过研究相关文献,他找到了该病的发病原因:在深邃的太平洋海底中,出现了一条名为 drd 的巨龙,它掌握着睡眠之精髓,能随意延长大家的睡眠时间。正是由于 drd 的活动,起床困难综合症愈演愈烈,以惊人的速度在世界上传播。为了彻底消灭这种病,atm 决定前往海底,消灭这条恶龙。

历经千辛万苦,atm 终于来到了 drd 所在的地方,准备与其展开艰苦卓绝的战斗。drd 有着十分特殊的技能,他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来,drd 的防御战线由 n 扇防御门组成。每扇防御门包括一个运算 op 和一个参数 t,其中运算一定是 OR,XOR,AND 中的一种,参数则一定为非负整数。如果还未通过防御门时攻击力为 x,则其通过这扇防御门后攻击力将变为 x op t。最终drd 受到的伤害为对方初始攻击力 x 依次经过所有 n 扇防御门后转变得到的攻击力。

由于 atm 水平有限,他的初始攻击力只能为 0 到 m 之间的一个整数(即他的初始攻击力只能在 0,1,…,m 中任选,但在通过防御门之后的攻击力不受 m 的限制)。为了节省体力,他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害,请你帮他计算一下,他的一次攻击最多能使 drd 受到多少伤害。

输入格式

第一行包含两个整数,依次为 n,m,表示 drd 有 n 扇防御门,atm 的初始攻击力为 0 到 m 之间的整数。

接下来 n 行,依次表示每一扇防御门。每行包括一个字符串 op 和一个非负整数 t,两者由一个空格隔开,且 op 在前,t 在后,op 表示该防御门所对应的操作,t 表示对应的参数。

输出格式

一行一个整数,表示 atm 的一次攻击最多使 drd 受到多少伤害。

样例一

input

3 10
AND 5
OR 6
XOR 7

output

1

explanation

atm可以选择的初始攻击力为 0,1,…,10。

假设初始攻击力为4,最终攻击力经过了如下计算
4 AND 5 = 4
4 OR 6 = 6
6 XOR 7 = 1

类似的,我们可以计算出初始攻击力为 1,3,5,7,9 时最终攻击力为 0,初始攻击力为 0,2,4,6,8,10 时最终攻击力为 1,因此 atm 的一次攻击最多使 drd 受到的伤害值为 1。

题解

30pt Brute

#include "cmath"
#include "cstring"
#include "cstdlib"
#include "cstdio"
#include "iostream"
#include "algorithm"
#define rep(i,l,r) for(i = l;i < r; i++)
#define derep(i,l,r) for(i = l;i > r; i--)
#define maxn 110000
#define N 1074000000
using namespace std;
long long i,j,k;
long long n,m,a;
long long ATK,atk = 0;
char c;

/*
 * m	DEF limit
 * a	ATK
 * c	Command class just the "op" in the question
 * h	hurt
 */

struct node
{
	char c[4];
	long long a;
}P[maxn];

inline void Solve(long long i)
{
	atk = i;
	rep(j,0,n)
	{
		if (P[j].c[0] == 'A')
		{
			//printf("%lld & %lld = ",atk,P[j].a);
			atk = atk & P[j].a;
		}
		if (P[j].c[0] == 'O')
		{
			//printf("%lld | %lld = ",atk,P[j].a);
			atk = atk | P[j].a;
		}
		if (P[j].c[0] == 'X')
		{
			//printf("%lld xor %lld = ",atk,P[j].a);
			atk = atk ^ P[j].a;
		}
		//printf("%lld\n", atk);
	}
	//printf("atk=%d\n",atk);
	if (atk > ATK)
		ATK = atk;
	//printf("ATK=%d\n", ATK);
}

void Init()
{
	scanf("%lld%lld",&n,&m);
	rep(i,0,n)
		scanf("%s%lld", P[i].c, &P[i].a);

	rep(i,0,m+1)
	Solve(i);

	printf("%lld\n", ATK);
}


int main()
{
	freopen("2.in","r",stdin);
	
	Init();

	fclose(stdin);
	return 0;
}

[CodeVS1160]蛇形矩阵

经历了 Day3 的挫折,不由得想起了曾近屡交屡 WA 的蛇形矩阵(毕竟当时太弱)。为了挺过难关,重拾信心,便重新审视了一下题…

题目描述 Description

小明玩一个数字游戏,取个n行n列数字矩阵(其中n为不超过100的奇数),数字的填补方法为:在矩阵中心从1开始以逆时针方向绕行,逐圈扩大,直到n行n列填满数字,请输出该n行n列正方形矩阵以及其的对角线数字之和.

输入描述 Input Description

n(即n行n列)

输出描述 Output Description

n+1行,n行为组成的矩阵,最后一行为对角线数字之和

自己的分析 My Opinion

利用左上角的点为 (n-1)^2 的特性进行模拟移动。

#include "cmath"
#include "cstring"
#include "cstdlib"
#include "cstdio"
#include "iostream"
#include "algorithm"
#define rep(i,l,r) for(i = l;i < r; i++)
#define derep(i,l,r) for(i = l;i > r; i--)
#define N 100
int arr[N][N];
int i,j,n,k = 0,t,margin = 0;
using namespace std;
void Init()
{
    scanf("%d", &n);
    memset(arr,0,sizeof(arr));
}

void Print()
{
    rep(i,0,n)
    {
        rep(j,0,n)
        printf("%d  ", arr[j][i]);
        printf("\n");
    }   
}

void Solve()
{
    arr[(n-1)/2][(n-1)/2]=1;
    int n1 = n;
    while(margin < (n-1)/2)
    {
        //left top
        arr[0+margin][0+margin] = pow((n1-1-margin),2)+1;
        //top
        rep(i,1+margin,n-margin)
            arr[i][0+margin] = arr[i-1][0+margin]-1;
        //left
        rep(i,1+margin,n-margin)
            arr[0+margin][i] = arr[0+margin][i-1]+1;
        //bottom
        rep(i,1+margin,n-margin)
            arr[i][n-1-margin] = arr[i-1][n-1-margin]+1;
        //right
        rep(i,1+margin,n-1-margin)
            arr[n-1-margin][i] = arr[n-1-margin][i-1]-1;
        margin++;
        n1 = n1 - 1;
    }
}

void Diagonal_line()
{
    int sum = -1;
    rep(i,0,n)
        sum+=arr[i][i];
    derep(i,n-1,-1)
        sum+=arr[n-i-1][i];
    printf("%d", sum);
}

int main()
{
    Init();
    Solve();
    Print();
    Diagonal_line();
    return 0;
}

HNOI2015-Virtual 行记

Day1

上午从8点坐到11点半,3个小时全耗在LXY故意卡分的 Distance 上,最后靠样例数据水了 30pt。qwq所幸全场无人挂零。
Matrix 和 Circle 分别考了矩阵和最小圆覆盖,也跪了。
下午的 Hard Problem Choose Talk 讲了牛顿二项式、费马小定理、拉格朗日定理,真个人都不好了

Day2

在教室上文化课,并没有参加 Day2 的考试。
中午看了看题,树链剖分 Sub,Prufer 数列 Calc 以及期望题 Exp。
相较 Day1 的题目,题面简洁易懂,但几乎全是数学题qwq

Day3

Day3 简直爆炸
大致浅析了莫队算法,树上莫队,欧拉序列,平衡树,凸包,变形装箱等综合性题目,但是完 全 没 听 懂

Day4

文化课

Day5

文化课

Day6

全场膜拜 vfk、ydc,121页课件惊呆众人

浅析并查集

写在前面

紫苑镇(シオンタウン ,Lavender Town),是关都地区的一个小镇。赤绿青黄与火红叶绿中,紫苑镇是座著名的鬼镇,镇上的神奇宝贝塔是集中安葬故去的口袋妖怪的场所。不过在金银水晶与新金魂银里,紫苑镇上建起了收讯塔,现代化的气息浓郁起来。

据镇里的居民介绍,紫苑镇是著名的精灵墓地。所有的安葬悼亡活动都在镇上的口袋妖怪塔进行。作为一座中型城镇,它镇民大多是在口袋妖怪塔周围长大,相信灵魂的存在并有着很深的宗教信仰,常去塔中祭拜,祈祷口袋妖怪们平安幸福。紫苑镇人口数量不多的原因可能在于镇里没有道馆,所以训练家不会在此多作停留,但也有些人会为了纪念他们死去的口袋妖怪而留在镇上。

为了改善居民的生活质量,我们的训练家HJWJBSR,将对紫苑镇的地下排污管道进行重修。按照地图规划,他将使得所有房屋都被管道联通(即每个房屋至少有一条排污管道相连)。
我们的训练家HSH还需要修几条路,就能使所有的房屋都能顺利的排出污水呢?

怎么感觉这题目跟并查集没点关系..

概念

并查集是一个可以确认节点是否属于同一根的树状结构,即判断多个节点之间的亲属关系。

理解

引用laserss的一段文字。
话说江湖上散落着各式各样的大侠,有上千个之多。他们没有什么正当职业,整天背着剑在外面走来走去,碰到和自己不是一路人的,就免不了要打一架。但大侠们有一个优点就是讲义气,绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”,只要是能通过朋友关系串联起来的,不管拐了多少个弯,都认为是自己人。这样一来,江湖上就形成了一个一个的群落,通过两两之间的朋友关系串联起来。而不在同一个群落的人,无论如何都无法通过朋友关系连起来,于是就可以放心往死了打。但是两个原本互不相识的人,如何判断是否属于一个朋友圈呢?

我们可以在每个朋友圈内推举出一个比较有名望的人,作为该圈子的代表人物,这样,每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”……两人只要互相对一下自己的队长是不是同一个人,就可以确定敌友关系了。

但是还有问题啊,大侠们只知道自己直接的朋友是谁,很多人压根就不认识队长,要判断自己的队长是谁,只能漫无目的的通过朋友的朋友关系问下去:“你是不是队长?你是不是队长?”这样一来,队长面子上挂不住了,而且效率太低,还有可能陷入无限循环中。于是队长下令,重新组队。队内所有人实行分等级制度,形成树状结构,我队长就是根节点,下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候,只要一层层向上问,直到最高层,就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通,至于他们是如何连通的,以及每个圈子内部的结构是怎样的,甚至队长是谁,并不重要。所以我们可以放任队长随意重新组队,只要不搞错敌友关系就好了。于是,门派产生了。
并查集
下面我们来看并查集的实现。 int pre[1000]; 这个数组,记录了每个大侠的上级是谁。大侠们从1或者0开始编号(依据题意而定),pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己,那说明他就是掌门人了,查找到此为止。也有孤家寡人自成一派的,比如欧阳锋,那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁?不认识!要想知道自己的掌门是谁,只能一级级查上去。 find这个函数就是找掌门用的,意义再清楚不过了(路径压缩算法先不论,后面再说)。

int find(int x)//查找我(x)的掌门
{
    int r=x;//委托 r 去找掌门
    while (pre[r ]!=r)//如果r的上级不是r自己(也就是说找到的大侠他不是掌门 = =)
    r=pre[r];//r 就接着找他的上级,直到找到掌门为止。
    return r;//掌门驾到~~~
}

再来看看join函数,就是在两个点之间连一条线,这样一来,原先它们所在的两个板块的所有点就都可以互通了。这在图上很好办,画条线就行了。但我们现在是用并查集来描述武林中的状况的,一共只有一个pre[]数组,该如何实现呢? 还是举江湖的例子,假设现在武林中的形势如图所示。虚竹小和尚与周芷若MM是我非常喜欢的两个人物,他们的终极boss分别是玄慈方丈和灭绝师太,那明显就是两个阵营了。我不希望他们互相打架,就对他俩说:“你们两位拉拉勾,做好朋友吧。”他们看在我的面子上,同意了。这一同意可非同小可,整个少林和峨眉派的人就不能打架了。这么重大的变化,可如何实现呀,要改动多少地方?其实非常简单,我对玄慈方丈说:“大师,麻烦你把你的上级改为灭绝师太吧。这样一来,两派原先的所有人员的终极boss都是师太,那还打个球啊!反正我们关心的只是连通性,门派内部的结构不要紧的。”玄慈一听肯定火大了:“我靠,凭什么是我变成她手下呀,怎么不反过来?我抗议!”抗议无效,上天安排的,最大。反正谁加入谁效果是一样的,我就随手指定了一个。这段函数的意思很明白了吧?

void join(int x,int y)//我想让虚竹和周芷若做朋友
{
    int fx=find(x),fy=find(y);//虚竹的老大是玄慈,芷若MM的老大是灭绝
    if(fx!=fy)//玄慈和灭绝显然不是同一个人
    pre[fx ]=fy;//方丈只好委委屈屈地当了师太的手下啦
}

再来看看路径压缩算法。建立门派的过程是用join函数两个人两个人地连接起来的,谁当谁的手下完全随机。最后的树状结构会变成什么样,也完全无法预计,一字长蛇阵也有可能。这样查找的效率就会比较低下。最理想的情况就是所有人的直接上级都是掌门,一共就两级结构,只要找一次就找到掌门了。哪怕不能完全做到,也最好尽量接近。这样就产生了路径压缩算法。

设想这样一个场景:两个互不相识的大侠碰面了,想知道能不能揍。 于是赶紧打电话问自己的上级:“你是不是掌门?” 上级说:“我不是呀,我的上级是谁谁谁,你问问他看看。” 一路问下去,原来两人的最终boss都是东厂曹公公。 “哎呀呀,原来是记己人,西礼西礼,在下三营六组白面葫芦娃!” “幸会幸会,在下九营十八组仙子狗尾巴花!” 两人高高兴兴地手拉手喝酒去了。 “等等等等,两位同学请留步,还有事情没完成呢!”我叫住他俩。 “哦,对了,还要做路径压缩。”两人醒悟。 白面葫芦娃打电话给他的上级六组长:“组长啊,我查过了,其习偶们的掌门是曹公公。不如偶们一起及接拜在曹公公手下吧,省得级别太低,以后查找掌门麻环。” “唔,有道理。” 白面葫芦娃接着打电话给刚才拜访过的三营长……仙子狗尾巴花也做了同样的事情。 这样,查询中所有涉及到的人物都聚集在曹公公的直接领导下。每次查询都做了优化处理,所以整个门派树的层数都会维持在比较低的水平上。路径压缩的代码,看得懂很好,看不懂也没关系,直接抄上用就行了。总之它所实现的功能就是这么个意思。

举个例子

从前有个Life Winner,ItSukaShido。有一天,他遇见了她,他对她一见钟情,她对他却并无回忆。为了讨好Zuhang Chen(陈紫涵),Shido必须与她搭讪。那么问题来了,我们怎么知道他和她是否是同一所高中的学生呢?

再举个例子

几年后,如圣经中的Adam和Eve一般,ItSukaShido和Zuhang Chen诞生了爱的结晶。但是,无数宗代相传,孩子们早已忘记了自己的祖先的名字。那么,为了帮助这些孩子,我们只需要以O(n-1)的时间,从前之后,顺着生命的延续,告诉他们祖先的名字——Shido。然后他们的父亲都变成Shido了…(路径压缩)

听说的样题

/* 显然我并没有做过 */
HDU 2094 产生冠军
HDU 1213 How Many Tables
POJ 1611 The Suspects 裸题
POJ 2524 Ubiquitous Religions 裸题
POJ 1182 食物链 扩展
POJ 2492 A Bug’s Life 扩展
POJ 1861 Network 并查集+最小生成树
POJ 1703 Find them, Catch them 扩展
POJ 2236 Wireless Network 应用题
POJ 1988 Cube Stacking 应用题
POJ 2912 Rochambeau 难题
POJ 1733 Parity game 难题
POJ 1308 Is It A Tree? 难题

云里雾里的最小覆盖圆[完结]

思路

随机打乱所有点 初始化圆为1,2两个点为直径的圆 for i in (3,n+1) : if i不在当前圆内 : 设圆为1,i两个点为直径的圆 for j in (1,i) : if j不在当前圆内 : 设圆为j,i两个点为直径的圆 for k in (1,j) : if k不在当前圆内 : 设圆为i,j,k三个点确定的圆 在随机打乱的前提下,可以使用期望证明整个算法的复杂度是O(n)的。 ——keavil

几个关键定义

F[i]是P[1],P[2]…P[i]的最小覆盖圆
FF[j]是P[1],P[2]…P[j],P[i] 的最小覆盖圆,就是FF[j]是在i已经确定的情况下定义的
FFF[k]表示P[1]-P[k]∪P[i]并P[j]的最小覆盖圆

几乎都是改的LXY的代码Z]9F[T{S_F@JDH~KYDUHCQP

#include "cstring"
#include "cstdio"
#include "cmath"
#include "algorithm"
#include "cstdlib"
#include "iostream"
#define N 1100000
#define eps 1e-6
using namespace std;

struct point{
	double x,y;

	//点坐标快速赋值函数
	inline point(){}
	inline point(double X,double Y)
	{
		x = X;
		y = Y;
	}
	//重定义运算符
	inline point operator - (const point &t)const
	{
		return point(x - t.x,y - t.y);
	} 
	/*
		inline bool operator <(const point &t) const
		{
			return x < t.x;
		}
	*/
}p[N],T;

struct Cir
{
	point o;
	double r;

	inline double path(const point &A)//绝对距离
	{
		return sqrt(pow(A.x,2)+pow(A.y,2));
	}

	inline void get1(const point &A,const point &B)//以两点的path为直径的圆
	{
		o = point((A.x+B.x)/2,(A.y+B.y)/2);
		r = path(o-A);
	}

	inline void get2(const point &A,const point &B,const point &C)
	{
		double k1,b1,k2,b2;

		point m1,m2;//A-B B-C中点
		m1 = point((A.x+B.x)/2.0,(A.y+B.y)/2.0);//快速赋值
		m2 = point((B.x+C.x)/2.0,(B.y+C.y)/2.0);
		//P[8] = point(2,3) 快速点坐标赋值

		/*
			Warning!!!!
			万一 B.x = A.x 呢
			你就 /0 了!
			这是错误
			反正概率很小
			那就懒得改了
		*/

		k1 = (B.y-A.y)/(B.x-A.x);
		k1 = -1.0 / k1;
		k2 = (C.y-B.y)/(C.x-B.x);
		k2 = -1.0 / k2;

		b1 = m1.y - k1 * m1.x;
		b2 = m2.y - k2 * m2.x;

		o.x = (b2 - b1)/(k1 - k2);
		o.y = k1 * o.x + b1;
		r = path(A-o);
	}
}C,AA;

inline int sn(double x)
{
	return x < -eps ? -1 : x > eps ? 1 : 0;
}

inline bool in(const point &P,Cir C)
{
	double l = AA.path(P - C.o);
	return sn(l - C.r) <= 0;
	/*
		等价于
		if(sn(l - C.r) <= 0)
			return 1;
		else
			return 0;
	*/
}


int main()
{
	freopen("cir.in","r",stdin);
	//Init

	long long n;
	scanf("%lld",&n);
	for (long long i = 1; i <= n; i++)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	
	//Solve

	//long long i,j,k;
	C.get1(p[1],p[2]);
	//printf("%lf %lf %lf\n", C.o.x,C.o.y,C.r);//first circle

	for (int i = 3; i <= n; i++)//跳过前3点
	{
		if (!in(p[i],C))//假如不在圆内
		{
			C.get1(p[1],p[i]);
			for (int j = 1; j <= i-1; j++)
			{
				if (!in(p[j],C))
				{
					C.get1(p[j],p[i]);
					for (int k = 1; k <= j-1; k++)
					{
						if (!in(p[k],C))
						{
							C.get2(p[j],p[k],p[i]);
							//printf("%lf %lf %lf\n", C.o.x,C.o.y,C.r);
						}
					}
				}
			}
		}
	}
	printf("%lf %lf %lf\n", C.o.x,C.o.y,C.r);
	return 0;
}