这次校赛是组队赛,和LJR WWZ组队。状态比去年要好一点,不过最后比较卡,思路不开阔。一共做了7个题,罚时比别人多了好多,主要是因为中间有道题题意不太清楚坑了好几遍。

Problem A: LOL少年

Description
小R最近喜欢上了LOL,他很想在游戏中记录下来自己的精彩瞬间,但是他一打入迷了就根本记不清自己最多完成了几次连杀,你能写一个程序去帮助他吗?

Input
多组case,每组case第一行包括一个n(0 <= n <= 1000),代表有n组击杀记录。
接下来有n行格式为str1 Killed str2的击杀记录,表示str1玩家击杀了str2玩家。
最后一行为一个字符串str,代表小R的游戏ID。
Output
一个正整数,表示小R最多完成了几次连杀。

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
在2050年机器人战争爆发,聪明的机器猫为了帮助大雄打赢这场战争,从自己口袋里掏出了机器人战棋,每一个战棋都可以成为一名战士,哆啦A梦决定给他们整整队,哆啦A梦发现第 i 个位置的战士编号为 Ai(显然 A 是一个排列)。经过计算,哆啦A梦发现,让第 i 个位置的战士编号为 Bi 时,他的军队可以发挥出最大的战斗力(保证 B 也是一个排列)。
哆啦A梦可以发出指令来改变战士们的排列顺序,每一次,他都会报出一个整数 i(1≤i<n)。如果排在第 i 个位置的战士编号大于第 i+1 个位置的战士,那么这两个战士会交换顺序,否则这一个命令将会被忽略。
现在哆啦A梦希望他的军队能够发挥出最强大的战斗力,于是他想要知道是否存在一种指令序列,使得战士们可以按照排列 B 的方式排列。
但是因为战士数目实在是太多,哆啦A梦一时间也没有看出答案。于是他用时间机器带来了你——21世纪最著名的民间科学家来帮他计算这个问题的答案。

Input
输入数据第一行包含一个正整数 n(n<=100000)。
接下来两行每行 n 个正整数,分别描述排列 A和排列 B。

Output
对于每组数据,如果存在这样的指令序列,输出“YES”,否则输出“NO”(引号不输出,请注意大小写)。

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

Sample Output
YES
NO

Analysis
看第数列B,从左边到右边,找到第一个数在A数列中的位置,则A中这个位置左边不能有比他小的数,这个数不可能再最前面。然后把A中这个数设置成inf,继续在B中按照同样方法判断下去。
需要用到区间查询最小值和修改点,用线段树就好了。

#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
你的朋友是闰年2月29日出生,他想知道接下来的第i个生日是什么时候,请你帮他计算他该在哪一年举办生日聚会。

Input
输入包含多组样例,每组样例都由一个年份y和一个n组成(0<y<10000,0<n<100),输入由两个0结束。
Output
每组样例输出只包含一个整数,代表从y年开始的第n个生日在哪一年举办。

Sample Input
2015 2
2016 2
0 0

Sample Output
2020
2020

Analysis
从第y年开始找到第n个闰年,循环判断一下就好。注意不是单纯+4。

#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
输入包含多组样例,每组样例首先包含四个正整数,城市的数量n(0<n<1000),城市中无向道路的条数m(0<m<1000000),恐怖分子的数量s(0<s<10),情报交换站的数量t(0<t<10),接下来会有m行,每行三个正整数,前两个为城市的标号u、v(1<=u,v<=n && u != v),第三个为他们之间的距离d(0<d<100)。相邻两城市之间可能有多条道路。接下来一行有s个正整数,代表当前恐怖分子所藏匿的城市标号,紧接着一行有t个正整数,代表情报交换站所在的城市标号。注意在s和t中出现的城市标号不重叠。输入以0 0 0 0结束

Output
如果恐怖分子可以将情报送出,输出要走的最短路程。否则,输出”What a pity!”(不包含引号)

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
图论基础题,求10次最短路。由于边太多了,所以要用没有堆优化的dijkstra,复杂度为O(N*N).

#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
给定一个长度为n的序列(n <= 1000) ,记该序列LIS(最长上升子序列)的长度为m,求该序列中有多少位置不相同的长度为m的严格上升子序列。

Input
先输入一个T,表明下面会有几组数据。
每组数据先输入一个n,表明数组大小。
下面一行有n个数代表该数组,且 1<=a[i]<=n;

Output
输出为一行,只需输出上述要求的个数(输出保证结果小于2^31)。

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

Sample Output
1
2
1

Analysis
动态规划,在求最长上升子序列的基础上,加个数组,表示最长上升子序列的个数,随dp一起计算就好。

#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 + 5 + 7)+(2 + 4 + 6 + 8),前4个奇数与前4个偶数的和。
36 = 1^3 + 2^3 + 3^3,还是前3个自然数的立方和
同样,我国军事家孙子大大还有《三十六计》
人能承受的安全电压是36V!! 神奇!
有这么多的36的性质,GMC自然也想到了一个问题,在区间[L,10^5]中第一个和36相关的数是谁呢?我们给“和36相关”一个定义:对于一个数字,如果他其中包含36,并且3的右边一定包含6,6的左边一定包含3,并且能整除36,那么我们就称这个数字为与36相关。如:36036是与36相关的,63036不相关。
现在GMC很想知道[L,10^5]之间第一个与36相关的数是多少,你能帮我一下吗。

Input
第一行是测试样例数T(1<=T<=10^5)
接下来T行每行包括1个正整数L(1<=L<=10^5),表示GMC想知道的询问区间为[L,10^5]

Output
输出包含T行,每行对应一个询问,包含在区间[L,10^5]中第一个与“36相关的数”,如果找不到,输出“-1”

Sample Input
1
100

Sample Output
360

Analysis
打表然后查找即可。题意有坑,“3的右边一定包含6”的意思是“3右边的数一定是3”…

#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
有一堆形状完全一样的箱子,但是他们的强度不同,如果一个箱子的强度为x,那么这个箱子上面最多可以放x个箱子。
现在我们已知一堆箱子的强度,我们想把这些箱子放置成一列一列的形状,每一列包含多个箱子,问最少可以放多少列。

Input
输入为多组数据,第一行为样例数T
每组数据先输入一个n(1<=n<=100),表示箱子的总数
紧接着输入n个数x1,x2,x3…xn(0<=xi<=100),第i个数表示第i个箱子的强度

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

欢迎留言