老年退役选手体验NOIP2018被题目吊打…
题目大意: 给定长为n n n 数列a [ i ] a[i] a [ i ] ,每次操作可以任选L , R L,R L , R ,令a [ i ] − = 1 a[i] -= 1 a [ i ] − = 1 ,其中i ∈ [ L , R ] i \in [L,R] i ∈ [ L , R ] 。求最少操作次数使a [ i ] a[i] a [ i ] 全都变为0。1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1 ≤ n ≤ 1 0 5 。
去年NOIP前后就听说有道和NOIP2013积木大赛一模一样的题。
总之就是可以把操作反过来看成是将一个全0数列区间加1变成a [ i ] a[i] a [ i ] ,然后区间加显然每次范围越大越好,那么每次区间加左端点一定尽可能靠左,所以只需要求有多少个块左边没有别的块即可。不难得出这个数目就是∑ max ( a [ i ] − a [ i − 1 ] , 0 ) \sum\max(a[i]-a[i-1],0) ∑ max ( a [ i ] − a [ i − 1 ] , 0 ) 。复杂度O ( n ) O(n) O ( n ) 。
1 2 3 4 5 6 #include <bits/stdc++.h> using namespace std ;#define rint register int inline int rf () {int r;int s=0 ,c;for (;!isdigit (c=getchar());s=c);for (r=c^48 ;isdigit (c=getchar());(r*=10 )+=c^48 );return s^45 ?r:-r;}int n, a, b, s; int main () {for (n = rf(); n--; b = rf(), s += max(b-a,0 ), a = b); return !printf ("%d\n" ,s);}
题目大意: 给定大小为n n n 集合a [ i ] a[i] a [ i ] ,求一个最小的集合b [ i ] b[i] b [ i ] ,满足集合{ ∑ x i a [ i ] ∣ x 1 , x 2 , . . . , x n ∈ N } = { ∑ x i b [ i ] ∣ x 1 , x 2 , . . . , x m ∈ N } \lbrace \sum x_ia[i] | x_1,x_2,...,x_n \in \mathbb N \rbrace = \lbrace \sum x_ib[i] | x_1,x_2,...,x_m \in \mathbb N \rbrace { ∑ x i a [ i ] ∣ x 1 , x 2 , . . . , x n ∈ N } = { ∑ x i b [ i ] ∣ x 1 , x 2 , . . . , x m ∈ N } 。输出集合b b b 的大小即可。T ≤ 20 T \le 20 T ≤ 2 0 组数据,每组数据n ≤ 100 n \le 100 n ≤ 1 0 0 ,1 ≤ a [ i ] ≤ 2.5 × 1 0 4 1 \le a[i] \le 2.5 \times 10^4 1 ≤ a [ i ] ≤ 2 . 5 × 1 0 4 。
数据范围限制比较诡异,似乎在暗示什么O ( T n m ) O(Tnm) O ( T n m ) 或者O ( T ( n 2 + m ) ) O(T(n^2+m)) O ( T ( n 2 + m ) ) 类似的做法。直接按照要求模拟: 通过递推求出目标集合{ ∑ x i a [ i ] ∣ x 1 , x 2 , . . . , x n ∈ N } \lbrace \sum x_ia[i] | x_1,x_2,...,x_n \in \mathbb N \rbrace { ∑ x i a [ i ] ∣ x 1 , x 2 , . . . , x n ∈ N } 然后贪心反推出b [ i ] b[i] b [ i ] ,即从小到大扫描目标集合,如果某个位置不能被表示,就加入b b b 集合中,然后更新更大的数能否被表示。这样就得到了一个O ( T ( n m + m 2 ) ) O(T(nm+m^2)) O ( T ( n m + m 2 ) ) ,其中通过a [ i ] a[i] a [ i ] 构造目标集合是O ( n m ) O(nm) O ( n m ) 的,而从目标集合构造b [ i ] b[i] b [ i ] 看上去是O ( m 2 ) O(m^2) O ( m 2 ) 的。
实际上,仔细观察对于目标集合构造b [ i ] b[i] b [ i ] 过程的两层循环:
1 for (rint i = 1 , j; i <= m; i++) if (d[i]&&!f[i]) for (++s, j = i; j <= m; f[j] |= f[j-i], j++);
内层循环发生一次,则++s
,但是s
就是b b b 集合的大小。显然有∣ b ∣ ≤ ∣ a ∣ = n |b| \le |a| = n ∣ b ∣ ≤ ∣ a ∣ = n ,因此这个二层循环均摊复杂度是不会超过O ( n m ) O(nm) O ( n m ) 的。
因此写个暴力交上去就可以过。复杂度O ( T n m ) O(Tnm) O ( T n m ) ,本人为方便剪枝排了一下序,复杂度O ( T n ( m + log n ) ) O(Tn(m + \log n)) O ( T n ( m + log n ) ) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include <bits/stdc++.h> using namespace std ;#define rint register int inline int rf () {int r;int s=0 ,c;for (;!isdigit (c=getchar());s=c);for (r=c^48 ;isdigit (c=getchar());(r*=10 )+=c^48 );return s^45 ?r:-r;}bool d[25005 ], f[25005 ]; int T, n, m, s, a[105 ];int main () { for (f[0 ] = d[0 ] = 1 , T = rf(); T--; printf ("%d\n" ,s)) { n = rf(); generate(a+1 ,a+n+1 ,rf); sort(a+1 ,a+n+1 ); memset (d+1 ,0 ,m=a[n]); memset (f+1 ,0 ,m); s = 0 ; for (rint i = 1 , j; i <= m; i++) for (j = 1 ; j <= n && a[j] <= i; d[i] |= d[i-a[j]], j++); for (rint i = 1 , j; i <= m; i++) if (d[i]&&!f[i]) for (++s, j = i; j <= m; f[j] |= f[j-i], j++); } return 0 ; }
题目大意: 给定一棵n n n 个点的边带权树,求在其上选择至少m m m 条不重边的链,最短链最长是多少。m < n ≤ 5 × 1 0 4 m \lt n \le 5 \times 10^4 m < n ≤ 5 × 1 0 4 。
首先把题目的恰好m m m 拓展成至少m m m ,对答案没有什么影响,因为条数更多显然不优,但考虑起来会容易一些。
刚开始想了一会儿没啥思路,重新读了一遍题,看到那个"最短赛道的长度尽可能大"的时候突然激起了OI选手的原始冲动~~,找回了当年的感觉~~…
所以肯定是二分答案了,那么就是要求最多可以拼出多少条长度不小于m i d mid m i d 的链。树形DP每个点开一个vector
或multiset
贪心搞一搞就行了: 因为每个点只能向上传一个链,那么每个点处一定贪心匹配,然后将剩下的最长链传上去。这里的贪心匹配就是指对于所有儿子传上来的链,已经足够长的直接单独成链,不够长的找一个最短的加起来足够长的匹配。复杂度O ( n log n log w ) O(n \log n \log w) O ( n log n log w ) 。二分边界可以做一点小剪枝。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <bits/stdc++.h> using namespace std ;#define MAXN 50000 #define rint register int inline int rf () {int r;int s=0 ,c;for (;!isdigit (c=getchar());s=c);for (r=c^48 ;isdigit (c=getchar());(r*=10 )+=c^48 );return s^45 ?r:-r;}int fir[MAXN+5 ], f[MAXN+5 ], tot, n, m, s, lef, mid, rig, Ans; multiset <int >::iterator it; multiset <int > S;struct Edge {int to,nex,w; Edge(){} Edge(int _to, int _nex, int _w){to=_to,nex=_nex,w=_w;}}e[(MAXN<<1 )+5 ];inline void Add (int a, int b, int w) {e[tot] = Edge(b,fir[a],w), fir[a] = tot++, e[tot] = Edge(a,fir[b],w), fir[b] = tot++;}void DP (int p, int fa) { for (int u = fir[p], v; ~u; (v=e[u].to)^fa?DP(v,p),0 :0 , u = e[u].nex); S.clear(); f[p] = 0 ; for (int u = fir[p], v; ~u; (v=e[u].to)^fa?e[u].w+f[v]<mid?S.insert(e[u].w+f[v]),0 :++s:0 , u = e[u].nex); for (int a; S.size(); a = *S.begin(), S.erase(S.begin()), (it=S.lower_bound(mid-a))!=S.end()?S.erase(it),++s:f[p]=max(f[p],a)); } int main () { n = rf(); m = rf(); memset (fir+1 ,-1 ,n<<2 ); for (rint i = 1 , u, v, w; i < n; u = rf(), v = rf(), Add(u,v,w=rf()), rig += w, i++); for (lef = 1 , rig /= m; lef <= rig; mid = lef+rig>>1 , s = 0 , DP(1 ,0 ), s >= m ? Ans = mid, lef = mid+1 : rig = mid-1 ); return !printf ("%d\n" ,Ans); }
~~果然是老了啊…~~这道题交上去居然WA了。
注意一个细节: 一定要提前删去本来就足够长的,不能偷懒,以防后面一个本来就足够长的链因为被搜索到而和别人匹配,这不会立即影响匹配数,但是会影响上传值。例如有两个子树3和10,m i d = 10 mid = 10 m i d = 1 0 ,这时10必须单独成链,然后上传3;而如果13成链却只能上传0,所以不能认为13还是10成链对答案没有影响。
出于同样的原因,这里一定是从最小值开始找一个最小的能和它匹配的,而不是从最大值开始找一个最小的能和它匹配的,例如三个子树4 5 6,m i d = 9 mid = 9 m i d = 9 ,如果从最小值开始则9成链,上传6,从最大值开始虽然10也能成链,但只能上传5了。
顺带复习一下二分查找和邻接表…
题目大意: 给定一棵n n n 点树或环套树,求一个字典序最小的DFS序。n ≤ 5 × 1 0 3 n \le 5 \times 10^3 n ≤ 5 × 1 0 3 。
刚读完题,没看m m m 的条件,感觉没思路。乍一看上去和Codeforces1106D 挺像的,但是很快就可以意识到,那道题可以随便回溯,这道题只能回溯一次。
发现只有树或者环套树以后就可以做了,但是O ( n ) O(n) O ( n ) 做法实现起来应该会挺麻烦的,又纠结了一段时间最后发现n ≤ 5 × 1 0 3 n \le 5 \times 10^3 n ≤ 5 × 1 0 3 …
感觉自己不是很擅长这类环套树题目,找环后进行环上处理的过程总是感觉很痛苦…还好这道题O ( n 2 log n ) O(n^2 \log n) O ( n 2 log n ) 可以过: 枚举环套树环上一条边删去跑最小字典序DFS。
于是也没有管常数,实现方式比较取巧: 因为懒得去找环了,所以枚举删所有边,如果删完以后还有环,在DFS的时候会死循环,当检测到循环(同一个点经过两次)的时候,就把当前序列的首项改为正无穷直接退出,字典序就是正无穷了,绝对不会被选上。
而且…最小字典序DFS空间复杂度怎么控制空间啊?搞得我只能开vector<int> q[5005]
了…感觉这题写得又丑又慢又难受…起码代码不压行最短榜排到第二了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> using namespace std ;#define rint register int inline int rf () {int r;int s=0 ,c;for (;!isdigit (c=getchar());s=c);for (r=c^48 ;isdigit (c=getchar());(r*=10 )+=c^48 );return s^45 ?r:-r;}int fir[5005 ], n, m, tot, ban = -1 ; vector <int > S, T, q[5005 ]; bool b[5005 ];struct Edge {int to,nex; Edge(){} Edge(int _to, int _nex){to=_to,nex=_nex;}}e[10005 ];inline void Add (int a, int b) {e[tot] = Edge(b,fir[a]), fir[a] = tot++, e[tot] = Edge(a,fir[b]), fir[b] = tot++;}inline void Cmin () {for (rint i = 0 ; i < n; i++) if (S[i]<T[i]){T = S; return ;} else if (S[i]>T[i]) return ;}void DFS (int p, int fa) { q[p].clear(); S.push_back(p); if (b[p]){S.resize(n), S[0 ] = n+1 ; return ;} b[p] = 1 ; for (int u = fir[p], v; ~u; (unsigned )(u^ban)>1 &&(v=e[u].to)^fa?q[p].push_back(v),0 :0 , u = e[u].nex); sort(q[p].begin(),q[p].end()); for (auto v:q[p]) DFS(v,p); q[p].clear(); } void Work () {S.clear(); memset (b+1 ,0 ,n); DFS(1 ,0 ); Cmin();}int main () { n = rf(); m = rf(); memset (fir+1 ,-1 ,n<<2 ); for (rint i = 1 ; i <= m; Add(rf(),rf()), i++); for (rint i = 0 ; i < n; T.push_back(n-i), i++); if (m<n) Work(); else for (ban = 0 ; ban < tot; Work(), ban += 2 ); for (rint i = 0 ; i < n; printf ("%d%c" ,T[i],"\n " [i<n-1 ]), i++); return 0 ; }
事后补题:
整理一下思路: 首先将DFS序不完整,即最后一定要回溯到1,这对答案没有影响。然后任何一种方案就都可以分为6部分: 从1好到出发并经过一部分子树到达环上一点x x x ,从x x x 开始绕着环走并经过一部分子树到达y y y ,掉头绕着走经过剩下的子树回到x x x ,继续绕着走并经过一部分子树到达y y y 前一个点,掉头绕着走经过剩下的子树回到x x x ,从x x x 回溯经过剩下的子树到1。
那么不在环上的部分就是直接套最小字典序DFS,在换上的时候就顺着环走,只需要求出掉头的点即可。
掉头是从第二部分到第三部分,所以掉头点就是"从x x x 开始绕着环走并经过一部分子树"的下一个要访问的点标号大于"掉头绕着走经过剩下的子树"的下一个要访问的点的标号。
"从x x x 开始绕着环走并经过一部分子树"每个点的流程是先访问这个点,然后从小到大访问这个点子树中所有标号小于下一个点的,不访问标号大于下一个点的,然后走向下一个点重复。
"掉头绕着走经过剩下的子树"每个点的流程是掉头回溯到一个点,从小到大访问这个点子树中所有未访问的点,然后继续回溯。
所以掉头的条件就是【环上下一个点】标号大于【环上上一个子树有剩余的点的最小直接儿子】标号。
一开始纠结了挺久,总觉得这样有问题: 不能很好处理x x x 点,因为如果x x x 点的子树中有一个包含1,这个子树已经访问过了,会有问题。不过后来意识到没有影响。因为从1走上来以后一定第一个走x x x ,然后走x x x 的一部分子树,然后走x x x 环上邻居中标号较小的那个。因此从一开始就走那个标号小的邻居,x x x 点处是不可能掉头的。
看上去很复杂,模拟会很难受,不过学习别人/自己思考了一下实现的细节技巧,可以大大降低代码复杂度,感觉很巧妙:
代码第6行DFSc(p,fa)
函数。
对于带有顺序问题的环套树问题一般考虑用DFS找环。顺带复习一下Tarjan…
代码第5行vector<int> e[5005]
。
跑最小字典序DFS也只能vector<int> q[5005]
了,但是可以不用邻接表而用vector
存边,这样q
和边表实际上是共用的,而且可以在DFS之前一劳永逸地排序。之前没有这样做是因为O ( n 2 log n ) O(n^2 \log n) O ( n 2 log n ) 做法中需要枚举边,枚举边的时候邻接表显然比vector
方便得多。
代码第5行DFSa(p)
函数。
事实上不需要真的比较字典序,最小字典序DFS在边表排过序以后可以大胆直接输出。注意这里采用bool b[5005]
而不是记录上一个点,是为后面方便做准备,而且空间上直接重复利用找环过程中用到的标记数组。
代码第11行。
就是处理环上选择方向的问题。c[0] = c[k]; c[k+1] = c[1];
两句为后面方便做准备。
代码第12 ~ 16行。
直接按照6各部分模拟看上去很麻烦,事实上只需要找到要掉头的边,将那条边删除然后直接套最小字典序DFS。即将所有问题都转化回最小字典序DFS——一个已经被很好解决了的问题。删边实际上也只需要删掉一条单向边就足够了,节省重复编码,不过正因为如此前面需要用bool b[5005]
。
现在代码就又短又快了…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include <bits/stdc++.h> using namespace std ;#define rint register int inline int rf () {int r;int s=0 ,c;for (;!isdigit (c=getchar());s=c);for (r=c^48 ;isdigit (c=getchar());(r*=10 )+=c^48 );return s^45 ?r:-r;}vector <int > e[5005 ]; bool b[5005 ]; int s[5005 ], c[5005 ], n, m, t, k; void DFSa (int p) {printf ("%d " ,p); b[p] = 1 ; for (auto v:e[p]) if (!b[v]) DFSa(v);}bool DFSc (int p, int fa) {b[s[++t]=p] = 1 ; for (auto v:e[p]) if (v^fa){if (b[v]){for (; s[t]^v; c[++k] = s[t--]); c[++k] = s[t--]; return 1 ;} if (DFSc(v,p)) return 1 ;} return b[s[t--]]=0 ;}int main () { n = rf(); m = rf(); for (rint i = 1 , u, v; i <= m; u = rf(), v = rf(), e[u].push_back(v), e[v].push_back(u), i++); for (rint i = 1 ; i <= n; sort(e[i].begin(),e[i].end()), i++); if (m<n){return DFSa(1 ),puts ("" ),0 ;} DFSc(1 ,0 ); c[1 ]<c[k-1 ]?rotate(c+1 ,c+k,c+k+1 ):reverse(c+1 ,c+k+1 ); c[0 ] = c[k]; c[k+1 ] = c[1 ]; for (rint i = 2 , r = c[0 ], j; i <= k; i++) { j = n+1 ; for (auto v:e[c[i]]) v^c[i-1 ]&&v>c[i+1 ]?j=min(j,v):0 ; j<n+1 ?r=j:0 ; if (r < c[i+1 ] || i == k){e[c[i]].erase(lower_bound(e[c[i]].begin(),e[c[i]].end(),c[i+1 ])); break ;} } return memset (b+1 ,0 ,n),DFSa(1 ),puts ("" ),0 ; }
题目大意: 给定一个n × m n \times m n × m 的表格,求有多少种每个格子填充0 0 0 或1 1 1 的方法,使得从( 1 , 1 ) (1,1) ( 1 , 1 ) 到( n , m ) (n,m) ( n , m ) 的单调非上升路径满足: 靠下的路径形成的01序列字典序不小于靠上的路径形成的01序列字典序。其中"靠下"定义为两条路径第一个不同的分叉点处向下走的路径,"靠上"同理定义为向右走的路径。1 ≤ n ≤ 8 , m ≤ 1 0 6 1 \le n \le 8, m \le 10^6 1 ≤ n ≤ 8 , m ≤ 1 0 6 。
提前知道了这道题是个规律题,感觉失去了很多乐趣…不过即使是这样,想要真正做出这道题而不是打表找规律(真香警告)个人感觉依然是比较有挑战的。为方便起见交换n n n 和m m m ,设1 ≤ m ≤ 8 1 \le m \le 8 1 ≤ m ≤ 8 ,m < n ≤ 1 0 6 m \lt n \le 10^6 m < n ≤ 1 0 6 。记A n s m ( n ) Ans_m(n) A n s m ( n ) 为一个m m m 行n n n 列的格子的答案。
A n s 1 ( n ) = 2 n Ans_1(n) = 2^n A n s 1 ( n ) = 2 n ,单独试试就好了。
首先,手玩不难发现第一行总是随便填的,接着会发现每个1左下角就被强制填1了。
仔细思考不难发现,任何一个1,左下角一定全是1。进而得到:
Claim #1: 同一条对角线上,一定左下角全是1,右上角全是0,不能交替出现。
接下来沿着对角线分析,为方便起见对格子进行斜切:
这样每一步都必须向右,只能选择平走或向右下走。那么条件就变成了,对于任意一个竖列,一定上半部分是0,下半部分是1。那么横着看就相当于一个枚举子集。即对于中间的n − m n-m n − m 行:
上面每一行是下一行的子集。这个问题是很好计数的: n个元素的集合( 的 子 集 ) k (的子集)^k ( 的 子 集 ) k 有多少种?答案是( k + 1 ) n (k+1)^n ( k + 1 ) n 。因为这等价于给每个元素表一个序号i ∈ { 0 , 1 , 2 , . . . , k } i \in \lbrace 0,1,2,...,k\rbrace i ∈ { 0 , 1 , 2 , . . . , k } 表示其在前i i i 次取子集的时候都被取到了,第i + 1 i+1 i + 1 次却没被取到。
然后手动枚举两端的情况就得到A n s 2 ( n ) = 2 × 3 n − 1 × 2 = 4 × 3 n − 1 Ans_2(n) = 2 \times 3^{n-1} \times 2 = 4 \times 3^{n-1} A n s 2 ( n ) = 2 × 3 n − 1 × 2 = 4 × 3 n − 1 ,以此类推。
真简单
然而并不是,在m = 3 m = 3 m = 3 的时候这里就开始不一样了。事实上,【任意一个竖列,一定上半部分是0,下半部分是1】只是一个必要条件,而不是一个充分条件。还有什么情况呢?观察之前举得那个例子,就不是一个合法方案:
这是因为竖直有连续2个0出现,那么就会出现一条路径在其左侧分叉,在其右侧汇合,这样两条路径上的01序列完全相同,但是路径上下关系已经确定了,这样后面只要再出现分叉就会有问题。也就是说一旦出现这样一个"平行四边形"结构,那么后面的路径必须完全一样了,因此得到:
Claim #2: 任意竖列上出现连续两个0或1,其后的一个范围内所填的0或1必须相同。具体见下图,同色区域0或1必须相同。
不难发现,这样的结构在第二列就可以出现,于是我们试对于m = 3 m = 3 m = 3 的情况讨论第二列填的是00、01还是11,就可以求得A n s 3 ( n ) Ans_3(n) A n s 3 ( n ) 。
如果第二列填的是00或11,那么如图:
最开始两列只能都填0或1,有4种方法;第三列随便填,有4种方法;此后的n − 3 n-3 n − 3 列就是枚举子集(这时候即使再产生平行四边形结构也对填数方案没有影响了),最后两列有4种方法。方法数就是64 × 3 n − 3 64 \times 3^{n-3} 6 4 × 3 n − 3 。
如果第二列填的是01,那么没有产生平行四边形结构,从第三列开始,如图:
这是候只有011可以不产生平行四边形结构了(011产生的平行四边形结构在最后一行,对答案没有影响)。那么枚举在第i ∈ { m , m + 1 , . . . , n } i \in \lbrace m,m+1,...,n \rbrace i ∈ { m , m + 1 , . . . , n } 列填入了不是011的东西(即000,001和111三种)。方案数就是:
2 × ( ( ∑ i = 3 n − 1 3 ⏟ i × 4 ⏟ i + 1 × 3 n − i − 1 × 2 ⏟ n + m − 1 ) + 3 × 3 ⏟ i = n + 1 × 3 ⏟ ∄ i ) × 2 2 \times \left( \left( \sum_{i=3}^{n-1} \underbrace{3}_{i} \times \underbrace{4}_{i+1} \times 3^{n-i-1} \times \underbrace{2}_{n+m-1} \right) + \underbrace{3 \times 3}_{i=n} + \underbrace{1 \times 3}_{\nexists i} \right) \times 2
2 × ( ( i = 3 ∑ n − 1 i 3 × i + 1 4 × 3 n − i − 1 × n + m − 1 2 ) + i = n 3 × 3 + ∄ i 1 × 3 ) × 2
化简得原式$ = 16 \times 3^{n-2} - 12 + 12 = 16 \times 3^{n-2}$。
所以总方案数就是A n s 3 ( n ) = 64 × 3 n − 3 + 16 × 3 n − 2 = 112 × 3 n − 3 Ans_3(n) = 64 \times 3^{n-3} + 16 \times 3^{n-2} = 112 \times 3^{n-3} A n s 3 ( n ) = 6 4 × 3 n − 3 + 1 6 × 3 n − 2 = 1 1 2 × 3 n − 3 。
当m ≥ 4 m \ge 4 m ≥ 4 的时候,不难发现第三列已经成为了限制因素,因为第三列总是要产生一个平行四边形结构的。
如果第二列填的是00或11,那么同上分析可以得:
有2 × 2 × 4 m − 2 × 3 n − m × 2 m − 1 = 2 3 m − 3 × 3 n − m 2 \times 2 \times 4^{m-2} \times 3^{n-m} \times 2^{m-1} = 2^{3m-3} \times 3^{n-m} 2 × 2 × 4 m − 2 × 3 n − m × 2 m − 1 = 2 3 m − 3 × 3 n − m 。
如果第二列填的是01,第三列填的是000或111,可得:
有2 × 1 × 2 × 5 × 4 m − 4 × 3 n − m × 2 m − 1 = 5 × 2 3 m − 7 × 3 n − m 2 \times 1 \times 2 \times 5 \times 4^{m-4} \times 3^{n-m} \times 2^{m-1} = 5 \times 2^{3m-7} \times 3^{n-m} 2 × 1 × 2 × 5 × 4 m − 4 × 3 n − m × 2 m − 1 = 5 × 2 3 m − 7 × 3 n − m 。
接下来情况就复杂了起来,因为接下来的情况产生平行四边形就不能忽略不计了,观察发现:
右半部分几乎完全相同,且最左上角第一个随便填,那么3 n − m − 1 × 2 m 3^{n-m-1} \times 2^{m} 3 n − m − 1 × 2 m 的系数就几乎完全相同。除了右下角和左下方倒数第二个这种情况会有问题,但是正如我们在算m = 3 m = 3 m = 3 遇到的问题是同样的,要么一直保持同一个方式填充,要么一旦违反这个模式,就会立即进入其他6中情况,枚举违反的位置,可以得到一个以4为公比的等比数列,等比数列求和后会发现4 k 4^k 4 k 转化为2 2 k 2^{2k} 2 2 k 后依然是2 m 2^m 2 m 的倍数。极度不严谨的证明。
因此只需要搞清楚左半部分的方案数即可…打表吧,求了一天没通过严谨可证的方法求出来,果然是老年选手。
提出3 n − m − 1 × 2 m 3^{n-m-1} \times 2^{m} 3 n − m − 1 × 2 m 的系数,对左半边一个直角梯形打表(直角梯形等价于平行四边形割掉右半部分,而右半部分根据如上分析一定至少是2 m − 2 2^{m-2} 2 m − 2 ,那么直接用m × ( m + 1 ) m \times (m+1) m × ( m + 1 ) 平行四边形(即答案)逆推出直角梯形即可):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include <bits/stdc++.h> using namespace std ;#define MOD 1000000007 #define rint register int inline int rf () {int r;int s=0 ,c;for (;!isdigit (c=getchar());s=c);for (r=c^48 ;isdigit (c=getchar());(r*=10 )+=c^48 );return s^45 ?r:-r;}inline int fxp (int s, int n=MOD-2 ) {int a=1 ;for (;n;n&1 ?a=1l l*a*s%MOD:0 ,s=1l l*s*s%MOD,n>>=1 );return a;}int f[9 ] = {0 ,1 ,3 ,14 ,57 ,223 ,887 ,3543 ,14167 };int g[9 ] = {0 ,2 ,9 ,42 ,168 ,666 ,2658 ,10626 ,42498 };int Work (int n, int m) {switch (n<m?n^=m^=n^=m:0 ,m){ case 1 : return fxp(2 ,n); case 2 : return 4l l*fxp(3 ,n-1 )%MOD; case 3 : return 112l l*fxp(3 ,n-3 )%MOD; default : return (n>m?1l l*g[m]*fxp(3 ,n-m-1 )%MOD:1l l*f[m])*fxp(2 ,m)%MOD; }} int main () {return !printf ("%d\n" ,Work(rf(),rf()));}
浪费了一整天的大好时光。
事后咕题:
发现居然有人推出来了?不过依然不是手算的,是用递推求的。感兴趣的可以戳这里 (或者直接去百度)。
坐等谁能手算到8 × 8 8 \times 8 8 × 8 一定要告诉我!!!!!!
题目大意: 给定一棵n n n 个点的树,每个点涂黑或白,黑色有代价,每条边必须有一个黑点,给定m m m 个询问每次固定两个点的颜色,求染色方案的最小代价。n , m ≤ 1 0 5 n,m \le 10^5 n , m ≤ 1 0 5 。
终于可以写一道正经的码代码题目了。
这东西我记得当时叫做"链分治",不过后来好像还是普遍接受了"动态DP"这样一个名字。
链分治的主体思路就是将DP运算看做矩阵运算(重载乘法和加法),然后用树链剖分维护树上矩阵。具体过程就是将一个点的所有轻儿子"浓缩"(这个过程一般具有可减性)到这个点上,对于每条树链做一个链式的DP,即树链上一个点的答案就是链的前缀和。修改的时候修改轻儿子的"浓缩"值即可。
以这道题为例,展示一下链分治的通用思考过程。
首先有DP方程(0表示不放军队,即白色;1反之):
f [ p ] [ 0 ] = ∑ f [ v ] [ 1 ] f [ p ] [ 1 ] = w p + ∑ min ( f [ v ] [ 0 ] , f [ v ] [ 1 ] ) f[p][0] = \sum f[v][1] \\
f[p][1] = w_p + \sum \min(f[v][0],f[v][1]) \\
f [ p ] [ 0 ] = ∑ f [ v ] [ 1 ] f [ p ] [ 1 ] = w p + ∑ min ( f [ v ] [ 0 ] , f [ v ] [ 1 ] )
第二步考虑"浓缩"轻儿子,记录一个轻儿子的贡献和:
g [ p ] [ 0 ] = ∑ v ≠ h v y p f [ v ] [ 1 ] g [ p ] [ 1 ] = w p + ∑ v ≠ h v y p min ( f [ v ] [ 0 ] , f [ v ] [ 1 ] ) g[p][0] = \sum_{v \ne hvy_p} f[v][1] \\
g[p][1] = w_p + \sum_{v \ne hvy_p} \min(f[v][0],f[v][1]) \\
g [ p ] [ 0 ] = v = h v y p ∑ f [ v ] [ 1 ] g [ p ] [ 1 ] = w p + v = h v y p ∑ min ( f [ v ] [ 0 ] , f [ v ] [ 1 ] )
那么用"浓缩"后的值来维护DP值就有:
f [ p ] [ 0 ] = g [ p ] [ 0 ] + f [ h v y p ] [ 1 ] f [ p ] [ 1 ] = g [ p ] [ 1 ] + min ( f [ h v y p ] [ 0 ] , f [ h v y p ] [ 1 ] ) f[p][0] = g[p][0] + f[hvy_p][1] \\
f[p][1] = g[p][1] + \min(f[hvy_p][0],f[hvy_p][1])
f [ p ] [ 0 ] = g [ p ] [ 0 ] + f [ h v y p ] [ 1 ] f [ p ] [ 1 ] = g [ p ] [ 1 ] + min ( f [ h v y p ] [ 0 ] , f [ h v y p ] [ 1 ] )
第三步将DP方程改为矩阵乘法,这里定义取min是矩阵加法,相加是矩阵乘法。
[ + ∞ g [ p ] [ 0 ] g [ p ] [ 1 ] g [ p ] [ 1 ] ] [ f [ h v y p ] [ 0 ] f [ h v y p ] [ 1 ] ] = [ f [ p ] [ 0 ] f [ p ] [ 1 ] ] \left[
\begin{matrix}
+\infty & g[p][0] \\
g[p][1] & g[p][1] \\
\end{matrix}
\right]
\left[
\begin{matrix}
f[hvy_p][0] \\
f[hvy_p][1] \\
\end{matrix}
\right]
=
\left[
\begin{matrix}
f[p][0] \\
f[p][1] \\
\end{matrix}
\right]
[ + ∞ g [ p ] [ 1 ] g [ p ] [ 0 ] g [ p ] [ 1 ] ] [ f [ h v y p ] [ 0 ] f [ h v y p ] [ 1 ] ] = [ f [ p ] [ 0 ] f [ p ] [ 1 ] ]
然后注意一下边界情况: 现在的单位矩阵是[ 0 + ∞ + ∞ 0 ] \left[\begin{matrix}0 & +\infty \\ +\infty & 0 \end{matrix}\right] [ 0 + ∞ + ∞ 0 ] ,而最后的答案就是:
( ∏ p [ + ∞ g [ p ] [ 0 ] g [ p ] [ 1 ] g [ p ] [ 1 ] ] ) [ 0 0 ] \left(\prod_p\left[
\begin{matrix}
+\infty & g[p][0] \\
g[p][1] & g[p][1] \\
\end{matrix}
\right]\right)
\left[
\begin{matrix}
0 \\
0 \\
\end{matrix}
\right]
( p ∏ [ + ∞ g [ p ] [ 1 ] g [ p ] [ 0 ] g [ p ] [ 1 ] ] ) [ 0 0 ]
得到f [ 1 ] [ 0 / 1 ] f[1][0/1] f [ 1 ] [ 0 / 1 ] ,而最后答案又是两者取min
。这里有一个小Trick,观察发现:
[ + ∞ g [ a ] [ 0 ] g [ a ] [ 1 ] g [ a ] [ 1 ] ] [ + ∞ g [ b ] [ 0 ] g [ b ] [ 1 ] g [ b ] [ 1 ] ] = A \left[
\begin{matrix}
+\infty & g[a][0] \\
g[a][1] & g[a][1] \\
\end{matrix}
\right]
\left[
\begin{matrix}
+\infty & g[b][0] \\
g[b][1] & g[b][1] \\
\end{matrix}
\right] = A
[ + ∞ g [ a ] [ 1 ] g [ a ] [ 0 ] g [ a ] [ 1 ] ] [ + ∞ g [ b ] [ 1 ] g [ b ] [ 0 ] g [ b ] [ 1 ] ] = A
展开以后一定是A [ 0 ] [ 1 ] > A [ 0 ] [ 0 ] A[0][1] \gt A[0][0] A [ 0 ] [ 1 ] > A [ 0 ] [ 0 ] 且A [ 1 ] [ 1 ] > A [ 1 ] [ 0 ] A[1][1] \gt A[1][0] A [ 1 ] [ 1 ] > A [ 1 ] [ 0 ] ,因此最后答案就是min(A[0][1],A[1][1])
,可以简化代码。
具体的修改过程需要缜密划分,不要漏掉情况,详见代码中void UP(p)
函数。
复杂度O ( n log n + m log 2 n ) O(n \log n + m \log ^2 n) O ( n log n + m log 2 n ) 。在UOJ上会被Hack数据卡常/卡复杂度成97…这题应该O ( ( n + m ) log n ) O((n + m) \log n) O ( ( n + m ) log n ) 才是intended算法~~,那就先咕了再说~~。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <bits/stdc++.h> using namespace std ;#define MAXN 100000 #define ll long long #define lc(p) (p<<1) #define rc(p) (p<<1|1) #define mid ((lef+rig)>>1) #define INF 100000000000ll #define rint register int inline int rf () {int r;int s=0 ,c;for (;!isdigit (c=getchar());s=c);for (r=c^48 ;isdigit (c=getchar());(r*=10 )+=c^48 );return s^45 ?r:-r;}vector <int > e[MAXN+5 ]; ll f[MAXN+5 ][2 ], g[MAXN+5 ][2 ], T1, T2, A; int w[MAXN+5 ], fa[MAXN+5 ], dep[MAXN+5 ], sz[MAXN+5 ], hvy[MAXN+5 ], pos[MAXN+5 ], top[MAXN+5 ], bot[MAXN+5 ], s[MAXN+5 ], n, m, d;struct Mat { ll c[2 ][2 ]; inline Mat () {c[0 ][0 ]=c[0 ][1 ]=c[1 ][0 ]=c[1 ][1 ]=INF;} inline Mat (ll A, ll B, ll C, ll D) {c[0 ][0 ]=A,c[0 ][1 ]=B,c[1 ][0 ]=C,c[1 ][1 ]=D;}}I(0 ,INF,INF,0 ),C,T,t[262145 ];inline Mat &operator * (const Mat &A, const Mat &B){ C.c[0 ][0 ]=min(A.c[0 ][0 ]+B.c[0 ][0 ],A.c[0 ][1 ]+B.c[1 ][0 ]);C.c[0 ][1 ]=min(A.c[0 ][0 ]+B.c[0 ][1 ],A.c[0 ][1 ]+B.c[1 ][1 ]); C.c[1 ][0 ]=min(A.c[1 ][0 ]+B.c[0 ][0 ],A.c[1 ][1 ]+B.c[1 ][0 ]);C.c[1 ][1 ]=min(A.c[1 ][0 ]+B.c[0 ][1 ],A.c[1 ][1 ]+B.c[1 ][1 ]); return C; } void DFS1 (int p) {dep[p]=dep[fa[p]]+1 ,sz[p]=1 ;for (auto v:e[p])v^fa[p]?fa[v]=p,DFS1(v),sz[p]+=sz[v],sz[v]>sz[hvy[p]]?hvy[p]=v:0 :0 ;}void DFS2 (int p) {s[pos[p]=++d]=bot[p]=p;hvy[p]?top[hvy[p]]=top[p],DFS2(hvy[p]),bot[p]=bot[hvy[p]]:0 ;for (auto v:e[p])v^fa[p]&&v^hvy[p]?top[v]=v,DFS2(v),0 :0 ;}void DP (int p) {g[p][0 ]=0 ;g[p][1 ]=w[p];for (auto v:e[p])v^fa[p]?DP(v),v^hvy[p]?g[p][0 ]+=f[v][1 ],g[p][1 ]+=min(f[v][0 ],f[v][1 ]):0 :0 ;f[p][0 ]=g[p][0 ]+f[hvy[p]][1 ];f[p][1 ]=g[p][1 ]+min(f[hvy[p]][1 ],f[hvy[p]][0 ]);}void BD (int p, int lef, int rig) {t[p]=lef^rig?BD(lc(p),lef,mid),BD(rc(p),mid+1 ,rig),t[lc(p)]*t[rc(p)]:Mat(INF,g[s[lef]][0 ],g[s[lef]][1 ],g[s[lef]][1 ]);}inline void ED (int p, int lef, int rig, int x) {t[p]=lef^rig?x<=mid?ED(lc(p),lef,mid,x):ED(rc(p),mid+1 ,rig,x),t[lc(p)]*t[rc(p)]:Mat(INF,g[s[lef]][0 ],g[s[lef]][1 ],g[s[lef]][1 ]);}inline Mat QU (int p, int lef, int rig, int L, int R) {return L^lef||R^rig?(L<=mid?QU(lc(p),lef,mid,L,min(mid,R)):I)*(R>mid?QU(rc(p),mid+1 ,rig,max(mid+1 ,L),R):I):t[p];}void UP (rint p) { for (ED(1 ,1 ,n,pos[p]), p = top[p]; p^1 ; ED(1 ,1 ,n,pos[fa[p]]), p = top[fa[p]]) T = QU(1 ,1 ,n,pos[p],pos[bot[p]]), g[fa[p]][0 ] -= f[p][1 ], g[fa[p]][1 ] -= min(f[p][0 ],f[p][1 ]), f[p][0 ] = T.c[0 ][1 ], f[p][1 ] = T.c[1 ][1 ], g[fa[p]][0 ] += f[p][1 ], g[fa[p]][1 ] += min(f[p][0 ],f[p][1 ]); } int main () { n = rf(); m = rf(); rf(); generate(w+1 ,w+n+1 ,rf); for (rint i = 1 , u, v; i < n; u = rf(), v = rf(), e[u].push_back(v), e[v].push_back(u), i++); DFS1(1 ); DFS2(top[1 ]=1 ); DP(1 ); BD(1 ,1 ,n); for (int a, x, b, y; m--; A = min(T.c[0 ][1 ],T.c[1 ][1 ]), printf ("%lld\n" ,A<INF?A:-1 ), g[a][x] = T1, UP(a), g[b][y] = T2, UP(b)) a = rf(), x = !rf(), b = rf(), y = !rf(), T1 = g[a][x], T2 = g[b][y], g[a][x] = INF, UP(a), g[b][y] = INF, UP(b), T = QU(1 ,1 ,n,pos[1 ],pos[bot[1 ]]); return 0 ; }
注意一下调了巨长时间: g[a][x] = INF, UP(a), g[b][y] = INF, UP(b)
一开始我偷懒写成了g[a][x] = g[b][y] = INF, UP(a), UP(b)
。这样是不行的,加入a
是b
的祖先,那么更新a
的时候就要用到b
的数据,这时候b
的数据是错的。
而且早些时候我还试图偷懒写成了swap(T1,g[a][x]), swap(T2,g[b][y])
,其中T1
和T2
都是+ ∞ +\infty + ∞ ,准备操作完再swap
回来。由于同样的原因,如果a
是b
的祖先,实际上最后g[a][x]
还真的不一定就是+ ∞ +\infty + ∞ 。
完了要是考NOIP2018怕不是要D2退役了…
P.S.: NOIP2018发生了啥啊?这UOJ口碑有点惨惨啊?
扫描二维码即可在手机上查看这篇文章,或者转发二维码来分享这篇文章: