【BZOJ 4374】Little Elephant and Boxes

相关链接

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

解题报告

这题如果钱的总数小一点就可以直接DP了
于是我就想到了这个题:BZOJ 2749
于是我们就可以把钱给离散化到900以内啦!
但这样我们没有办法进行转移,然后就不会了 QwQ

不过万能的Claris告诉我们,物品只有30个
于是我们可以折半暴搜,这样的话就不需要转移了
直接枚举左侧的值,右侧搞一个指针跟着动一动就好
时间复杂度: $O(nm{2^{\frac{n}{2}}} + n{m^2})$

【Codeforces 747F】Igor and Interesting Numbers

相关链接

题目传送门:http://codeforces.com/contest/747/problem/F
优雅的暴力:http://codeforces.com/blog/entry/49171?#comment-331886
官方题解:http://codeforces.com/blog/entry/49171
神犇代码:http://codeforces.com/contest/747/submission/23125896

解题报告

首先这题推一推式子发现答案最多9位的样子
于是我们就可以暴力搜索,用Meet in Middle来做就好

当然这题有更加清真的、类似数位DP的做法
假定我们能够做到给定字符串长度和每个数字可以用多少次,求有多少种合法情况的话
显然可以像数位DP一样,从高位到低位逐位确定每一位的数字应该是多少

现在问题转化为如何求的合法情况。
依次考虑每一种数字,显然对答案的贡献只与有多少个空位有关
于是f[i][j]表示现在考虑到第i种数字,还剩j个空位的方案数
这样的话,暴力转移即可。
时间复杂度:O(16^3+16*9)

Code

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

int k,t,C[21][21],res[21];
char ori[]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};

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 LL solve(int len, bool ty) {
	static LL f[2][20]; bool w,p;
	memset(f,0,sizeof(f));
	f[p=0][ty] = 1; w = 1; 
	for (int i=0;i<16;i++,w^=1,p^=1) {
		memset(f[w],0,sizeof(f[w]));
		for (int j=len;~j;j--) 
			for (int k=min(len-j,res[i]-(ty&(i==0)));~k;k--) 
				f[w][j+k] += f[p][j] * C[k][len-j];
	}
	return f[p][len];
}

int main() {
	for (int i=0;i<=20;i++) {
		C[0][i] = C[i][i] = 1;
		for (int j=1;j<i;j++) 
			C[j][i] = C[j-1][i-1] + C[j][i-1];
	}
	k = read(); t = read();
	for (int i=0;i<=15;i++) 
		res[i] = t;
	LL tmp; int len=1;
	while ((tmp = solve(len,0) - solve(len,1)) < k) 
		k -= tmp, len++;
	for (int i=len,ret=1;i;ret=0,i--) {
		res[ret]--;
		while ((tmp = solve(i-1,0)) < k) 
			res[ret++]++, res[ret]--, k -= tmp;
		printf("%c",ori[ret]);
	}
	return 0;
}

【日常小测】subset

题目传送门:https://oi.qizy.tech/wp-content/uploads/2016/11/20161104.pdf

这题如果是亦或之类的,大家应该都会做吧!
但这题是&的话,有些时候就需要同时进入左右子树了QAQ
这个我们不难想到:http://uoj.ac/problem/176
简直一毛一样有木有?

然而这么做有一个问题:这货只能用Fat Node的持久化形式
这样的话,在最后复制左右子树的时候,复杂度还是不对啊QAQ
所以这样似乎没法做了QAQ
如果可以的话,可不可以给我讲一讲? _(:з」∠)_

还是来说一说std吧:
将二进制下前八位作为数组的一维下标
将二进制的后八位作为数组的二维下标
然后在查询时暴力第二维,修改时暴力第一维
时间复杂度O(n*2^8)

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

const int N = 300;
const int MX = 256;

int f[N][N],n;
char pat[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;
}

inline void modify(int w, int delta) {
	for (int i=0;i<MX;i++) {
		if ((i&w)==(w&255)) {
			f[i][w>>8] += delta;
		}
	}
}
 
inline int query(int w) {
	int ret = 0;
	for (int i=0,sta=w>>8;i<MX;i++) {
		if ((i&sta)==i) {
			ret += f[w&255][i];
		}
	}
	return ret;
} 
 
int main(){
	freopen("subset.in","r",stdin);
	freopen("subset.out","w",stdout);
	n = read();
	for (int i=1;i<=n;i++) {
		scanf("%s",pat+1);
		if (pat[1] == 'a') modify(read(),1);
		else if (pat[1]=='d') modify(read(),-1);
		else printf("%d\n",query(read()));	
	}
	return 0;
}