【日常小测】三明治

相关链接

题目传送门: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;
}

【TopCoder SRM713】PowerEquation

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14573&rd=16882

题目大意

给定$n(n \le 10^9)$,问有多少组不同的$a^b=c^d$成立
要求$1 \le a,b,c,d \le n$

解题报告

假设$a^b=c^d$,我们在枚举到$gcd(a,c)$的时候计算
如果$gcd(a,c)=a=c$的话,贡献显然是$n$
所以我们枚举$gcd$只需要枚举到$\sqrt{n}$
又因为次数非常小,所以我们可以暴力算有多少种指数满足要求
于是总的复杂度大概是$\sqrt{n}$的

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】打牌

相关链接

题目传送门: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;
}

【TopCoder SRM712】LR

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14569&rd=16881

解题报告

我们经过观察发现,操作顺序不影响结果
于是我们就可以暴力枚举多少个$L$多少个$R$然后暴力判断
时间复杂度:$O(n \log^2 10^{17})$

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

相关链接

题目传送门: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 4145】[AMPPZ2014] The Prices

相关链接

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

解题报告

先来说一个自己YY的暴力
枚举每一个合法集合,考虑这个集合的物品全部在某一个商店购买
如果我们把这些集合再拿来搞一搞组合,显然可以搞出来正确答案
使用背包DP的话,直接做复杂度是$O(4^m)$,考虑一点优化:
根据我们对于集合的定义,两个集合能够组合在一起,当且仅当两个集合没有交集
然后写个程序跑一跑,发现这种组合大概只会有4e7个,于是暴力搞一搞就好啦!
然后就垫底了 QwQ

现在考虑正解
刚刚我们其实是把整个商店买了哪些物品当作一个新物品,然后用新物品来进行背包DP
考虑我们直接把商店里面的物品拿来做背包DP会有什么问题:商店本身的花费$d_i$不好整
于是我们分阶段来背包DP,每一个商店一个阶段。
在这个阶段中,我们给所有状态加上这个商店的花费$d_i$,表示我们钦定这个商店要买东西
然后把物品拿来做背包,最后再和上个阶段的对应状态取个$min$
然后就做完啦!时间复杂度: $O(nm{2^m})$

Code

贴的这份代码是我YY的暴力

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

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

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));
	n = read(); m = read();
	for (int i=1,d;i<=n;i++) {
		d = read();
		for (int j=1;j<=m;j++) 
			cost[j] = read();
		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 ——————————
感觉使用以下代码来枚举子集可能会使我的暴力不那么接近于TLE:

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

【BZOJ 4059】[Cerc2012] Non-boring sequences

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4059
神犇题解Ⅰ:http://blog.csdn.net/popoqqq/article/details/46380617
神犇题解Ⅱ:http://krydom.com/bzoj4059/

解题报告

考虑直接找出所有不无聊的区间
直接 $ O(n^2)$ 枚举的话,会T掉,于是考虑分治
假如当前考虑到的区间为(l,r),且这个区间中一个只出现过一次的数为x,下标为p
那么显然,横跨x的区间合法,两边的区间就递归下去做就好啦!

但如果每一次我们从左到右扫描x的话,时间复杂度长这样:$ T(n) = T(n – 1) + n$
这样的话,上限是 $ O(n^2)$ 显然不清真
考虑同时从两边开始扫描的话,复杂度就变为了: $ T(n) = T(p) + T(n – p) + \min (n – p,p)$
于是这个是:$ O(n\log n)$ 的,于是就可以愉快的暴力啦!
至于复杂度的证明的话,我们发现这货的形式和线段树的启发式合并的式子长得一毛一样
因为线段树的启发式合并是 $ O(n\log n)$ 的,那么这货的复杂度也就是对的啦!

当然你也可以使用归纳法什么的来证明复杂度
甚至你可以根本不用这个暴力的算法,而使用优雅的矩形面积并来做:
http://www.cnblogs.com/DaD3zZ-Beyonder/p/5803964.html

【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 4419】发微博

链接

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

题解

我的想法是把关系修改扔到map里面去
然后log(n)的时间查询上一个修改是多久
这样问题就变成了询问时间l到r中点c进行了多少次+1操作
这个用主席树就可以了

然而看了题解之后发现,似乎用暴力搞就可以了?
用前缀和的思想:
关系建立的时候减去,关系解除时加回来
最后再用set处理一下剩下的就可以辣!

【NOIP十连测】[D1T1] String Master

题目传送门:http://oi.cyo.ng/wp-content/uploads/2016/10/noip_test1_statements.pdf

std是O(n^3)的算法?
明明NOIP范围内可以O(n^2logn)搞的!
就是二分长度,然后用滑动窗口搞一搞

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

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 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);
	n = read(); k = read();
	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

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

这个玩意,貌似可以暴力?
预处理出斜着的线上的点有多少,这样在暴力转移的时候,可以做到O(1)
然后就是写代码的事情了,然而写了两个小时了,没写出来QAQ
弃疗………..

—– 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 n,m,q,sz,head[N],vout,X,Y;
int mat[N][N],f[2][N][N];

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 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 = head[j];
			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;
			head[j+1] = tmp;
		}
	}	 
	
}

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++) { 
		init(T); sz = read(); q = read();  
		for (int i=1,x,y;i<=sz;i++) x = read(), y = read(), mat[x][y]++;
		prework(); 
		for (int k=1;k<=q;k++) {
			solve(min(m+n,read()));
			printf("%d (%d,%d)\n",vout,X,Y);
		} 
	}
	return 0;
}

然而DZY告诉我们,这货可以变成正方形?
参见:http://dzy493941464.is-programmer.com/posts/86498.html
仔细想了一想:我们可以通过将整个图旋转45°,然后重新编号,然后就变成了正方形?
然后就是很常规的滑动窗口了?

—– 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;

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

#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(){
	n = read(); k = read(); q = read(); MX = n * 2 - 1; 
	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];
	for (int i=1;i<=q;i++) solve(read());
	return 0;
} 

【Codeforces 698D】Limak and Shooting Points

题目传送门:http://codeforces.com/contest/699/problem/F

就是一个傻逼的暴力搜索,
但始终wa一个点,MD弃了

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