【East!模拟赛 Round_VI】(YGY_Round) 题目

一. 题目概况

二. 其它限制

代码长度限制为64 K。

全部解释权归编辑者所有。

三. 题目链接

    dark    foul    VN

四. It is a contest by YGY. 

黑暗侵袭

Time Limit: 1 Sec  Memory Limit: 128 MB

Background

此题旨在教学全局最小割Stoer_Wagner算法，大家可以放心AC。

魔神们决定向人界进行无尽的侵袭。

Description

祖安，晴。

魔神们决定侵袭祖安。我们默认1号节点就是魔神们的时空节点，每一波侵袭将从这里开始。

每一波侵袭中，值班魔神将发起若干场战役，每一场战役将会侵袭一个阴暗度最大的未被侵袭城市，而阴暗度则由该城市相邻已被侵袭城市到此城市的思维影响度加和得到。

而如果有多个城市阴暗度相同，则优先侵袭标号小的城市。

比如节点1向节点2有3条无向思维影响，强度分别为2、6、7，而没有别的城市被侵袭，则我们认为此时节点2的阴暗度为2+6+7=15。

但是众星之子索拉卡降临，每次魔神将祖安全部侵袭，她就会拯救整个祖安，并且将最后被侵袭的两个城市拓建成一个大城市，最可怕的是，值班魔神侵袭最后一个城市时的阴暗度还会变成该魔神力量的消耗值。魔神们自然不甘心，于是它们会换一个魔神再次侵袭祖安，直到整个祖安变成一个城市而无法侵袭为止。

现在，战争学院想知道每个魔神消耗了多少力量，同时还需要你，王者召唤师来告诉学院消耗最小的魔神消耗了多少力量，作为回报，会长会给你（233333+他目前心情值）%353个天赋点。

 魔神：包括但不限于卡萨丁、卡尔萨斯……
Input

    第一行包含两个整数n，m 表示城市的个数和思维影响的个数，其中1为魔神侵袭祖安的初始点。

    接下来m行每行三个int：ui,vi,leni表示第i个思维影响在ui到vi之间，强度为leni。

Output

先输出一行若干个数，每行为该值班魔神力量的消耗值。

第二行输出一个数，表示最小的消耗值。

Sample Input 

3 3

1 2 1

2 3 1

3 1 2

Sample Output 

2 3

2
[explaination]

Data Constraint

对于100%的数据，n<=500,m<=10000 。

虚空遁地

Time Limit: 1 Sec  Memory Limit: 128 MB

Background

在地上全是洞的召唤师峡谷，***哪家强？

Description

在环形的召唤师峡谷上，双头雷克赛可以沿着顺时针在没有突刺的平地间行走，或者沿着地洞逆时针回挖，当然，雷克赛并不叫“瓦绝吉”，所以它不会让两个地洞的路径交叉。但它一旦经过某个点，那个点就会形成突刺。而同时某一点还被战争学院设置成了dopo+faker，只要靠近就会被击杀（哪怕是从地底也一样，所以机智的雷克赛会把地洞从环的另一侧挖过去），也就是说此点不能经过。

雷克赛的两个头轮流操纵虚空掘地兽前进，小头先手并且可以随意选择起始节点，大头后手操纵，每次操作可以得到一点身体掌控点数，两个头都想在掌控权比对方大的同时得到尽量多的掌控点数，问最终谁的掌控点数更多？（根据某不知名规则，大头天生有1/6个掌控点数。）

因为直播间放的是小头的直播，所以小头的点数多则认为小头玩得“非常遛”，而点数少则是“污得不行”。

Input

    第一行三个整数n，m，p表示环上有n个点按标号顺时针环形排列，m组地洞，p点有大魔王*2。

接下来m行，每行三个整数u，v表示u~v有一个地洞。

Output

    输出一行一个字串，“66666”表示小头点数多，“foul”表示大头点数多。（不输出引号“”）

Sample Input 1

10 0 7

Sample Output 1

66666

Sample Input 2

5 5 3

1 1

1 4

2 3

3 4

4 5

Sample Output 2

66666

Data Constraint

首先对“交叉”进行解释：

不妨把两个洞口a、b看作是一个开口向上的抛物线的两个零点，而抛物线的定义域为[a,b]，“交叉”即两抛物线有交点且此点斜率异号。

1<=P,u,v<=N<=1×10^6

0<=M<=1×10^7

数据保证合法，所有输入均∈N+。

Blank_Killer  留白过多有害健康(但是这并不是雷克塞)

血色薇恩

Time Limit: 3 Sec  Memory Limit: 512 MB

Background

薇恩讨厌魔法，所以她的所有技能都没有ap加成。但是为什么她有蓝条呢？233。。

    现在薇恩想要解析她的蓝条，然后把它移除。

Description

猎魔人协会发现薇恩的蓝条由魔法符文构成，每点蓝量都是一个符文串，并且对其它蓝量造成影响，而且这种影响还随时间而改变，且失去了这点蓝量进入下一点蓝量时，当前的第一个符文就会消失。

容易发现vn的蓝条就是一个字符串，第k点蓝量代表的符文串就是她初始蓝量第k长的后缀。

现在他们收集了一场solo里每个时刻vn的蓝量波动数据，发现了每秒某些蓝量会互相影响，而这个影响值就是这些蓝量两两之间的容纳度（最长公共前缀）。

猎魔人协会非常穷酸(dou)，没有计算机，还不想求助战争学院，只能来威胁你来免费解析这些数据，说不解析就给0分。

Input

第一行两个自然数n、m，表示vn的蓝量和solo持续时长。

接下来的一行为一个字符串，表示初始蓝量符文串。

再接下来m行，每行先是一个自然数pi，表示第i个时刻有pi点蓝量互相影响；然后是pi个自然数，表示这些互相影响的蓝量。

Output

输出m行，每行一个影响值，因为答案可能过大，所以需要mod 23,333,333,333,333,333。(2后16个3,质数)

Sample Input

7 3

popoqqq

1 4

2 3 5

4 1 2 5 6

Sample Output

0

0

2

[explaination]

Query1: oqqq并不能再影响谁。

Query2: poqqq和qqq之间并不能互相影响。

Query3: popoqqq和opoqqq并非不是不能再影响谁，而qqq和qq并不是不能互相影响，而且他俩之间影响度为2。

Data Constraint

vn也很穷，所以她只有小写字母的符文（所有字符都是小写字母）

有的时候（对于10%的数据）vn空蓝，只有不超过1点蓝量。

有的时候（对于30%的数据）vn在solo，只有不超过1000点蓝量。

有的时候（对于60%数据）vn无视了装备的“唯一”被动，所以她可能出了6个大天使之杖，有不超过10000点蓝量。

当然，毕竟天下有千千万个秀得飞起的vn（对于100%的数据），所以把这么多vn的蓝量加和，还是可以有不超过500，000点蓝量的。

众所周知，vn把敌方控住就可以一套带走（对于30%数据），所以solo时间只有1s。

当然，vn毕竟是个大后期（对于100%的数据），所以solo的时间可能很长很长，但是可以保证的是每一次能互相影响的蓝量总数加和不会超过3，000，000。

Blank_Killer  留白过多有害健康(但是这并非不是薇恩)

题解暂时先不发，过一周再发。

随便提提，

第一题SW算法裸题，第二题有向有环有限制博弈，多想想开始与结束、还有必胜节点神马的，第三题后缀树+虚树。

传到BZOJ上的题意可能比这个清晰一些233，，

【East!模拟赛 Round_VI】(YGY_Round) 题目

原文：http://blog.csdn.net/vmurder/article/details/42804061