月度归档:2017年04月

BZOJ 4801: [Lydsy2017年4月月赛]打牌(枚举)

Description

小Q同学正在和糖老师一起打(d)牌(p)。这个游戏需要52张牌,分为四种花色(H表示红心,S表示黑桃,C表示梅花
,D表示方块),每种花色有A,K,Q,J,10,9,8,7,6,5,4,3,2这么多张牌,其中A是最大的,2是最小的。游戏的第一
轮从小Q同学开始,他会先展示一张牌,然后轮到糖老师展示一张牌。双方都展示完手牌之后进入结算环节,展示
较大的牌的人会获得这一轮的胜利(如果两个人展示的牌大小相同那么先展示牌的人获胜),并且得到较大的牌对
应的分值,分值就是牌上的数字,比如J是11,Q是12,K是13,A是1。结算后扔掉这一轮展示的牌,然后从上一轮
的获胜者开始下一轮,游戏进行到双方打完所有牌为止。为了简单起见,现在每个人都只有两张牌,并且全过程中
双方都能看到对方的手牌,也就是明牌打。你需要求出两个人都使用最优策略的情况下,小Q同学的得分减去糖老
师的得分的最大值。

Input

第一行是一个正整数 T (1≤T≤10000),表示测试数据的组数。
每组测试数据包含两行,每行有两张牌,分别表示小Q和糖老师手上的牌。每张牌会按照 XY 的格式给出,其中 X
是A,K,Q,J,T(表示10),9,8,7,6,5,4,3,2,1之一, Y 是花色(H,S,C,D之一)。保证任何一张牌至多出现一次。

Output

对于每组测试数据,输出一个整数,表示结果。

Sample Input

2
AH 2S
3C 4D
2H 5S
3C 4D

Sample Output

-3
1
打牌的情况只有两轮,所以暴力枚举第一个人先出哪张牌,然后再枚举第二个人出哪张牌,第二个人肯定是要让第一个人比自己多的越少越好。所以min,max取取就好了。。。。

 

BZOJ 4144: [AMPPZ2014]Petrol(多源最短路+离线并查集)

Description

给定一个n个点、m条边的带权无向图,其中有s个点是加油站。
每辆车都有一个油量上限b,即每次行走距离不能超过b,但在加油站可以补满。
q次询问,每次给出x,y,b,表示出发点是x,终点是y,油量上限为b,且保证x点和y点都是加油站,请回答能否从x走到y。

Input

第一行包含三个正整数n,s,m(2<=s<=n<=200000,1<=m<=200000),表示点数、加油站数和边数。
第二行包含s个互不相同的正整数c[1],c[2],…c[s](1<=c[i]<=n),表示每个加油站。
接下来m行,每行三个正整数u[i],v[i],d[i](1<=u[i],v[i]<=n,u[i]!=v[i],1<=d[i]<=10000),表示u[i]和v[i]之间有一条长度为d[i]的双向边。
接下来一行包含一个正整数q(1<=q<=200000),表示询问数。
接下来q行,每行包含三个正整数x[i],y[i],b[i](1<=x[i],y[i]<=n,x[i]!=y[i],1<=b[i]<=2*10^9),表示一个询问。

Output

输出q行。第i行输出第i个询问的答案,如果可行,则输出TAK,否则输出NIE。

Sample Input

6 4 5
1 5 2 6
1 3 1
2 3 2
3 4 3
4 5 5
6 4 5
4
1 2 4
2 6 9
1 5 9
6 5 8
 

Sample Output

TAK
TAK
TAK
NIE
发现题目只询问加油站之间的距离,假如我把所有的加油站之间的距离搞出来就好了,也就是想办法把非加油站的点去掉。发现对于每个非加油站点,如果到这个点的剩余油量可以到达离他最近的加油站,那么去那个加油站加满油再回来,一定不会比不去差。那我们可以想象一下有一条边\((u,v)\),从\(u\)到\(v\)的过程,\(u\)和\(v\)都不是加油站。那么两点距离可以视为从离\(u\)最近的加油站\(A\)行驶到\(u\)再走\((u,v)\)这条边,再到\(v\)最近的加油站\(B\)。这样的话我们就相当于把这些加油站抠了出来,之间互相连边。
所以我们先用Dijkstra跑多源最短路,求出每个点的距离最近加油站。然后修改一下边权为\(w+dis[u]+dis[v]\),我们把边和询问都按照从小到大排序。对于每个询问,把小于他的\(b\)的边全部加入,然后判断一下询问的两个点是否联通就好了。

 

BZOJ 3943: [Usaco2015 Feb]SuperBull(最大生成树)

Description

Bessie and her friends are playing hoofball in the annual Superbull championship, and Farmer John is
 in charge of making the tournament as exciting as possible. A total of N (1 <= N <= 2000) teams are
 playing in the Superbull. Each team is assigned a distinct integer team ID in the range 1…2^30-1
to distinguish it from the other teams. The Superbull is an elimination tournament — after every ga
me, Farmer John chooses which team to eliminate from the Superbull, and the eliminated team can no l
onger play in any more games. The Superbull ends when only one team remains.Farmer John notices a ve
ry unusual property about the scores in matches! In any game, the combined score of the two teams al
ways ends up being the bitwise exclusive OR (XOR) of the two team IDs. For example, if teams 12 and
20 were to play, then 24 points would be scored in that game, since 01100 XOR 10100 = 11000.Farmer J
ohn believes that the more points are scored in a game, the more exciting the game is. Because of th
is, he wants to choose a series of games to be played such that the total number of points scored in
 the Superbull is maximized. Please help Farmer John organize the matches.
贝西和她的朋友们在参加一年一度的“犇”(足)球锦标赛。FJ的任务是让这场锦标赛尽可能地好看。一共有N支球
队参加这场比赛,每支球队都有一个特有的取值在1-230-1之间的整数编号(即:所有球队编号各不相同)。“犇”
锦标赛是一个淘汰赛制的比赛——每场比赛过后,FJ选择一支球队淘汰,淘汰了的球队将不能再参加比赛。锦标赛
在只有一支球队留下的时候就结束了。FJ发现了一个神奇的规律:在任意一场比赛中,这场比赛的得分是参加比赛
两队的编号的异或(Xor)值。例如:编号为12的队伍和编号为20的队伍之间的比赛的得分是24分,因为 12(01100)
Xor 20(10100) = 24(11000)。FJ相信比赛的得分越高,比赛就越好看,因此,他希望安排一个比赛顺序,使得所
有比赛的得分和最高。请帮助FJ决定比赛的顺序

Input

The first line contains the single integer N. The following N lines contain the N team IDs.
第一行包含一个整数N接下来的N行包含N个整数,第i个整数代表第i支队伍的编号, 1<=N<=2000

Output

Output the maximum possible number of points that can be scored in the Superbull.
一行,一个整数,表示锦标赛的所有比赛的得分的最大值

Sample Input

4
3
6
9
10

Sample Output

37

HINT

样例解释:
FJ先让编号为3和编号为9的队伍进行比赛,然后让编号为9的队伍赢得比赛(淘汰编号为6的队伍),现在
剩下了编号为6910的队伍。然后他让编号为6和编号为9的队伍比赛,然后让编号为6的队伍赢得比赛。现在编号为6
10的队伍留了下来最后让编号为6和编号为10的队伍比赛,让编号为10的队伍赢得比赛。所有比赛的得分和就是:(
3Xor9)+(6Xor9)+(6Xor10)=10+15+12=37
一场比赛淘汰一个球队,所以\(n\)个球队共需要\(n-1\)场比赛。\(n \leq 2000\),我们可以\(n^{2}\)建图,求出异或权值,然后跑个最大生成树好了。。。
感觉稠密图Kruskal果然是没有prim跑得快,跑了2s多。。。