清华集训Day1=。=

=。=这里是没什么卵用的一句开场白喵~(终于连这样一句话都懒得写了)

今天是清华集训Day1=。=,题目在dalao们眼里好像比较水,然而作为蒟蒻的场外选手雪舞喵常规的敲了3个暴力,勉强水了119分。

那么来看题吧=。=今天雪舞喵聪明的把原题粘了上来

T1 Alice和Bob又在玩游戏

时间限制: 2.0 秒 内存限制: 1024 MB

【题目背景】

Alice和Bob又在玩游戏。

【题目描述】

有n个节点,m条边(0≤m≤n−1),构成若干棵有根树,每棵树的根节点是该连通块内编号最小的点。
Alice和Bob轮流操作(Alice先手),每回合选择一个没有被删除的节点x,将x及其所有祖先全部删除,不能操作的人输。
需要注意的是,树的形态是在一开始就确定好的,删除节点不会影响剩余节点父亲和儿子的关系。
比如:1-3-2 这样一条链,1号点是根节点,删除1号点之后,3号点还是2号点的父节点。
假设Alice和Bob都足够聪明,问Alice有没有必胜策略。

【输入格式】

从标准输入读入数据。
第一行一个正整数T,表示该测试点有T组数据;接下来T组数据。
对于每组数据: 输入第一行两个整数n,m,分别表示点数和边数(节点从1开始编号)。 接下来m行,每行两个正整数a,b,表示节点a和节点b之间有一条边,输入数据中没有重边。

【输出格式】

输出到标准输出。
输出T行,每行输出Alice先手并且Alice和Bob都足够聪明的情况下谁获胜.

【样例】

输入

4
2 1
1 2
3 2
1 2
1 3
2 0
3 1
1 2

输出

Alice
Alice
Bob
Alice

说明

输入共4组数据;
第一组数据输入是一条链,Alice可以一次性把所有节点都删掉。
第二组数据,Alice先手第一步删除1号点即可胜利。

【数据范围和约定】

对于10%的数据,m=0;
对于20%的数据,1≤n≤20;
对于40%的数据,1≤n≤100;
对于60%的数据,1≤n≤1000;
对于100%的数据,1≤T≤10,1≤n≤1e5,∑n≤2e5,0≤m≤n−1,输入数据保证不会形成环,且每棵树的大小≤5e4。


这好像是哪里的一道原题=。=大概是线段树启发式合并模板题什么的,然而雪舞喵并没有见过

于是雪舞喵就写了个60分n^2暴力,直接深搜算每颗子树的sg函数,假设已经算出某个点的所有子树的sg函数,只需要枚举一下删除子树中的哪个点,把删除后的sg函数都求出来,找个不在其中的最小值即可=。=

考试的时候雪舞喵还一直在想这题100分是不是有什么奇怪的结论之类的,然后证了半天都没证出来,结果标算是把一棵子树中的sg函数用线段树之类的维护一下,然后启发式合并什么的,好像可以卡到nlogn,然而雪舞喵一脸蒙蔽,过会找那个课件看看去。

代码最后一块贴吧=。=


T2 魔法小程序

时间限制: 1.0 秒 内存限制: 32 MB

【题目描述】

有这样一段魔法的程序:(其中所有的数组下标从 0 开始,所有的除法的结果为整数,且向 0 取整)

定义数组 a[], b[], c[]

 

这个程序目前十分低效(显然时间复杂度至少是平方量级的),无法快速完成百万级别的计算,但我们现在的任务不仅是优化它。
现在我们给出这段程序的输出,你需要完成一个“非确定机”的工作,给出一个可能的输入。
请注意本题的空间限制。

【输入格式】

从标准输入读入数据。
第一行输入 a 的长度。第二行输入一些空格隔开的正整数,依次表示 a 的每一项。
第三行输入 c 的长度。第四行输入一些空格隔开的整数,依次表示 c 的每一项。
每一行相邻的两个数,恰好用一个空格隔开。

a 的长度不会超过 1e4。a 的每一个元素不会超过 1e9。
c 的长度不会超过 1e6。对 c 的元素的范围没有直接的保证,但是保证存在一个解 b,使得 b 的每一个元素的绝对值都不超过 1e9。
a 和 c 都至少拥有一个元素。

【输出格式】

输出到标准输出。
第一行输出 a 的长度。第二行输入一些空格隔开的正整数,依次表示 a 的每一项。
第三行输出 b 的长度。第四行输入一些空格隔开的整数,依次表示 b 的每一项。
每一行相邻的两个数,恰好用一个空格隔开。
你必须保证你输出的 b 的每一个元素的绝对值都不超过 1e9。保证存在一个可行的解满足这个条件。如果有多个可行的解,你可以输出任意一个。

【样例】

输入

3
2 3 3
10
1 0 2 9 3 8 4 7 5 6

输出

3
2 3 3
10
1 -1 1 8 1 -2 3 4 0 -10

【子任务】

本题分为若干个子任务,但是不采用捆绑测试。每个子任务中有若干个测试点,只要你对于某个测试点的输出正确,即可获得该测试点的分数。某个子任务的分数是指其各个测试点的分数之和。

我们设 n 为 c 的长度,设 m 为 a 的长度,则:

子任务1(4分)

n=1,m≤100。

子任务2(22分)

n≤100,m≤100。

子任务3(6分)

n≤1000,m≤1000。

子任务4(8分)

n≤1e4。

子任务5(21分)

n=2^m,a 中所有元素均为 2。

子任务6(9分)

a 中所有元素均为 2。

子任务7(7分)

m=1。

子任务8(12分)

m≤20。

子任务9(11分)

没有特殊的约定。


=。=这题是saffah出的,非常友好,只要把输入原样输出就可以得到4分……

然而好像坑也挺多的,然而那是针对写标算的dalao们的,跟写暴力的雪舞喵并没有什么关系=。=

首先小小的吐槽一下这奇妙的伪代码(c艹+py+中文?)

然后一看程序好像是b向量乘个01矩阵等于c向量=。=

后来我发现中间那段循环都跟b的内容没啥关系啊,于是就暴力的把中间那个循环跑一遍,跑出个01矩阵。

显然这个矩阵是下三角的,于是直接n^2求一下b就完事了=。=

居然水到了29分=。=原因大概是那个并不捆绑的subtask

然后m=1好像直接二维前缀和就可以了=。=

标算是快速子集和变换(好像是这个名字?)奇妙的推广一下=。=看来雪舞喵也有必要看一下那个快速子集和变换(?)


T3 数据交互

时间限制: 3 秒 内存限制: 512 MB

【问题描述】

一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据 线则看做一条树边。两个服务器进行数据交互时,数据会经过连接这两个服务器的路径上的所有服务 器(包括这两个服务器自身)。每个数据交互请求都有一个非负的重要度,越重要的请求显然需要得 到越高的优先处理权。此外,如果在某一个时刻存在一条非常重要(可以看作重要度无穷大)、且数 据量巨大的交互请求,则所有被该交互经过的服务器都会优先处理这条交互并阻塞,从而导致其他通 过这些服务器的交互出现延迟。

现在,你作为一个网络系统的管理员,要监控整个系统的运行状态。 系统的运行也很简单,在每一个时刻,只有可能出现下列二种事件中的一种:

  • 在某两个服务器之间出现一条新的数据交互请求;
  • 某个数据交互请求结束;

我们假设这些事件中的交互请求的数据量都足够小。你的任务是在每一个时刻的事件结束后,求出:

如果突然出现一条非常重要、且数据量巨大的交互请求,那么因其造成延迟的数据交互请求的重要 度之和最大可能是多少?

【输入格式】

从标准输入读入数据。

输入的第一行包含二个正整数N,M,分别表示服务器的个数、事件(时刻)的个数。

接下来N−1行,每行两个整数u,v,描述一条树边。u和v是服务器的编号,服务器编号1…n。

接下来M行,按发生时刻依次描述每一个事件;即第i行(i=1,2,3,…,m)描述时刻ii发生的事件。事件的描述有两种:

  • + u v w 服务器u和v之间出现了一条重要度为w的数据交互请求
  • − t 时刻t出现的数据交互请求结束

【输出格式】

输出到标准输出。

输出M行,每行一个整数,依次描述在每个事件后,如果突然出现一条非常重要、且数据量巨大的交互请求,那么因其造成延迟的数据交互请求的重要度之和的最大值。如果此时没有任何数据交互请求,输出 0。

【样例】

输入

5 6
1 2
2 4
4 3
2 5
+ 1 4 7
+ 5 5 4
- 1
+ 3 4 3
+ 1 1 6
- 2

输出

7
11
4
7
10
9

【数据范围与约定】

对于30%的数据,有1≤N,M≤100。

另有30%的数据,没有第二类事件,即所有请求都不会结束。

对于100%的数据,有1≤N,M≤1e5,所有的输入数据均为 int 范围内的非负整数。

保证输入合法。


这题好像挺难的,全场没有AC的,只有一个90和一个60,其他大部分都是和雪舞喵一样的30分暴力=。=(顺便一提90的好像是被浪浪卡了?)

由于讲题的时候我一直在尝试弹幕功能,于是没怎么听标算是啥,好像是对于每条路径在点上加正权在边上加负权,然后维护个最长链次长链啥的=。=

总之30分暴力还是很简单的,每个点上挂个bool数组,对于添加直接暴力遍历那一条路径加上去,删除直接把权值改成0,然后计算的时候从每个点dfs一遍统计统计就可以了=。=

那么最后粘一下3道题的雪舞喵暴力代码

T1

T2

T3

12.04.2016

Yukimai

(^=。=^)

发表评论