【日常小测】三明治

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

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() {
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

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

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;

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() {
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] 聪聪和可可

#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];

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(){