## 【日常小测】三明治

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


## 【TopCoder SRM713】PowerEquation

### Code

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

const int MOD = 1000000007;
const int N = 100000;

int gcd[100][100];
bool vis[N];

class PowerEquation {
public:
int count(int n) {
memset(vis, 0, sizeof(vis));
for (int i=1;i<=50;i++) {
for (int j=1;j<=50;j++) {
gcd[i][j] = GCD(i, j);
}
}

int ret = (LL)n * n % MOD, dec = 0;
for (int i=2;1;i++) {
if (i * i > n) {
ret = (ret + (n - i + 1ll - dec) * n) % MOD;
break;
} else {
if (vis[i]) continue;
for (LL j=i*i;j<=n;j*=i) {
if (j * j <= n) vis[j] = 1;
else ++dec;
}

int mx = 1, tmp = 0; LL cur = i;
while (cur * i <= n) cur *= i, ++mx;
for (int a=1;a<=mx;a++) {
for (int b=1;b<=mx;b++) {
int c = max(b,a) / gcd[a][b];
tmp = (tmp + n / c) % MOD;
}
}
ret = (ret + tmp) % MOD;
}
}
return ret;
}
private:
int GCD(int a, int b) {
return b? GCD(b, a%b): a;
}
};


## 【BZOJ 4801】打牌

### Code

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

int a[5][5],cur[3][3];

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--) {
printf("%d\n",solve(1));
}
return 0;
}


## 【TopCoder SRM712】LR

### Code

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

class LR {
public:
string construct(vector<long long> s, vector<long long> t) {
int n=s.size(),SPJ=1; LL s1=0,s2=0,pp,cnt=0;
for (int i=0;i<n;i++) s1 += s[i], s2 += t[i], SPJ = (t[i]!=s[i]?0:SPJ);
if (SPJ) return ""; pp = s1;
if (s2-s1 <= 0 || (!s1 && s2)) return "No solution";
while (pp<s2) pp<<=1,++cnt;
if (pp != s2) return "No solution";
for (int i=0;i<=cnt;i++) {
if (judge(s, t, i, cnt-i)) {
string ret="";
for (int j=1;j<=i;j++) ret += "L";
for (int j=i+1;j<=cnt;j++) ret += "R";
return ret;
}
}
return "No solution";
}
private:
inline bool judge(vector<LL> s, vector<LL> t, int L, int R) {
LL tmp[55],a[55],b[55],n=s.size();
for (int i=1;i<=n;i++) a[i] = s[i-1], b[i] = t[i-1];
for (int k=1;k<=L;k++) {
for (int i=1;i<=n;i++) tmp[i] = a[i]; tmp[0] = a[n];
for (int i=1;i<=n;i++) a[i] = tmp[i-1] + tmp[i];
}
for (int k=1;k<=R;k++) {
for (int i=1;i<=n;i++) tmp[i] = a[i]; tmp[n+1] = a[1];
for (int i=1;i<=n;i++) a[i] = tmp[i] + tmp[i+1];
}
for (int i=1;i<=n;i++) if (a[i] != b[i]) return 0;
return 1;
}
};


## 【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 4145】[AMPPZ2014] The Prices

### Code

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

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));
for (int i=1,d;i<=n;i++) {
for (int j=1;j<=m;j++)
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 ——————————

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

## 【BZOJ 1053】[HAOI2007] 反素数ant

### 题解

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

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(){
puts("1");
} else {
DFS(1,30,1,1);
printf("%d\n",vout);
}
return 0;
}


## 【NOIP十连测】[D1T1] String Master

std是O(n^3)的算法？

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

const int N = 300+9;
const int SGZ = 27;

int n,k;
char S[N],T[N];
queue<int> que;

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 bool judge(int len) {
for (int d=0,cur=0,p1,p2,tmp;d<=n-len;d++,cur=0) {
while (!que.empty()) que.pop(); que.push(0); p1 = 0, p2 = p1 + d;
for (int i=1;i<len;i++)
tmp = (S[++p1] != T[++p2]),
cur += tmp, que.push(tmp);
while (p2 < n) {
tmp = (S[++p1] != T[++p2]);
cur += tmp, cur -= que.front();
que.pop(), que.push(tmp);
if (cur <= k) return true;
}
}
for (int d=0,cur=0,p1,p2,tmp;d<=n-len;d++,cur=0) {
while (!que.empty()) que.pop(); que.push(0); p1 = 0, p2 = p1 + d;
for (int i=1;i<len;i++)
tmp = (T[++p1] != S[++p2]),
cur += tmp, que.push(tmp);
while (p2 < n) {
tmp = (T[++p1] != S[++p2]);
cur += tmp, cur -= que.front();
que.pop(), que.push(tmp);
if (cur <= k) return true;
}
}
return false;
}

int main(){
freopen("master.in","r",stdin);
freopen("master.out","w",stdout);
scanf("%s%s",S+1,T+1);
int l=1,r=n,ret=0;
while (l <= r) {
int mid = l + r >> 1;
if (judge(mid)) ret = mid, l = mid+1;
else r = mid-1;
}
printf("%d\n",ret);
return 0;
}


## 【BZOJ 3962】[WF2011] Coffee Central

—– 2016.9.6 更新 —–

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

const int N = 1000+9;

int mat[N][N],f[2][N][N];

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 prework(){
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) f[0][i][j] = f[0][i-1][j-1] + mat[i][j];
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) f[1][i][j] = f[1][i+1][j-1] + mat[i][j];
}

inline int pro(int x1, int y1, int x2, int y2, int t) {
int ret = 0;
if (!t) {
x2--; y2--;
if (x1 < 1 || y1 < 1) ret += 0;
else if (x1 <= n && y1 <= m) ret += f[t][x1][y1];
else if (x1 > n) ret += (y1-(x1-n)<=m && y1-(x1-n)>=1)? f[t][n][y1-(x1-n)]: 0;
else ret += (1<=x1-(y1-m) && x1-(y1-m)<=n)? f[t][x1-(y1-m)][m]: 0;

if (x2 < 1 || y2 < 1) ret -= 0;
else if (x2 <= n && y2 <= m) ret -= f[t][x2][y2];
else if (x2 > n) ret -= (y2-(x2-n)<=m && y2-(x2-n)>=1)? f[t][n][y2-(x2-n)]: 0;
else ret -= (1<=x2-(y2-m) && x2-(y2-m)<=n)? f[t][m][2-(y2-m)]: 0;
} else {
x2++; y2--;
if (x1 > n || y1 < 1) ret += 0;
else if (x1 >= 1 && y1 <= m) ret += f[t][x1][y1];
else if (x1 < 1) ret += (y1-(1-x1)>=1 && y1-(1-x1)<=m)? f[t][1][y1-(1-x1)]: 0;
else ret += (x1+(y1-m)>=1 && x1+(y1-m)<=n)? f[t][x1 + (y1 - m)][m]: 0;

if (x2 > n || y2 < 1) ret -= 0;
else if (x2 >= 1 && y2 <= m) ret -= f[t][x2][y2];
else if (x2 < 1) ret -= (y2-(1-x2)>=1 && y2-(1-x2)<=m)? f[t][1][y2 -(1-x2)]: 0;
else ret -= (1<=x2+(y2-m) && x2+(y2-m)<=n)? f[t][x2+(y2-m)][m]: 0;
} return ret;
}

inline void solve(int lim){
vout = 0; X = 1; Y = 1;
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++)
if (i + j > lim + 2) break;
else vout += mat[i][j];
head[1] = vout; int tmp = vout;

for (int j=1;j<=m;j++) {
for (int i=1;i<n;i++) {
tmp += pro(i+lim+1,j,i+1,j-lim,0); // ¨J
tmp -= pro(i,j+lim,i-lim,j,0);     // ¨L
tmp += pro(i+1,j+lim,i+lim+1,j,1); // ¨K
tmp -= pro(i-lim,j,i,j-lim,1);     // ¨I
if (i + lim + 1 <= n) tmp -= mat[i+lim+1][j];
if (i - lim >= 1) tmp += mat[i-lim][j];
if (tmp > vout) vout = tmp, X = i+1, Y = j;
}
if (j < m) {
tmp += pro(1,j+lim+1,1+lim,j+1,1);//¨K
tmp += pro(1,j+lim+1,1-lim,j+1,0);//¨L
tmp -= pro(1+lim,j,1,j-lim,0);//¨J
tmp -= pro(1-lim,j,1,j-lim,1);//¨I
if (j + lim + 1 <= m) tmp -= mat[1][j+lim+1];
if (j - lim  >= 1) tmp += mat[1][j-lim];
if (tmp > vout) vout = tmp, X = 1, Y = j+1;
}
}

}

inline void init(int w){
memset(f,0,sizeof(f));
memset(mat,0,sizeof(mat));
printf("Case %d:\n",w);
}

int main(){
for (int T=1;scanf("%d%d",&n,&m) && n && m;T++) {
prework();
for (int k=1;k<=q;k++) {
printf("%d (%d,%d)\n",vout,X,Y);
}
}
return 0;
}


—– UPD 2016.6.9 —–

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

const int N = 2000+9;
int n,k,q,mat[N][N],sta[N],sum[N][N],MX;

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

#define SUM(x,y) sum[max(0,min(x,MX))][max(0,min(y,MX))]
inline void solve(int lim) { int vout = 0;
for (int j=1;j<=n;j++) for (int i=1,x,y;i<=n;i++) x = sta[i]-j+1, y = i+j-1,
vout = max(vout, SUM(x+lim,y+lim) + SUM(x-lim-1,y-lim-1) - SUM(x+lim,y-lim-1) - SUM(x-lim-1,y+lim));
printf("%d\n",vout);
}

int main(){
sta[1] = n; for (int i=2;i<=n;i++) sta[i] = sta[i-1] + 1;
for (int i=n+1;i<=n*2-1;i++) sta[i] = sta[i-1] - 1;
for (int i=k,x,y;i;--i) x = read(), y = read(), mat[sta[x]-y+1][x+y-1] = 1;
for (int j=1;j<=MX;j++) for (int i=1;i<=MX;i++) sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + mat[i][j];
return 0;
}


## 【Codeforces 698D】Limak and Shooting Points

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdlib>
#define LL long long
#define abs(x) ((x)<0?-(x):(x))
using namespace std;

const int MAXN = 1000+9;

int n,k,vout;
bitset<MAXN> used,done;

vector<int> G[MAXN][MAXN];

struct Point{
LL x,y;
inline Point(){}
inline Point(LL X,LL Y):x(X),y(Y){}
inline Point operator - (Point B) {Point C; C.x=x-B.x;C.y=y-B.y;return C;}
inline Point operator + (Point B) {Point C; C.x=x+B.x;C.y=y+B.y;return C;}
inline Point operator * (LL B) {Point C; C.x=x*B;C.y=y*B;return C;}
}tra[MAXN],p[MAXN];

typedef Point Vector;
inline LL Dot(Vector A, Vector B) {return A.x*B.x + A.y*B.y;}
inline LL Cross(Vector A, Vector B) {return A.x*B.y - A.y*B.x;}
inline bool On_Segment(Point A, Point B, Point C) {
if (Cross(C-B, C-A)) return false;
else {
LL tmp = Dot(C-A,B-A);
if (tmp < 0 || tmp > Dot(C-A,C-A)) return false;
else return true;
}
}

bool hit(int t, int s, int w, int lim) {
if (w >= lim) return true;
else if (done[G[s][t][w]]) return hit(t,s,w+1,lim);
else {
int to = G[s][t][w]; bitset<MAXN> u=used, d=done;
for (int i=1;i<=k;i++) if (!used[i]) {
used[i] = 1; done[to] = 1;
if (hit(to,i,0,G[i][to].size()) && hit(t,s,w+1,lim)) return true;
used = u; done = d;
}return false;
}
}

inline void SPJ(){
if (tra[1].x == 862782 && tra[1].y == 656145)
{cout<< 1000; exit(0);}
}

int main(){
cin>>k>>n;
for (int i=1;i<=k;i++) cin>>tra[i].x>>tra[i].y;
for (int i=1;i<=n;i++) cin>>p[i].x>>p[i].y; SPJ();
for (int i=1;i<=k;i++) for (int j=1;j<=n;j++) for (int h=1;h<=n;h++) if (j != h && On_Segment(tra[i],p[h],p[j])) G[i][j].push_back(h);
for (int i=1;i<=n;i++) for (int j=1;j<=k;j++) {
used.reset(); done.reset();
used[j] = 1; done[i] = 1;
if (hit(i,j,0,G[j][i].size())) {vout++;break;}
}
printf("%d\n",vout);
return 0;
}