hihocoder35 模板场

Posted by Cww97 on 2017-11-12

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/78514950
ak完这场之后立刻做去年的北京场,然后就卡铜牌题了

连续训练真的有毒,这场还ak了不少人

A 有歧义的号码

按题意模拟

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
 #include <bits/stdc++.h>
using namespace std;
map <int, int> mp;

inline void initmp(){
mp[1] = 1;
mp[2] = 2;
mp[5] = 5;
mp[6] = 9;
mp[8] = 8;
mp[9] = 6;
mp[0] = 0;
}

inline void wtf(int n) {
int x = 1, cnt = 1, ans = 0;
for (int i = 1; i <= n; i++) {
if(i == x * 10) cnt++, x = i;
int p = i, tmp = 0;
bool ok = true;
for(int j = 0; j < cnt; j++, p /= 10) {
if (mp.find(p%10) == mp.end()) {
ok = false; break;
}
tmp = (tmp*10 + mp[p % 10]);
}
if (tmp<=n && ok && tmp!=i && (i%10)>0) {
printf("%d\n", i);
}
}
}
int main(){
initmp();
for (int n; cin >> n;) {
wtf(n);
}
return 0;
}

B 最短游览路线

bfs,起点先不标记vis,bfs到起点return

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
const int INF = 0x3f3f3f3f;

struct Edge{
int from, to, nxt;
Edge(){}
Edge(int f, int t, int n):from(f), to(t), nxt(n){}
}edges[N];
int n, head[N], E;

inline void init(){
E = 0;
memset(head, -1, sizeof head);
}

inline void addEdge(int f, int t){
edges[E] = Edge(f, t, head[f]);
head[f] = E++;
}

bool vis[N];
int dist[N];
inline int bfs(int s){
queue <int> Q;
memset(vis, false, sizeof vis);
memset(dist, 0, sizeof dist);
for (Q.push(s); !Q.empty();){
int u = Q.front(); Q.pop();
//printf("u = %d\n", u);
for (int i = head[u]; ~i; i = edges[i].nxt){
Edge &e = edges[i];
if (vis[e.to]) continue;
dist[e.to] = dist[u] + 1;
//printf("dist[%d] = %d\n", e.to, dist[e.to]);
vis[e.to] = true;
Q.push(e.to);
if (e.to == s) return dist[s];
}
}
return dist[s];
}

int main(){
//freopen("in.txt", "r", stdin);
for (int m; ~scanf("%d%d", &n, &m);){
init();
for (int u, v; m--;){
scanf("%d%d", &u, &v);
addEdge(u, v);
}
int ans = bfs(1);
printf("%d\n", ans);
}
return 0;
}

C 重复字符串匹配

kmp,听说string里的find也能过

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
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 7;
int Next[N];
char A[N], B[N];
int ans = 0;

void getNext(int m, char b[]){
int i = 0,j = -1;
Next[0] = -1;
while (i < m){
if (j == -1 || b[i] == b[j]){
if (b[++i] != b[++j]) Next[i]=j;
else Next[i] = Next[j];
}else j = Next[j];
}
}

//主程序里每组数据需要memset a,b数组!!!
void KMP(int n, char a[], int m, char b[]){
int i = 0, j = 0;
getNext(m, b);//这行视情况可以放在main里面
while (i < n && j < m){
if (j == -1 || a[i] == b[j]) i++, j++;
else j = Next[j];
if (!i && !j)break;
if (j == m){
ans = 1;
j = Next[j];
}
}
}

int main(){
int _;
scanf("%d", &_);
for (; _--;) {
scanf("%s", A);
scanf("%s", B);
int lenA = strlen(A);
int lenB = strlen(B);
int tmp = (lenB - 1) / lenA;
for(int i = 0; i < tmp; i++)
for(int j = 0; j < lenA; j++) A[j + lenA * i] = A[j];
int LenA = lenA * tmp;
ans = 0;
for(int i = 0; i < 3; i++) {
for(int j = 0; j < lenA; j++) A[j + LenA + lenA * i] = A[j];
KMP(LenA+lenA*i+lenA, A, lenB, B);
if(ans == 1) {
printf("%d\n", tmp+i+1);
break;
}
}
if (!ans) puts("-1");
}
return 0;
}

D 缩写命名

二分图,很裸,也没卡匈牙利

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
#include<bits/stdc++.h>
using namespace std;
const int N = 200 + 7;
const int INF = 0x3f3f3f3f;

struct Hungary{
vector <int> G[N];
bool used[N];// main里面记得memset
int girl[N], n;
inline void init(int _n){
n = _n;
for (int i = 0; i <= n; i++) G[i].clear();
}
inline void addEdge(const int &u, const int &v){
G[u].push_back(v);
//printf("addEdge %d %d\n", u, v);
}

bool Find(int x){
for (int i = 0; i < G[x].size(); i++){ //扫描每个妹子
int j = G[x][i];
if (used[j]) continue;
// 如果有暧昧并且还没有标记过
// (这里标记的意思是这次查找曾试图改变过该妹子的归属问题,
// 是没有成功,所以就不用瞎费工夫了)
used[j] = 1;
if (girl[j] == -1 || Find(girl[j])) {
//名花无主或者能腾出个位置来,这里使用递归
girl[j] = x;
return true;
}
}
return false;
}

inline int hungary(const int &n, const int &m){
int all = 0;
memset(girl, -1, sizeof girl);
for (int i = 0; i < n; i++) {
memset(used, 0, sizeof(used)); //这个在每一步中清空
if (Find(i)) all += 1;
}
//for (int i = 0; i < m; i++) printf("girl[%d] = %d\n", i, girl[i]);
//printf("all = %d\n", all);
return all;
}
} hg;

string w[N];

int main(){
//freopen("in.txt", "r", stdin);
int _;
scanf("%d", &_);
string s;
for (int n; _--;){
scanf("%d", &n);
cin >> s;
int len = s.length();
for (int i = 0; i < n; i++) cin >> w[i];
hg.init(len);
for (int i = 0; i <= len; i++){
for (int j = 0; j < n; j++){
if (w[j].find(s[i]) == string::npos) continue;
hg.addEdge(i, j);
}
}
int mat = hg.hungary(len, n);
if (mat >= len) puts("Yes");
else puts("No");
}
return 0;
}