## Problem A: LOL少年

Description

Input

Output

Sample Input
5
VV Killed CC
CC Killed VV
CC Killed SR
R Killed SC
CC Killed TT
CC

Sample Output
3

HINT
1.如果小R被击杀了那么下次计算他的连杀数就要从0开始计算啦！
2.玩家的ID由大小写字母组成长度小于50。

Analysis
map模拟一下就好，注意及时清空

```#include<bits/stdc++.h>
using namespace std;

map<string, int> cnt;
map<string, int> ans;

int main() {
int n;
while(cin >> n) {
cnt.clear(), ans.clear();
while(n--) {
string x, y; cin >> x >> y >> y;
++cnt[x];
ans[x] = max(ans[x], cnt[x]);
ans[y] = max(ans[y], cnt[y]);
cnt[y] = 0;
}
string s; cin >> s;
cout << ans[s] << endl;
}
return 0;
}
```

## Problem D: 哆啦A梦的军队

Description

Input

Output

Sample Input
3
2 3 1
2 1 3
3
2 1 3
3 1 2

Sample Output
YES
NO

Analysis

```#include<bits/stdc++.h>
using namespace std;

#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int maxn = 102400, inf = 0x3f3f3f3f;
int Min[maxn<<2];
int pos[maxn], tot;

void pushUp(int rt) {
Min[rt] = min(Min[rt<<1], Min[rt<<1|1]);
}

void build(int l, int r, int rt) {
if(l == r) {
scanf("%d", &Min[rt]);
pos[Min[rt]] = ++tot;
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushUp(rt);
}

void update(int pos, int x, int l, int r, int rt) {
if(l == r) {
Min[rt] = x;
return;
}
int m = (l + r) >> 1;
if(pos <= m) update(pos, x, lson);
else update(pos, x, rson);
pushUp(rt);
}

int query(int L, int R, int l, int r, int rt) {
if(l >= L && r <= R)
return Min[rt];
int m = (l + r) >> 1;
int ret = inf;
if(L <= m) ret = min(ret, query(L, R, lson));
else ret = min(ret, query(L, r, rson));
return ret;
}

int main() {
int N;
while(~scanf("%d", &N)) {
tot = 0;
build(1, N, 1);
bool ok = true;
for(int i = 1; i <= N; ++i) {
int x; scanf("%d", &x);
if(!ok) continue;
int t = pos[x];
int m = query(1, t, 1, N, 1);
// printf("!!! %d %d %d\n", x, t, m);
if(m < x) ok = false;
update(t, inf, 1, N, 1);
}
if(ok) puts("YES");
else puts("NO");
}
return 0;
}
```

## Problem E: 何时才是我生日

Description

Input

Output

Sample Input
2015 2
2016 2
0 0

Sample Output
2020
2020

Analysis

```#include<bits/stdc++.h>
using namespace std;

bool judge(int x) {
return (x % 400 == 0) || (x % 4 == 0 && x % 100 != 0);
}

int main() {
int y, n;
while(cin >> y >> n, y || n) {
int cnt = 0;
while(true) {
if(judge(y)) ++cnt;
if(cnt >= n) break;
y += 1;
}
cout << y << endl;
}
return 0;
}
```

## Problem F: 恐怖袭击

Description
A国是一个拥有n个城市的大国，B国正密谋对A国发动恐怖袭击，但在此之前需要打探A国的一些情报。于是B国的首脑派遣了s个恐怖分子潜入A国的不同城市，在此之前，B国已经在A国的t个不同的城市设立了情报交换站，用以将情报秘密送往本国。现已知该s个恐怖分子共享情报，他们想用最短的时间将情报送往t个交换站中的任意一个。你能帮他们计算所要走的最短路程吗？
Input

Output

Sample Input
6 1 3 3
4 5 1
1 2 3
4 5 6

6 2 2 4
1 3 3
2 4 4
1 2
3 4 5 6

0 0 0 0

Sample Output
What a pity!
3

Analysis

```#include<bits/stdc++.h>
using namespace std;

const int maxn = 1024, inf = 0x3f3f3f3f;
int cost[maxn][maxn], d[maxn];
bool used[maxn];

int N, M, A, B;
int st[maxn], ed[maxn];

// O(N * N)
void dijkstra(int s) {
memset(d, inf, sizeof(d)); d[s] = 0;
memset(used, false, sizeof(used));
while(true) {
int u = -1;
for(int i = 1; i <= N; ++i)
if(!used[i] && (u == -1 || d[i] < d[u]))
u = i;
if(u == -1) break;
used[u] = true;
for(int i = 1; i <= N; ++i)
d[i] = min(d[i], d[u] + cost[u][i]);
}
}

int main() {
while(scanf("%d%d%d%d", &N, &M, &A, &B), N || M || A || B) {
memset(cost, inf, sizeof(cost));
for(int i = 1; i <= N; ++i)
cost[i][i] = 0;

for(int i = 1; i <= M; ++i) {
int x, y, w; scanf("%d%d%d", &x, &y, &w);
cost[x][y] = min(cost[x][y], w);
cost[y][x] = min(cost[y][x], w);
}
for(int i = 1; i <= A; ++i)
scanf("%d", st + i);
for(int i = 1; i <= B; ++i)
scanf("%d", ed + i);
int best = inf;
for(int i = 1; i <= A; ++i) {
dijkstra(st[i]);
for(int j = 1; j <= B; ++j)
best = min(best, d[ed[j]]);
}
if(best >= inf) puts("What a pity!");
else printf("%d\n", best);
}
return 0;
}
```

## Problem G: LIS

Description

Input

Output

Sample Input
3
2
1 2
4
1 2 4 4
5
1 2 3 4 5

Sample Output
1
2
1

Analysis

```#include<bits/stdc++.h>
using namespace std;

const int maxn = 1024;
int N, v[maxn];
int dp[maxn], mx[maxn];

int main() {
int T; scanf("%d", &T);
while(T--) {
memset(dp, 0, sizeof(dp));
memset(mx, 0, sizeof(mx));
scanf("%d", &N);
for(int i = 1; i <= N; ++i)
scanf("%d", v + i);
dp[1] = 1; mx[1] = 1;
for(int i = 2; i <= N; ++i) {
mx[i] = 1;
for(int j = 1; j < i; ++j) {
if(v[j] >= v[i]) continue;
mx[i] = max(mx[i], mx[j] + 1);
}
if(mx[i] == 1) {
dp[i] = 1;
continue;
}
dp[i] = 0;
for(int j = 1; j < i; ++j) {
if(v[j] >= v[i]) continue;
if(mx[j] + 1 == mx[i])
dp[i] += dp[j];
}
}
int maxlen = *max_element(mx + 1, mx + 1 + N);
int ans = 0;
for(int i = 1; i <= N; ++i)
if(mx[i] == maxlen)
ans += dp[i];
printf("%d\n", ans);
}
return 0;
}
```

## Problem I: 36的奇妙之旅

Description
36是个奇妙的数字.

36 = 1^3 + 2^3 + 3^3，还是前3个自然数的立方和

Input

Output

Sample Input
1
100

Sample Output
360

Analysis

```#include<bits/stdc++.h>
using namespace std;

const int maxn = 102400;
vector<int> v;

bool judge(int x) {
if(x % 36) return false;
char s[15]; sprintf(s, "%d", x);
int len = strlen(s);
bool has = false;
for(int i = 0; i < len-1; ++i) {
if(s[i] == '3' && s[i+1] == '6')
has = true;
}
if(!has) return false;
for(int i = 0; i < len; ++i) {
if(s[i] == '3' && s[i+1] != '6')
return false;
if(s[i] == '6' && (i == 0 || s[i-1] != '3'))
return false;
}
return true;
}

void init() {
for(int i = 1; i < maxn; ++i) {
if(judge(i)) {
v.push_back(i);
}
}
}

int main() {
init();
int T; scanf("%d", &T);
while(T--) {
int x; scanf("%d", &x);
int ans = *lower_bound(v.begin(), v.end(), x);
if(ans > 100000) ans = -1;
printf("%d\n", ans);
}
return 0;
}
```

## Problem K: 摆 箱 子

Description

Input

Output

Sample Input
2
3
0 0 10
5
0 1 2 3 4

Sample Output
2
1

Analysis

```#include<bits/stdc++.h>
using namespace std;

const int maxn = 110, inf = 0x3f3f3f3f;
int N, v[maxn];
int A[maxn], B[maxn];

bool judge(int all) {
memset(A, 0, sizeof(A));
memset(B, inf, sizeof(B));
for(int i = 0; i < N; ++i) {
int cur = i % all;
if(A[cur] >= B[cur])
return false;
++A[cur];
B[cur] = min(B[cur], A[cur] + v[i]);
}
return true;
}

int main() {
int T; scanf("%d", &T);
while(T--) {
scanf("%d", &N);
for(int i = 0; i < N; ++i)
scanf("%d", v + i);
sort(v, v + N, greater<int>());
for(int i = 1; i <= N; ++i) {
if(judge(i)) {
printf("%d\n", i);
break;
}
}
}
return 0;
}
```