【BZOJ 3925】[ZJOI2015] 地震后的幻想乡

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3925
神犇题解Ⅰ:http://blog.csdn.net/skywalkert/article/details/47792065
神犇题解Ⅱ:http://www.cnblogs.com/yousiki/p/6437155.html

解题报告

题目上说:

对于$n$个$[0,1]$之间的随机变量$x_1,x_2,\cdots ,x_n$,第$k$小的那个的期望值是$\frac{k}{n+1}$

即加入$k$条边后恰好有生成树的情况的最大边的期望权值为$\frac{k}{n+1}$
设$g_k$为加入$k$条边后恰好使所有点连通的方案数
于是原题的答案为$\frac{1}{m+1}\sum\limits_{i=1}^{m}{\frac{i \cdot g_i}{m \choose i}}$

设$f_k$为加入$k$条边后原图不连通的方案数
我们可以交换一下求和顺序可使答案变为:$\frac{1}{m+1}\sum\limits_{i=0}^{m}{\frac{f_i}{m \choose i}}$
于是问题变为求$f_k$与$g_k$

我们首先可以发现,$f_k$加$g_k$一定等于所有的方案
那么设点集$S$的诱导子图中的边数为$cnt_{S}$,仅对于点集$S$有效的$f_k,g_k$为$f_{S,k},g_{S,k}$
则有:$f_{S,k}+g_{S,k}={cnt_S \choose k}$,于是只需要求出$g_{S,k},f_{S,k}$中的任意一个

类比带标号的连通图计数,我们可以列出递推式:$f_{S,i+j} = \sum\limits_{T \subset S}{g_{T,i} {cnt_{S-T} \choose j}}$
又$g_{S,k}={cnt_S \choose k} – f_{S,k}$,所以这个递推式可以直接递推
于是这题就做完啦!时间复杂度:$O(m 4^n)$
又因为上述$T \subset S$所以我们直接枚举子集,复杂度优化到$O(m 3^n)$

【BZOJ 4607】[PA2015 Final] Edycja

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4607
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5545772.html
神犇题解Ⅱ:http://blog.csdn.net/jzhang1/article/details/51697706

前言

这题大概放了三个月了
每一次清理题目的时候都会翻出这个题
然后看一两个小时又扔回去,因为不会啊

解题报告

就是先有一个结论:一号操作最后做不会使答案变劣
然后还有一个结论:对于每一种字符,至多进行一次二号操作
这两个似乎比较显然,想一想都能想出来

有了这两个结论之后我们就可以得到一个贪心的策略:

定义$tra(x,y)$为所有最开始为$x$的位置在目标串中不为$y$的个数
对于每一种字符$c$我们,我们找到字符$g_c$($g_c$可能等于$c$)
满足$g_c$能使$tra(c,g_c)$最小

考虑将26个字符看成26个点,把$g_c$看作由$c$连向$g_c$的一条边,这显然是一个图
如果这个图上不存环,那么此时已经是最优解。

但如果有环,则你不能找到一种合法的交换顺序,这是不合法的
另外,需要注意,如果一个连通块是一个内向树,则我们是可以多花费一次二号操作的代价使其合法的
比如下面这个图,我们可以先将$a$移动到$e$,然后移动环上的其他字符,最后把$e$移到$a$:

刚刚有说,如果有环,那么环是不合法的,于是我们需要调整一些出边,来破坏掉环
这里又有一个结论:我们破坏环的过程不会产生新的环,这个看起来非常显然,详细证明可以找Claris
至于破坏掉环的过程非常复杂,不能贪心,但我们注意到环的个数最多为13,所以我们可以用状压DP来做
于是这题嘴巴上就做完了!但感觉细节非常多的样子,于是就不写代码了(逃

【日常小测】tree

题目大意

给定一棵大小为$n(n \le 3000)$的树,带边权
请你给出一个长度为$k(k \le n)$的序列$\{a_i\}$
要求序列中两两元素不同,请你最小化$\sum\limits_{i=1}^{k-1}{dis(a_i,a_{i+1})}$

解题报告

我们看一看这个式子可以发现实际上是要我们给出一个大小为$k$的连通块
问你这个连通块内的边权乘上$2$再减掉直径的最小值是多少

于是我们定义$h_{i,j}$为$i$的子树中选$j$个点,还没有考虑直径的最小花费
$f_{i,j}$表示在$i$的子树里,选$j$个点,直径包含$i$的最小花费
$g_{i,j}$表示在$i$的子树里,选$j$个点,已经考虑过直径且直径不包含$i$的最小花费
然后我们暴力$DP$就可以了

我们的时间复杂度是$T(n)=\sum\limits_{i}{\sum\limits_{fa_i=fa_j}{size_i \cdot size_j}}$
仔细想一想的话,每一堆点只会在$LCA$处被计算,时间复杂度是$O(n^2)$的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3009;
const int M = N << 1;
const LL INF = 1e18;

int n,k,head[N],nxt[M],to[M],cost[M],sz[N];
LL vout=INF,f[N][N],g[N][N],h[N][N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void AddEdge(int u, int v, int c) {
	static int E = 1; cost[E+1] = cost[E+2] = c;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void update(int w, int fa) { 
	fill(f[w], f[w]+1+N, INF);
    fill(g[w], g[w]+1+N, INF);
	fill(h[w], h[w]+1+N, INF);
	f[w][1] = g[w][1] = h[w][1] = 0; sz[w] = 1;
	for (int i=head[w],t;i;i=nxt[i]) {
		if ((t=to[i]) != fa) {
			update(to[i], w); 
			for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
				for (int j=1;j<=sz[t];j++) {
					g[w][x+j] = min(g[w][x+j], g[w][x] + h[t][j] + tmp);
					g[w][x+j] = min(g[w][x+j], f[w][x] + f[t][j] + cost[i]);
					g[w][x+j] = min(g[w][x+j], h[w][x] + g[t][j] + tmp);
				}
			}
			for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
				for (int j=1;j<=sz[t];j++) {
					f[w][x+j] = min(f[w][x+j], h[w][x] + f[t][j] + cost[i]);
					f[w][x+j] = min(f[w][x+j], f[w][x] + h[t][j] + tmp);
				}
			} 
			for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
				for (int j=1;j<=sz[t];j++) 
					h[w][x+j] = min(h[w][x+j], h[w][x] + h[t][j] + tmp);
			} 
			sz[w] += sz[t];
		}	
	}
	vout = min(vout, f[w][k]);
	vout = min(vout, g[w][k]); 
}

int main() {
	n = read(); k = read();
	for (int i=2,u,v;i<=n;i++) {
		u = read(); v = read();
		AddEdge(u, v, read());
	}
	update(1, 1);
	printf("%lld\n",vout);
	return 0;
}

【BZOJ 3711】[PA2014] Druzyny

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3711
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/4654215.html
神犇题解Ⅱ:http://blog.csdn.net/u010600261/article/details/54917569

解题报告

去膜了题解,好神啊!
本题一个区间要同时受$c_i,d_i$的限制

于是我们先只考虑$d_i$的限制
那么对于某一个区间的右端点$i$来讲,设合法的左端点$\in [g_i,i)$
至于$g_i$怎么求?搞一个队列就可以了?或者二分也是可以的
另外还需要注意一点:$g_i$是单调递增的

现在我们再来考虑$c_i$的限制,我们使用分治来解决
在$solve(l,r)$的时候,我们找出$c_i$最大的那个点$k$,然后递归下去
在合并上来的时候,我们就只需要考虑$[l,k-1]$对于$[k,r]$的贡献了
更进一步:因为$c_k$是$[l,r]$中最大的那个,所以对于此时所有的转移,$c_i$的限制均只需要考虑$c_k$
那么此时对于$i \in [k,r]$来讲,其合法的左端点$j \in [max(l,g_i),min(k-1,i-c_k)]$
因为$g_i$单调递增,所以我们对于$[k,r]$从左到右分四段考虑:

  1. $g_i \le l$且$i-c_k \le k-1$
    我们的首先我们肯定可以使用线段树来更新
    但更进一步,对于这一类点,我们只需要在查询第一个点时使用线段树就可以了
    因为这是一个前缀,之后$i$每向右移一位,合法的$j$也最多增加$1$
    不难发现,总的暴力操作次数不大于左右区间中较小的一段
    时间复杂度:$O(\log + \min(r-k+1,k-l))$
  2. $g_i \le l$且$k-1 < i-c_k$
    对于这些点,我们查询的是整个左区间
    我们整体查一次,然后一起更新就可以了
    时间复杂度:$O(\log n)$
  3. $l < g_i < k$
    对于这些点,我们查询的是左区间的一个后缀,我们直接在线段树上查就好
    考虑所有会影响到$i$的$solve$,它们的左区间一定没有交集
    也就是说只会有一个$solve$的左区间包含$g_i$
    于是对于每一个$i$,在整个算法中只会被查询一次
    所以这部分复杂度是$O(n \log n)$的,且不需要考虑到分治的复杂度中去
  4. $g_i \le k$
    直接不管就好

现在我们来分析分治的复杂度:$T(a+b)=T(a)+T(b)+min(a,b)+\log n$
我们发现这和启发式合并一样,于是复杂度是$O(n \log n)$的
在算上第三类更新的复杂度,总时间复杂度仍然为$O(n \log n)$

值得一提的是,这种与最值相关的问题使用分治来解决已经多次出现
比如HDU 5575,一定要引起重视啊

【BZOJ 4182】Shopping

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4182
神犇题解:http://www.cnblogs.com/clrs97/p/4676134.html

解题报告

这个是一个多重背包,于是我们定义$f_{i,j}$为走到第$i$个点,花费$j$元的最大收益
我们先搞出一个DFS序,现在对于点$i$我们可以选或不选
若选,那么我们转移到DFS序的下一个去
若不选,那么我们需要跳过他的整个子树——这在DFS序上是一段连续的区间
于是我们就可以在$O(nm \log d)$的时间复杂度内解决这个问题了

另外Claris的点分的做法也非常好玩啊
通用性还要更强一点,提供了一种新的思路

—————————— UPD 2017.3.19 ——————————
这题今天写了写代码,似乎不能直接DP,会有一系列问题
将上述DP套个点分就没有问题了,不过套点分的话,就直接像Claris那么做就好啦
总之复杂度似乎还是只能做到$O(nm \log n \log m)$

【BZOJ 3482】[COCI2013] hiperprostor

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3482
神犇题解:http://www.cnblogs.com/clrs97/p/4675155.html

解题报告

我们发现一条路径的长度为$ax+b$,是一条直线的形式
那么我们如果求出所有直线的凸包,那么就可以$O(n)$计算答案了

现在考虑如何搞出凸包:

若两条直线的斜率相等,那么纵截距较小的一定优于纵截距较大的
于是我们可以定义状态$f_{i,j}$表示到达$i$点,斜率为$j$,的路径纵截距最小是多少
这个我们可以使用Dijkstra搞出来,之后我们显然可以$O(n)$构造出凸包了

有了凸包后,每一条线段的贡献就是一个等差数列,这个显然可以$O(1)$计算
于是总的时间复杂度就是$O(Qn^2 \log (n^2))$

【日常小测】排列

题目大意

给定$n(n \le 10^9),k(k \le 4)$,定义$p_i$为排列中第$i$个数
询问长度为$n$且$|p_i-i| \le k$的排列的个数$\pmod {1e9+7}$

解题报告

不难发现$k$很小,于是我们可以状压DP
进一步观察,有用的状态只有70个
于是我们可以$O(70^3 \log n)$的复杂度用矩阵快速幂解决

不过这题还可以用线性$K$阶递推式的那个解法
用特征多项式做到一个比较优的复杂度
GEOTCBRL就是用这个A的,太强大了_(:з」∠)_

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int MOD = 1000000007;
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
int n,K,t,tot,itr[1000],num[1000];
struct Matrix{
    int a[70][70];
    inline Matrix() {memset(a,0,sizeof(a));}
    inline Matrix(Matrix *tmp) {memcpy(a,tmp->a,sizeof(a));}
    inline Matrix(int v) {memset(a,0,sizeof(a));for(int i=0;i<tot;i++)a[i][i]=v;}
    inline void reset() {memset(a,0,sizeof(a));}
    inline Matrix operator * (const Matrix &B) {
        Matrix ret;
        for (int i=0;i<tot;i++) for (int j=0;j<tot;j++) for (int k=0;k<tot;k++) 
            ret.a[i][j] = (ret.a[i][j] + (LL)a[k][j] * B.a[i][k]) % MOD;
        return ret;
    }
    inline Matrix operator ^ (int t) {
        Matrix ret(1),w(this); 
        for (;t;t>>=1,w=w*w)
            if (t&1) ret=ret*w;
        return ret;
    }
}ans,tra;
 
int main() {
    for (;~scanf("%d%d",&n,&t);tot=0) {
        t <<= 1; K = 1 << t;
        ans.reset(); tra.reset();
        for (int i=0;i<K;i++) {
            if (__builtin_popcount(i) != t/2) continue;
            else itr[i] = tot, num[tot++] = i;
        }
        for (int h=0,cur,i;i=num[h],h<tot;h++) {
            for (int j=0;j<=t;j++) {
                if (i&(1<<j)) continue;
                cur = i | (1 << j);
                if (!(cur&1)) continue;
                tra.a[h][itr[cur>>1]] = 1;
            }
        } 
        t = itr[(1<<(t/2))-1]; ans.a[t][0] = 1; 
        tra = tra ^ n; ans = ans * tra;  
        printf("%d\n",ans.a[t][0]);
    }
    return 0;
}

【日常小测】Hope

题目大意

给定排列的长度$n(n\le10^5)$和常数$k(k\le10^5)$
对于单个排列$A$中的每$i$位:我们连一条从$i$出发,到其右边第一个比它大的位,如果没有就不连
定义$A$的花费为 $\sum$其中每一个连通块的大小$^k$
询问所有长度为$n$的排列的花费和$(\bmod 998244353)$

解题报告

设$f_i$为排列长度为$i$的答案,假设我们已经求出了$f_{i-1}$
我们考虑枚举$i$放在哪里,那么$i$之前的数全部连向$i$,之后的数是递归一个子问题
于是我们可以写出暴力的$DP$:${f_i} = \sum\limits_{j = 1}^i {{j^k}(j – 1)!C_{i – 1}^{j – 1}{f_{i – j}}} $
我们化一化式子可以得到$\frac{f_i}{(i-1)!}=\sum\limits_{j=1}^{i}{j^k \cdot \frac{f_{i-j}}{(i-j)!}}$
这显然是一个卷积的形式,于是可以用$NTT$优化

另外,对于$f_i$来讲,$f_{1 \sim i-1}$都会对它有贡献
那么这有是一个典型的$CDQ$分治的模型,于是我们还需要套上一个$CDQ$分治

在另外的话,我们回顾一下推出暴力$DP$的过程
不难发现我们是以最大值的插入作为突破口
那么这种题目与最大值相关的问题,这应该算是套路之一吧!
例如:HDU 5575

—————————— UPD 2017.3.17 ——————————
Claris说这题在OEIS上能找到$O(n)$的递推式 QwQ
Claris太强啦! _(:з」∠)_

【日常小测】巡游计划

题目大意

有$n(n \le 52501)$个城市,依次分布在数轴上
若你到达$i$号城市,则你必须停留$a_i$个单位时间
若你当前在$i$号城市,则你只能前往编号$\in (i,i+k]$的城市
若你在城市$i$,打算前往城市$j$,那么你会花费$|p_i-p_j| \cdot b_i$的时间
现在你从$1$号城市出发,最终到达$n$号城市,问花费的最短时间

解题报告

下面内容建立在你已经会了BZOJ 1492的维护凸壳的做法

先不考虑那个绝对值的限制,显然就是一个斜率DP的形式
我们考虑对序列建一个线段树,每一次得到了$i$号城市的答案后
我们在线段树上进行依次区间加的操作,即将$i$号城市对应的点加入线段树对应结点的凸壳内
因为在线段树上只会被拆分成$O(\log n)$个结点、插入凸壳复杂度$O(\log n)$,于是复杂度为$O(n \log^2 n)$

至于如何查询?我们从左到右依次处理,假设我们当前想得到$i$号城市的答案
那我们在$i$在线段树内对应的节点到根的路径上的每一个凸壳我们都询问一次答案
然后取一个最值就可以了,时间复杂度仍然是$O(n \log^2 n)$的

现在我们考虑绝对值的限制
我们可以钦定$p_i$与$p_j$的大小关系
具体来说,我们在得到$i$号城市的答案后,我们只是将他扔到线段树上去,但先不建立凸包
然后我们对那棵线段树进行中序遍历,那么在走到结点i的时候,我们已经知道了需要查询哪些点,凸壳总共有哪些点
于是我们将这些东西扔到一起,然后排序,然后从小到大遍历一次

如果是查询的点,就到当前的凸壳中更新答案
如果是应该加入到凸壳的点,那就加入到凸壳中
因为已经排过序,所以绝对值可以打开

我们再从大到小再来一遍,这样就可以得到这个结点的所有答案了
不难发现一个点只会被插入凸壳$O(\log n)$次,也只会被查询这么多次
所以时间复杂度仍然为$O(n \log^2 n)$

【BZOJ 4762】最小集合

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4762

吐槽

这题之前在绍一集训的时候就考过一次,今天又考了
但还是写炸了,或许老年选手不适合写代码吧!

解题报告

为了代码好写,我们先按照二进制位取反
这样的话,问题变为选出一些数,使其或起来为全集,且少一个都不行

我们考虑$f[i][j]$为将前$i$个数加入集合之后,或起来为$j$的方案数
这样可以防止一个数被之前的数代替,但对于之后的数却无能为力
于是我们加一维$f[i][j][k]$,其中$k$表示后面的数或起来为$k$

这样就可以使用类似容斥的思想进行两种转移

  1. $f[i][j][k] \to f[i+1][j|a_i][k-(k \& a_i)]$表示不强制非法
  2. $-f[i][j][k] \to f[i+1][j|a_i][(k-(k \& a_i))|(a_i-(a_i \& j))]$表示强制非法
    ps: 根据容斥原理,第二种转移会配上$-1$的系数

此时我们已经可以进行$O(n \cdot 4^{\omega})$的DP了
再仔细想想,第三维一定是第二维的子集,于是复杂度降到$O(n \cdot 3^{\omega})$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1001;
const int M = (1 << 10) - 1;
const int MOD = 1000000007;

int n,vout,a[N],f[1<<10][1<<10];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main() {
	n = read();
	for (int i=1;i<=n;i++) a[i] = read() ^ M;
	f[0][0] = 1; 
	for (int t=1;t<=n;t++) {
		for (int i=M,ti,tj,uni;~i;--i) {
			if ((ti = (a[t] | i)) > i) {
				uni = ti - i;
				for (int j=i;;(--j)&=i) {
					tj = (j - (j & a[t]));
					f[ti][tj] = (f[ti][tj] + f[i][j]) % MOD;
					f[ti][tj|uni] = (f[ti][tj|uni] - f[i][j]) % MOD;
					if (!j) break;
				}
			}
		}
	}
	printf("%d\n",(f[M][0]+MOD)%MOD);
	return 0;
}

【日常小测】传送门

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/03/438964732567423.png
官方题解:http://paste.ubuntu.com/24129177/

解题报告

这题当然可以用二维线段树做
不过显然KD-Tree更好写

但考场上T了两个点
加上一个如果子树最优解大于已知答案就不进入的剪枝后速度就成Rank 1了 QwQ

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 200009;
 
int n,vout,itr[N];
struct Point{int x,y,a,b,mnx,mny,mxx,mxy,v,ori,ch[2];}p[N];
inline bool cmpx(const Point &A, const Point &B) {return A.x < B.x;}
inline bool cmpy(const Point &A, const Point &B) {return A.y < B.y;}
inline bool cmp(const int a, const int b) {return p[a].x < p[b].x || (p[a].x == p[b].x && p[a].y < p[b].y);}
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
class KD_Tree{
    int root,ans_tmp;
    public:
        inline void init() {
            n = read();
            for (int i=1;i<=n;i++) {
                p[i].mnx = p[i].mxx = p[i].x = read();
                p[i].mny = p[i].mxy = p[i].y = read();
                p[i].a = read(); p[i].b = read();
            }       
            build(root, 1, n, 0);
        }
        inline void insert(int id, int v) {
            insert(root, 1, n, id, v);
        }
        inline int query(int id) {
            ans_tmp = 0;
            query(root, 1, n, id, judge(id, root));
            return ans_tmp;         
        }
    private:
        void build(int &w, int l, int r, bool t) {
            if (l == r) w = l;
            else if (l < r) {
                int mid = l + r >> 1; w = mid;
                if (t) nth_element(p+l, p+mid, p+r+1, cmpx);
                else nth_element(p+l, p+mid, p+r+1, cmpy);
                build(p[w].ch[0], l, mid-1, t^1);
                build(p[w].ch[1], mid+1, r, t^1);
                for (int i=0,s;i<2;i++) if (s = p[w].ch[i]) {
                    p[w].mnx = min(p[s].mnx, p[w].mnx);
                    p[w].mny = min(p[s].mny, p[w].mny);
                    p[w].mxx = max(p[s].mxx, p[w].mxx);
                    p[w].mxy = max(p[s].mxy, p[w].mxy);
                }
            }
        }
        inline bool Contain(int w, int id) {
            if (!w) return 0;
            else return p[w].mnx <= p[id].x && p[id].x <= p[w].mxx && p[w].mny <= p[id].y && p[id].y <= p[w].mxy;
        }
        void insert(int w, int l, int r, int id, int v) {
            p[w].v = max(p[w].v, v);
            if (l < r) {
                int mid = l + r >> 1;
                if (Contain(p[w].ch[0], id)) insert(p[w].ch[0], l, mid-1, id, v);
                if (Contain(p[w].ch[1], id)) insert(p[w].ch[1], mid+1, r, id, v);
            }
        }
        inline int judge(int i, int j) {
            if (p[i].x <= p[j].mnx && p[i].y <= p[j].mny && p[j].mxx <= p[i].a && p[j].mxy <= p[i].b) return 2;
            else return max(p[i].x, p[j].mnx) <= min(p[i].a, p[j].mxx) && max(p[i].y , p[j].mny) <= min(p[i].b, p[j].mxy);
        }
        void query(int w, int l, int r, int id, int ty) {
            if (ty == 2) ans_tmp = max(ans_tmp, p[w].v);
            else {
                if (p[id].x <= p[w].x && p[w].x <= p[id].a && p[id].y <= p[w].y && p[w].y <= p[id].b) ans_tmp = max(ans_tmp, p[w].ori);
                int mid = l + r >> 1, tmp;
                if (p[w].ch[0] && p[w].val > ans_tmp && (tmp = judge(id, p[w].ch[0]))) query(p[w].ch[0], l, mid-1, id, tmp);
                if (p[w].ch[1] && p[w].val > ans_tmp && (tmp = judge(id, p[w].ch[1]))) query(p[w].ch[1], mid+1, r, id, tmp);
            }
        }
}kd;
 
int main() {
    kd.init();
    for (int i=1;i<=n;i++) itr[i] = i;
    sort(itr+1, itr+1+n, cmp);
    for (int j=n,v,i=itr[j];j;i=itr[--j]) {
        v = kd.query(i);
        kd.insert(i, ++v);
        p[i].ori = v;
        vout = max(v, vout);    
    }
    printf("%d\n",vout);
    return 0;
}

【BZOJ 4347】[POI2016] Nim z utrudnieniem

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4347
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5006924.html
神犇题解Ⅱ:http://blog.csdn.net/lych_cys/article/details/50788730

解题报告

这题暴力$DP$的复杂度是$O(nd \cdot \max \{a_i\})$的,显然不能通过此题
但我们注意到,对于一个数$a_i$来讲,小于等于它的数的NIM和不会超过$2 \cdot a_i$
于是我们将$a_i$排序之后再$DP$,每一次枚举异或值只枚举到$2 \cdot a_i$
又因为$\sum\limits_{i=1}^n{a_i} \le 10^7$ 所以公共的更新次数不会超过$2 \cdot 10^7$
于是总时间复杂度就是$O(md)$的了

虽然$md$可以到$10^8$,而且感觉这个上界非常紧的样子
给人一种严重的跑不过的感觉
但却跑得飞快? 可能是数据比较水吧?

哦,对了,这题还卡内存
连滚动数组都给卡掉了
于是我们学习Claris的技巧,$f[k][j]$和$f[k \ xor \ a_i][j]$一起更新就可以啦!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int M = 500009;
const int N = 1100000;
const int MOD = 1000000007;
 
int n,D,XOR,f[N][10],g[2][10],arr[M];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
int main() {
    n = read(); D = read(); 
    for (int i=1;i<=n;i++) XOR ^= (arr[i] = read());
    sort(arr+1, arr+1+n); 
    f[0][0] = 1;
    for (int i=1,LIM=1;i<=n;i++) {
        while (LIM <= arr[i]) LIM <<= 1;
        for (int v=1,nv;v<LIM;v++) {
            if ((nv=(arr[i]^v)) <= v) { 
                for (int d=0,t=1%D;d<D;++d,(++t)%=D) {
                    g[1][t] = (f[nv][t] + f[v][d]) % MOD;       
                    g[0][t] = (f[nv][d] + f[v][t]) % MOD;
                }
                for (int d=0;d<D;d++) {
                    f[nv][d] = g[1][d];
                    f[v][d] = g[0][d];
                }
            }
        } 
    }
    if (n % D == 0) f[XOR][0]--;
    printf("%d\n",(f[XOR][0]+MOD)%MOD);
    return 0;
}

【BZOJ 4282】慎二的随机数列

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4282
神犇题解:http://blog.csdn.net/PoPoQQQ/article/details/48998981

解题报告

首先我们需要得到一个结论:一定存在一组最优解,使得所有的模糊的位置均在LIS中
现在我们来证明一下这个结论:

考虑如果有一组最优解中存在一个模糊的位置不在最优解中
那么讲这个模糊的位置换成后面的第一个确定位置的数即可,这样不会使答案变劣

于是我们就假设一个确定的位置的前缀中有a个不确定位置
那么我们把该确定位置的值减去a(相当于把那a个不确定位置在值域上留出位置)
然后对确定的串做一次LIS,然后加上不确定位置的个数即可

Code

我写LIS一直用的BIT,但PoPoQQQ大爷的LIS似乎更加优雅
他是直接维护一个最优的LIS,然后每一次lower_bound就可以了!

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;

int n,m,tot,vout,_hash[N],f[N],arr[N];
char pat[10];

class Fenwick_Tree{
	int mx[N];
	public:
		inline void modify(int p, int v) {
			for (int i=p;i<=tot;i+=lowbit(i))
				mx[i] = max(mx[i], v);
		}
		inline int query(int p) {
			int ret = 0; 
			for (int i=p-1;i;i-=lowbit(i))
				ret = max(ret, mx[i]);
			return ret;
		}
	private:
		inline int lowbit(int x) {
			return x & (-x);
		}
}BIT;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read();
	for (int i=1;i<=n;++i) {
		scanf("%s",pat+1);
		if (pat[1] == 'K') {
			arr[++tot] = read() - m;
			_hash[tot] = arr[tot];		
		} else ++m;
	}
	n = tot; sort(_hash+1, _hash+1+tot);
	tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
	for (int i=1;i<=n;i++) {
		arr[i] = lower_bound(_hash+1, _hash+1+tot, arr[i]) - _hash;
		f[i] = BIT.query(arr[i]) + 1;
		vout = max(f[i], vout);
		BIT.modify(arr[i], f[i]);
	} 
	printf("%d\n",vout + m);
	return 0;
}

【BZOJ 4416】[SHOI2013] 阶乘字符串

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4416
神犇题解Ⅰ:http://blog.csdn.net/flaze_/article/details/52607165
神犇题解Ⅱ:http://309459245.lofter.com/post/1dd7269e_a37f28d

解题报告

第一次做这么神奇的判定性题目
感觉非常神奇啊!神清气爽!

闲来无事写了一份beamer,大家随便看看吧
另外,这货的证明是错的:http://blog.csdn.net/horizon_smz/article/details/50905084
slide

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = (1<<21) + 9;
const int M = 500;
const int SGZ = 21;

int n,m,f[N],last[SGZ],nxt[M][21];
char pat[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	for (int T=read();T;T--) {
		m = read();
		scanf("%s",pat+1);
		n = strlen(pat+1);
		if (m > 21) {
			puts("NO");
			continue;
		}
		for (int i=0;i<m;i++) 
			last[i] = nxt[n+1][i] = n + 1;
		for (int i=n;~i;i--) {
			for (int j=0;j<m;j++) 
				nxt[i][j] = last[j];
			if (i) last[pat[i]-'a'] = i;
		}
		for (int i=1,lim=1<<m;i<lim;i++) {
			f[i] = 0;
			for (int j=0;j<m;j++) {
				if (i & (1 << j)) {
					f[i] = max(f[i], nxt[f[i^(1<<j)]][j]);
				}
			}	
		}
		if (f[(1<<m)-1] <= n) puts("YES");
		else puts("NO");
	}
	return 0;
}

【BZOJ 3997】[TJOI2015] 组合数学

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3997
神犇题解:http://blog.csdn.net/popoqqq/article/details/45171469

解题报告

这题又™是结论题
需要用到的结论:

Dilworth定理:DAG的最小链覆盖=最大点独立集

类似的结论还有:

最大团=补图上的最小点覆盖的补集
最大反链的大小=最小链划分
最大链的大小=最小反链划分

知道结论之后,实际上就是让你求一些点,相互不能到达,且点权和最大
这样的话,从左下到右上搞一个DP就可以了!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000+9;

int n,m,val[N][N],f[N][N],g[N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	for (int T=read();T;T--) {
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		m = read(); n = read();
		for (int j=1;j<=m;j++) {
			for (int i=1;i<=n;i++) {
				val[i][j] = read();
			}
		}
		for (int i=1;i<=n;i++) {
			for (int j=m,cur=0;j;j--) {
				f[i][j] = cur + val[i][j];
				cur = max(cur, g[j]);
				g[j] = max(g[j], f[i][j]);
			}
		}
		int vout = 0;
		for (int i=1;i<=m;i++) 
			vout = max(vout, g[i]);
		printf("%d\n",vout);
	}
	return 0;
}