/*

试一试：
看看我如何状态转移
总满意度我看看，每进入一个新人，算一下他将就好还是已有的某个人将就好

好像得排序，具体怎么排不知道

看一下前8组是否能过，n<=30


先dfs看看，O(3^n)，2.058911e+014，显然TLE了


200
1e7
可以O(n^3)

第12可以水过去

想想前8或前11如何得分

显然，需要决定谁去A,谁去B,谁去C。求总和。但是不能简单取最大值

想一个快于等于O(n^3)的


先想c=0，即一半去A一半去B
如果这样，需统计B比A大的和A比B大的
哪一种少优先选择，其次从多的那一种只能选一部分去另一个了。此时让差小的去另一个更优。
时间复杂度O(nlogn),即使用了priority_queue也没法进一步优化最坏情况
此时8组到手。

看看此时有去C的了，……
分为3类:A最大的，B最大的，C最大的。因为交换无影响
设最多的为a,第二为b，最少为c
显然，不可能a和b同时大于n/2
所以只有a里的人能将就，去b和去c如何定?
若a多出来的人都去b完全可以，因为a+b<n
所以将A根据差排序决定去B还是去C。
因为无需关心a,b,c具体是啥，算出差即可。

无需关心?好像需要关心a,b,c中a的值，b和c不用关心
100分到手。

好像不对。我需要记录最大值从哪里取的，只从从a取的里面减即可

所以应该可以:

================================================================

第二题，大图论

我想想……

只有两种途径让它变成连通图

1.修复已有边
2.使用新增点，并加入新增点和已有点的连边

怎么修复可以跑一遍kruskal(或Prim)。但是不然，现在有新增点了。
新增点与每个点都能有连边，所以，有个笨办法，根据新增点状况进行dfs
这样O(mlogm*2^k)(kruskal)
O(n^2*2^k) (prim)

想想怎么基于其中一个改
cc
直接跑一遍prim能过4个
O(n^2*2^k)能过8个
O(mlogm*2^k)能过4个

prim基于已访问过点，kruskal基于边，想一下基于prim的吧

基于prim，可以不加任何点求出最小生成树。再想想如何在prim过程中加点使得加过点之后更小

加点只需要付加过点的权值。即已有这个点，边是能考虑的。

那么怎么加点呢?Kruskal还是Prim?

啊?特殊性质A?
如果有特殊性质A，即直接把这些点加进去即可，可以不连通这些点?
不连通这些点?K还是P?
只要不连通这些即可，prim是把已联通的连通块连接边加入新点，kruskal是选所有边不构成环的最小边。

我想想……

如果存在两个点使得经其中一个新点路更短，则路最短的新点一定在答案中。然后
跑一个dijkstra只能获得从一个点的最短路，可能这步"优化"更慢了

先想想特殊A吧

有了特殊A，即求最小生成树，其中几个节点可以是非树节点。

好像既然特殊A有后半句，找一下最大的i，之后前i个点都免费了。此时只剩下所有点跑个最小生成树，同时删去

预期4个

==================================
先做第三个吧。

第三个，我需要先算出字符串的区别。即掐头去尾

这样之后，有一个子串关系:

a<=b<=c

a是掐头去尾后的 b是s_{i,1} c是原串

只要对于每个有此子串关系的s_{i,1}判断替换之后的会怎样就行.

接下来就是如何快速判断是否有这个关系。


判断可以用KMP做到O(s)，s是字符串长度。我看看这种做法能得多少分


5e6?
接下来，既然总长是5e6，且为多测，O(L1+n*L2)


根据上面的思路，我需要先把每个小串的next表算出来，这一步O(L1)
然后对于每个q,求出它掐头去尾的next表，然后比较每个串是否符合这个子串关系
设这个q大串长度为s
O(s*n)
即O(n*L2)

q=1对此做法无影响
若有B，掐头去尾肯定是baaa...a或aaaa...b
根据b位置左边的a个数和右边的a个数就行。
比较子串关系变成O(1)
此时总复杂度是O(n*q)
看看能不能让它带log



好了，预期6组

试试哈希?

哈希之后，如何判断是否有子串关系?有点难

===================================
看第四题吧。
第四题我看一下是否会做

第四题我可以写个dfs骗骗分

看看折半搜索?
n!好像没法折半，有没有剪枝
如果没面试的所有人耐心都低于了没通过的，则break掉
想想其他的。
想不到。就这样写吧
第四题有个特殊性质A，有A的直接阶乘取模。



m=n时全1则阶乘取模，有0则0

m=1?
这个我想想……
m=1时只录取一个人即可。则可以所有情况减都不录取的情况

都不录取看看能不能求

都不录取?
第一天是1时一定能有人录取
如果第一天是0，不知道了。

此时预期7个

好了
第二题预期4组
第三题6组
第四题7组

那么先做第四题


*/
int main(){
	return 0;
}








