【日常小测】三明治

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/07/20170623_statement.pdf

解题报告

假如我们钦定某个格子先取走靠左的三角形,那么其余格子是先取走靠左还是靠右就全部定下来了
于是我们暴力枚举一下,复杂度是$O(n^4)$

更进一步,我们发现:

假如我们钦定先取走$(x, y)$这个格子的靠左三角形
那么我们一定得先将$(x – 1, y)$这个格子的左三角形取走,然后再取走一些其他的三角形

于是同一行的信息是可以共用的,然后就可以记忆化搜索了
时间复杂度是$O(n^3)$的

Code

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

const int N = 500;
const int INF = 1e7;

char mp[N][N];
int n, m, ans[N];
bool up[N][N], dw[N][N], InStack[N][N], vis[N][N];

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

inline int F(int x, int y, int t) {
	InStack[y][x] = 1;
	int nx = x + (t == 1? 1: -1), ny = y, nt = t, ret = 1;
	ret += vis[ny][nx]? 0: (InStack[ny][nx]? INF: F(nx, y, t));
	nx = x; ny = up[y][x] == t? y - 1: y + 1; nt = up[y][x] == t? up[ny][nx]: dw[ny][nx];
	ret += vis[ny][nx] || ret >= INF? 0: (InStack[ny][nx]? INF: F(nx, ny, nt));	
	vis[y][x] = 1;
	InStack[y][x] = 0;
	return ret > INF? INF: ret;
}

inline void init() {
	memset(vis, 0, sizeof(vis));
	for (int j = 1; j <= m; j++) {
		vis[j][0] = 1;
		vis[j][n + 1] = 1;
	}
	for (int i = 1; i <= n; i++) {
		vis[0][i] = 1;
		vis[m + 1][i] = 1;
	}
}

int main() {
	m = read(); n = read();
	for (int j = 1; j <= m; j++) {
		scanf("%s", mp[j] + 1);
		for (int i = 1; i <= n; i++) {
			up[j][i] = 1;
			dw[j][i] = 0;
			if (mp[j][i] == 'Z') {
				swap(up[j][i], dw[j][i]);
			}
		}
	}
	for (int j = 1; j <= m; j++) {
		init();
		for (int i = n; i; i--) {
			ans[i] = ans[i + 1] < INF? F(i, j, 1) + ans[i + 1]: INF;
		}
		init();
		for (int i = 1; i <= n; i++) {
			ans[i] = min(ans[i], ans[i - 1] < INF? F(i, j, 0) + ans[i - 1]: INF);
			printf("%d ", ans[i] >= INF? -1: ans[i] << 1);
		}
		putchar('\n');
	}
	return 0;
}

【BZOJ 2471】Count

相关链接

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

解题报告

我们考虑从高位开始,逐位枚举。那么每枚举一位相当于将序列划分为10分,并且取其中一份。
对于一段连续的序列来讲,我们只需要关注其进入这段序列之前会匹配到x的哪一位、匹配完这一段之后匹配到了x的哪一位、这期间总共贡献了多少次成功的匹配。
不难发现这个状态是很少的,于是我们可以记忆化搜索。

另外这题很容易扩展到:“左右边界为任意值的情况”
然后我把这题搬到了今年的全国胡策里,不知道有没有人能切掉

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 16;
const int M = 10;
const int SGZ = 10;
const int MOD = 1000000007;
 
int n, m, nxt[M];
char s[M];
struct Transfer{
    LL pos, cnt;
    inline Transfer() {
    }
    inline Transfer(LL a, LL b):pos(a), cnt(b) {
    }
    inline Transfer operator + (const Transfer &T) {
        return Transfer(T.pos, cnt + T.cnt);
    }
}t[M][SGZ];
map<int, Transfer> f[N][M];
struct MatchStatus{
    int HashVal;
    Transfer t[M];
    inline void GetHashVal() {
        const static int MOD = 1000000007;
        const static int SEED1 = 13, SEED2 = 131;
        HashVal = 0;
        for (int i = 0; i < m; i++) {
            HashVal = (HashVal + (LL)t[i].pos * SEED2 + t[i].cnt) * SEED1 % MOD;
        }
    }
    inline bool operator < (const MatchStatus &MS) const {
        return HashVal < MS.HashVal;
    }
};
 
inline Transfer DFS(int w, int p, const MatchStatus &cur) {
    if (w <= 0) {
        return cur.t[p];
    } else if (f[w][p].count(cur.HashVal)) {
        return f[w][p][cur.HashVal];
    } else {
        Transfer ret(p, 0);
        for (int i = 0; i < SGZ; i++) {
            MatchStatus nw = cur;
            for (int j = 0; j < m; j++) {
                nw.t[j] = nw.t[j] + t[nw.t[j].pos][i];
            }
            nw.GetHashVal();
            ret = ret + DFS(w - 1, ret.pos, nw);
        }
        return f[w][p][cur.HashVal] = ret;
    }
}
 
int main() {
    while (~scanf("%d %s", &n, s + 1) && n) {
        m = strlen(s + 1);
        for (int i = 1; i <= m; i++) {
            s[i] -= '0';
        }
        nxt[1] = 0;
        for (int i = 2, j = 0; i <= m; nxt[i++] = j) {
            for (; j && s[j + 1] != s[i]; j = nxt[j]);
            j += s[j + 1] == s[i];
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < SGZ; j++) {
                int k = i;
                for (; k && s[k + 1] != j; k = nxt[k]);
                k += s[k + 1] == j;
                t[i][j] = k == m? Transfer(nxt[k], 1): Transfer(k, 0);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                f[i][j].clear();
            }
        }
        Transfer ans(0, 0);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < SGZ; j++) {
                MatchStatus cur;
                for (int k = 0; k < m; k++) {
                    cur.t[k] = t[k][j];
                }
                cur.GetHashVal();
                ans = ans + DFS(i - 1, ans.pos, cur);
            }
        }
        printf("%lld\n", ans.cnt);
    }
    return 0;
}

【AtCoder】[Regular Contest 075 F] Mirrored

相关链接

题目传送门:http://arc075.contest.atcoder.jp/tasks/arc075_d

解题报告

之前PKUSC的时候考过$n + rev(n) = d$的版本
所以这一次把暴搜重新打一次就过了

Code

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

int *mth, *spj, a2[100], a1[100]; 

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;
}

LL DFS(LL res, LL l, LL r) {
	if (l <= r) {
		if (res == 0) {
			return l == r? 10: 1;
		} else {
			return 0;
		}
	} else {
		LL ret = 0, cur = l - r;
		l /= 10; r *= 10;
		for (int i = -9; i <= 9; i++) {
			if (abs(res - i * cur) < l * 11) {
				ret += mth[i] * DFS(res - i * cur, l, r);				
			}
		}
		return ret;
	}
}

int main() {
	mth = a1 + 50;
	spj = a2 + 50;
	for (int i = 0; i <= 9; i++) {
		for (int j = -9; j <= 0; j++) {
			mth[i + j]++;
		}
	}
	for (int i = 1; i <= 9; i++) {
		for (int j = -9; j <= 0; j++) {
			spj[i + j]++;
		}
	}
	LL ans = 0, D = -read();
	for (LL mx = 1e18; mx >= 10; mx /= 10) {
		LL delta = mx - 1;
		for (int i = -8; i <= 9; i++) {
			ans += spj[i] * DFS(D - i * delta, mx / 10, 10);
		}
	}
	cout<<ans<<endl;
	return 0;
}

【BZOJ 4801】打牌

相关链接

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

解题报告

大暴搜游戏题
复杂度:$O(4T)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
int a[5][5],cur[3][3];
 
inline int read() {
    char s[5]; scanf("%s",s);
    if (s[0] == 'A') return 14;
    if (s[0] == 'K') return 13;
    if (s[0] == 'Q') return 12;
    if (s[0] == 'J') return 11;
    if (s[0] == 'T') return 10;
    return s[0] - '0';
}
 
inline int val(int x) {
    if (x == 14) return 1;
    else return x; 
}
 
int solve(int t) {
    if (t == 1) {
        cur[0][0] = a[0][0]; cur[0][1] = a[0][1];
        int s1 = solve(2); 
        swap(cur[0][0], cur[0][1]);
        int s2 = solve(2);
        return max(s1, s2);  
    } else if (t == 2) {
        cur[1][0] = a[1][0]; cur[1][1] = a[1][1];
        int s1 = solve(3);
        swap(cur[1][0], cur[1][1]);
        int s2 = solve(3);
        return min(s1, s2);
    } else {
         if (cur[0][0] >= cur[1][0]) {
            if (cur[0][1] >= cur[1][1]) {
                return val(cur[0][0]) + val(cur[0][1]);
            } else {
                return val(cur[0][0]) - val(cur[1][1]);
            } 
         } else {
            if (cur[0][1] > cur[1][1]) {
                return -val(cur[1][0]) + val(cur[0][1]);    
            } else {
                return -val(cur[1][0]) - val(cur[1][1]) ;
            }
         }
    }
}
 
int main() {
    int t; cin>>t; 
    for (;t;t--) {
        a[0][0] = read(); a[0][1] = read();
        a[1][0] = read(); a[1][1] = read();
        printf("%d\n",solve(1));
    }
    return 0;
}

【Codeforces 797E】Array Queries

相关链接

题目传送门:http://codeforces.com/contest/797/problem/E

解题报告

我们发现暴搜加上记忆化的复杂度是$O(n \sqrt{n})$的
于是暴搜就好了

Code

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

const int N = 100009;

struct Query{int p,k,id;}q[N];
int n,m,stp[N],a[N],ans[N];
queue<int> vis;

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 bool cmp(const Query &A, const Query &B) {
	return A.k < B.k; 
}

inline void init() {
	for (;!vis.empty();vis.pop()) {
		stp[vis.front()] = 0;
	}
}

int DFS(int w, int k) {
	if (w > n) return 0;
	else if (stp[w] > 0) return stp[w];
	else return vis.push(w), stp[w] = DFS(w + a[w] + k, k) + 1;	
}

int main() {
	n = read(); for (int i=1;i<=n;i++) a[i] = read();
	m = read(); for (int i=1;i<=m;i++) q[i].p = read(), q[i].k = read(), q[i].id = i;
	sort(q+1, q+1+m, cmp);
	for (int i=1;i<=m;i++) {
		if (i > 1 && q[i].k != q[i-1].k) init();
		ans[q[i].id] = DFS(q[i].p, q[i].k);
	} 
	for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

【BZOJ 3990】[SDOI2015] 排序

相关链接

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

解题报告

最开始一眼看成神题,还在想$SDOI$这是要赶超$ZJOI$的节奏啊
然后就发现看漏条件了 _(:з」∠)_

因为每一次只能交换一个$2^k$的块,并且$2$的不同次幂之间不会相互影响
话一句话来说,考虑交换长度为$2^k$的块时,所有长度为$2^{k-1}$的块的顺序必须已经排好
且长度为$2^k$的块,只能有至多两块位置不对
于是我们搞一发$DFS$就好了,时间复杂度:$O(n \log n)$

【BZOJ 3917】[Baltic2014] sequence

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3917
神犇题解Ⅰ:http://blog.csdn.net/lcrtest/article/details/51312981
神犇题解Ⅱ:http://blog.csdn.net/neither_nor/article/details/52604754

吐槽

他们说这题是APIO 2016练习赛的题目,为什么我一点印象都没有 QwQ
想了很久都只会$O(\frac{n^2}{64})$的暴力,我也很绝望啊…..

解题报告

我们发现,对于比较高的位数来讲,其一样的数在一起
考虑将一样的数合在一起,并且从低位到高位处理

记录二进制状态$f_{i,j}$表示在第$i$位的时候,第$j$块里需要哪些数
如果当前只需要一个数了,那么就可以直接返回辣!(如果是0需要特判)
否则的话,我们枚举这一位在第一个数中是多少
因为下一层中连续的区间长度大概都比现在这一位连续的区间长10倍
所以我们可以把这一位中的状态每十个合成一块,下一层的话又是一个递归子问题,我们可以递归下去
考虑每一层的总复杂度:第$i$层有$10^i$个分叉,每个分叉内有$\frac{n}{10^i}$个块,于是每一层的复杂度是$O(n)$的
下面我们来总复杂度$T(n)=10 \cdot T(\frac{n}{10}) + n$
根据主定理,这货是$O(n \log{n})$的

【BZOJ 4294】[PA2015] Fibonacci

相关链接

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

解题报告

做这题,我们需要有一个前置结论:

Fibonacci数列在$\bmod 10^n$的时候,循环节为$6 \times 10^n$

至于这个结论怎么证明,我也不知道
不过这个结论可以用这里的知识自己搞出来:传送门

那么知道了这个结论之后
我们就可以从低位到高位DFS了
每一层只会尝试$0 \sim 9$,虽然看起来会$T$
不过复杂度是玄学,所以跑得飞快

【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;
}

【BZOJ 1053】[HAOI2007] 反素数ant

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1053
神犇题解:http://medalplus.com/?p=2105

题解

这种题看一眼就会去想找规律吧?
打个表看一看大概是这样:

于是我们可以找到如下规律:
1.质因数是连续的,也就是说我们只用考虑37及之前的质因数
2.较大的质因数个数一定少于较小的质因数的个数

于是我们就可以写个深搜
枚举出所有符合条件的数
然后用这些数去更新答案辣!

Code

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

const int SZ = 12;

int n,num,vout,pri[]={0,2,3,5,7,11,13,17,19,23,29,31,37};

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 DFS(int t, int last, int w, int v) {
	if (t == 13) {
		if (v == num) {
			vout = min(vout, w);
		} else if (v > num) {
			vout = w;
			num = v;
		}
	} else {
		for (int i=0,cur=1;i<=last;i++,cur*=pri[t]) {
			if ((LL)cur * w > n) break;
			else {
				DFS(t+1, i, w*cur, v*(i+1));
			} 
		}
	}
}
 
int main(){
	if ((n=read()) == 1) {
		puts("1");
	} else {
		DFS(1,30,1,1);
		printf("%d\n",vout);
	}
	return 0;
}

【BZOJ 1024】[SCOI2009] 生日快乐

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

算一算发现状态只有五六百种的样子
再加上每个状态的转移只有不超过10个
于是就可以记忆话搜索辣!
然而似乎直接暴搜也可以过 (╯‵□′)╯︵┻━┻

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)<0?-(x):(x))
using namespace std;

const double INF = 1e9;
const double EPS = 1e-3;

struct Data{
	double x,y,val;
	inline Data() {}
	inline Data(double x, double y, double val):x(x),y(y),val(val) {
		if (x < y) swap(x, y);
	}
	inline bool operator < (const Data &tmp) const {
		if (abs(tmp.x - x) < EPS && abs(tmp.y - y) < EPS) return 0;
		else if (tmp.x - x > EPS) return 1;
		else if (x - tmp.x > EPS) return 0;
		else if (tmp.y - y > EPS) return 1;
		else return 0;  
	}
};
set<Data> S;
set<Data>::iterator itr;

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;
}

double DFS(double x, double y, int n) {
	if (n == 1) {
		if (x < y) swap(x, y);
		return x / y; 
	} else {
		itr = S.find(Data(x,y,0));
		if (itr != S.end()) return itr->val;
		else {
			double ret = INF;
			for (int i=1;i*2<=n;i++) {
				ret = min(ret, max(DFS(x*i/n,y,i), DFS(x*(n-i)/n,y,n-i)));
				ret = min(ret, max(DFS(x,y*i/n,i), DFS(x,y*(n-i)/n,n-i)));
			}
			S.insert(Data(x,y,ret));
			return ret;
		}
	}
}

int main(){
	int x=read(),y=read(),n=read();
	printf("%.6lf\n",DFS(x,y,n));
	return 0;
}

【日常小测】subset

题目传送门:http://oi.cyo.ng/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;
}

【UVa 11464】Even Parity

题目传送门:https://uva.onlinejudge.org/index.php&problem=2459
中文题面:《算法竞赛·入门经典·训练指南》P15

瞄一眼,觉得是这道题:http://www.lydsy.com/JudgeOnline/problem.php?id=3503
结果仔细一看:这题居然不能用线性基来搞,因为没法保证改变的数最少QAQ

还是是能用std的做法:
枚举第一行的所有状态,之后递推出整个棋盘的局面
然后计算更改量,最后用更改量来更新答案
复杂度:\(O({2^n} \cdot {n^2})\)