# hihoCoder 1506-投掷硬币

hihoCoder 1506-投掷硬币

### 输出

2 1
0.5 0.5

0.500000

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


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


# hihoCoder 1505-小Hi和小Ho的礼物

hihoCoder 1505-小Hi和小Ho的礼物

### 描述

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


### 输出

5
1 1 2 2 2

12

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


# hihoCoder 1502-最大子矩阵

hihoCoder 1502-最大子矩阵

### 输出

3 3 9
1 2 3
2 3 4
3 4 5

4

sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+matrix[i][j]

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)----
|               |

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


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

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

### 输出

2
file_name
lineNumber

fileName
line_number

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


# hihoCoder 1495-矩形分割

hihoCoder 1495-矩形分割

### 描述

/\
\/


/\/\
\  /
\/\


### 输出

3 4
/\/\
\  /
\/\

7

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


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


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

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


# hihoCoder 1494-一面砖墙

hihoCoder 1494-一面砖墙

### 描述

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


### 输出

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


# hihoCoder 1493-歌德巴赫猜想

hihoCoder 1493-歌德巴赫猜想

### 输出

10

3 7

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


# hihoCoder 1487-岛屿3

hihoCoder 1487-岛屿3

### 描述

H国正在进行一项持续N周的填海造岛工程。整片工程海域可以被看作是1000x1000的网格。

#..
...
...


#..
.#.
...


#..
##.
...


### 输出

3
0 0
1 1
1 0

1 1 4
2 2 8
1 3 8

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


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


# hihoCoder 1485-hiho字符串

hihoCoder 1485-hiho字符串

### 输出

happyhahaiohell

5

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


# hihoCoder week 84-1-Lucky Substrings

hihoCoder week 84-1-Lucky Substrings

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

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