Category: 杂项

题目传送门：http://uoj.ac/problem/137
官方题解：http://vfleaking.blog.uoj.ac/blog/714

这个题，考试的时候想到了50分的算法，但没写出来QAQ
都搞到这个程度了：

还是没有想出来，可惜啊！

70分算法的关键：\(\left( \begin{array}{l}
x\\
y
\end{array} \right) = \left( \begin{array}{l}
x – 1\\
y
\end{array} \right) + \left( \begin{array}{l}
x – 1\\
y – 1
\end{array} \right)\)

100分的关键：
看一看上面那个图，组合数实际的意义是从(u,v)走到每个点的路径的个数
于是搞一搞dp即可

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

const int N = 300+9;
const int MOD = 998244353;

int f[N][N][N*2],n,m,q,X;

inline int read(){
	X = (100000005*(LL)X+20150823) % MOD;
	return X / 100;
}

int main(){
	cin>>m>>n>>q>>X;
	for (int i=1,u,v,k;i<=q;i++) {
		v = read()%m+1, u = read()%n+1, k = read()%(n+m-v-u+1);
		f[u][v][k]++;
	} 
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) {
		for (int k=0;k<=n+m;k++) (f[i][j][k] += (f[i-1][j][k+1] + f[i][j-1][k+1]) % MOD) %= MOD;
		(f[i][j][0] += (f[i-1][j][0] + f[i][j-1][0]) % MOD) %= MOD;
	}
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) 
		printf("%d%c",f[i][j][0],(i==n?'\n':' '));
	return 0;
}

题目传送门：http://codeforces.com/contest/713/problem/C

我™之前做过这原题！然而考试的时候没想到怎么做QAQ

I well vegatable are!

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

const int N = 3000+9;
const LL INF = 1e15;

int arr[N],hash[N],n,tot;
LL f[N][N],MN[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;
}

#define update(x,y) (x=((x)==-1||(y)<(x)?(y):(x)))
#define abs(x) ((x)>0?(x):-(x))

int main(){
	n = read(); 
	for (int i=1;i<=n;i++) hash[i] = arr[i] = read() - i;
	sort(hash+1,hash+1+n); tot = unique(hash+1,hash+1+n) - hash - 1;
	for (int i=1;i<=n;i++) memset(f[i],-1,sizeof(f[i])), MN[i] = -1;
	for (int i=1;i<=n;i++) {
		LL best = INF;
		for (int j=1;j<=tot;j++) {
			if (~f[i-1][j]) best = min(best, f[i-1][j]);
			update(f[i][j],best+abs(arr[i]-hash[j]));
		}
	} 
	LL vout = INF;
	for (int i=1;i<=tot;i++) if (~f[n][i])
		vout = min(vout, f[n][i]);
	cout<<vout; 
	return 0;
}

至于为什么减去下标答案不会变？
我们可以考虑差分序列啦！

—– UPD 2016.9.14 —–
这题看策爷的代码，可以用左偏树搞到O(nlogn)

原来这个题目可以贪心！
考虑最后的样子，一定长这样：

加入一个堆，其中位数不满足整体不减的话，即与左边的堆合并
为什么这么贪心的是对的呢？因为不管你砍哪一步分开，那一部分的差距都会更大，即不可能成为最优解

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

题目传送门：http://codeforces.com/contest/710/problem/E
官方题解：http://codeforces.com/blog/entry/46761

这题，做法很多:
有简单粗暴型：http://www.cnblogs.com/Coolxxx/p/5797798.html
也有优雅递推型：http://blog.csdn.net/qq_33184171/article/details/52289905
我是第二种，不过第二种有一个东西需要证明：至少存在一组最优解使得-1操作至多连续进行1次

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

const int N = 1e7+9; 

int n,x,y;
LL f[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;
}

int main(){
	n = read(); x = read(); y = read();
	f[1] = x; for (int i=2;i<=n;i++) {
		f[i] = f[i-1] + x;
		if (i & 1) f[i] = min(f[i], f[i+1>>1] + x + y);
		else f[i] = min(f[i], f[i>>1] + y);
	}
	printf("%I64d\n",f[n]);
	return 0;
}

题目传送门：http://codeforces.com/contest/703/problem/E
官方题解：http://codeforces.com/blog/entry/46434
中文题面：http://www.cnblogs.com/dramstadt/p/5759206.html

题解的话，看官方题解就好
唯一想吐槽的就是：CF上居然卡常！
看看这通过的名单，™大家都是压线过的啊

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

const int M = 7000;
const int N = 1000+9;
const int INF = 10000000;

LL k,Hash[M],buf[M],sum[2][M];
int n,cnt,f[2][M],nxt[N][M],vout[N][M];
unordered_map<LL,int> idx;

inline LL read(){
	char c=getchar(); LL 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 LL find(LL w){
	int l=1, r=cnt, mid;
	while (l <= r) {
		mid = l + r >> 1;
		if (Hash[mid] == w) return mid;
		else if (Hash[mid] < w) l = mid+1;
		else r = mid-1;
	} 
}

inline void Decomposision(LL num) {
	LL lim = sqrt(num); if (lim*lim != num) lim++;
	for (int i=1;i<=lim;i++) if (num % i == 0) buf[++cnt] = i, buf[++cnt] = num/i;
	if (lim*lim == num) cnt--;
	for (int i=1;i<=cnt;i++) Hash[i] = buf[i];
	sort(Hash+1,Hash+1+cnt);
	for (int i=1;i<=cnt;i++) idx[buf[i]] = find(buf[i]);
}

inline LL GCD(LL a, LL b){
	while (b) {
		a = a%b;
		swap(a, b);
	}
	return a;
}

inline void SPJ(){
	if (k == 1) {
		LL vout = 1, tmp = read();
		for (int i=2;i<=n;i++) {
			LL t1 = read(); if (t1 < tmp) 
			tmp = t1, vout = i;
		} cout<<1<<endl<<vout; exit(0);
	}
}

int main(){
	n = read(); k = read(); SPJ();
	Decomposision(k); 
	for (int i=2;i<=cnt;i++) f[0][i] = INF; int now=1,pre=0;
	for (int i=1;i<=n;i++,pre^=1,now^=1) {
		LL w = read(), t2, t3 = GCD(w,k);
		for (int j=2,tmp,t1;j<=cnt;j++) {
			tmp = f[pre][t1=idx[Hash[j]/GCD(Hash[j],t3)]]+1;
			t2 = w + sum[pre][t1];
			if (f[pre][j] > tmp  || (f[pre][j] == tmp && t2 <= sum[pre][j])) 
				f[now][j] = tmp, nxt[i][j] = t1, vout[i][j] = i, sum[now][j] = t2;
			else f[now][j] = f[pre][j], nxt[i][j] = j, vout[i][j] = 0, sum[now][j] = sum[pre][j];
		}
	}
	if (f[pre][cnt] == INF) printf("-1\n");
	else {
		printf("%d\n",f[pre][cnt]);
		LL w = cnt, stp = n;
		while (w) {
			if (vout[stp][w]) printf("%d ",vout[stp][w]);
			w = nxt[stp][w]; stp--;
		}
	}
	return 0;
}