Category Archives: hihoCoder

hihoCoder 1506-投掷硬币

hihoCoder 1506-投掷硬币

#1506 : 投掷硬币

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi有一枚神奇的硬币。已知第i次投掷这枚硬币时,正面向上的概率是Pi
现在小Hi想知道如果总共投掷N次,其中恰好M次正面向上的概率是多少。

输入

第一行包含两个整数N和M。
第二行包含N个实数P1, P2, ... PN
对于30%的数据,1 <= N <= 20
对于100%的数据,1 <= N <= 1000, 0 <= M <= N, 0 <= Pi <= 1

输出

输出一行一个实数表示恰好M次正面向上的概率。注意行末需要包含一个换行符'\n'。
输出与标准答案误差在0.001以内都被视为正确。

样例输入
2 1
0.5 0.5
样例输出
0.500000

某枚硬币在第i次投掷时,正面向上的概率为Pi,现在投掷N次,问恰好有M次正面向上的概率是多少。
这一题可以看成有N枚硬币,编号1~N,第i枚硬币正面向上的概率为Pi,把所有硬币一起抛向空中,问落地之后出现M枚正面向上的概率。
我一开始是这么做的,每一枚硬币都有可能正面向上或者反面向上,所以枚举所有2^N种情况,累加所有出现M次正面向上的概率。其实就是DFS,代码如下:

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;
double ans = 0;
int n, m;
void dfs(const vector<double>& probs, double curprob, int step, int up) {
	if (up == m) {
		double oneans = curprob;
		for (int i = step; i < n; ++i)oneans *= (1 - probs[i]);
		ans += oneans;
		return;
	}
	if (step < n) {
		dfs(probs, curprob*probs[step], step + 1, up + 1);
		dfs(probs, curprob*(1 - probs[step]), step + 1, up);
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	vector<double> probs(n, 0);
	for (int i = 0; i < n; ++i) scanf("%lf", &probs[i]);
	dfs(probs, 1, 0, 0);
	printf("%lf\n", ans);
	return 0;
}

不出所料,本代码提交TLE,只能过30%的数据。
其实每一枚硬币都有正面向上或者反面向上的选择,马上想到背包问题,对于每个商品有选或者不选这两种情况,所以本题实际上也是换了个马甲的背包问题。
令dp[i][j]表示前i枚硬币出现j枚正面向上的概率。那么对于第i枚硬币,有两种选择,如果第i枚硬币正面向上,则前i-1枚硬币只能有j-1枚正面向上,即dp[i][j]+=dp[i-1][j-1]*probs[i]。如果第i枚硬币反面向上,则前i-1枚硬币需要有j枚正面向上,所以dp[i][j-1]+=dp[i-1][j-1]*(1-probs[i])。最终返回dp[n][m]。
代码如下:

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;
int main() {
	//freopen("input.txt", "r", stdin);
	int n, m;
	scanf("%d %d", &n, &m);
	vector<double> probs(n + 1, 0);
	for (int i = 1; i <= n; ++i)scanf("%lf", &probs[i]);
	vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0));
	dp[0][0] = 1.0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= i; ++j) { //现在有i枚硬币,所以正面向上的个数j不超过i
			dp[i][j] += dp[i - 1][j - 1] * probs[i];  // head
			dp[i][j - 1] += dp[i - 1][j - 1] * (1 - probs[i]); // tail
		}
	}
	printf("%lf\n", dp[n][m]);
	return 0;
}

本代码提交AC,用时48MS。

hihoCoder 1505-小Hi和小Ho的礼物

hihoCoder 1505-小Hi和小Ho的礼物

#1505 : 小Hi和小Ho的礼物

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

某人有N袋金币,其中第i袋内金币的数量是Ai。现在他决定选出2袋金币送给小Hi,再选2袋金币送给小Ho,同时使得小Hi和小Ho得到的金币总数相等。他想知道一共有多少种不同的选择方法。
具体来说,有多少种下标四元组(i, j, p, q)满足i, j, p, q两两不同,并且i < j, p < q, Ai + Aj = Ap + Aq
例如对于数组A=[1, 1, 2, 2, 2],一共有12种选法:

i j p q
1 3 2 4
1 3 2 5
1 4 2 3
1 4 2 5
1 5 2 3
1 5 2 4
2 3 1 4
2 3 1 5
2 4 1 3
2 4 1 5
2 5 1 3
2 5 1 4

输入

第一行包含一个整数N。
第二行包含N个整数,A1, A2, A3 ... AN
对于70%的数据,1 <= N <= 100
对于100%的数据,1 <= N <= 1000, 1 <= Ai <= 1000000

输出

不同选择的数目。

样例输入
5
1 1 2 2 2
样例输出
12

简化一下题意就是:给定一个数组,从中取出四个数a,b,c,d,使得a+b=c+d,问一共有多少种取法。
首先尝试了一下O(n^4)的暴力方法,过了70%的数据。后面想想先把所有数存hash表,然后固定a,b,c三个数,如果a+b-c也在hash表中,则找到一种合法的取法,想来复杂度能降到O(n^3),提交之后居然WA,没理解。
后来参考大神的解法。首先把数及其频率hash到hash1中,然后把任意两数之和的频率hash到hash2中。最后遍历a和b,则hash2[a+b]是所有和为a+b的两数取法数,hash2[a+b]-hash1[a]*hash1[b]则是所有不是a和b但两数之和也是a+b的取法数,如果a,b本身有多次重复的话,还需要加上(hash1[a]-1)*(hash1[b]-1)。
比如有三个1和两个2,a=1,b=2,则还剩两个1和一个2,此时,如果从1,2中选两个数等于3,则有2*1=2种取法,即(hash1[a]-1)*(hash1[b]-1)。但是还有可能有0+3=3的情况,这就是hash2[a+b]-hash1[a]*hash1[b]。
当然还需要分a和b是否相等两种情况,因为a==b的情况有点特殊。
代码如下:

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<unordered_map>
using namespace std;
int main() {
	//freopen("input.txt", "r", stdin);
	int n;
	scanf("%d", &n);
	vector<long long> nums(n, 0);
	unordered_map<long long, int> hash1, hash2;
	for (int i = 0; i < n; ++i) {
		scanf("%lld", &nums[i]);
		++hash1[nums[i]];
	}
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			++hash2[nums[i] + nums[j]];
		}
	}
	long long ans = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (nums[i] != nums[j])ans += hash2[nums[i] + nums[j]] - hash1[nums[i]] * hash1[nums[j]] + (hash1[nums[i]] - 1)*(hash1[nums[j]] - 1);
			else {
				int cnt = hash1[nums[i]];
				int left = cnt - 2;
				ans += hash2[nums[i] + nums[j]] - cnt*(cnt - 1) / 2 + left*(left - 1) / 2;
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

本代码提交AC,用时444MS。

hihoCoder 1502-最大子矩阵

hihoCoder 1502-最大子矩阵

#1502 : 最大子矩阵

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一个NxM的矩阵A和一个整数K,小Hi希望你能求出其中最大(元素数目最多)的子矩阵,并且该子矩阵中所有元素的和不超过K。

输入

第一行包含三个整数N、M和K。
以下N行每行包含M个整数,表示A。
对于40%的数据,1 <= N, M <= 10
对于100%的数据,1 <= N, M <= 250 1 <= K <= 2147483647 1 <= Aij <= 10000

输出

满足条件最大的子矩阵所包含的元素数目。如果没有子矩阵满足条件,输出-1。

样例输入
3 3 9
1 2 3
2 3 4
3 4 5
样例输出
4

给定一个N*M的矩阵,要从中找出一个元素最多的子矩阵,使得该子矩阵的和不超过K。
如果确定了子矩阵的左上角点和右下角点,则唯一确定了该子矩阵。所以我们可以用一种完全暴力的方法来试一下这个题。两层循环确定左上角点(i,j),两层循环确定右下角点(u,v),再两层循环累加从(i,j)到(u,v)的元素和,如果和不超过K,则更新最大元素个数,否则继续循环。复杂度为O(n^6),TLE,但是能过40%的数据。
类似这样求子矩阵的和,子数组的和等问题,一般都需要求从0到i的累加和。网上有一题也是求最大子矩阵的问题,但是那道题定义子矩阵的大小是用子矩阵的和来定义的,而本题是用子矩阵中元素个数来定义的。但是原理差不多,可以参考
定义一个二维数组sum[i][j]表示固定子矩阵的左上角坐标为(1,1)(假设矩阵的下标从1开始),当右下角坐标为(i,j)时,这个子矩阵的和是多少。则有:
sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+matrix[i][j]
这个很好理解,相当于求面积,sum[i][j-1]+sum[i-1][j]加了两遍sum[i-1][j-1],所以要减掉一个,最后再加上sum[i][j]独有的matrix[i][j]。
有了sum[i][j]之后,怎样求任意一个子矩阵的和呢?假设我们要求第i,j两行、u,v两列交成的子矩阵的和,应该怎样计算呢。这个也很好算,也是面积的加加减减,如下图所示,把(j,v)的面积减去(j,u)左边以及(i,v)上边的面积,但是(i,u)左上的面积减了两次,所以还要加上。总结成公式就是:
cursum=sum[j][v]-sum[j][u-1]-sum[i-1][v]+sum[i-1][u-1]

      |               |
-----(i,u)----------(i,v)----
      |               |
      |               |
-----(j,u)----------(j,v)----
      |               |

通过cursum公式,我们很容易就能求出任意一个子矩阵的和了。但是要求和不超过K,且元素个数最多的子矩阵,还是免不了枚举起点和终点。所以最后求解的时候,我还是枚举了起点(i,j)和终点(u,v),然后通过上述公式求到子矩阵的和cursum,如果cursum不超过K,则更新最大子矩阵元素个数。
但是,这种方法还是TLE了!在我几近绝望的时候,我试着把v的遍历顺序由u→m改成了由m→u。什么意思呢,因为要求元素个数最多,如果从u列到最大的m列的子矩阵和都不超过K,则此时的元素个数肯定是在这个循环里最大的,所以直接跳过了v从u→m-1的那些列。但是如果v的遍历顺序是u→m,则开始的好多v的子矩阵和都不超过K,这样的话,v就需要遍历很久才能找到一个超过K的子矩阵和,最坏的情况是,遍历到最大值m时的子矩阵和也不超过K,所以还不如从最大值往小的遍历。这么简单的一改,居然AC了!不知道会不会是数据太弱了,毕竟复杂度都是一样的O(n^4)
代码如下:

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<string>
#include<climits>
using namespace std;
int main() {
	//freopen("input.txt", "r", stdin);
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	vector<vector<int>> matrix(n + 1, vector<int>(m + 1, 0));
	int minvalue = INT_MAX;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			scanf("%d", &matrix[i][j]);
			minvalue = min(minvalue, matrix[i][j]);
		}
	}
	if (minvalue > k)printf("-1\n");
	else if (minvalue == k)printf("1\n");
	else {
		int ans = INT_MIN;
		vector<vector<int>> sum(n + 1, vector<int>(m + 1, 0));
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i][j];
			}
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = i; j <= n; ++j) {
				//for (int u = 1; u <= m; ++u) {
				//	for (int v = u; v <= m; ++v) { // TLE
				//		int cursum = sum[j][v] - sum[j][u - 1] - sum[i - 1][v] + sum[i - 1][u - 1];
				//		if (cursum <= k)ans = max(ans, (j - i + 1)*(v - u + 1));
				//		else break;
				//	}
				//}
				for (int u = 1; u <= m; ++u) {
					for (int v = m; v >= u; --v) {
						int cursum = sum[j][v] - sum[j][u - 1] - sum[i - 1][v] + sum[i - 1][u - 1];
						if (cursum <= k) {
							ans = max(ans, (j - i + 1)*(v - u + 1));
							break;
						}
					}
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

本代码提交AC,用时169MS。

hihoCoder 1501-风格不统一如何写程序

hihoCoder 1501-风格不统一如何写程序

#1501 : 风格不统一如何写程序

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi写程序时习惯用蛇形命名法(snake case)为变量起名字,即用下划线将单词连接起来,例如:file_name、 line_number。
小Ho写程序时习惯用驼峰命名法(camel case)为变量起名字,即第一个单词首字母小写,后面单词首字母大写,例如:fileName、lineNumber。
为了风格统一,他们决定邀请公正的第三方来编写一个转换程序,可以把一种命名法的变量名转换为另一种命名法的变量名。
你能帮助他们解决这一难题吗?

输入

第一行包含一个整数N,表示测试数据的组数。(1 <= N <= 10)
以下N行每行包含一个以某种命名法命名的变量名,长度不超过100。
输入保证组成变量名的单词只包含小写字母。

输出

对于每组数据,输出使用另一种命名法时对应的变量名。

样例输入
2
file_name
lineNumber
样例输出
fileName
line_number

本题要求把蛇形命名法和驼峰命名法相互转换。简单题,首先判断字符串中是否有下划线来区分原命名法,然后遍历字符串,找下划线或者大写字母,然后直接转换即可。
代码如下,注意在getline之前把换行符读了。

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<string>
using namespace std;
int main() {
	//freopen("input.txt", "r", stdin);
	int n;
	char c;
	scanf("%d", &n);
	scanf("%c", &c); // 读取换行符\n
	string line;
	while (n--) {
		getline(cin, line);
		if (line.find('_') != string::npos) {
			string ans = "";
			int len = line.size(), i = 0, j = 0;
			for (j = 0; j < len; ++j) {
				if (line[j] == '_'&&j + 1 < len) {
					line[j + 1] = toupper(line[j + 1]);
					ans += line.substr(i, j - i);
					i = j + 1;
				}
			}
			ans += line.substr(i, j - i);
			cout << ans << endl;
		}
		else {
			string ans = "";
			int len = line.size(), i = 0, j = 0;
			for (j = 0; j < len; ++j) {
				if (isupper(line[j])) {
					line[j] = tolower(line[j]);
					if(ans=="") ans += line.substr(i, j - i);
					else ans += "_" + line.substr(i, j - i);
					i = j;
				}
			}
			ans += "_" + line.substr(i, j - i);
			cout << ans << endl;
		}
	}
	return 0;
}

本代码提交AC,用时0MS。

hihoCoder 1495-矩形分割

hihoCoder 1495-矩形分割

#1495 : 矩形分割

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi有一块由NxM个单位正方形组成的矩形。现在小Ho在某些单位正方形上画了一道分割线,这条分割线或者是单位正方形的主对角线(用'\'表示),或者是副对角线(用'/'表示)。
现在小Hi想知道这些分割线把NxM的矩形分割成了多少块区域。
例如

/\
\/

就把2x2的矩形分成了5个区域。

/\/\
\  /
 \/\

把3x4的矩形分成了7个区域。

输入

第一包含两个整数N和M。(1 <= N, M <= 100)
以下N行每行包含M个字符。每个字符只可能是/\或者空格。

输出

分割成的区域数目。

样例输入
3 4
/\/\
\  /
 \/\
样例输出
7

本题又是一个考察并查集的题,再一次栽在了并查集!
给定一个由n*m个小正方形组成的大矩形,现在在某些小正方形上画一道分隔线,该分隔线可能是小正方形的主对角线\,也可能是副对角线/。问经过分隔之后,把大矩形分隔成了多少块区域。
判断平面区域个数问题,一般都可以转化为并查集的问题,但是这题相对上一次的并查集又进了一步,这题应该算是三维的并查集了。
对于小正方形的每个点,我们用三维信息来表示(x,y,z),其中x,y表示顶点所在小正方形的行号和列号,z表示该顶点在该小正方形中的位置,坐标从左上角开始顺时针递增,如下图。

0-----1
|     |
|     |
3-----2

初始时,每个顶点自成一体,所以par[i]=i。
但是因为画的分隔线只能是对角线,所以相邻两个正方形中的共享边肯定属于同一个区域,应该把相邻正方形共享边的两个顶点union起来。比如下图中,第一列的两个正方形,蓝色的两条边应该union,即左上角正方形的2号节点应该和左下角正方形的0号节点union;同理,第一行的两个正方形,红色的两条边也应该union,即左上角的1号节点和右上角的3号节点union。
其实,红色的边也可以union 0和2,但此时蓝色的边就应该union 1和3了,只要两者不一致并在整个程序中统一就行。

0-----1  0-----1
|     |  |     |
|     |  |     |
3-----2  3-----2
0-----1
|     |
|     |
3-----2

注意,不是把红色边的0和1 union,2和3 union,因为0和1可能属于不同的区域,比如下图中,红色的0和1就属于不同的区域了。

0-----1  0-----1
|   / |  | \   |
| /   |  |   \ |
3-----2  3-----2
0-----1
|     |
|     |
3-----2

初始化完成之后,就需要进行并查集操作了。如果遇到空格,好说,把这个正方形的四个顶点都union起来。
如果遇到左斜杠/,类似于上图左上角的分隔线,则把这个正方形中的四个顶点分成了两个不同的区域。此时,我们需要统一一个划分顶点的规则:被分隔的对角点和其顺时针的下一个顶点属于一个集合。比如3顺时针的下一个顶点是0,所以3和0 union;1顺时针的下一个顶点是2,所以1和2 union。
类似的,如果遇到右斜杠\,类似上图右上角的分隔线。根据统一的规则,0和1 union,2和3 union。
所有操作完成之后,统计一下并查集中不同区域的个数就是最终结果。
代码如下,注意%c会读取换行符,所以在每行开头先%c读取上一行的换行符。

#include<iostream>
#include<cstdio>
#include<unordered_map>
#include<algorithm>
#include<functional>
#include<vector>
using namespace std;
const int MAXN = 105;
int n, m;
vector<int> par(MAXN * MAXN * 4);
int find_par(int u) {
	if (par[u] != u)
		par[u] = find_par(par[u]);
	return par[u];
}
void union_par(int u, int v) {
	par[find_par(u)] = find_par(v);
}
int id(int x, int y, int z) {
	return x * m * 4 + y * 4 + z;
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	int total = n * m * 4;
	for (int i = 0; i < total; ++i)par[i] = i;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (i > 0)union_par(id(i, j, 0), id(i - 1, j, 2));
			if (j > 0)union_par(id(i, j, 3), id(i, j - 1, 1));
			//if (i < n - 1)union_par(id(i, j, 2), id(i + 1, j, 0)); // 多余
			//if (j < m - 1)union_par(id(i, j, 1), id(i, j + 1, 3)); // 多余
		}
	}
	char c;
	for (int i = 0; i < n; ++i) {
		scanf("%c", &c); // 读取上一行的\n
		for (int j = 0; j < m; ++j) {
			scanf("%c", &c);
			if (c == ' ') {
				union_par(id(i, j, 0), id(i, j, 1));
				union_par(id(i, j, 1), id(i, j, 2));
				union_par(id(i, j, 2), id(i, j, 3));
				//union_par(id(i, j, 3), id(i, j, 0)); // 多余
			}
			else if (c == '/') {
				union_par(id(i, j, 3), id(i, j, 0));
				union_par(id(i, j, 1), id(i, j, 2));
			}
			else if (c == '\\') {
				union_par(id(i, j, 0), id(i, j, 1));
				union_par(id(i, j, 2), id(i, j, 3));
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < total; ++i) {
		if (find_par(i) == i)++ans;
	}
	printf("%d\n", ans);
	return 0;
}

本代码提交AC,用时4MS。

hihoCoder 1494-一面砖墙

hihoCoder 1494-一面砖墙

#1494 : 一面砖墙

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi的学校的教学楼前有一面砖墙。这面墙由N层砖砌成,其中从上到下第i层包含Ci块高度相同但宽度不同的砖。
例如下图所示的这面墙,由3层砖砌成。其中第1层包含3块砖,从左到右宽度依次是6、4和3;第2层包含4块砖,从左到右依次宽度依次是4、4、2和3;第3层包含3块砖,从左到右宽度依次是5、6和2。

+------------+
|  6  | 4 |3 |
+------------+
| 4 | 4 |2|3 |
+------------+
| 5  | 6   |2|
+------------+
          ^

现在小Hi想在墙上画一道竖线,并且希望竖线穿过的砖块数目越少越好(如果竖线刚好在左右两块砖的交界处,则不会穿过砖块)。例如上例在墙^标示的位置画线,只会穿过一块砖。
注意小Hi不能在墙的左右边沿画线。

输入

第一行一个整数N,表示层数。 (1 < N <= 100000)
以下N行每行包含若干个整数。其中第一个整数Ci代表该层砖块的数目,之后Ci个整数表示从左到右每块砖的宽度。
整面墙总砖块数目不超过100000,总宽度不超过100000000。

输出

最少穿过的砖块数目。

样例输入
3
3 6 4 3
4 4 4 2 3
3 5 6 2
样例输出
1

一面墙,由若干层砖砌成,每层有不同块不同宽度的砖。现在墙上画一道线,问最少能穿过多少块砖。重点是,如果线是画在某两块砖的交界处,则不算穿过这两块砖。
根据重点,画的线必须穿过越多层砖的交界处越好,如果这条线在这一层处于交界处,则在这一层没有和砖相交。所以我们只需统计一下所有层每两块砖之间的交界处坐标,我们在出现最多次数的交界处画一条线,则穿过最少的砖,穿过的砖块数是总的层数减去该交界坐标的频数。
代码如下:

#include<iostream>
#include<cstdio>
#include<unordered_map>
#include<algorithm>
#include<functional>
using namespace std;
int main() {
	//freopen("input.txt", "r", stdin);
	unordered_map<int, int> hash;
	int n, ci, width, total;
	scanf("%d", &n);
	total = n;
	while (n--) {
		scanf("%d", &ci);
		int sum = 0;
		while (ci--) {
			scanf("%d", &width);
			sum += width;
			if (ci != 0)++hash[sum];
		}
	}
	int maxlevel = 0;
	for (auto it = hash.begin(); it != hash.end(); ++it) {
		maxlevel = max(maxlevel, it->second);
	}
	printf("%d\n", total - maxlevel);
	return 0;
}

本代码提交AC,用时60MS。

hihoCoder 1493-歌德巴赫猜想

hihoCoder 1493-歌德巴赫猜想

#1493 : 歌德巴赫猜想

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

哥德巴赫猜想认为“每一个大于2的偶数,都能表示成两个质数之和”。
给定一个大于2的偶数N,你能找到两个质数P和Q满足P<=Q并且P+Q=N吗?

输入

一个偶数N(4 <= N <= 1000000)

输出

输出P和Q。如果有多组解,输出P最小的一组。

样例输入
10
样例输出
3 7

给定一个大于2的偶数N,找出两个质数P和Q,满足P<=Q且P+Q=N。
我还以为这题有什么数论技巧,没想到直接从小到大暴力枚举P就行了。。。
代码如下:

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
bool isPrim(int x) {
	if (x < 2)return false;
	for (int i = 2; i <= sqrt(x); ++i) {
		if (x%i == 0)return false;
	}
	return true;
}
int main() {
	int N;
	scanf("%d", &N);
	for (int i = 2; i <= N / 2; ++i) {
		if (isPrim(i) && isPrim(N - i)) {
			printf("%d %d\n", i, N - i);
			return 0;
		}
	}
	return 0;
}

本代码提交AC,用时0MS。

hihoCoder 1487-岛屿3

hihoCoder 1487-岛屿3

#1487 : 岛屿3

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

H国正在进行一项持续N周的填海造岛工程。整片工程海域可以被看作是1000x1000的网格。
每周都有一块1x1的单位方格海域被填成陆地。如果我们将连成一片的陆地(一块单位方格与它上下左右4个单位方格是相连的)视为岛屿,H国想监测每周末整片海域中一共存在有多少个岛屿,以及这些岛屿的总面积和总周长各是多少。
假设工程持续三周,第一周被填的海域坐标是(0, 0),那么第一周结束后有1座岛屿、总面积是1、总周长是4:

#..
...
...

第二周被填的海域坐标是(1, 1),那么第二周结束后有2座岛屿、总面积是2、总周长是8:

#..
.#.
...

第三周被填的海域坐标是(1, 0),那么第三周结束后有1座岛屿、总面积是3、总周长是8:

#..
##.
...

你能完成这项任务么?

输入

第一行包含一个整数N,表示工程持续的周数。(1 <= N <= 100000)
以下N行每行包含两个整数x和y,表示当周被填的海域坐标。(0 <= x, y < 1000)

输出

输出N行,每行包含3个整数,依次是当周末岛屿的数量、总面积和总周长。

样例输入
3
0 0
1 1
1 0
样例输出
1 1 4
2 2 8
1 3 8

有一个1000*1000的海域,每周往其中填入1*1的陆地,要求输出每周该海域中会形成多少个岛屿,以及岛屿的总面积和总周长。
其实这题不算难,只是太久没用并查集,用了DFS导致超时了。现在分别介绍两种方法。
首先我们来解决总面积和总周长这两个问题。
总面积好说,每周填入一个单元的陆地,则面积加一。
总周长要稍微注意,如果新加入的方块和其他所有方块都不邻接,则贡献+4周长;如果和一个已有方块邻接,则贡献+4-2周长;如果和两个已有方块邻接,则贡献+4-2*2周长;如果和3个已有方块邻接,则贡献+4-2*3周长。。。所以每加入一个方块,就看看该方块四周,如果和intercnt个方块邻接,则贡献周长+4-2*intercnt。
最麻烦的是求岛屿个数。当然可以像往常一样,对所有点DFS,求连通分量,但是TLE。
我稍微优化了一下,在board中,把每个连通分量都标记为一个不同的islandID,每次新加入一个方块时,令board[x][y]=++islandID,并从这个方块开始DFS,把所有和(x,y)连通的方块的ID都标记为新的(x,y)的islandID,同时记录一下被(x,y) DFS的方块旧的islandID。通过这个过程,能知道新方块(x,y)和多少个不同的旧岛屿相连,同时把所有和(x,y)相连的旧岛屿都标记为新的islandID了。
假设原来有n个岛屿,和新方块相连的旧岛屿有m个,则加入新方块之后,岛屿数更新为n-m+1,即m个旧岛屿都缩成1个新岛屿了。
DFS思路的代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cstdio>
#include<unordered_set>
using namespace std;
vector<vector<int>> board(1000, vector<int>(1000, 0));
vector<pair<int,int>> dirs = { {1,0},{-1,0},{0,1},{0,-1} };
void dfs(int x,int y, int islandID, unordered_set<int>& neighbor) {
	neighbor.insert(board[x][y]);
	board[x][y] = islandID;
	for (int i = 0; i < dirs.size(); ++i) {
		int newx = x + dirs[i].first, newy = y + dirs[i].second;
		if (newx >= 0 && newx < 1000 && newy >= 0 && newy < 1000 && board[newx][newy] != 0 && board[newx][newy] != islandID)dfs(newx, newy, islandID, neighbor);
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	int N, x, y;
	int island = 0, area = 0, perimeter = 0;
	int islandID = 1;
	bool first = true;
	scanf("%d", &N);
	while (N--) {
		scanf("%d %d", &x, &y);
		board[x][y] = islandID;
		++area;
		if (first) {
			perimeter = 4;
			island = 1;
			first = false;
		}
		else {
			int intercnt = 0; // 邻接方块数
			for (int i = 0; i < dirs.size(); ++i) {
				int newx = x + dirs[i].first, newy = y + dirs[i].second;
				if (newx >= 0 && newx < 1000 && newy >= 0 && newy < 1000 && board[newx][newy] != 0)++intercnt;
			}
			perimeter = perimeter + 4 - 2 * intercnt;
			if (intercnt == 0)++island;
			else {
				unordered_set<int> neighbor; // 邻接岛屿旧编号+新方块编号
				dfs(x, y, islandID, neighbor);
				island = island - neighbor.size() + 2; // 因为neighbor中包含新方块编号,所以这里要多加1
			}
		}
		++islandID;
		printf("%d %d %d\n", island, area, perimeter);
	}
	return 0;
}

本代码提交TLE,用时2792MS。
比赛结束之后,看了看AC的代码,用的全是并查集,没一个用DFS的。。。
好吧,那就改成并查集。求总面积和总周长的方法都一样,不同的是求岛屿个数。
我们用数组来实现并查集,把坐标(x,y)编码成x*1000+y便于存入一维数组。对于每个新加入的点u,在并查集中先用自己代表自己,represent[u]=u。然后环顾四周,把四周陆地所在岛屿的代表放到neighbor中并去重,这样就能得到新方块邻接的旧岛屿数,根据n-m+1算到新岛屿数。最后把邻接的旧岛屿和新方块u union起来。
代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cstdio>
#include<unordered_set>
using namespace std;
vector<vector<int>> board(1000, vector<int>(1000, 0));
vector<pair<int, int>> dirs = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };
vector<int> represent(1000 * 1000, -1);
int find_rep(int u) {
	if (u == represent[u])return u;
	else {
		represent[u] = find_rep(represent[u]);
		return represent[u];
	}
}
void union_rep(int u, int v) {
	represent[find_rep(u)] = find_rep(v);
}
int main() {
	//freopen("input.txt", "r", stdin);
	int N, x, y, u;
	int island = 0, area = 0, perimeter = 0;
	bool first = true;
	scanf("%d", &N);
	while (N--) {
		scanf("%d %d", &x, &y);
		board[x][y] = 1;
		++area;
		u = x * 1000 + y;
		represent[u] = u;
		if (first) {
			perimeter = 4;
			island = 1;
			first = false;
		}
		else {
			int intercnt = 0; // 邻接方块数
			unordered_set<int> neighbor; // 邻接岛屿
			for (int i = 0; i < dirs.size(); ++i) {
				int newx = x + dirs[i].first, newy = y + dirs[i].second;
				if (newx >= 0 && newx < 1000 && newy >= 0 && newy < 1000 && board[newx][newy] == 1) {
					++intercnt;
					neighbor.insert(find_rep(newx * 1000 + newy));
				}
			}
			for (auto it = neighbor.begin(); it != neighbor.end(); ++it)union_rep(u, *it);
			perimeter = perimeter + 4 - 2 * intercnt;
			island = island - neighbor.size() + 1;
		}
		printf("%d %d %d\n", island, area, perimeter);
	}
	return 0;
}

本代码提交AC,用时436MS,果然快了不少。

hihoCoder 1485-hiho字符串

hihoCoder 1485-hiho字符串

#1485 : hiho字符串

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

如果一个字符串恰好包含2个'h'、1个'i'和1个'o',我们就称这个字符串是hiho字符串。
例如"oihateher"、"hugeinputhugeoutput"都是hiho字符串。
现在给定一个只包含小写字母的字符串S,小Hi想知道S的所有子串中,最短的hiho字符串是哪个。

输入

字符串S
对于80%的数据,S的长度不超过1000
对于100%的数据,S的长度不超过100000

输出

找到S的所有子串中,最短的hiho字符串是哪个,输出该子串的长度。如果S的子串中没有hiho字符串,输出-1。

样例输入
happyhahaiohell
样例输出
5

如果字符串中包含2个h,1个i和1个o,则称该子串为hiho字符串。给定一个字符串s,问s中最短的hiho子串长度是多少。如果不存在hiho子串,则输出-1。
首先,肯定不能用两层循环暴力解法,这样的话需要O(n^3),因为判断子串是否是hiho串还需要O(n),所以乘起来就是O(n^3)
我当时的解法是,首先扫一遍字符串,记录下每个位置及其前面出现的h,i,o字符总数。然后我使用两层循环,把对应位置的h,i,o数目作差,如果等于2,1,1,则更新结果。但是O(n^2)的复杂度还是TLE了。
看了下第一名的解法,虽然复杂度也是O(n^2),但是高明许多。设置两个指针i,j,区间[i,j]相当于一个滑动窗口,对于每个i,j往后走,直到h,i,o次数不低于2,1,1,如果正好是2,1,1,则把当前长度j-i和结果比较。i往后走时,对应的s[i]频率要减1。
代码如下,注意第23行,必须是大于号,不能是大于等于,因为如果只是hash['o']==1就跳出的话,假设输入字符串是"oihateher",则第0位时hash['o']==1,此时跳出,导致起点i变成了1而找不到正确结果。具体用这个样例测试一下就知道。

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN = 100005;
int main() {
	string s;
	cin >> s;
	//s = "oihateher";
	int n = s.size();
	if (n < 4) {
		cout << -1;
		return 0;
	}
	vector<int> hash(256, 0);
	int ans = MAXN;
	for (int i = 0, j = 0; i < n; ++i) {
		while (j < n && (hash['h'] < 2 || hash['i'] < 1 || hash['o'] < 1)) {
			++hash[s[j++]];
			if (hash['h'] > 2 || hash['i'] > 1 || hash['o'] > 1)break;
		}
		if (hash['h'] == 2 && hash['i'] == 1 && hash['o'] == 1)
			ans = min(ans, j - i);
		--hash[s[i]];
	}
	if (ans == MAXN)cout << -1;
	else cout << ans;
	return 0;
}

本代码提交AC,用时13MS。

hihoCoder week 84-1-Lucky Substrings

hihoCoder week 84-1-Lucky Substrings
题目1 : Lucky Substrings
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
A string s is LUCKY if and only if the number of different characters in s is a fibonacci number. Given a string consisting of only lower case letters, output all its lucky non-empty substrings in lexicographical order. Same substrings should be printed once.
输入
A string consisting no more than 100 lower case letters.
输出
Output the lucky substrings in lexicographical order, one per line. Same substrings should be printed once.
样例输入
aabcd
样例输出
a
aa
aab
aabc
ab
abc
b
bc
bcd
c
cd
d


如果一个字符串中不同字母的个数是斐波那契数,则称这个字符串是Lucky的,问字符串S中哪些子串是Lucky子串。
要正确理解Lucky的定义,是不同字母的个数,而不是不同字母的个数序列。比如aabc是Lucky的,因为其有a,b,c共3种字母,而3在斐波那契数列中,所以aabc是Lucky的。不能理解为aabc中a出现2次,b,c分别出现1次,构成1,1,3是斐波那契数列,所以aabc是Lucky的。
所以只能枚举所有子串,判断每个子串是否为Lucky的。如果知道了S[i,...,j]中不同字母的个数,判断S[i,...,j+1]时,只要判断S[j+1]这个字母是否在之前出现过。所以通过保存之前不同字母的个数,可以快速判断S[i,...,j+1]的情况。
完整代码如下:

#include<iostream>
#include<string>
#include<set>
#include<vector>
using namespace std;
set<int> FIB_NUM = { 1,2,3,5,8,13,21 };
int main() {
	string s;
	cin >> s;
	set<string> ans;
	int n = s.size();
	for (int i = 0; i < n; i++) {
		vector<bool> alphabet(26, false);
		int cnt = 0;
		for (int j = i; j < n; j++) {
			if (!alphabet[s[j] - 'a']) {
				alphabet[s[j] - 'a'] = true;
				cnt++;
			}
			if (FIB_NUM.find(cnt) != FIB_NUM.end()) {
				ans.insert(s.substr(i, j - i + 1));
			}
		}
	}
	set<string>::iterator it = ans.begin();
	while (it != ans.end()) {
		cout << *it << endl;
		it++;
	}
	return 0;
}

本代码提交AC,用时17MS,内存0MB。