山东省第六届ACM大学生程序设计竞赛解题报告【9/12】

发表于 | 更新于 | 分类于
－－－－－－－－－－－山东省第六届ACM大学生程序设计竞赛解题报告－－－－－－－－－－ －

A.Nias and Tug-of-War【签到】

题意：给出$n$个人的身高和体重，按身高从低到高排序后从前往后轮流报数(1,2,1,2…)，报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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int t, n;
struct node
{
    double h, w;
} a[111];
bool cmp(node u, node v)
{
    return u.h < v.h;
}
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        double sum = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%lf%lf", &a[i].h, &a[i].w);
        sort(a, a + n, cmp);
        for(int i = 0; i < n; ++i)
        {
            if(i & 1)
                sum += a[i].w;
            else
                sum -= a[i].w;
        }
        if(sum == 0)
            puts("fair");
        else
            puts(sum > 0 ? "blue" : "red");
    }
    return 0;
}

B.Lowest Unique Price【线段树】

题意：对一个集合进行三种操作。b x向集合中添加一个$x$，c x将集合中的$x$删掉一个，q查询集合中只出现一次的最小值。

思路：

踩坑：建树及更新时应建最大的值的树而非$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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000020;
int sum[maxn], c[maxn * 4];
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int no = 1000005;
void build(int l, int r, int rt) {
	c[rt] = no;
	if (l == r) {
		sum[l] = 0;
		return;
	}
	int m = (l + r) >> 1;
	build(lson);
	build(rson);
}
void pushup(int rt) {
	c[rt] = min(c[rt << 1], c[rt << 1 | 1]);
}
void update(int l, int r, int rt, int x,int y) {
	if (l == r) {
		sum[l] += y;
		if (sum[l] == 1)
			c[rt] = l;
		else
			c[rt] = no;
		return;
	}
	int m = (l + r) >> 1;
	if (x <= m)
		update(lson, x, y);
	else
		update(rson, x, y);
	pushup(rt);
}
int main() {
	int te;
	ios::sync_with_stdio(0);
	cin >> te;
	while (te--) {
		int n;
		cin >> n;
		build(1, no, 1);
		for(int i=0;i<n;i++) {
			char a; int b;
			cin >> a;
			if (a == 'b') {
				cin >> b;
				update(1, no, 1, b, 1);
			}
			else if (a == 'c') {
				cin >> b;
				update(1, no, 1, b, -1);
			}
			else {
				int t = c[1];
				if (t == no)
					cout << "none\n";
				else
					cout << t << "\n";
			}
		}
	}
	return  0;
}

C.Game!【博弈】

题意：$n$个石子围成一圈，每次每个玩家可以取走任意一个石子或者相邻的两个石子，问谁会赢。

思路：$n \leq 2$时先手可一次全部取走，其余情况后手都可以通过“模仿”操作控制局面从而得以取胜。

同一个题目：POJ 2484

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

int t;
long long n;
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld", &n);
        puts(n > 2 ? "blankcqk" : "zbybr");
    }
    return 0;
}

D.Stars

题意：有$n$个星星在空中，每个星星的坐标$(x, y)$都是独一无二的，现在要你选择一个矩形区域使得矩形的边长为整数且边分别平行于$x$轴或$y$轴，问覆盖至少$k$个星星的时候最小的矩形面积是多少，星星恰好在矩形的边长上的时候不计入总数。

思路：根据题意可想到：若矩形边上的点计入总数的话，此矩形的实际面积就是$(h + 1) \times (w + 1)$。赛中有个想法是二分长和宽+枚举起点坐标，但是需要二维树状数组维护一下，觉得有些麻烦就没写。

1
2


E.BIGZHUGOD and His Friends I

题意：现在有一副不完整的扑克牌，$A$的面值为$1$，$2$ ~ $10$的面值为$2$ ~ $10$，$J$、$Q$、$K$、小王、大王的面值都为$10$。游戏规则为每次从牌中随机抽$5$张，将这$5$张分为两组，一组两张，一组三张。问两组的和都是$10$的倍数的概率是多少。

思路：DP？

1
2


F.BIGZHUGOD and His Friends II【数学】【塞瓦定理】

题意：$123$初始分别在$\triangle ABC$的$ABC$三顶点处，他们以相同的速度分别向$BCA$移动，问是否存在这么一个时刻使得$1C$、$2A$、$3B$交于一条直线。

思路：有个神奇的数学定理叫做塞瓦定理，运用这个定理，此问题轻易解决。

假设在$t$时刻达到题目所说要求，则有$\frac{a-x}{t} \times \frac{b-x}{t} \times \frac{c-x}{t} = 1$，对于此式子左边，若$t$增大，则整体是减小的，反之亦然。因此我们只需要不断比较他和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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps = 1e-8;

int t;
double a, b, c, res;
bool check(double x)
{
    return (a - x) * (b - x) * (c - x) >= x * x * x;
}
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lf%lf%lf", &a,&b,&c);
        double l = 0.0, r = min(a, min(b, c)), m;
        while(r - l > eps)
        {
            m = (l + r) / 2.0;
            if(check(m))
                l = m;
            else
                r = m;
        }
        printf("YES %.4f\n", l);
    }
    return 0;
}

G.Cube Number【数学】

题意：给出一个包含不同数字的集合，求可以从这里面挑出多少对数字使得它们的乘积为立方数。

思路：

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

typedef long long ll;

const int maxn = 1000050;

int n, m;
int ar[maxn];
int br[maxn];
int cr[maxn];

int cnt;
int pri[maxn];
bool is[maxn];

void init () {
    is[0] = is[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (is[i] == 0) {
            pri[++cnt] = i;
        }
        for (int j = 1; j <= cnt && 1ll*i*pri[j] < maxn; ++j) {
            is[i*pri[j]] = 1;
            if (i % pri[j] == 0) {
                break;
            }
        }
    }
}

int main () {
    int t;
    init();
    scanf("%d", &t);
    while (t--) {
        m = 0;
        memset(ar, 0, sizeof(ar));
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            int v;
            scanf("%d", &v);
            ll tmp = 1, ttmp = 1;
            for (int j = 1; j <= cnt && 1ll*pri[j]*pri[j] <= v; ++j) {
                if (v % pri[j] == 0) {
                    int k = 0;
                    while (v % pri[j] == 0) {
                        v /= pri[j];
                        ++k;
                    }
                    k %= 3;
                    if (k == 1) {
                        tmp *= 1ll*pri[j];
                        ttmp *= 1ll*pri[j]*pri[j];
                    }
                    else if (k == 2) {
                        tmp *= 1ll*pri[j]*pri[j];
                        ttmp *= 1ll*pri[j];
                    }
                }
            }
            if (v != 1) {
                tmp *= 1ll*v;
                ttmp *= 1ll*v*v;
            }
            if (tmp >= 1ll*maxn || ttmp >= 1ll*maxn) {
                continue;
            }
            if (ar[tmp] == 0) {
                br[++m] = tmp;
                cr[m] = ttmp;
            }
            ++ar[tmp];
        }
        ll res1 = 0, res2 = 0;
        for (int i = 1; i <= m; ++i) {
            if (br[i] == cr[i]) 
                res1 += 1ll*ar[br[i]]*(ar[br[i]]-1)/2;
            else 
                res2 += 1ll*ar[br[i]]*ar[cr[i]];
        }
        cout << res1+res2/2 << '\n';
    }
    return 0;
}

H.Square Number【数学】

题意：给出一个包含不同数字的集合，求可以从这里面挑出多少对数字使得它们的乘积为平方数。

思路：

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

typedef long long ll;

const int maxn = 1000050;

int n, m;
int ar[maxn];
int br[maxn];
int cr[maxn];

int cnt;
int pri[maxn];
bool is[maxn];

void init () {
    is[0] = is[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (is[i] == 0) {
            pri[++cnt] = i;
        }
        for (int j = 1; j <= cnt && 1ll*i*pri[j] < maxn; ++j) {
            is[i*pri[j]] = 1;
            if (i % pri[j] == 0) {
                break;
            }
        }
    }
}

int main () {
    int t;
    init();
    scanf("%d", &t);
    while (t--) {
        m = 0;
        memset(ar, 0, sizeof(ar));
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            int v;
            scanf("%d", &v);
            ll tmp = 1;
            for (int j = 1; j <= cnt && 1ll*pri[j]*pri[j] <= v; ++j) {
                if (v % pri[j] == 0) {
                    int k = 0;
                    while (v % pri[j] == 0) {
                        v /= pri[j];
                        ++k;
                    }
                    k %= 2;
                    if (k == 1) {
                        tmp *= 1ll*pri[j];
                    }
                }
            }
            if (v != 1) {
                tmp *= 1ll*v;
            }
            if (tmp >= 1ll*maxn) {
                continue;
            }
            if (ar[tmp] == 0) {
                br[++m] = tmp;
            }
            ++ar[tmp];
        }
        ll res1 = 0;
        for (int i = 1; i <= m; ++i)
            res1 += 1ll*ar[br[i]]*(ar[br[i]]-1)/2;
        cout << res1<< '\n';
    }
    return 0;
}

I.Routing Table【字典树】

题意：给出一个路由表，表中包含$n$条传输路径，每条此传输路径包括$ip$地址，子网掩码的位数以及端口号。给出$m$个目标$ip$地址，问他们最适合传输的路径的端口号是多少。判断标准为：先看网络号，网络号相同的直接传输；如果有多个网络号可以匹配则传输子网掩码位数最长的那个；如果依旧相同则传输端口号最小的那个。否则使用默认端口号65535。

思路：网络号为$ip$地址与子网掩码进行AND运算得出的结果，子网掩码位数的意思的32位的子网掩码从前往后数有多少位为1。算出这个后就是将$m$个目标$ip$地址匹配的问题了，这里的匹配类似于字符串的匹配，建好字典树直接查就可以了。

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

string tem;
int b[] = {128,64,32,16,8,4,2,1};
int t, n, m, pro, a[5];
void getTEM()
{
    tem.clear();
    for(int i = 0; i < 4; ++i)
    {
        for(int j = 0; j < 8; ++j)
        {
            if(a[i] & b[j])
                tem.push_back('1');
            else
                tem.push_back('0');
        }
    }
}
struct Trie
{
    int nex[N * 32][2], tot;
    int pre[N * 32];
    void init()
    {
        tot = 1;
        memset(nex, 0, sizeof(nex));
        memset(pre, -1, sizeof(pre));
    }
    void add()
    {
        int now = 1;
        getTEM();
        int dep = min((int)tem.size(), a[4]);
        for(int i = 0; i < dep; ++i)
        {
            if(nex[now][tem[i] - '0'] == 0)
                nex[now][tem[i] - '0'] = ++tot;
            now = nex[now][tem[i] - '0'];
        }
        if(pre[now] == -1)
            pre[now] = pro;
        else
            pre[now] = min(pre[now], pro);
    }
    int query()
    {
        int now = 1, res = -1;
        getTEM();
        for(int i = 0; i < 32; ++i)
        {
            if(pre[now] != -1)
                res = pre[now];
            if(nex[now][tem[i] - '0'] == 0)
                break;
            else
                now = nex[now][tem[i] - '0'];
        }
        if(res == -1)   res = 65535;
        return res;
    }
} trie;

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        trie.init();
        scanf("%d%d", &n,&m);
        for(int o = 1; o <= n; ++o)
        {
            scanf("%d.%d.%d.%d/%d %d",&a[0],&a[1],&a[2],&a[3],&a[4], &pro);
            trie.add();
        }
        for(int o = 1; o <= m; ++o)
        {
            scanf("%d.%d.%d.%d",&a[0],&a[1],&a[2],&a[3]);
            printf("%d\n", trie.query());
        }
    }
    return 0;
}

J.Single Round Math【大数】

题意：给出两个数$n$、$m$，问它们是否相等且都是$11$的倍数。

思路：开上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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 10010;

bool flag;
int t, len, sum;
char a[N], s[N];
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        flag = 1;
        scanf("%s%s", a, s);
        if(strcmp(a, s))
            flag = 0;
        else
        {
            sum = 0;
            len = strlen(s);
            for(int i = 0; i < len; ++i)
            {
                sum = sum * 10 + s[i] - '0';
                sum %= 11;
            }
            if(sum)
                flag = 0;
        }
        puts(flag ? "YES" : "NO");
    }
    return 0;
}

K.Last Hit

题意：$n$个小兵在塔下，塔会按照从$1$ ~ $n$的顺序挨个攻击每个小兵，每次给单个小兵造成$x$点伤害。你每次可选择任意一个小兵进行攻击并且对它造成$y$点伤害。当你攻击完小兵后，小兵的$HP \leq 0$你就补刀成功一次，塔先攻击然后再你选择攻击或不攻击，问你最多补多少兵。

思路：？？？

1
2


L.Circle of Friends【强连通分量】【缩点】

题意：先说一下朋友圈的定义：A认为和B是朋友，B也认为A是朋友，那他们就是真正的朋友，这是A和B互相帮助是不需要请吃饭的；A认为和B是朋友，B认为和C是朋友，C认为和A是朋友，那么他们仨之间也是真正的朋友。A认为和B是朋友，而B不认为和A是朋友，那么A向B寻求帮助是要请B吃饭的。

现在给出$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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const int maxm = 100005;
const int inf = 0x3f3f3f3f;
struct fuck {
	int u, v, ne;
}ed[maxm];
int head[maxn], cnt;
int low[maxn], dfn[maxn], Stack[maxn], belong[maxn];
int kkdex, top; int scc;
bool instack[maxn]; int sum[maxn];
void add(int u, int v) {
	ed[cnt].v = v; ed[cnt].ne = head[u]; ed[cnt].u = u;
	head[u] = cnt++;
}
void tarjan(int u) {
	int v;
	low[u] = dfn[u] = ++kkdex;
	Stack[top++] = u;
	instack[u] = 1;
	for (int i = head[u]; ~i; i = ed[i].ne) {
		v = ed[i].v;
		if (!dfn[v]) {
			tarjan(v);
			if (low[u] > low[v])low[u] = low[v];
		}
		else if (instack[v] && low[u] > dfn[v]) {
			low[u] = dfn[v];
		}
	}
	if (low[u] == dfn[u]) {
		scc++;
		do {
			v = Stack[--top];
			instack[v] = 0;
			belong[v] = scc;
			sum[scc]++;
		} while (v != u);
	}
}
void solve(int n) {
	for (int i = 0; i < n; i++) {
		dfn[i] = 0;
		instack[i] = 0;
		sum[i] = 0;
	}
	kkdex = scc = top = 0;
	for (int i = 0; i < n; i++) {
		if (!dfn[i])
			tarjan(i);
	}
}
void init() {
	cnt = 0;
	memset(head, -1, sizeof head);
}
vector<int>G[maxn];
int dis[maxn];
int bfs(int x, int y) {
	queue<int>q;
	q.push(x);
	dis[x] = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
	//	cout << "go: " << u << endl;
		if (u == y)return dis[u];
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i];
			if (dis[v] > dis[u] + 1) {
				dis[v] = dis[u] + 1;
				q.push(v);
			}
		}
	}
	return -1;
}
int main() {
	int te;
	scanf("%d", &te);
	while (te--) {
		init();
		int n, m;
		scanf("%d%d", &n, &m);
		while (m--) {
			int a, b;
			scanf("%d%d", &a, &b);
			add(a, b);
		}
		solve(n);
		for (int i = 0; i <= scc; i++)
			G[i].clear(), dis[i] = inf;
		for (int i = 0; i < cnt; i ++) {
			int v = ed[i].v; int u = ed[i].u;
			if (belong[u] != belong[v]) {
				G[belong[u]].push_back(belong[v]);
			//	cout << belong[u] << " ? " << belong[v] << endl;
			}
		}
		cout << bfs(belong[0], belong[n - 1]) << endl;
	}
	return 0;
}
Donate comment here
0%