本文主要是介绍noi.ac 七一挑战赛，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

A

\(\;\)
给定\(n\)个字符串\(a_1,a_2,\cdots,a_n\)和\(b\)，\(q\)次询问
每次询问给定\(i_1,i_2,...,i_k\)和\(x,y\) \(i_1<i_2<\cdots < i_k\)
求出\(a_{i_1}+a_{i_2}+\cdots+a_{i_k}和b[x...y]\)的最长公共子序列
\(n\leq 10, |b|\leq 10^3, q\leq 10^6\)
20s,2048MB
观察到\(q\)很大，说明我们不大可能对于每组询问再在线的去处理
可能是预处理一些东西，然后对于每组询问快速的得到答案

Step 1

\(\;\)
不妨先去处理\(v_{i,x,y}\)表示\(a_i\)与\(b[x..y]\)的最长公共子序列
大概就是枚举一下\(x\)，然后在求一下\(a_i\)和\(b[x\;to\;n]\)就可以了
时间复杂度：\(O(n \times |b|^2 \times |a|)\)
上限是\(10^9\)，没有什么问题
\(\;\)

Step 2

\(\;\)
发现\(n\)很小，所以最多有1024种选法
设\(f_{S,x,y}\)表示选了\(S\)这个状态的字符串集，匹配\([x...y]\)的最优答案
但你会发现一件事情，这样会导致空间达到\(10^9\)，不行。
考虑优化空间。
既然全部存不下来，我们不妨去一半一半的存，所谓的折半搜索
在查询的时候，我们就只需枚举一下断点取最大值就可以了
怎么求\(f\)?
在\(x,S\)和最后一个字符串固定的情况下，现在相当于我们是\(y\)一直向右移动，现在想要找到一个断点使得答案更优
若直接暴力枚举转移，时间复杂度必然会多出一个\(|b|^3\)，还要乘上一堆东西，不行。

Step 3 (决策单调性)

\(\;\)
考虑最优决策有什么性质，在\(y\)向右滑动的过程中，我们发现决策点也一定是单调不降的
设\(ch_{i,j}\)表示\([i...j]\)的最优决策在哪里，即有：\(ch_{i,j+1}\geq ch_{i,j}\)
这个真的需要非常感性的理解
我口胡一波：若加上\(j+1\)后，对决策点有影响，我们肯定是\(a_i\)的某个位置和\(j+1\)，且这个位置应该在原先匹配的几对点的最后面
若刨去这个点，单看前面，那么决策点就一定不会往左挪，但有可能往后挪，使得让左边更宽敞，且右边因为腾出去了一个位置，可能就会导致最左边的那个点向右移
\(\;\)
然后就可以用决策单调性把\(O(|b|^3)\)优化成\(O(|b|^2 log|b|)\)
\(\;\)

Code

http://noi.ac/submission/131764

B

\(\;\)
现在有\(n\)个人，其中一些人可以进行搏斗，而搏斗关系构成了一张有向无环图，一条边\((u,v,w)\)表示如果\(v\)打败了\(u\)，可以获得\(w\)的收益。
每个人有一个\(a_i\)，表示初始的经济是多少，且如果他这是第\(x+1\)次获胜，之前已获胜了\(x\)次，他会获得\(n-x\)的收益
设\(X\)为所有活下来的人的总收益，\(Y\)为一次都没赢过的人的数量，现在要最大化\(\frac{X^k}{Y},(k\in \{1,2\})\)
\(n\leq 150,\;m\leq 500,\; a_i\leq 10000, \;w\leq 1000\)
\(\;\)

我们注意到一个人能干掉很多个人，但不能被很多人干掉。
所以这就出现了一个类似二分图匹配的东西（但其实不是二分图匹配）
考虑用网络流来做
\(\;\)

Step 1 建图

\(\;\)
将每个点拆成两个点\(x,x'\)
因为一个人最多会被干掉一次，所以从源点\(S\)向\(x\)连一条容量为\(1\)，费用为\(0\)的边
考虑搏斗关系，显然会从\(u\)向\(v'\)连一条容量为\(1\)，费用为\(w\)
然后考虑一个点胜利之后的收益，所以从\(x'\)向汇点连容量为全为\(1\)，但费用是\(n, n-1,n-2....\)的边
然后我们直接跑一个最大费用流即可
\(\;\)

Step 2 处理Y

\(\;\)
我们发现这个\(Y\)非常的讨厌，比较难去维护它
有一种思路是：我们就去枚举\(n-y\)，即至少赢了一场的人的数量。
即：我们从\(x'\)向伪汇点\(T'\)连一条容量为1，费用为\(INF+n\)的边，然后从\(x'\)向汇点\(T\)连\(n-1,n-2...\)的边，然后从\(T'\)向\(T\)连一条容量为\(y\)的边
这样建有什么好处？
因为我们建了费用为正无穷的边，所以我们显然会贪心的把这些边给流满，也就说只要我们存在1种方案使得至少有\(n-y\)个人赢，我们的流一定会满足这种方案
而且在满足有\(n-y\)个人赢的情况下，因为跑的是最大流，我们显然会使其余的收益尽可能的大。
这样就满足了勒令\(y\)个人输，且求出在这种情况下最优收益是多少

Code

http://noi.ac/submission/131845

C

\(\;\)
给定一个\(1,n\)的排列，设其最长上升子序列长度为\(m\)
每一次询问给出\(k\)
选出\(i_1,i_2,\cdots,i_m\)，最大化\(\sum_{j=2}^m ln(a_{i_j}-a_{i_{j-1}}+k)\)

找特殊性质

\(\;\)
设\(f_i\)表示以\(i\)为结尾的最长上升子序列的长度
发现，所有\(f_i=x\)的点，随着下标增大，\(a_i\)是递减的。
由于\(x\)层在最终的dp中一定是由第\(x-1\)层转移而来的
一种朴素想法就是暴力枚举转移，复杂度\(O(n^2)\)
\(\;\)

又是决策单调性

为什么这玩意的转移还是满足决策单调性的呢?
假如说对于\(f_i=f_j=x,(i<j)\),\(i\)的最优决策点是\(k\)，\(j\)的最优决策点\(l\)小于\(k\)
那么即可得到:\(f_l+ln(a_j-a_l+k)\geq f_k+ln(a_j-a_k+k)\)
但因为我们知道\(f_l+ln(a_i-a_l+k)\leq f_k+ln(a_i-a_k+k)\)
由于\(ln\)函数随着\(x\)增大增长的越来越慢，而两边\(ln\)里面相当于同时加上\(a_j-a_i\)
而又因为\(a_l>a_k\)，所以势必左边的增量会更少，那么出现矛盾了。
所以我们就可以用决策单调性解决这个问题
\(\;\)

Code

http://noi.ac/submission/131778

这篇关于noi.ac 七一挑战赛的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！