20160729 训练记录

tonyfang posted @ 2016年7月30日 08:33 in 随笔 with tags C++ OI , 698 阅读

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即可。

image

下面这张图,蓝色格子到红色格子 包括 第一行第三列 和 第四列黑色格子以上的,都要+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;
}

uburt.in 说:
2023年6月17日 13:55

Following verification, you must give a copy of your Aadhar card that has been self-attested.You must enter your personal information, such as your Aadhar card number, as well as your registered phone number, to which you will receive an OTP, uburt.in when creating an account on any KRA's eKYC site. Following verification, you must give a copy of your Aadhar card that has been self-attested. You must enter your personal information, such as your Aadhar card number, as well as your registered phone number, to which you will receive an OTP, when creating an account on any KRA's eKYC site.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter