东北四省赛Feedback
VCVCVCFop_zz · · 个人记录
Replay
ZXH：
1、 前期小失误比较多，水题没有1A有比较大劣势
2、 在1011被卡T无法自拔，1005感觉很靠谱但是wa有点裂开
3、 1011太过于习惯依赖数据结构混，把单调队列忘了，凭空多个log被卡T也是活该。。虽然ST表能过这很不公平（
HJZ:
-
1002:“exclusive OR operation”看成OR属实毒瘤，明明1005用的XOR，不过也是我眼残。
-
1003:f(0)需要特判，因为不明显出现在数据范围里结果卡了半天，自闭。
-
1008:字典序在比较数字和字母时就是按ascii排，由于初期不确定一直没敢写。
-
1009:真正的签到题，初期榜上没人切导致大家都以为是毒瘤题。
WPH:
他们两个吐槽完了。
被打爆了。
Problems
1001
Unsolved
1002
Solved by hjz &wph 04:14:23
题意：3*n个人，分成m个队，有3个组，每组有n个人，每个人有一个值。一个队的实力值=f(a,b)+f(a,c)，求一个方案，让m个队的实力值最大
题解：从n<=200不难想到网络流，从S’到S连边限制m个队，S连到B，B连到A，A连到A’限制A数量，A‘连到C，C连到T，跑费用流即可，一开始把xor看成or，比较坑，模板签到。
1003
Solved by hjz &zxh 01:15:11(-3)
题意：有函数f，给n,m，求f(n)+f(f(n))+f(f(f(n)))…递归m次。
题解：不难发现每次期望除2，于是很容易到个位数，个位数之后f不变，暴力到n=f(n)之后统计即可。要注意f(0)=0
1004
Solved by hjz 00:14
题意：给定每个人到达终点的时间，终点有一个高度从0~H往返的皇冠，当一个人到达终点时皇冠高度<=h，则这个人直接触摸它，否则会一直等到皇冠高度<=h时触摸。每个人还有一个延迟时间，即当其在t时刻触摸皇冠，系统会判定为t+c[i]时刻触摸。输出最早触摸皇冠的人。
题解：模拟，对每个人计算其触摸皇冠的时间，加上延迟取最小即可。
1005:
Unsolved by zxh&wph (-6)
虽然没过但是还是能写（
题意：求一个N*N的向量，要字典序最小，且线性无关
题解： 贪心发现前面的K+1个应该是形如
000001111
000010111
000011011
000011101
000011110
发现偶数情况下不可行，但是当时没发现这个问题，虽然已经意识到偶数好像不太对劲但还是没花力气去想..不知道在干什么
奇数时，这样线性基后k+1位都已经塞满了，于是前面只能往高位放，简单的构造（然后没过呜呜呜呜呜
1006
Unsolved
1007
Solved by wph 00:16:44(-1)
题意
k个人做游戏。
玩n轮，k个人轮流上。
当轮到一个人的时候，那个人拿牌堆最上面的一张作为自己的牌（如果原来已有，则替换原来的）。
一共有四种不同类型的牌，每张牌上有数字。
每轮游戏结束后，统计玩家手上权值和为5的牌的种类有多少个。
最后输出每轮统计值的总和。
题解
模拟一下，动态维护每种牌有的权值是多少。
1008
Solved by wph&zxh 03:03:58(-2)
题意：删除一个字符，要求压缩后长度最小的情况下字典序最小
题解：不难发现，要使得长度减小的条件是一个字符出现1,2，或者16的幂次。存下后就是各种情况讨论字典序。注意细节即可
Problem 1009:
Solved by wph && hjz 01:30:28
题意：一张等边权完全图，从中选择一些边保留，使得到的图任意两点的最短距离等于题给距离。
题解：先找出所有题给距离的最小值，那么一条边的边权便是这个最小值。然后两点最后有边直接相连当且仅当两点的题给距离为此最小值，于是答案便是最小值的个数。
1010：
Solved by zxh 00:28:09(-1)
题意：给定N,N*N网格图，一个点颜色不同于给定的四个点，问染色数量
题解：写个BFS发现，N>=4时只有两个联通块，手玩1,2,3,即可，签到
1011
Unsolved by zxh (-8)
题意：懒得说了
题解：发现所谓憋气就是花u的代价从一个k*k的矩阵中转移，显然是个二维RMQ问题，其余DP没有任何难度，在每一列开一个单调队列做RMQ即可（std）
据说世末是ST表过的…线段树因为常数大卡不过去，线段树做法大概也是每一列开线段树，然后在处理一行的时候预处理出前面列可行域的RMQ，再建一个线段树做RMQ，确实可以用ST表代替但是就是不想写（淦
然后这么板的单调队列都没反应过来确实是生锈了..
1012
Unsolved
1013：
Solved by zxh 00:11:59(-1)
题意 1是好数，若n是好数,5n+13, 13n+5, 5n−13, 13n−5也是好数，输入x问是不是好数
题解：BFS即可，签到