title : HNCPC Multi-university Training Round3
date : 2022-7-29
tags ：ACM,练习记录
author : LINNO
没补的题有EIK。按难度顺序。
签到题，照题意算税收。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include签到题，照题意判断输出哪个语句。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
return 0;
}
队友过的题，给定最开始拥有的数字和每个数字能涂的颜色，数字可以整数划分，问总共能够产生多少种集合。（存在数字不同或者某一个数字颜色不同则集合不同）
数据很小，爆搜+打表就能过。
#include 给定n，构造长度为 2 n 2^n 2n的01串，使得从原串开始二分得到的子串种数最多（就是把一个串按中间分为左右个子串，然后子串再继续这样划分）。
构造思路：0000~1111一共有16种不同的字符，每个长度为4，那么将0和15、1和14…7和8拼在一起是一个最优的方案，可以拼 2 7 2^7 27的长度，那我们确认一下n的范围按，然后照同样的方法把 2 20 2^{20} 220次方搞出来就可以了。n<=4的时候按人类智慧写一下。
#include队友过的题，没看。
#include 给n堆东西，其中每堆都有ai个坏的和bi个好的，每次你可以从两堆之中个取一个（你不能控制取到好的还是坏的），问最终是否不能从两堆之中都取到好的。
我们肯定每次取都是一好一坏，那么推一推不等式可以知道最终不能取到两个好的条件为 有某一堆 ∑ b − b i < = ∑ a , 并且记其他堆坏的加起来比该堆好的多的堆数唯一 有某一堆\sum b-b_i <=\sum a ,\\并且记其他堆坏的加起来比该堆好的多的堆数唯一 有某一堆∑b−bi<=∑a,并且记其他堆坏的加起来比该堆好的多的堆数唯一
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
return 0;
}
背包问题，W是1e12。给定每个物品的体积和价值，然后问如果把W改成 3 W 2 \frac{3W}{2} 23W时的一个选择方案，使得该方案比能装入容量为W物品时的最优解价值更高。
在原最优解的基础上随便筛入一个物品肯定是一个解，但是我们没办法得到原来的最优解。背包多出来了1/2的容量，那么可以按照这个大小划分两类物品，先在小于等于W/2的物品中贪心选取一组解，原最优解中大于W/2的物品不超过1个，那么我们枚举一下需要进行替换的大物品，就做完了。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
return 0;
}
题意：给定n ( n ≤ 10 ) (n\le 10) (n≤10)个厨师可做的菜数、每道菜所需要做的次数 a i ( a i ≤ 50 ) a_i(a_i\le50) ai(ai≤50)。每次可以选两道菜并花 c i , j ( c i , j < 100 ) c_{i,j}(c_{i,j}<100) ci,j(ci,j<100)的时间去做，问最小需要的总时间，如果无解输出-1。
思路：数据很小，拆成 ∑ a \sum a ∑a个点然后两两做最小权匹配，套个带花树的板子即可。
#include问[a,b]中相同数字出现位数最多有多少个，有多少个数可以达到这个位数。
一看题目就是数位DP,跟一般数位DP的形式一样，考虑每一位对答案的贡献，记录当前位置枚举的数字上界、以及有无前导0。
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
return 0;
}