【BZOJ 4710】[JSOI2011] 分特产

相关链接

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

解题报告

先不考虑每个人至少一个的限制条件
那么我们可以将每一类物品分别考虑,用一个插板法就可以解决问题

现在考虑每一个人至少一个的限制
我们可以大力容斥一波!

于是总的时间复杂度就是:$O(nm)$

Code

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

const int N = 2009;
const int MOD = 1000000007;

int n,m,ans,a[N],C[N][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;
}

inline int cal(int x) {
	int ret = C[x][n];
	for (int i=1;i<=m;i++) {
		ret = (LL)ret * C[n-x-1][a[i]+n-x-1] % MOD;
	}
	return ret;
}

int main() {
	n = read(); m = read(); 
	C[0][0] = 1;
	for (int i=1;i<N;i++) {
		C[0][i] = 1;
		for (int j=1;j<N;j++) {
			C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD;
		}
	}
	for (int i=1;i<=m;i++) a[i] = read();
	for (int i=0;i<n;i++) {
		if (i&1) ans = (ans - cal(i)) % MOD;
		else ans = (ans + cal(i)) % MOD;
	} 
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}

【BZOJ 4145】[AMPPZ2014] The Prices

相关链接

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

解题报告

先来说一个自己YY的暴力
枚举每一个合法集合,考虑这个集合的物品全部在某一个商店购买
如果我们把这些集合再拿来搞一搞组合,显然可以搞出来正确答案
使用背包DP的话,直接做复杂度是$O(4^m)$,考虑一点优化:
根据我们对于集合的定义,两个集合能够组合在一起,当且仅当两个集合没有交集
然后写个程序跑一跑,发现这种组合大概只会有4e7个,于是暴力搞一搞就好啦!
然后就垫底了 QwQ

现在考虑正解
刚刚我们其实是把整个商店买了哪些物品当作一个新物品,然后用新物品来进行背包DP
考虑我们直接把商店里面的物品拿来做背包DP会有什么问题:商店本身的花费$d_i$不好整
于是我们分阶段来背包DP,每一个商店一个阶段。
在这个阶段中,我们给所有状态加上这个商店的花费$d_i$,表示我们钦定这个商店要买东西
然后把物品拿来做背包,最后再和上个阶段的对应状态取个$min$
然后就做完啦!时间复杂度: $O(nm{2^m})$

Code

贴的这份代码是我YY的暴力

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

const int N = 100+9;
const int M = 65536;

int n,m,cost[N],f[M];
pair<int,int> que[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;
}

void DFS(int w, int sta, int c) {
	if (w == m + 1) {
		f[sta] = min(f[sta], c);
	} else {
		DFS(w+1, sta, c);
		DFS(w+1, sta|(1<<w-1), c+cost[w]);
	}
}

void update(int t, int sta, int w) {
	if (t == m + 1) {
		f[sta|w] = min(f[sta|w], f[sta] + f[w]);
	} else {
		update(t+1, sta, w);
		if ((sta&(1<<(t-1))) == 0)
			update(t+1, sta, w|(1<<(t-1)));
	}
}

int main() {
	memset(f,60,sizeof(f));
	n = read(); m = read();
	for (int i=1,d;i<=n;i++) {
		d = read();
		for (int j=1;j<=m;j++) 
			cost[j] = read();
		DFS(1, 0, d);
	}
	for (int i=1,lim=1<<m;i<lim;i++)
		que[i] = make_pair(__builtin_popcount(i), i);
	sort(que+1, que+(1<<m));
	for (int i=1,lim=1<<m;i<lim;i++) 
		update(1, que[i].second, 0);
	printf("%d\n",f[(1<<m)-1]);
	return 0;
}

—————————— UPD 2017.2.7 ——————————
感觉使用以下代码来枚举子集可能会使我的暴力不那么接近于TLE:

for (int i=s;i;i=(i-1)&s) {}

【BZOJ 4455】[ZJOI2016] 小星星

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4455
神犇题解:http://www.cnblogs.com/DaD3zZ-Beyonder/p/5793086.html

解题报告

这题这个阶乘级别的状压DP大家都会吧?

$f(i,j,S)$ 表示树上第$i$个点,对应图中第$j$个点,子树中的对应状态状压后为$S$的方案数

然后我发现了两件事:
1. 这样会T
2. 我不会更优的算法了

正解的话,用了一个非常神奇的DP
考虑枚举有图中有哪些点被映射,然后 $O(n^3)$ 就可以求出满足边的限制的方案数(但点不一定是一一对应的)
然后我们加上点数刚好的情况,减去点数差一的情况,加上相差为2的情况…
于是我们就可以在 $O(2^n \cdot n^3)$ 的时间复杂度内解决这个问题啦!

【BZOJ 3930】[CQOI2015] 选数

相关链接

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

解题报告

这题,仔细想一想,岂不是跟这个题一样:https://oi.qizy.tech/?p=498
于是答案就是这个东西:$ \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^m { \cdots \sum\limits_{k = 1}^m {[gcd(i,j, \cdots ,k) = K]} } } = \sum\limits_{i = 1}^{\left\lfloor {\frac{m}{K}} \right\rfloor } {\sum\limits_{j = 1}^{\left\lfloor {\frac{m}{K}} \right\rfloor } { \cdots \sum\limits_{k = 1}^{\left\lfloor {\frac{m}{K}} \right\rfloor } {[gcd(i,j, \cdots ,k) = 1]} } } = \sum\limits_{d = 1}^{\left\lfloor {\frac{m}{K}} \right\rfloor } {\mu (d) \cdot {{\left\lfloor {\frac{m}{{Kd}}} \right\rfloor }^n}}$
于是剩下的锅就是预处理莫比乌斯函数的前缀和了!
然而我只会 $ O(n)$ 的做法,于是就跪了

PoPoQQQ大爷给了一种神奇的做法:http://blog.csdn.net/popoqqq/article/details/44917831
大概就是说,莫比乌斯函数的前缀和可以进行如下变换:
$ \sum\limits_{i = 1}^n {\mu (i) = 1 – \sum\limits_{i = 2}^n {(0 – \mu (i)) = } 1 – \sum\limits_{i = 2}^n {(\sum\limits_{j|i} {\mu (j)} – \mu (i))} = 1 – \sum\limits_{i = 2}^n {\sum\limits_{j|i,i \ne j} {\mu (j)} } } = 1 – \sum\limits_{j = 1}^n {\mu (j) \cdot (\left\lfloor {\frac{n}{j}} \right\rfloor – 1)} = 1 – \sum\limits_{j = 1}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {\mu (j) \cdot (\left\lfloor {\frac{n}{j}} \right\rfloor – 1)}$
换一句话说,莫比乌斯函数的前缀和可以做到 $ O(\sqrt n \log n)$
这样的话,感觉复杂度是 $ O(n \log n)$ 的
然而PoPoQQQ大爷说,预处理前 $ S$ 个值的话,复杂度就可以变成:$ O(\frac{n}{S}\sqrt n lo{g_2}\frac{n}{S})$
然而并不知道怎么证明,感觉很有道理的样子!

当然这题还有容斥的做法
首先有结论:$ gcd(i,j) \le (r – l),(i,j \in (l,r))$
证明的话,参见这里:https://blog.sengxian.com/solutions/bzoj-3930
于是考虑 $ f(i)$ 表示gcd为i的方案数,则 $ f(i) = {\left\lfloor {\frac{m}{{Ki}}} \right\rfloor ^n} – \sum\limits_{i|j} {f(j)}$
这样的话, $ f(1)$ 就是答案辣!

—————————— UPD 2017.2.20 ——————————
突然发现,莫比乌斯函数的前缀和不是杜教筛的模板题吗?
当然PoPoQQQ的做法也有可取之处:不用复杂度公式推导

【UOJ 246】[UER #7] 套路

相关链接

题目传送门:http://uoj.ac/contest/35/problem/246
官方题解:http://matthew99.blog.uoj.ac/blog/2085

解题报告

这题真™是套路深啊!
一言不合就根号大军了

具体来说的话,我们考虑答案的区间长度为 $ len$
并且钦定一个阀值 $ S$

  1. 考虑 $ len<S$ 的情况
    我们枚举右端点,暴力向左扫 $ S$ 个就可以了

  2. 考虑 $ len \ge S$ 的情况
    我们发现相似度不会超过 $ \frac{m}{{len – 1}}$
    于是考虑在权值上暴力向两边扫 $ S$ 个

这样的话,我们就可以在 $ O(nS + n\frac{m}{s})$ 的复杂度内解决这个问题了
不难发现,当 $ S = \sqrt m$ 时复杂度最优

Code

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

const int N = 200000+9;

int n,m,K,S,a[N],gap[N],lst[N];
LL vout;

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(); m = read(); 
	K = read(); S = sqrt(m) + 1;
	for (int i=1;i<=n;i++) a[i] = read();
	
	memset(gap,60,sizeof(gap));
	for (int i=1;i<=n;i++) {
		for (int j=i-1;j>=i-S&&j;--j) {
			gap[j] = min(gap[j], gap[j+1]);
			gap[j] = min(gap[j], abs(a[i] - a[j]));
			if (i-j+1 >= K) vout = max(vout, (LL)(i - j) * gap[j]);
		}
	}
	memset(gap,0,sizeof(gap));
	for (int i=1;i<=n;i++) {
		for (int j=0;j<=S;j++) {
			if (j) gap[j] = max(gap[j], gap[j-1]);
			if (a[i]-j >= 1) gap[j] = max(gap[j], lst[a[i]-j]);
			if (a[i]+j <= m) gap[j] = max(gap[j], lst[a[i]+j]);
			if (i-gap[j] >= K) vout = max(vout, (LL)(i-gap[j]-1) * (j+1)); 
		}
		lst[a[i]] = i;
	}
	printf("%lld\n",vout);
	return 0;
}

【BZOJ 4262】Sum

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4262
神犇题解-1:http://www.cnblogs.com/clrs97/p/4824806.html
神犇题解-2:http://blog.csdn.net/qq_34637390/article/details/51313126

题解

我们不妨将所有询问按照右端点\(r_i\) 排序
假设当前处理的所有询问右端点统一为last
定义\(val_i^{last} = \min (\{ {a_j}|j \in [i,last]\} )\)
定义\(sum_i^{last} = \sum\limits_{j = i}^{last} {val_i^j}\)
不难发现对于左右端点在l-r的所有区间的min和为\(\sum\limits_{i = l}^r {sum_i^r}\)
更进一步,每一个原题中提到的询问可以拆成:\(\sum\limits_{i = {l_1}}^{{r_1}} {sum_i^{{r_2}}} – \sum\limits_{i = {l_1}}^{{r_1}} {sum_i^{{l_2} – 1}}\)

接下来的事情就是用线段树来维护val和sum辣!
考虑last向右移动一个单位,我们首先需要将一些点的val更新
然后我们需要将每一个点当前的val累加到sum里面去

每一个点维护四个变量a,b,c,d来表示标记
定义 new_val = a * val + b * len
定义 new_sum = sum + c * val + d * len
显然更新val需要用到的参数是 {0,val',0,0}
而默认的参数则应该为 {1,0,0,0}
更新sum的参数则应该为 {1,0,1,0}

于是就可以将这两种标记一起下传了
至于为什么可以混在一起?
因为这货是矩阵乘法啊!
ps:矩阵乘法并没有交换律,只有结合律,所以在修改时也得下传标记

Code

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

const int N = 100000+9;
const int M = N << 1;
const int MOD = 1000000000;
const int SEED1 = 1023;
const int SEED2 = 1025;

int n,m,tot,arr[N],stk[N];
LL vout[N];
struct Query{
	int lim,l,r,t,id;
	inline bool operator < (const Query &B) const {
		return lim < B.lim;
	}
}q[M];

namespace Segment_Tree{
	#define SEG Segment_Tree
	int ch[M][2],L,R,cnt,root;
	LL sum[M],val[M],ans_tmp;
	struct Tag{
		LL a,b,c,d;
		inline Tag() {a=1;b=c=d=0;}
		inline Tag(LL a, LL b, LL c, LL d):a(a),b(b),c(c),d(d) {}
		inline Tag operator * (const Tag &B) {
			return (Tag){a*B.a, B.b+b*B.a, a*B.c+c, B.d+d+b*B.c};
		}
	}tag[M],delta;
	
	void Build(int &w, int l, int r) {
		w = ++cnt;
		tag[w] = Tag(1,0,0,0);
		val[w] = sum[w] = 0;
		if (l < r) {
			int mid = l + r + 1 >> 1;
			Build(ch[w][0],l,mid-1);
			Build(ch[w][1],mid,r);
		}
	} 
	
	inline void init() {
		cnt = 0;
		Build(root,1,n);
	}
	
	inline void Add(int w, int l, int r, Tag v) {
		static int len; len = r - l + 1;
		sum[w] += val[w] * v.c + len * v.d;
		val[w] = val[w] * v.a + len * v.b;
		tag[w] = tag[w] * v;
	}
	
	inline void push_down(int w, int l, int mid, int r) {
		Add(ch[w][0],l,mid-1,tag[w]);
		Add(ch[w][1],mid,r,tag[w]);
		tag[w] = Tag(1,0,0,0);
	}
	
	inline void GetSum() {
		Add(root,1,n,Tag(1,0,1,0));
	}
	
	void Modify(int w, int l, int r) {
		if (L <= l && r <= R) {
			Add(w,l,r,delta);
		} else {
			int mid = l + r + 1 >> 1;
			if (tag[w].a != 1 || tag[w].b || tag[w].c || tag[w].d) 
				push_down(w,l,mid,r);
			if (L < mid) Modify(ch[w][0], l, mid-1);
			if (R >= mid) Modify(ch[w][1], mid, r);
			val[w] = val[ch[w][0]] + val[ch[w][1]];
			sum[w] = sum[ch[w][0]] + sum[ch[w][1]];
		}
	}
	
	inline void modify(int l, int r, int v) {
		delta = Tag(0,v,0,0);
		L = l, R = r;
		Modify(root,1,n);
	}
	
	void query(int w, int l, int r) {
		if (L <= l && r <= R) {
			ans_tmp += sum[w];
		} else {
			int mid = l + r + 1 >> 1;
			if (tag[w].a != 1 || tag[w].b || tag[w].c || tag[w].d) 
				push_down(w,l,mid,r);
			if (L < mid) query(ch[w][0], l, mid-1);
			if (R >= mid) query(ch[w][1], mid, r);
		}
	}
	
	inline LL query(int l, int r) {
		ans_tmp = 0;
		L = l; R = r;
		query(root,1,n);
		return ans_tmp;
	}
};

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() {
	m = read();
	for (int i=1,l1,l2,r1,r2;i<=m;i++) {
		l1 = read(); r1 = read();
		l2 = read(); r2 = read();
		if (l2 > 1) q[++tot] = (Query){l2-1,l1,r1,-1,i};	
		q[++tot] = (Query){r2,l1,r1,1,i};
		n = max(n, max(r1, r2));
	}
	sort(q+1, q+1+tot);
	for (int i=1,c1=SEED1,c2=SEED2;i<=n;i++) {
		arr[i] = c1 ^ c2;
		c1 = (LL)SEED1 * c1 % MOD;
		c2 = (LL)SEED2 * c2 % MOD;
	}
	
	SEG::init();
	for (int i=1,top=0,cur=1;i<=n;i++) {
		while (top && arr[stk[top]] > arr[i]) top--;
		SEG::modify(stk[top]+1, i, arr[i]);
		SEG::GetSum(); stk[++top] = i;
		while (cur <= tot && q[cur].lim == i) {
			vout[q[cur].id] -= SEG::query(q[cur].l, q[cur].r) * q[cur].t;
			cur++;
		}
	}
	SEG::init();
	for (int i=1,top=0,cur=1;i<=n;i++) {
		while (top && arr[stk[top]] < arr[i]) top--;
		SEG::modify(stk[top]+1, i, arr[i]);
		SEG::GetSum(); stk[++top] = i;
		while (cur <= tot && q[cur].lim == i) {
			vout[q[cur].id] += SEG::query(q[cur].l, q[cur].r) * q[cur].t;
			cur++;
		}
	}
	
	for (int i=1;i<=m;i++) 
		printf("%lld\n",vout[i]);
	return 0;
}

【BZOJ 2794】[POI2012] Cloakroom

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2794
数据生成器:http://paste.ubuntu.com/23946550/
神犇题解:http://trinklee.blog.163.com/blog/static/23815806020149855817630

题解

这个题目假如没有A[]和B[]的限制的话,就是一个正常的背包
然而有了这两个东西,而且复杂度要求O(1)询问,这样我就不会了 QwQ

考虑传统背包的局限性:
1)添加物品的顺序没有限制,但实际上是浪费了一些性质
2)DP的是一个bool数组,只记录是否可以凑出,这样实际上也是浪费了信息

于是考虑离线,将询问的m和物品的a[]都按照升序排好序
然后规定f[i][j]表示用前i个物品,凑出j的b[]的最小值的最大值
之后对于每个询问,A[]可以用i来限制,B[]可以直接判断

于是边DP边回答询问的话
就可以O(1)处理所有询问辣!
★,°:.☆( ̄▽ ̄)/$:.°★ 。

Code

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

const int N = 1000+9;
const int M = 1000000+9;
const int INF = 100000;

struct Event{
	int a,b,c,d;
	inline Event() {}
	inline Event(int _a, int _b, int _c):a(_a),b(_b),c(_c) {}
	inline bool operator < (const Event &B) const {return a < B.a;}
}t[N],q[M];

int f[M],arr[M+N<<1],vout[M],tot,n,m,mx;

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,a,b,c;i<=n;i++) {
		a = read(); b = read(); c = read();
		arr[++tot] = c; arr[++tot] = b;
		t[i] = Event(b, c, a);
	}
	m = read();
	for (int i=1,a,b,c;i<=m;i++) {
		a = read(); b = read(); c = read() + a;
		arr[++tot] = a; arr[++tot] = c;
		q[i] = Event(a, c, b);
		q[i].d = i;
	}
	sort(arr+1, arr+1+tot);
	tot = unique(arr+1, arr+1+tot) - arr - 1;
	for (int i=1;i<=n;i++) {
		t[i].a = lower_bound(arr+1, arr+1+tot, t[i].a) - arr;
		t[i].b = lower_bound(arr+1, arr+1+tot, t[i].b) - arr;
		mx = max(mx, t[i].a);
	}
	for (int i=1;i<=m;i++) {
		q[i].a = lower_bound(arr+1, arr+1+tot, q[i].a) - arr;
		q[i].b = lower_bound(arr+1, arr+1+tot, q[i].b) - arr;
		q[i].a = min(q[i].a, mx);
	}
	sort(t+1, t+1+n);
	sort(q+1, q+1+m);
	f[0] = 1e9;
	for (int j=1,p1=1;j<=m;j++) {
		for (;t[p1].a<=q[j].a&&p1<=n;p1++) {
			for (int i=INF-t[p1].c,to=INF;i>=0;i--,to--) {
				f[to] = max(f[to], min(f[i], t[p1].b));	
			}
		}
		vout[q[j].d] = f[q[j].c] > q[j].b;
	}
	for (int i=1;i<=m;i++) {
		if (vout[i]) puts("TAK");
		else puts("NIE");
	}
	return 0;
}