2019 SDNU ACM-ICPC Provincial Team Selection Round 2【完结】

发表于 | 更新于 | 分类于
－－－－－－－－－－山东省第十届acm大学程序设计竞赛山师选拔赛第二场－－－－－－－－－－

A - Arc of Dream【矩阵快速幂】

题意：给出表达式，求第$n$项的值是多少。

思路：矩阵快速幂，注意特判$n = 0$和$n = 1$的情况。

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
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long ll;

const ll mod = 1e9+7;

const int maxn = 6;

struct Matrix {
    ll mp[maxn][maxn];
};

Matrix E, O;

Matrix matrix_multi (Matrix A, Matrix B, int a, int b, int c) {
    Matrix tmp = O;
    for (int i = 1; i <= a; ++i) {
        for (int j = 1; j <= c; ++j) {
            for (int k = 1; k <= b; ++k) {
                tmp.mp[i][j] += A.mp[i][k]*B.mp[k][j]%mod;
                tmp.mp[i][j] %= mod;
            }
        }
    }
    return tmp;
}

Matrix matrix_qm (Matrix A, ll b, int dr) {
    Matrix ans = E;
    while (b) {
        if (b&1) {
            ans = matrix_multi(ans, A, dr, dr, dr);
        }
        b >>= 1;
        A = matrix_multi(A, A, dr, dr, dr);
    }
    return ans;
}

void init () {
    memset(E.mp, 0, sizeof(E.mp));
    memset(O.mp, 0, sizeof(O.mp));
    for (int i = 1; i <= 5; ++i) {
        E.mp[i][i] = 1;
    }
}

int main () {
    init();
    ll n, a0, ax, ay, b0, bx, by;
    while (scanf("%lld %lld %lld %lld %lld %lld %lld", &n, &a0, &ax, &ay, &b0, &bx, &by) != EOF) {
        Matrix T = O;
        T.mp[1][1] = 1, T.mp[1][2] = 1;
        T.mp[2][2] = ax*bx%mod, T.mp[2][3] = ax*by%mod, T.mp[2][4] = ay*bx%mod, T.mp[2][5] = ay*by%mod;
        T.mp[3][3] = ax%mod, T.mp[3][5] = ay%mod;
        T.mp[4][4] = bx%mod, T.mp[4][5] = by%mod;
        T.mp[5][5] = 1;
        if (n == 0) {
            cout << 0 << '\n';
            continue;
        }
        else if (n == 1) {
            cout << a0*b0%mod << '\n';
            continue;
        }
        else {
            Matrix A = O;
            A.mp[1][1] = 0, A.mp[2][1] = a0*b0%mod, A.mp[3][1] = a0%mod, A.mp[4][1] = b0%mod, A.mp[5][1] = 1;
            T = matrix_qm(T, n, 5);
            A = matrix_multi(T, A, 5, 5, 1);
            cout << A.mp[1][1]%mod << '\n';
        }
    }
    return 0;
}

B - Bear and Friendship Condition【并查集||DFS】

https://alberts97.github.io/cf-771a/

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int MAX = 150010;

bool vis[MAX];
int n, m, x, y;
vector<int> G[MAX];

void DFS(int t, int & v, int & e)
{
    vis[t] = true;
    ++v;
    e += G[t].size();
    for(int i = 0; i < G[t].size(); ++i)
        if(!vis[G[t][i]])
            DFS(G[t][i], v, e);
}

int main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i)
    {
        if(!vis[i])
        {
            int e = 0, v = 0;
            DFS(i, v, e);
            if(e != 1ll * v * (v - 1))
            {
                puts("NO");
                return 0;
            }
        }
    }
    puts("YES");
    return 0;
}

C - Code shortening【字典树】【启发式合并】

https://alberts97.github.io/cf-965e/

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
const int MAX = 1e5 + 5;

char str[MAX];
multiset<int> st[MAX];
int n, tot, now, nex[MAX][26], dep[MAX], res;
void add()
{
    now = 1;
    for(int i = 0; str[i]; ++i)
    {
        if(!nex[now][str[i]-'a'])
        {
            nex[now][str[i]-'a'] = ++tot;
            dep[tot] = dep[now] + 1;
        }
        now = nex[now][str[i]-'a'];
    }
    st[now].insert(dep[now]);
}
void DFS(int u = 1)
{
    bool emp = (u > 1 && st[u].empty());
    for(int i = 0; i < 26; ++i)
    {
        int v = nex[u][i];
        if(!v)  continue;
        DFS(v);
        for(auto t : st[v])
            st[u].insert(t);
        st[v].clear();
    }
    if(emp)
    {
        st[u].erase(--st[u].end());
        st[u].insert(dep[u]);
    }
}
int main()
{
    tot = 1;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%s", str);
        add();
    }
    DFS();
    for(auto t : st[1])
        res += t;
    printf("%d\n", res);
    return 0;
}

D - Design a navigation【签到】

题意：告诉你一个数字显示的方法，要求输出按这个方法显示的情况。

思路：直接写就可以，但很容易写复杂了，下面是比较简洁的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int n, p, k;
int main()
{
    scanf("%d%d%d", &n, &p, &k);
    if(p - k > 1) printf("<< ");
	for(int i = p - k; i <= p + k; i++) if(1 <= i && i <= n) printf((i == p) ? "(%d) " : "%d ", i);
	if(p + k < n) printf(">> ");
    return 0;
}

E - Excting Secret Chamber at Mount Rushmore【Floyd】

题意：给出$n$组字母，每组有两个，意味着前者可以转化为后者。在转化过程中遵循传递性，即如果$a$可以转换为$b$，$b$可以转化为$c$，那么$a$也可以转换为$c$。 给出$m$组单词，问前者是否可以通过若干次转换转换为后者。

思路：只有$26$个字母，可以直接Floyd判断单词间是否联通。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 26;

bool a[N][N];
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < N; ++i) a[i][i] = true;

    char aa, bb;
    for(int i = 0; i < n; ++i)
    {
        cin >> aa >> bb;
        a[aa-'a'][bb-'a'] = true;
    }

    for(int k = 0; k < N; ++k)
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < N; ++j)
                a[i][j] |= a[i][k] & a[k][j];

    string s, l;
    for(int i = 0; i < m; ++i)
    {
        cin >> s >> l;
        bool flag = s.length()==l.length();
        if(flag)
        {
            for(int j = 0; j < s.length(); ++j)
                if(!a[s[j]-'a'][l[j]-'a'])
                {
                    flag = false;
                    break;
                }
        }
        puts(flag ? "yes" : "no");
    }
    return 0;
}

F - From Y to Y【构造】

两年前做的，具体什么操作记不清了。不过两年前能做出来说明不难。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

int n, tot, t;
string ans = "";
char ss[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q'};
int main()
{
    while(cin >> n)
    {
        ans = "";
        int now = 16;
        for(int i = 0; i < now; ++i)
        {
            ans.push_back(ss[i]);
            tot = t = 1;
            while(tot <= n)
            {
                ans.push_back(ss[i]);
                t++;
                tot = t*(t+1)/2;
            }
            n -= (t-1)*t/2;
        }
        cout << ans << endl;
    }
    return 0;
}

G - Godsend【规律】

两年前做的，具体什么操作记不清了。不过两年前能做出来说明不难。

PS：这一题卡了cin。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int n, t;
bool flag;
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&t);
        if(t & 1)   flag = true;
    }
    puts(flag ? "First" : "Second");
    return 0;
}

H - How to do that【数据结构】

题意：有两种操作，一是将某个数字加入栈中(add$x$)，另一种是取栈顶数字(remove`)，要求取出的数字的顺序按照$1$ ~ $n$的顺序，给你一系列操作，你可以在任何一次操作之后将栈内的数字重排，问你最少重排多少次。

思路：重排可以理解为将栈内元素全部按照顺序排好，这个操作不需要直接模拟，直接清空栈内元素就可以。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
using namespace std;

char op[11];
stack<int> st;
int n, x, now, res;
int main()
{
    now = 1;
    scanf("%d",&n);
    for(int i = 1; i <= 2 * n; ++i)
    {
        scanf("%s", op);
        if(op[0] == 'a')
        {
            scanf("%d", &x);
            st.push(x);
        }
        else
        {
            if(!st.empty())
            {
                if(st.top() == now)
                    st.pop();
                else
                {
                    while(!st.empty())
                        st.pop();
                    ++res;
                }
            }
            ++now;
        }
    }
    printf("%d\n", res);
    return 0;
}

I - Interesting Yang Hui Triangle【Lucas定理应用】

题意：杨辉三角第$n$行的$n+1$个数有多少个数可以被$p$整除。

思路：Lucas定理的应用，自己搜一下。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long ll;

const int maxn = 1e5+5;

ll p, n;

int main () {
    int cas = 0;
    while (scanf("%lld %lld", &p, &n) != EOF && p+n) {
        ll ans = 1;
        while (n) {
            ans = ans*(n%p+1)%10000;
            n /= p;
        }
        printf("Case %d: %04lld\n", ++cas, ans);
    }
    return 0;
}

J - Judge Fake or Leak【模拟】

题意：模拟ICPC规则下封榜后队伍排名变化情况，即给出封榜前的和封榜后的排名，判断是否合法。

思路：因为答案非Fake即Leak，所以我们采用交随机数的方法。模拟。

K - King_jy and Cities【最短路】

题意：$n$个城市，$m$条双向路和$k$条单向路，问$k$条单向路中有多少条是可以关闭后不影响从$1$到其余$n - 1$个城市的最短长度的。

思路：建图统计。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200005;
const int maxm = 1000005;
const long long inf = 0x3f3f3f3f3f3f3f3f;
struct edge {
	int u, v, w, ne, hc;
}ed[maxm];
int head[maxn], cnt, tot; long long dis[maxn], sum;
int vis[maxn], times[maxn]; int change[maxn], id[maxn];
int n, m;
void init() {
	cnt = 0;
	for (int i = 0; i <= n; i++) {
		dis[i] = inf, times[i] = 0, vis[i] = 0, head[i] = -1, change[i] = 0;
	}
}
void addedge(int u, int v, int w, int t) {
	ed[cnt].u = u; ed[cnt].v = v; ed[cnt].w = w; ed[cnt].hc = t;
	ed[cnt].ne = head[u]; head[u] = cnt++;
}
struct cmp {
	bool operator()(int a, int b) {
		return dis[a] > dis[b];
	}
};
bool spfa(int st) {
	priority_queue<int, vector<int>, cmp>q;
	dis[st] = 0; vis[st] = 1;
	q.push(st);
	while (!q.empty()) {
		int u = q.top();
		q.pop();
		vis[u] = 0;
		for (int i = head[u]; ~i; i = ed[i].ne) {
			int v = ed[i].v;
			if (dis[v] > dis[u] + ed[i].w || (dis[v] == dis[u] + ed[i].w&&change[v] == 1)) {
				dis[v] = dis[u] + ed[i].w;
				change[v] = ed[i].hc;
				if (!vis[v]) {
					vis[v] = 1;
					q.push(v);
					if (++times[v] > n) {
						return 0;
					}
				}
			}
		}
	}
	return 1;
}
int main() {
	int k;
	ios::sync_with_stdio(0);
	while (cin >> n >> m >> k) {
		init();
		while (m--) {
			int a, b, c;
			cin >> a >> b >> c;
			addedge(a, b, c, 0);
			addedge(b, a, c, 0);
		}
		int ans = 0;
		for (int i = 0; i < k; i++) {
			int a, b; cin >> a >> b;
			addedge(1, a, b, 1);
		}
		spfa(1);
		for (int i = 2; i <= n; i++) {
			if (change[i] == 1) {
				ans++;
			}
		}
		cout << k - ans << "\n";
	}
	return 0;
}

L - Lucky Numbers【签到】

题意：幸运数字定义为只包含7和8的数字，求不超过$n$位数的幸运数字的个数。

思路：写一下就发现是$\sum_1^{n} 2^i$。

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
#include <iostream>
#include <cstring>
using namespace std;

typedef long long ll;

const int maxn = 56;

ll C[maxn][maxn];
ll ans[maxn];

void init () {
    C[0][0] = C[1][0] = C[1][1] = 1;
    for (int i = 2; i < maxn; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j) {
            C[i][j] = C[i-1][j-1]+C[i-1][j];
        }
    }
    ans[1] = 2;
    for (int i = 2; i < maxn; ++i) {
        for (int j = i; j >= 0; --j) {
            ans[i] += C[i][j];
        }
    }
    for (int i = 1; i < maxn; ++i) {
        ans[i] += ans[i-1];
    }
}

int main () {
    init();
    int n;
    scanf("%d", &n);
    cout << ans[n] << '\n';
    return 0;
}
Donate comment here
0%