# hihoCoder 1552-缺失的拼图

hihoCoder 1552-缺失的拼图

### 输出

5
0 0 4 5
0 0 3 1
0 1 2 5
3 0 4 5
2 2 3 5

2 1 3 2

#include<algorithm>
#include<vector>
#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> Point;
int main() {
//freopen("input.txt", "r", stdin);
int n;
scanf("%d", &n);
map<Point, int> hash;
int a, b, c, d;
while (n--) {
Point left_bottom, right_top;
scanf("%d %d %d %d", &left_bottom.first, &left_bottom.second, &right_top.first, &right_top.second);
Point left_top = Point(left_bottom.first, right_top.second), right_bottom = Point(right_top.first, left_bottom.second);
++hash[left_bottom];
++hash[right_top];
++hash[left_top];
++hash[right_bottom];
}
set<Point> ans;
for (auto p : hash) {
if (p.second % 2 == 1) {
ans.insert(p.first);
}
}
a = c = ans.begin()->first;
b = d = ans.begin()->second;
for (auto p : ans) {
a = min(a, p.first);
b = min(b, p.second);
c = max(c, p.first);
d = max(d, p.second);
}
printf("%d %d %d %d\n", a, b, c, d);
return 0;
}


# hihoCoder 1551-合并子目录

hihoCoder 1551-合并子目录

### 描述

/hihocoder/offer22/solutions/p1
/hihocoder/challenge30/p1/test
/game/moba/dota2/uninstall

/hihocoder
/hihocoder/offer22
/hihocoder/offer22/solutions
/hihocoder/challenge30
/hihocoder/challenge30/p1
/game
/game/moba
/game/moba/dota2/

### 输出

3
/hihocoder/offer22/solutions/p1
/hihocoder/challenge30/p1/test
/game/moba/dota2/uninstall

8

#include<algorithm>
#include<vector>
#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
struct Node {
string key_;
map<string, Node*> children_;
Node(string key) :key_(key) {};
};
int main() {
//freopen("input.txt", "r", stdin);
int n;
scanf("%d\n", &n);
string line;
Node* root = new Node("");
while (n--) {
getline(cin, line);
int pre = 0;
int pos = line.find('//');
Node* cur = root;
while (pos != string::npos) {
if (pos != 0) {
string tmp = line.substr(pre + 1, pos - pre - 1);
if (cur->children_[tmp] == NULL) {
cur->children_[tmp] = new Node(tmp);
}
cur = cur->children_[tmp];
}
pre = pos;
pos = line.find('//', pos + 1);
}
}
ll ans = 0;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* cur = q.front();
q.pop();
++ans;
for (auto it : cur->children_) {
q.push(it.second);
}
}
printf("%lld\n", ans - 1);
return 0;
}


# hihoCoder 1550-顺序三元组

hihoCoder 1550-顺序三元组

### 输出

6
1 3 2 1 2 3

3

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


# hihoCoder 1543-SCI表示法

hihoCoder 1543-SCI表示法

### 输出

2
15
8

5
1

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
freopen("input.txt", "r", stdin);
scanf("%lld", &t);
while (t--) {
scanf("%lld", &n);
if (n == 1 || n == 2) {
printf("1\n");
} else {
ll i = 1, j = 2;
ll sum = i + j, ans = 0;
while (true) {
while (j <= n && sum < n) {
++j;
sum += j;
}
if (j > n)break;
while (i < j && sum > n) {
sum -= i;
++i;
}
if (sum == n) {
//printf("%d\n", j - i + 1);
ans = max(ans, j - i + 1);
break;
}
}
printf("%lld\n", ans);
}
}
return 0;
}


#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
freopen("input.txt", "r", stdin);
scanf("%lld", &t);
while (t--) {
scanf("%lld", &n);
if (n == 1 || n == 2) {
printf("1\n");
}
else {
ll ans = 1;
for (ll i = 1; i < n; ++i) {
ll sum = (1 + i)*i / 2;
if (sum > n)break;
ll left = sum - n;
if (left%i == 0) {
ans = max(ans, i);
}
}
printf("%lld\n", ans);
}
}
return 0;
}


# hihoCoder 1542-无根数变有根树

hihoCoder 1542-无根数变有根树

### 输出

5 4
1 2
3 1
4 3
5 1

3 1 4 0 1

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
const int kMaxN = 1005;
int n, k;
vector<int> parent(kMaxN, 0);
vector<vector<int>> graph(kMaxN, vector<int>(kMaxN, 0));
void DFS(int node, int pre) {
parent[node] = pre;
graph[node][pre] = 0;
graph[pre][node] = 0;
for (int i = 1; i <= n; ++i) {
if (graph[node][i] == 1) {
DFS(i, node);
}
}
graph[node][pre] = 1;
graph[pre][node] = 1;
}
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &k);
int a, b;
for (int i = 0; i < n - 1; ++i) {
scanf("%d %d", &a, &b);
graph[a][b] = 1;
graph[b][a] = 1;
}
DFS(k, 0);
for (int i = 1; i <= n; ++i)
printf("%d ", parent[i]);
return 0;
}


# hihoCoder 1519-逃离迷宫II

hihoCoder 1519-逃离迷宫II

### 输出

5 5
S.#.T
.....
.....
.....
.....

2

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
using namespace std;
const int MAXN = 505;
int n, m;
int startx, starty, endx, endy;
int ans = INT_MAX;
vector<vector<char>> maze(MAXN, vector<char>(MAXN, '0'));
vector<vector<char>> visited(MAXN, vector<char>(MAXN, '0'));
vector<vector<int>> dirs{ {-1,0},{1,0},{0,-1},{0,1} }; //up,down,left,right
vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向
bool ok(int x, int y) {
if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != '#')return true;
return false;
}
void dfs(int sx,int sy, int step) {
for (int i = 0; i < 4; ++i) {
int newx = sx + dirs[i][0], newy = sy + dirs[i][1];
if (ok(newx, newy) && visited[newx][newy] == '0') {
visited[newx][newy] = '1';
bool done = false;
while (ok(newx, newy)) {
visited[newx][newy] = '1';
if (newx == endx&&newy == endy) {
done = true;
break;
}
newx = newx + dirs[i][0], newy = newy + dirs[i][1];
}
if (done) {
ans = min(ans, step);
}
else {
dfs(newx + opdirs[i][0], newy + opdirs[i][1], step + 1);  // 往回走一步再递归
}
while (!(newx == sx&&newy == sy)) {
if (ok(newx, newy))visited[newx][newy] = '0'; // 复位
newx = newx + opdirs[i][0], newy = newy + opdirs[i][1];
}
}
}
}
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &m);
char c;
for (int i = 0; i < n; ++i) {
scanf("%c", &c);
for (int j = 0; j < m; ++j) {
scanf("%c", &maze[i][j]);
if (maze[i][j] == 'S') {
startx = i;
starty = j;
}
else if (maze[i][j] == 'T') {
endx = i;
endy = j;
}
}
}
visited[startx][starty] = '1';
dfs(startx, starty, 0);
if (ans == INT_MAX)printf("-1\n");
else printf("%d\n", ans);
return 0;
}


#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN = 505;
int n, m;
int startx, starty, endx, endy;
typedef struct P {
int x, y, step;
P(int x_, int y_, int step_) :x(x_), y(y_), step(step_) {};
};
vector<vector<char>> maze(MAXN, vector<char>(MAXN, '0'));
vector<vector<int>> dirs{ { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } }; //up,down,left,right
vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向
set<int> points;
bool ok(int x, int y) {
if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != '#')return true;
return false;
}
int id(int x, int y) {
return x*n + y;
}
int bfs() {
queue<P> q;
P p(startx, starty, 0);
q.push(p);
while (!q.empty()) {
p = q.front();
q.pop();
points.insert(id(p.x, p.y));
for (int i = 0; i < dirs.size(); ++i) {
int newx = p.x + dirs[i][0], newy = p.y + dirs[i][1];
while (ok(newx, newy)) {
if (newx == endx&&newy == endy) {
return p.step;
}
newx = newx + dirs[i][0], newy = newy + dirs[i][1];
}
int cornorx = newx + opdirs[i][0], cornory = newy + opdirs[i][1]; // 往回走一步
if (points.find(id(cornorx, cornory)) == points.end()) {
P tmp(cornorx, cornory, p.step + 1);
q.push(tmp);
}
}
}
return -1;
}
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &m);
char c;
for (int i = 0; i < n; ++i) {
scanf("%c", &c);
for (int j = 0; j < m; ++j) {
scanf("%c", &maze[i][j]);
if (maze[i][j] == 'S') {
startx = i;
starty = j;
}
else if (maze[i][j] == 'T') {
endx = i;
endy = j;
}
}
}
printf("%d\n", bfs());
return 0;
}


# hihoCoder 1518-最大集合

hihoCoder 1518-最大集合

### 输出

7
6 5 1 4 2 7 3

4

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
using namespace std;
unordered_map<int, int> result;
void solve(vector<int>& A, int start) {
unordered_set<int> si;
si.insert(start);
int last = start;
while (si.find(A[last]) == si.end()) {
si.insert(A[last]);
last = A[last];
}
int ans = si.size();
unordered_set<int>::iterator it = si.begin();
while (it != si.end()) {
result[*it] = ans; // 循环内的所有S[K]都相等
++it;
}
}
int main() {
//freopen("input.txt", "r", stdin);
int n;
scanf("%d", &n);
vector<int> A(n + 1, 0);
for (int i = 1; i <= n; ++i)scanf("%d", &A[i]);
for (int i = 1; i <= n; ++i) {
if (result.find(A[i]) == result.end())solve(A, A[i]);
}
int ans = 0;
for (unordered_map<int, int>::iterator it = result.begin(); it != result.end(); ++it)ans = max(ans, it->second);
printf("%d\n", ans);
return 0;
}


# hihoCoder 1504-骑士游历

hihoCoder 1504-骑士游历

### 输出

2 1 1

12

#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
vector<vector<int>> dirs = { { 1,2 },{ 1,-2 },{ 2,1 },{ 2,-1 },{ -2,1 },{ -2,-1 },{ -1,2 },{ -1,-2 } };
const int MAXN = 8;
const LL MOD = 1000000007;
vector<vector<LL>> matrix(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0));
inline bool ok(const int &x, const int &y) {
return x >= 0 && x < MAXN && y >= 0 && y < MAXN;
}
inline int id(const int &x, const int &y) {
return x*MAXN + y;
}
void init() {
for (int i = 0; i < MAXN; ++i) {
for (int j = 0; j < MAXN; ++j) {
for (int k = 0; k < dirs.size(); ++k) {
int x = i + dirs[k][0], y = j + dirs[k][1];
if (ok(x, y))matrix[id(i, j)][id(x, y)] = 1;
}
}
}
}
vector<vector<LL>> multi(const vector<vector<LL>>& mat1, const vector<vector<LL>>& mat2) {
vector<vector<LL>> ans(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0));
for (int i = 0; i < MAXN*MAXN; ++i) {
for (int j = 0; j < MAXN*MAXN; ++j) {
for (int k = 0; k < MAXN*MAXN; ++k) {
ans[i][j] = (ans[i][j] + mat1[i][k] * mat2[k][j]) % MOD;
}
}
}
return ans;
}
vector<vector<LL>> pow(vector<vector<LL>>& mat, int n) {
vector<vector<LL>> ans(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0));
for (int i = 0; i < MAXN*MAXN; ++i)ans[i][i] = 1; // 单位阵
while (n != 0) {
if (n & 1)ans = multi(ans, mat);
mat = multi(mat, mat);
n >>= 1;
}
return ans;
}
int main() {
int n, r, c;
scanf("%d %d %d", &n, &r, &c);
--r;
--c;
init();
vector<vector<LL>> finalMat = pow(matrix, n);
int idx = id(r, c);
// first way:
long long ans = 0;
for (int i = 0; i < MAXN*MAXN; ++i)ans = (ans + finalMat[idx][i]) % MOD;
printf("%lld\n", ans);
// second way:
//vector<vector<LL>> one(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0));
//one[idx][idx] = 1;
//one = multi(one, finalMat);
//long long ans = 0;
//for (int i = 0; i < MAXN*MAXN; ++i) {
//	for (int j = 0; j < MAXN*MAXN; ++j) {
//		ans = (ans + one[i][j]) % MOD;
//	}
//}
//printf("%lld\n", ans);
return 0;
}


# hihoCoder 1507-可疑的记录

hihoCoder 1507-可疑的记录

### 输出

3
1 2
1 3
1 3

2 3

1. 首先，如果这一行x,y中y如果出现1，则这一行肯定是有问题的，因为1是根节点，不可能在右边。
2. 其次，如果出现x==y，也有问题，因为树没有自回路。
3. 最后，正常的树中除了根节点，每个节点有且仅有一个父亲节点，如果添加了一行，且不满足上面两种情况，则肯定会出现某个点的父亲节点有两个！所以我们只需要找出出现两个父亲节点的节点即可，而且这两个父亲都有可疑。

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<unordered_map>
#include<unordered_set>
using namespace std;
int n, x, y;
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d", &n);
vector<int> xarry(n + 1, 0), yarry(n + 1, 0);
for (int i = 0; i < n; ++i) {
scanf("%d %d", &xarry[i], &yarry[i]);
}
vector<vector<int>> parent(n + 1, vector<int>());
for (int i = 0; i < n; ++i) {
if (yarry[i] == 1) { // 根节点不可能在右边
printf("%d\n", i + 1);
break;
}
if (xarry[i] == yarry[i]) { // 没有自回路
printf("%d\n", i + 1);
break;
}
parent[yarry[i]].push_back(i + 1);
}
for (int i = 1; i <= n; ++i) {
if (parent[i].size() > 1) {
printf("%d %d ", parent[i][0], parent[i][1]);
break; // 因为只添加了一行，所以只可能有一个节点有两个父亲
}
}
return 0;
}


# hihoCoder 1508-剑刃风暴

hihoCoder 1508-剑刃风暴

### 输出

10 2
0 10
0 10
9 10
1 2
4 5
8 8
8 4
4 2
7 7
0 7

3

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAX_N = 2005;
const double PI = acos(-1.0);
//const double R = 1.0;//定义覆盖圆半径为R
int T, n, total, R;
struct Point {
double x, y;
}point[MAX_N];
struct Angle {
double data;
int is;
bool operator < (const Angle& rhs) const {
return data<rhs.data;
}
}angle[MAX_N * 2];
inline double Dis(Point a, Point b)//计算线段ab的长度
{
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
inline double God(Point a, Point b)//计算向量ab的极角
{
double res = atan(fabs((b.y - a.y) / (b.x - a.x)));
if (b.y<a.y) {
if (b.x<a.x) res += PI;
else res = 2 * PI - res;
}
else {
if (b.x<a.x) res = PI - res;
}
return res;
}
void solve()
{
int res = 1;
for (int i = 0; i<n; i++) {
total = 0;
for (int j = 0; j<n; j++) {
if (i == j) continue;
double dist = Dis(point[i], point[j]);
if (dist>2.0 * R) continue;
double base = God(point[i], point[j]);
double extra = acos((dist / 2.0) / R); //计算差角
angle[total].data = base - extra; // in
angle[total++].is = 1;
angle[total].data = base + extra; // out
angle[total++].is = -1;
}
if (total <= res) continue;
sort(angle, angle + total);
int tmp = 1;
for (int j = 0; j<total; j++) {
tmp += angle[j].is;
res = max(res, tmp);
}
}
printf("%d\n", res);
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &R);
for (int i = 0; i<n; i++) {
scanf("%lf %lf", &point[i].x, &point[i].y);
}
solve();
return 0;
}