一台机器上配置多个Git的rsa

一台机器上配置多个 git 的 rsa

建立 rsa

1
ssh-keygen -t rsa -C "你的邮箱地址"

执行完这条命令之后, 会弹出如下提示:

1
Enter file in which to save the key (/Users/aaaa/.ssh/id_rsa):

在这里这里就是 “建立多个不同rsa“文件的地方,输入不同的名字,就会产生不同的rsa.例如输入: github_rsa。就产生了github_rsa.
重复上面的命令,再建立gitlab的即可。

修改 ssh config

现在,gitlab和github都有自己的rsa了。那么,如何引导选择不同的rsa验证呢。这时候需要修改 ssh config文件。
如果你的 ~/.ssh 目录下没有 请建立一个这样的文件, 文件名: config。
下面的事情是修改config文件。按照如下方式修改。

1
2
3
4
5
6
7
Host github.com
User 你的名字
IdentityFile ~/.ssh/id_rsa

Host gitlab.com
User 你的名字
IdentityFile ~/.ssh/csdn_rsa

删除本地全局设置

如果之前使用过程中使用过git config --global user.name或者 git config --global user.email 命令,git 会在 C 盘目下产生一个.gitconfig文件,这个文件中保存了全局的git帐号信息,应该删除掉。

参考资料

如何在一台机器上配置多个git的rsa


Centos7 卸载 MariaDB 并安装 Mysql

Centos7 卸载 MariaDB 并安装 Mysql

查看已安装的的 MariaDB 相关的模块

1
2
3
4
[user@localhost ~]$ rpm -qa | grep mariadb
mariadb-server-5.5.56-2.el7.x86_64
mariadb-5.5.56-2.el7.x86_64
mariadb-libs-5.5.56-2.el7.x86_64

卸载

1
2
3
[user@localhost ~]$ sudo rpm -e mariadb-server-5.5.56-2.el7.x86_64
[user@localhost ~]$ sudo rpm -e --nodeps mariadb-5.5.56-2.el7.x86_64
[user@localhost ~]$ sudo rpm -e --nodeps mariadb-libs-5.5.56-2.el7.x86_64

安装 MySql

1
2
3
4
wget 'https://dev.mysql.com/get/mysql57-community-release-el7-11.noarch.rpm'
sudo rpm -Uvh mysql57-community-release-el7-11.noarch.rpm
sudo yum install mysql-community-server
sudo systemctl start mysqld

修改 root 初始密码

MySQL5.7加强了root用户的安全性,因此在第一次安装后会初始化一个随机密码,以下为查看初始随机密码的方式,执行完该命令后则会看到一组随机字符串为初始密码。

1
grep 'temporary password' /var/log/mysqld.log

注意,log只有在mysql服务运行过一遍之后才会有显示

但是不管我怎么操作,在 mysqld.log 中仍然找不到自己的密码,于是,便只能使用终极的破
解操作了

1
sudo vim /etc/my.cnf

在 [mysqld_safe] 下增加一行

1
skip-grant-tables

即可跳过授权,直接进入mysql

修改密码

1
2
3
4
mysql -uroot
use mysql;
update mysql.user set authentication_string=password('123456') where user='root';
exit

此时即可以密码123456来登录 mysql 了

增加用户并授予权限

1
2
CREATE USER 'username'@'%' IDENTIFIED BY 'password';
GRANT all privileges ON databasename.tablename TO 'username'@'host'

参考文献

1.Centos 7 安装 MySQL
1.CentOS7.2 安装mysql5.7初始密码问题总结
1.centos7——MySql 5.7添加用户、删除用户与授权


Centos7 卸载 OpenJDK

Centos 卸载 OpenJDK

查找 OpenJDK 安装包

1
2
3
[root@localhost ~]# rpm -qa | grep openjdk
java-1.8.0-openjdk-headless-1.8.0.151-5.b12.el7_4.x86_64
java-1.8.0-openjdk-1.8.0.151-5.b12.el7_4.x86_64

卸载 OpenJDK 安装包

1
2
[root@localhost ~]# yum -y remove java-1.8.0-openjdk-headless-1.8.0.151-5.b12.el7_4.x86_64
[root@localhost ~]# yum -y remove java-1.8.0-openjdk-1.8.0.151-5.b12.el7_4.x86_64

参考文献

1.CentOS7卸载OpenJDK安装Oracle JDK


hihoCoder - 1523、数组重排2

#1523 : 数组重排2

描述

给定一个1-N的排列A1, A2, … AN,每次操作小Hi可以选择一个数,把它放到数组的最左边。

请计算小Hi最少进行几次操作就能使得新数组是递增排列的。


输入

第一行包含一个整数N。

第二行包含N个两两不同整数A1, A2, … AN。(1 <= Ai <= N)

对于60%的数据 1 <= N <= 20

对于100%的数据 1 <= N <= 100000


输出

一个整数代表答案


样例输入

5
2 3 1 4 5


样例输出

1


限制

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


思路

从数组的最后向前遍历,令flag=n,如果碰见a[i]==n,则n-1。遍历完n即为答案。原理即为此题是将不符合递增序列的数字放置最前方,则必定是将所有不符合序列的数字中最大的一个放到最前,因此只要将符合序列的数字个数找出删去即可。


题解

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
Author: Yuki
GitHub: https://github.com/Yuki-14544869/
Blog: https://yuki-14544869.github.io/
*/
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000") //手动扩栈
typedef long long LL;
#define INF = 0x3f3f3f3f;
#define eps 1e-10
#define ff(a, b, c, d) for(int a=b; a<c; a+=d)
#define fff(a, b, c, d) for(int a=b; a>=c; a-=d)
#define mm(a, b) memset(a, b, sizeof(a))
const double PIE = acos(-1.0);
void init() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
}


const int N = 100000+50;
int n;
int a[N] = {0};

int main() {
init();
cin >> n;
ff(i,0,n,1)
cin >> a[i];
int MAX = n;
fff(i,n-1,0,1)
if(a[i] == MAX)
MAX--;
cout << MAX << endl;
return 0;
}

Java

1
Writting...

hihoCoder - 1519、逃离迷宫II

#1519 : 逃离迷宫II

描述

小Hi被坏女巫抓进里一间有N x M个格子组成的矩阵迷宫。

有些格子是小Hi可以经过的,我们用’.’表示;有些格子上有障碍物小Hi不能经过,我们用’#’表示。小Hi的起始位置用’S’表示,他需要到达用’T’表示的格子才能逃离迷宫。

麻烦的是小Hi被坏女巫施了魔法,他只能选择上下左右某一个方向,沿着这个方向一直走,直到遇到障碍物或者迷宫边界才能改变方向。新的方向可以是上下左右四个方向之一。之后他还是只能沿着新的方向一直走直到再次遇到障碍物或者迷宫边界……

小Hi想知道他最少改变几次方向才能逃离这个迷宫。


输入

第一行包含两个整数N和M。 (1 <= N, M <= 500)

以下N行每行M个字符,代表迷宫。


输出

一个整数代表答案。如果小Hi没法逃离迷宫,输出-1。


样例输入

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


样例输出

2


限制

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


思路

BFS。往当前方向一直走到无路可走在转弯,一直重复。在节点内用flag标记当前转弯次数。


题解

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/*
Author: Yuki
GitHub: https://github.com/Yuki-14544869/
Blog: https://yuki-14544869.github.io/
*/
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int min = 0x3f3f3f3f;
#define ff(a, b, c, d) for(int a=b; a<c; a+=d)
#define mm(a, b) memset(a, b, sizeof(a))
namespace BFS {
int n, m;
char maps[505][505];
bool vis[505][505] = {false};
int ans[505][505] = {0};
int sx, sy, ex, ey;
int dis[4][2] = {-1,0,0,-1,1,0,0,1};//0左1上2右3下
struct node {
int x, y;
int cnt;
node(int _x, int _y, int _cnt):x(_x),y(_y),cnt(_cnt){}
};
bool check(int x, int y) {
if(x<0 || x>=n || y<0 || y>=m)
return false;
return maps[x][y] != '#';
}
void init() {
cin >> n >> m;
ff(i, 0, n, 1)
ff(j, 0, m, 1) {
cin >> maps[i][j];
if(maps[i][j]=='S')
sx=i, sy=j;
else if(maps[i][j]=='T')
ex=i, ey=j;
}
}
int bfs() {
vis[sx][sy] = true;
queue<node> q;
q.push({sx, sy, 0});

while(!q.empty()) {
node now = q.front();
q.pop();

ff(i, 0, 4, 1) {
//cout << now.x << " " << now.y << endl;
int x = now.x + dis[i][0];
int y = now.y + dis[i][1];
//cout << x << " " << y << endl;
if(!check(x, y))
continue;
if(maps[x][y] == 'T')
return now.cnt;
while(check(x+dis[i][0], y+dis[i][1])) {
x += dis[i][0];
y += dis[i][1];

if(x==ex && y==ey)
return now.cnt;
}
if(!vis[x][y]) {
int cnt = now.cnt + 1;
q.push((node){x, y, cnt});
vis[x][y] = true;
}
}
}
return -1;
}
}
using namespace BFS;
void intxt() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
}
int main() {
intxt();
init();
// cout << n << " " << m << endl;
// ff(i, 0, n, 1) {
// ff(j, 0, m, 1)cout << maps[i][j];
// cout << endl;
// }
// cout << sx << " " << sy << endl
// << ex << " " << ey << endl;
cout << bfs() << endl;
return 0;
}

Java

1
Writting...

hihoCoder - 1330、数组重排

#1330 : 数组重排

描述

小Hi想知道,如果他每次都按照一种固定的顺序重排数组,那么最少经过几次重排之后数组会恢复初始的顺序?

具体来讲,给定一个1 - N 的排列 P,小Hi每次重排都是把第 i 个元素放到第 Pi个位置上。例如对于 P = (2, 3, 1),假设初始数组是(1, 2, 3),重排一次之后变为(3, 1, 2),重排两次之后变为(2, 3, 1),重排三次之后变回(1, 2, 3)。

被排数组中的元素可以认为是两两不同的。


输入

第一行一个整数 N ,代表数组的长度。 (1 ≤ N ≤ 100)

第二行N个整数,代表1 - N 的一个排列 P 。


输出

输出最少重排的次数。


样例输入

3
2 3 1


样例输出

3


限制

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


思路

对于每一个点分别通过模拟得出最小步骤,再求每个最小步骤的最小公倍数。


题解

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/*
Author: Yuki
GitHub: https://github.com/Yuki-14544869/
Blog: https://yuki4294967295.cn/
*/
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000") //手动扩栈
typedef long long LL;
#define eps 1e-10
#define ff(a, b, c, d) for (int a = b; a < c; a += d)
#define fff(a, b, c, d) for (int a = b; a >= c; a -= d)
#define mm(a, b) memset(a, b, sizeof a)
const double PIE = acos(-1.0);
const int INF = 0x3f3f3f3f;
namespace IO {
const int MX = 4e7;
char buf[MX];
int c, sz;
void init() {
c = 0;
sz = fread(buf, 1, MX, stdin);
}
inline bool II(int &t) {
while(c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++;
if(c >= sz) return false;
bool flag = 0;
if(buf[c] == '-') flag = 1, c++;
for(t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0';
if(flag) t = -t;
return true;
}
}
using namespace IO;
void filein() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
}

int N;
int p[105] = {0};

LL GCD(LL a, LL b) {
LL tmp = a%b;
if(tmp == 0)
return b;
return GCD(b, tmp);
}

LL LCM(LL a, LL b) {
return a*b / GCD(a, b);
}
int main() {
//ios::sync_with_stdio(false);
filein();
//init();
//II(N);
while(~scanf("%d", &N)) {
mm(p, 0);
ff(i, 1, N+1, 1) {
scanf("%d", &p[i]);
}
LL ans = 1;
for(LL i=1; i<=N; ++i) {
LL tmp = p[i];
LL cnt = 1;
while(tmp!=i) {
tmp = p[tmp];
cnt++;
}
ans = LCM(ans, cnt);
}
printf("%lld\n", ans);
}



// ff(i, 1, N+1, 1) {
// cout << p[i] << endl;
// }

return 0;
}

Java

1
Writting...

hihoCoder - 1328、逃离迷宫

#1328 : 逃离迷宫

描述

小Hi正处在由 N × M 个房间组成的矩阵迷宫中。为了描述方便,我们把左上角的房间的坐标定为(0, 0),右下角房间的坐标定为(N-1, M-1)。每个房间可能是3种状态之一:开放的、关闭的、或者上锁的。

开放房间用’.’表示。小Hi可以从一个开放房间到达另一个相邻的(上下左右)开放房间。

关闭房间用’#’表示。小Hi永远不能进入一个关闭的房间。

上锁的房间用大写字母(‘A’, ‘B’, ‘C’ …)表示。小Hi在取得相应的钥匙前不能进入上锁的房间,而一旦取得钥匙就可以反复进入上锁的房间。每个房间的锁都是不同的,相应的钥匙在迷宫中的某一房间里,小Hi进入该房间就可以取得钥匙。

小Hi一开始处于一个开放房间,坐标(a, b)。迷宫的出口是一个开放或者上锁的房间,坐标(c, d)。假设小Hi每移动到一个相邻房间需要花费单位1的时间,那么小Hi到达出口最少需要花费多少时间?


输入

第一行包含7个整数: N , M , K , a , b , c , d . 其中N , M是矩阵的行列数;K 是上锁的房间数目,(a, b)是起始位置,(c, d)是出口位置。(1 ≤ N, M ≤ 100, 0 ≤ K ≤ 5, 0 ≤ a, c < N, 0 ≤ b, d < M)

以下 N 行每行包含 M 个字符,表示迷宫矩阵。

再以下 K 行每行两个整数 x, y,依次表示上锁房间A , B , C ….的钥匙所在房间坐标。(0 ≤ x < N, 0 ≤ y < M)


输出

输出到达出口的最短时间。如果小Hi永远到达不了出口,输出-1。


样例输入

4 4 2 0 0 0 3
.A.B
.#..
.#..
.#..
3 0
3 3


样例输出

15


限制

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


思路

状态压缩。用v[x][y][k]表示在(x,y)这个点是否访问过,v[x][y][z]的值为当前所花的时间,k的二进制表示现在身上有多少个钥匙。


题解

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/*
Author: Yuki
GitHub: https://github.com/Yuki-14544869/
Blog: https://yuki-14544869.github.io/
*/
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int min = 0x3f3f3f3f;
#define ff(a, b, c, d) for(int a=b; a<c; a+=d)
#define mm(a, b) memset(a, b, sizeof(a))

typedef struct node{
int x, y, sum;
};
char maps[105][105];
int vis[105][105][1<<6];
int dis[4][2] = {-1,0,0,-1,1,0,0,1};
int n, m, k, sx, sy, ex, ey;
vector<pair<int, int>> keys;
bool check(int x, int y) {
if(x<0 || x>=n || y<0 || y>=n)
return false;
if(maps[x][y]=='#')
return false;

return true;
}
int bfs() {
mm(vis, 0);
vis[sx][sy][0] = 0;
queue <node> q;
q.push((node){sx, sy, 0});

while(!q.empty()) {
node now = q.front();
q.pop();
if(now.x==ex && now.y==ey)
return vis[now.x][now.y][now.sum];

ff(i, 0, 4, 1) {
int nx = now.x+dis[i][0];
int ny = now.y+dis[i][1];
if(!check(nx, ny))
continue;
if(maps[nx][ny]=='.' && vis[nx][ny][now.sum]==0) {
vis[nx][ny][now.sum] = vis[now.x][now.y][now.sum]+1;
q.push((node){nx, ny, now.sum});
} else if(isdigit(maps[nx][ny])) {
int sum = now.sum|(1<<(maps[nx][ny]-'0'));
if(vis[nx][ny][sum])
continue;
vis[nx][ny][sum] = vis[now.x][now.y][now.sum] + 1;
q.push((node){nx, ny, sum});
} else if(isupper(maps[nx][ny])) {
if(now.sum&(1<<(maps[nx][ny]-'A')) && vis[nx][ny][now.sum]==0) {
vis[nx][ny][now.sum] = vis[now.x][now.y][now.sum] + 1;
q.push((node){nx, ny, now.sum});
}
}
}
}
return -1;
}

int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
cin >> n >> m >> k >> sx >> sy >> ex >> ey;
ff(i, 0, n, 1)
ff(j, 0, m, 1)
cin >> maps[i][j];

ff(i, 0, k, 1) {
int x, y;
cin >> x >> y;
keys.push_back({x, y});
maps[x][y] = '0' + i;
}
cout << bfs() << endl;
return 0;
}

Java

1
Writting...

hihoCoder - 1356、分隔相同整数

#1356 : 分隔相同整数

描述

给定一个包含N个整数的数组A。你的任务是将A重新排列,使得任意两个相等的整数在数组中都不相邻。

如果存在多个重排后的数组满足条件,输出字典序最小的数组。

这里字典序最小指:首先尽量使第一个整数最小,其次使第二个整数最小,以此类推。


输入

第一行包含一个整数N,表示数组的长度。(1 <= N <= 100000)

第二行包含N个整数,依次是 A1, A2, … AN。(1 <= Ai <= 1000000000)


输出

输出字典序最小的重排数组。如果这样的数组不存在,输出-1。


样例输入

4
2 1 3 3


样例输出

1 3 2 3


限制

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


思路

#1327 : 分隔相同字符思路类似,只不过因为数据量变大了,无法在时间限制内将数组遍历,于是考虑到了STL用以查询,维护一个二元组(x, y)。有以下集中操作:

  1. 插入/删除/修改其中某个元素(x,y)
  2. 查询x的最大值
  3. 查询y最大的二元组中x最小&次小的那个
  4. 查询x最小的二元组

题解

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*
Author: Yuki
GitHub: https://github.com/Yuki-14544869/
Blog: https://yuki4294967295.cn/
*/
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int min = 0x3f3f3f3f;
#define ff(a, b, c, d) for(int a=b; a<c; a+=d)
#define mm(a, b) memset(a, b, sizeof(a))


int N;
map<int, int> cnt;
typedef pair<int, int> p;
set<p, greater<p> > s;


int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
cin >> N;
int x;
ff(i, 0, N, 1) {
cin >> x;
cnt[x]++;
}

for(auto& x : cnt) {
s.insert({x.second, -x.first});
}

// for(auto&x : cnt) {
// cout << x.first << " " << x.second << endl;
// }

if(s.begin()->first > (N-1)/2+1) {
cout << "-1" << endl;
return 0;
}
//cout << "out : " << N << endl;
for(int res, pre=0; N--; pre=res) {
//cout << N << endl;
int temp = s.begin()->first;
if(temp > (N-1)/2+1) {
auto it = s.begin();
if(it->second == pre)
it++;
res = -it->second;
if(it->first==1)
cnt.erase(res);
else {
s.insert({it->first-1, it->second});
cnt[res]--;
}
s.erase(it);
} else {
auto it = cnt.begin();
if(it->first==pre)
it++;
res = it->first;
s.erase({it->second, -res});
if(it->second==1)
cnt.erase(it);
else {
it->second--;
s.insert({it->second, -res});
}
}
cout << res << ' ';
}
cout << endl;
return 0;
}

Java

1
Writting...

参考材料

hihocoder 1356 分隔相同整数


hihoCoder - 1327、分隔相同字符

#1327 : 分隔相同字符

描述

给定一个只包含小写字母’a’-‘z’的字符串 S ,你需要将 S 中的字符重新排序,使得任意两个相同的字符不连在一起。

如果有多个重排后字符串满足条件,输出字典序最小的一个。

如果不存在满足条件的字符串,输出INVALID。


输入

字符串S。(1 ≤ |S| ≤ 100000)


输出

输出字典序最小的答案或者INVALID。


样例输入

aaabc


样例输出

abaca


限制

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


思路

贪心,由题意易知VALID的充要条件即为此字母的长度小于整个字符串长度len/2向上取整。在每次贪心之后重新check新字符串是否VALID就可。


题解

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/*
Author: Yuki
GitHub: https://github.com/Yuki-14544869/
Blog: https://yuki-14544869.github.io/
*/
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int min = 0x3f3f3f3f;
#define ff(a, b, c, d) for(int a=b; a<c; a+=d)
#define mm(a, b) memset(a, b, sizeof(a))

string input;
int cnt[26] = {0};

bool check(int x) {
ff(i, 0, 26, 1)
if(cnt[i]>(x-1)/2+1)
return false;
return true;
}

int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
cin >> input;
int len = input.size();
//cout << len << endl;
ff(i, 0, len, 1)
cnt[input[i]-'a']++;
if(!check(len)) {
cout << "INVALID" << endl;
return 0;
}
/*
int pre = -1;
ff(i, 0, len, 1) {
ff(j, 0, 26, 1) {
if(cnt[j]>0 && j!=pre) {
cnt[j]--;
if(check(len-1)) {
putchar('a'+j);
pre = j;
len--;
break;
} else cnt[j]++;
}
}
}
*/

int pre = -1;
ff(i, 0, input.size(), 1) {
ff(j, 0, 26, 1) {
if(cnt[j] && j!=pre) {
cnt[j]--;
if(check(len-1)) {
putchar('a'+j);
pre=j;
len--;
break;
}
else cnt[j]++;
}
}
}
cout << endl;
return 0;
}

Java

1
Writing...

hihoCoder-1040、矩形判断

#1040 : 矩形判断

描述

给出平面上4条线段,判断这4条线段是否恰好围成一个面积大于0的矩形。


输入

输入第一行是一个整数T(1<=T<=100),代表测试数据的数量。
每组数据包含4行,每行包含4个整数x1, y1, x2, y2 (0 <= x1, y1, x2, y2 <= 100000);其中(x1, y1), (x2,y2)代表一条线段的两个端点。


输出

每组数据输出一行YES或者NO,表示输入的4条线段是否恰好围成矩形。


样例输入

3
0 0 0 1
1 0 1 1
0 1 1 1
1 0 0 0
0 1 2 3
1 0 3 2
3 2 2 3
1 0 0 1
0 1 1 0
1 0 2 0
2 0 1 1
1 1 0 1


样例输出

YES
YES
NO


限制

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


思路

这道题目思路简单。首先判断给出的四条线段能不能组成四边形,如果可以,在判断这个四边形是不是矩形。

判断是不是四边形:
输入了四条线段,总共有八个点。如果这八个点中,两两重合,总共有四个点,那么一定是一个四边形。判断八个点是不是两两重合,用set即可。set插入八个点,如果大小为四,那么就是两两重合。
一个四边形,如果一条边和另外三条边要么平行,要么垂直,那么就是矩形。判断平行或垂直,用斜率即可。


题解

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/*
Author: Yuki
GitHub: https://github.com/Yuki-14544869/
Blog: https://yuki-14544869.github.io/
*/
#include <map>
#include <set>
#include <cmath>
#include <vector>
#include <string>
#include <iostream>

using namespace std;
typedef long long LL;
const int min = 0x3f3f3f3f;
#define mp make_pair
namespace Geometry {
struct Point {
int x, y;
Point() {}
Point(int _x, int _y):x(_x), y(_y) {};

bool operator < (const Point& p) const {
//优先判断横坐标
if(x<p.x || (x==p.x&&y<p.y))
return true;
return false;
}

bool operator == (const Point p) const {
return (x==p.x && y==p.y);
}
};

struct Line {
Point a, b;
double dis;
double k;
Line() {}
Line(Point _a, Point _b):a(_a), b(_b) {
dis = sqrt((_a.x-_b.x)*(_a.x-_b.x) + (_a.y-_b.y)*(_a.y-_b.y));
}
};

struct Vector {
Point a, b;
double dis;
Vector() {}
Vector(Point _a, Point _b):a(_a), b(_b) {
dis = sqrt((_a.x-_b.x)*(_a.x-_b.x) + (_a.y-_b.y)*(_a.y-_b.y));
}
};
}
using namespace Geometry;
bool JudgePoint(Line *l) {
set<Point> p;
for(int i=0; i<4; ++i) {
p.insert(l[i].a);
p.insert(l[i].b);
}
return (p.size() == 4);
}
bool JudgeRect(Line *l) {
for(int i=1; i<4; ++i) {
//判断是否垂直
if((l[0].a.y-l[0].b.y)*(l[i].a.y-l[i].b.y) == -(l[0].a.x-l[0].b.x)*(l[i].a.x-l[i].b.x))
continue;
//判断是否平行
if((l[0].a.y-l[0].b.y)*(l[i].a.x-l[i].b.x) == (l[0].a.x-l[0].b.x)*(l[i].a.y-l[i].b.y))
continue;
return false;
}
return true;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
int T;
cin >> T;
while(T--) {
Line l[4];
int tmp1, tmp2, tmp3, tmp4;
for (int i = 0; i < 4; ++i) {
cin >> l[i].a.x >> l[i].a.y >> l[i].b.x >> l[i].b.y;
}
if(!JudgePoint(l)) {
cout << "NO" << endl;
continue;
} else if(!JudgeRect(l)) {
cout << "NO" << endl;
continue;
} else cout << "YES" << endl;
}
return 0;
}

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
/*
Author: Yuki
GitHub: https://github.com/Yuki-14544869/
Blog: https://yuki-14544869.github.io/
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
int[][] mat = new int[4][4];
while(T-- > 0) {
for(int i=0; i<4; ++i) {
for(int j=0; j<4; ++j) {
mat[i][j] = in.nextInt();
}
}
if(!judgePoint(mat)) {
System.out.println("NO");
continue;
}
if(!judgeRect(mat))
System.out.println("NO");
else System.out.println("YES");
}
in.close();
}

public static boolean judgePoint(int[][] mat) {
List<String> points = new ArrayList<String>();
for(int i=0; i<4; ++i) {
for(int j=0; j<4; j+=2) {
String point = String.valueOf(mat[i][j]) + "," + String.valueOf(mat[i][j+1]);
if(!points.contains(point)) {
points.add(point);
}
}
}
return (points.size() == 4);
}

public static boolean judgeRect(int[][] mat) {
for(int i=1; i<4; ++i) {
//判断是否垂直
if((mat[0][1]-mat[0][3])*(mat[i][1]-mat[i][3]) == -(mat[0][0]-mat[0][2])*(mat[i][0]-mat[i][2])){
continue;
}
//判断是否平行
if((mat[0][1]-mat[0][3])*(mat[i][0]-mat[i][2]) == (mat[0][0]-mat[0][2])*(mat[i][1]-mat[i][3])) {
continue;
}
return false;
}
return true;
}
}