【日常小测】三明治

相关链接

题目传送门:https://oi.qizy.tech/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;
}

【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 1415】[Noi2005] 聪聪和可可

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1415
数据生成器:http://paste.ubuntu.com/22417252/

论文题,记忆化深搜
我在处理该去哪时,用的三方的floyd
然而hzwer告诉我,平方的bfs就好QAQ,反正没有T,我就不改啦!(づ ̄ 3 ̄)づ

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 1000+9;
const int INF = 1000000;
const double sta = -0.5;

int n,m,C,M,d[MAXN][MAXN],to[MAXN][MAXN],cnt[MAXN];
double ans[MAXN][MAXN];

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

inline void Floyd(){
	for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) if (d[i][k] < INF) 
		for (int j=1;j<=n;j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) for (int k=1;k<=n;k++) 
		if (d[i][k] == 1 && d[k][j] == d[i][j]-1) {to[i][j] = k; break;}
	for (int i=1;i<=n;i++) to[i][i] = i;
}

double Get_Ans(int u, int v){
	if (ans[u][v] > sta) return ans[u][v];
	else {
		if (to[to[u][v]][v] != v) {
			ans[u][v] = Get_Ans(to[to[u][v]][v],v)+1;
			for (int i=1;i<=n;i++) if (d[v][i] == 1) ans[u][v] += Get_Ans(to[to[u][v]][v],i)+1;
			return ans[u][v] /= cnt[v];
		} else return ans[u][v] = 1;
	}
}

int main(){ 
	n = read(); m = read(); C = read(); M = read();
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) d[i][j] = INF, ans[i][j] = -1;
	for (int i=1;i<=n;i++) d[i][i] = 0, ans[i][i] = 0, cnt[i] = 1;
	for (int i=1,a,b;i<=m;i++) cnt[a = read()]++, cnt[b = read()]++, d[a][b] = d[b][a] = 1;
	Floyd(); printf("%.3lf\n",Get_Ans(C,M));
	return 0;
}