8.29~8.30六校联考模拟赛

解题报告

data文件里面的maker.py是数据生成器

首先是每个题目的状况

Day1

T1

感觉像是签到题
就按签到题做了
没什么好说的
除了中间无数次输入格式搞错。。。。。。

T2

特判的时候。。
啊。
这是交上去的代码的样子

很好
下一步放大

......
我
为了
检验
另外30%代码的正确性
把最暴力的代码(就是前30%)给注释掉了
呵
凉了凉了

T3

我这题。。。
心路历程。。。

60分O(t*n^3)做法
构建两张图
对两张图分别跑floyd
若某两个点之间的路径可以被松弛
那么这组数据不合法

100分
注意到每两个点之间有且仅有一条边
//假设把所有的边都反过来
//那么要满足的条件就变成了:
// 如果存在u->v和u->w,那么是否在同一张图中存在边v->w
///////////////////

bfs
每个入队的状态都标记
如果在扩展的时候遇到某个可以到达的点没有被标记到
那么这张图不合法

一张合法的图必定是一张从中间向四周延伸的图
第一个点到这张图里面所有点都有边
第二个点到这张图里面除了第一个点都有边
第三个点到这张图里面除了第一第二个点都有边
...
怎么找第一个点?

以上是对正解的尝试。。。。。。。。。 nlh于10:30记

蹲完坑回来之后继续考虑...本来打算10:30之后就只写暴力的
对于每个点,统计其在两张图里面能够到达的点的个数,分别记录在siz1[]和siz2[]
假设第一张图的点数为sum1,第二张图的点数为sum2
若第一张图中的每个点的siz1[]排序后形成了一个0~sum1-1的连续序列
因为两个点之间有且仅有一条边
...大样例第一组数据就过不去的说
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊不管了我就是要假定这样合法啊!
咳咳
第二张图同理
em
假装这样做是正确的。。。
(:з」∠) //nlh于10:33记

//不管怎样先写完暴力

......
看见那个128MB我有点虚
不然我判个环试试?????
有环就一定不行
没环就一定行
仔细想想好像到现在没找到反例的说...
就用这个思路了
虽然这个思路比上面10:33的更不靠谱,但考虑到128M的限制这个思路更安全不是吗
╮(╯▽╰)╭
nlh于11:05记

据说有种O(n*sqrt(n))的判断三元环的方法
可惜我不会
ε=(′ο｀*)))唉
只能写dfs咯
但愿数据不要太强qwq
nlh于11:15记

我都觉得自己天秀。。。
至于为啥写这些东西。。。
思绪太纷杂，突然想起就赶紧写下来。
写着写着就这样了。
而且还没实现。
GG

Day2

T1

评测机是Ubuntu 16.04
而我输出long long 用了I64d
GG

T2

暴力一会不会
写了个骗分(假设没有修改操作的情况下是最优解,然后就假(G)了)

T3

调试语句没删
可以
这比T1的lld写成I64d还优秀

然后是考场代码

y
h
p
w
s
l

每个题目的各种思路及正解代码

Day1

T1

算法1
分别用一个字符串来记录每个用户的用户名。
每次用「I_love_」加上一个用户的用户名来更新另一个用户的用户名。
最后直接输出 1 号用户的用户名

但是如果出一个非常恶心的数据比如:
2喜欢1
3喜欢2
4喜欢3
...
1000喜欢999
以上5行循环M/N次
那么来讨论用了什么来存储字符串
char 很好你MLE了
string 很好你TLE了
GG

算法2
为每个用户名建立一个节点。
记录每个用户当前的用户名是哪个节点。
每当有用户更改用户名时，创建一个新的节点，设置其父节点为另一个用户的当前用户名。
最后沿着父节点找到最初的用户名，并在之前输出若干个「I_love_」

算法2的代码

T2

30分做法
枚举每个区间计算平均值是否小于等于k
虽然k是整数，但还是要在计算平均值的时候用double

60分做法(a[i]<=a[i+1])
维护一个区间[l,r]其中r每次右移一位，然后向右移动l直到这个区间的平均值大于k
每次移动都对应一个合法的区间

100分做法
每组数据把所有的值减去k
那么题目转化为求有多少区间的和为负数
如果对转化后的区间做前缀和
那么问题转化为有多少区间$s_r-s_{0jl-1}\le0$
也就是说有多少$s_r\le s_l$
与逆序对类似(逆序对是$s_r\lt s_l$)
用树状数组或mergesort求解
注意特判l==0的情况

代码

T3

30分做法
O(n^3)
对于两个子图，分别枚举其中的三个点，判断其是否合法

或者更加装逼一点可以说考虑到如果存在u->v和v->w但是不存在u->w那么u->w的路径会被松弛
那么或许可以用Floyd
对两张图分别跑Floyd
如果某张图里面某点到某点的路径是可以被松弛的，那么这张图一定不合法

100分做法
考虑到两个点u,v之间有且仅有一条有向边，那么讨论着条边的情况
u->v 佳佳占领 u->v 菱菱占领
v->u 佳佳占领 v->u 菱菱占领
那么也就是说如果满足前提条件u->v和v->w在同一张图里面，有以下三种情况是不合法的
1. w->u在另一张图里
2. u->w在另一张图里面
3. w->u在同一张图里面
对于1.3两种情况，原图是显然有环的，而对于情况2，将其中一人的所有边反向之后得到的图是有环的
那么对原图和将一个人的边取反之后得到的图跑拓扑排序
如果两张图里面都没有环，那么输出YE5，否则输出N0
时间复杂度O(n^2)

另外就是对于这个题目用邻接表和邻接矩阵存储的时间复杂度和空间复杂度并没有太大差别

代码

Day2

T1

30分做法
枚举每个区间并计算答案

100分做法
考虑上面暴力时候的过程
令l=1,r=n
每次更新答案并分别尝试将l右移和r左移，分别向下递归
这样的做法是$\Theta(2^n)$
但是可以发现这样重复枚举了很多的情况，因为[l+1,r]和[l,r-1]的后继状态都覆盖了[l+1,r-1]以及其所有子区间
那么考虑：
假设$a_l\gt a_r,[l,r]$的答案为x，那么以r为右端点，以$[l+1,r-1]$为左端点的答案一定不会大于x，所以这些区间不需要考虑
那么$a_l\le a_r$的情况同理
只需要分别讨论就行了，每次统计答案之后让较小的一个端点向中间移动即可，代码只有些微的差异
时间复杂度$\Theta(n)$

代码

T2

30分
搜索，每次选两个数字进行操作并更新答案
可以发现最多操作n+2次
所以时间复杂度$\Theta(n^{n+2})$

100分
假设$a | b = a+x,a \& b = a-x$，那么$(a+x)^2+(b-x)^2=a^2+b^2+2*x(x+a-b)\ge a^2+b^2$
所以当能进行操作的时候，进行操作总是更优的
然后观察进行操作带来的贡献
进行这种操作相当于把两个数不同的二进制位全部移动到一个数上，最终尽量多的二进制位会被聚集在一起
那么首先统计每个二进制位有多少个，然后枚举每个数，从零开始将尽量多的二进制位加给它
时间复杂度$\Theta(n\log n)$

代码

T3

30分
枚举所有可能的放置情况，判断其是否合法，统计答案
$\Theta(2^{nm})$

50分做法
dp[i][p][q]表示前i行，上一行状态为p，当前行状态为q的方案书
其中p和q是unsigned int，其每个二进制位表示一行的某个位置是否放棋子
枚举前一行的状态，统计答案
用位运算判断其状态是否合法
时间复杂度$\Theta(n*2^3n)$

100分做法
对于50分的做法，考虑到每行的合法状态其实很少，远小于$2^n$，那么可以预处理出所有的合法状态，对50分做法进行修改，把p、q改为合法状态的编号
经过测试n=1时合法状态数只有406个
那么整个算法的时间复杂度降低为$\Theta(n\sigma^3)$,其中$\sigma\le 406$

代码