1. 小X的回文串

【题目大意】

给定每个字符的个数ai，求最短的回文串最长是多少。

【题解】

找找规律就好啦！

# include <stdio.h>

using namespace std;

int T, n, a[100010], N;

int main() {
	freopen("palindromic.in", "r", stdin);
	freopen("palindromic.out", "w", stdout);
	scanf("%d", &T);
	while(T--) {
		N = 0;
		scanf("%d", &n);
		for (int i=1; i<=n; ++i) {
			scanf("%d", &a[i]);
			if(a[i] & 1)  N ++;
		}
		if (N) {
			long long ans = 0;
			for (int i=1; i<=n; ++i) ans = ans + (a[i]>>1);
			ans = ans / N;
			ans = ans * 2;
			ans ++;
			printf("%lld\n", ans);
		} else {
			long long ans = 0;
			for (int i=1; i<=n; ++i) ans = ans + a[i];
			printf("%lld\n", ans);
		}
	}
	return 0;
}
	

2. 小Y的棋盘问题

【题目大意】

有一个n*m的棋盘，上面有一些棋子，每行每列最多只会有一个棋子，不会有两个棋子八连通。问随机一个空格子作为起点，再随机地选择一个空格子作为终点，求问不经过任意棋子最短路的期望长度是多少。多组，n,m<=2000。

【题解】

我们假设障碍可以直接走过去，我们可以用一个O(nm)的东西来解决它们的问题（曼哈顿距离和）

下面考虑路径经过障碍，会使得长度+2，我们只需要判断一下哪些需要+2即可。

下面这张图，蓝色格子到红色格子 包括 第一行第三列 和 第四列黑色格子以上的，都要+2

利用单调性维护即可。

# include <stdio.h>
# include <string.h>

using namespace std;

int T;
int n, m;
char map[1010];
int line[1010], row[1010];
long long cnt = 0;
long long c = 0;

long long get(int i, int j, int k) {
	return 4*(i-1)*(k-j);
}

int main() {
	freopen("chess.in", "r", stdin);
	freopen("chess.out", "w", stdout);
	scanf("%d", &T);
	while(T--) {
		memset(line, 0, sizeof(line));
		memset(row, 0, sizeof(row));
		c = 0; cnt = 0;
		scanf("%d%d", &n, &m);
		for (int i=1; i<=n; ++i) {
			scanf("%s", map);
			for (int j=0; j<m; ++j)
				if(map[j] == 'X') {
					cnt ++;
					row[i] = j+1;
					line[j+1] = i;	
					break;
				}
		}
		
		for (int i=1; i<n; ++i)
			for (int j=i+1; j<=n; ++j) 
				c = c + (m - (row[i]>0)) * (m - (row[j]>0)) * (j-i) * 2;
		
		for (int i=1; i<=n; ++i)
			if(row[i]) {
				c = c + get(row[i], row[i], m);
				for (int j=i-1; j>0 && row[j] && row[j] < row[j+1]; --j)
					c = c + get(row[j], row[i], m);
				for (int j=i+1; j<=n && row[j] && row[j] < row[j-1]; ++j)
					c = c + get(row[j], row[i], m);
			}
	
		for (int i=1; i<m; ++i)
			for (int j=i+1; j<=m; ++j) 
				c = c + (n - (line[i]>0)) * (n - (line[j]>0)) * (j-i) * 2;
		
		for (int i=1; i<=m; ++i)
			if(line[i]) {
				c = c + get(line[i], line[i], n);
				for (int j=i-1; j>0 && line[j] && line[j] < line[j+1]; --j)
					c = c + get(line[j], line[i], n);
				for (int j=i+1; j<=m && line[j] && line[j] < line[j-1]; ++j)
					c = c + get(line[j], line[i], n);
			}
			
		
		double ans;
		cnt = n*m - cnt;
		cnt = cnt * cnt;
		//printf("%lld\n", cnt);
		//printf("%lld\n", c);
		ans = (double)c / cnt;
		printf("%.4lf\n", ans);
	}
	return 0;
}

3. 小Z的旅行计划

【题目大意】

一个图，每条边只有在一些时候能够通行，问一个人能否在l到r的时间内从s到t。

【题解】

询问离线然后乱搞啦！

# include <stdio.h>
# include <algorithm>
using namespace std;

int n, m, qn;
struct edge {
	int u, v;
}e[666666];

struct quest {
	int l, r, s, t, id;
	bool operator <(quest a) const {
		return l > a.l;
	}
}q[666666];

int d[1010][1010], ans[1010];

inline int min(int a, int b) {
	return a<b?a:b;
}

int main() {
	freopen("plan.in", "r", stdin);
	freopen("plan.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &qn);
	for (int i=1; i<=m; ++i) 
		scanf("%d%d", &e[i].u, &e[i].v);
	
	for (int i=1; i<=qn; ++i)
		scanf("%d%d%d%d", &q[i].l, &q[i].r, &q[i].s, &q[i].t), q[i].id=i;
	
	sort(q+1, q+qn+1);	
	
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=n; ++j)
			d[i][j] = 222222222;
	
	int cur = 1;
	
	for (int i=m; i>=1; --i) {
		// connect
		d[e[i].u][e[i].v] = d[e[i].v][e[i].u] = i;
		// relax
		for (int j=1; j<=n; ++j) 
			d[e[i].u][j] = d[e[i].v][j]
						 = min(d[e[i].u][j], d[e[i].v][j]);
		while(cur<=qn && q[cur].l == i) {
			ans[q[cur].id] = d[q[cur].s][q[cur].t]<=q[cur].r;
			cur++;
		}
	}
	for (int i=1; i<=qn; ++i) ans[i] ? puts("Yes") : puts("No");
	return 0;
}