2018_SDNU_ACM-ICPC_Provincial_Team_Selection_Round_1【假装完结】

发表于 | 更新于 | 分类于

山东省第九届acm大学程序设计竞赛山师选拔赛第一场

(声明：标题是自己取的，如果有语法错误的话与他人无关)

—————————————————————–分割线—————————————————————–

A.网瘾少年周老灰(贪心)

题意：
周老灰玩炉石，场上目前有2 * n张牌，敌我各n张。
发动进攻的方式是每张牌只能攻击一张牌，进攻完成后，敌方士兵生命值减少我方进攻士兵的攻击力，我方士兵生命值也要减少敌方进攻士兵的攻击力，当生命之小于等于0时，这张卡牌将消失。
现在轮到我方发动进攻，问能否使得我方这一轮进行完后地方卡牌都被摧毁，而我方卡牌还都存活。

思路：
考虑到数据范围，直接做就行了(数据范围再大点的话就是二分图匹配了)。每次贪心选取我方能打败的敌方选手中攻击力最高的，一直这样选直到全部选完||打败不了的情况。

碎碎念：
数据出的太不负责了，出现了范围以外的数就不说了，TM除了一个本不该存在的n=0时输出Sorry about that!外，其他情况都输出Tell you a joke~？这种题目全随机数出现前一个答案的概率太小了，就不能手动出几组吗(没错我是因为他这个本不该出现的n=0浪费了近3小时的时间debug才如此气愤的)。
UPD(04.18)：等了一周后还没改，自己出了几组随机数和手动出的数据传上去后rejudge，果然hack掉了几个。

Mycode：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 105;

int t, n;
struct node
{
    bool flag;
    int hp, mp;
}a[MAX], b[MAX];

bool cmp(node u, node v)
{
    if(u.hp == v.hp)
        return u.mp < v.mp;
    return u.hp < v.hp;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        bool flag;
        memset(b, 0, sizeof(b));
        for(int i = 0; i < n; ++i)
            scanf("%d%d",&a[i].hp,&a[i].mp);
        for(int i = 0; i < n; ++i)
            scanf("%d%d",&b[i].hp,&b[i].mp);
        sort(a, a+n, cmp);
        sort(b, b+n, cmp);
        for(int i = 0; i < n; ++i)
        {
            flag = false;
            for(int j = n-1; j >= 0; --j)
            {
                if(b[j].flag == false && a[i].hp > b[j].mp && a[i].mp >= b[j].hp)
                {
                    flag = true;
                    b[j].flag = true;
                    break;
                }
            }
            if(!flag)   break;
        }
        if(flag)
            puts("Sorry about that!");
        else
            puts("Tell you a joke~");
    }
    return 0;
}

B.陆历川玩数位(数位DP)

题目原型：
HDU-4734: F(x)

队友补过了，目前不想补。

C.prime(素数筛)

题意：
给一个数n问n是否是素数，0 < n < 100000000。

思路：
据说出题人本打算考察位图筛的，但没想到数组可以开到1e8这么大，于是让大家用素数筛水过去了。队友说素数筛会超时，于是我上的Miller-Rabin。

Mycode：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int S = 8;//随机算法判定次数，一般8~10次就够了

//计算ret = (a*b)%c  a, b, c < 2^63
long long mult_mod(long long a, long long b, long long c)
{
    a %= c;
    b %= c;
    long long ret = 0;
    long long tem = a;
    while(b)
    {
        if(b & 1)
        {
            ret += tem;
            if(ret > c) ret -= c;//直接取模慢很多
        }
        tem <<= 1;
        if(tem > c) tem -= c;
        b >>= 1;
    }
    return ret;
}

//计算 ret = (a^n) % mod
long long pow_mod(long long a, long long n, long long mod)
{
    long long ret = 1;
    long long tem = a % mod;
    while(n)
    {
        if(n & 1) ret = mult_mod(ret, tem, mod);
        tem = mult_mod(tem, tem, mod);
        n >>= 1;
    }
    return ret;
}

// 通过 a^(n-1)=1(mod n)来判断n是不是素数
// n-1 = x * 2^t 中间使用二次判断
// 是合数返回true，不一定是合数返回false
bool check(long long a, long long n, long long x, long long t)
{
    long long ret = pow_mod(a, x, n);//a^x % n
    long long last = ret;
    for(int i = 1; i <= t; ++i)//进行t次(a^x % n)^2 % n
    {
        ret = mult_mod(ret, ret, n);
        if(ret == 1 && last != 1 && last != n - 1) return true;//合数
        last = ret;
    }
    if(ret != 1) return true;
    return false;//不一定是合数
}

//**************************************************
// Miller_Rabin算法
// 是素数返回true,(可能是伪素数)
// 不是素数返回false
//**************************************************
bool Miller_Rabin(long long n)
{
    if(n < 2) return false;
    if(n == 2) return true;
    if( (n&1) == 0) return false;//偶数
    long long x = n - 1;
    long long t = 0;
    while( (x&1) == 0) //将n分解为x*2^t;
    {
        x >>= 1;
        t++;
    }

    srand( time(NULL));

    for(int i = 0; i < S; ++i)
    {
        long long a = rand()%(n-1) + 1;//产生随机数a(并控制其范围在1 ~ n-1之间)
        if(check(a, n, x, t))//是合数
            return false;
    }
    return true;
}

int main()
{
    int T;
    long long n;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%lld", &n);
        if(Miller_Rabin(n))
            cout << "N" << endl;
        else
            cout << "Y" << endl;
    }
    return 0;
}

D.陆历川爱合并(K叉哈夫曼树)

题意：
从n个元素中每次取不超过k个元素进行合并，合并时的花费为k个元素价值的总和，并且合并出的新元素价值为这k个元素的总和。问当最终花费不超过T时，最小的k是多少。

思路：
0.当k=2时，这就是哈夫曼树，为使总花费最小，每次合并的两元素的价值最小。相关题目：SDNU-1412: Huffuman树。
1.显然k越大总花费越小，满足单调性，因此我们可以采用二分的方法枚举k。
2.因为每次取k个合并后变成一个总量其实减少了k-1个，每次减少这么多，再加上最后合并为1堆，因此当(n-1) % (k-1) == 0时，说明刚好能合并完成，否则会出现剩余的情况，如果最后合并这些多出来的部分的话会影响到上面1中的单调性，所以这种情况下要先合并多出来的这部分。
3.合并时可以维护小的值一直在队列前面，省下了排序/查找的时间。

K叉哈夫曼树模板：

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
int Hafuman(int k)  //返回总代价
{
	int ai, bi, blen;
	blen = 0;
	ai = bi = 0;
	int cost = 0;
	bool first = true;
	while (n - ai + blen - bi > 1)
	{
		int num = 0;
		if (first)
		{
			if ((n - k) % (k - 1) == 0)
				num = k;
			else
				num = (n - k) % (k - 1) + 1;
			first = false;
		}
		else
			num = k;
		int sum = 0;
		while (num--)
		{
			if (ai == n)
			{
				sum += b[bi];
				bi++;
			}
			else if (bi == blen)
			{
				sum += a[ai];
				ai++;
			}
			else if (a[ai] < b[bi])
			{
				sum += a[ai];
				ai++;
			}
			else
			{
				sum += b[bi];
				bi++;
			}
		}
		cost += sum;
		b[blen++] = sum;
	}
	return cost;
}

题目原型：
HDU-5884: Sort

Mycode：
(在HDU上过了，在这里T了，慢了200MS。自己将上面的模板套上后就能过了。)

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 100005;

int a[MAX];
queue<LL> Q;
int t, n, m, res;
bool judge(int k)
{
    while(!Q.empty())
            Q.pop();
    LL tot = 0;
    LL tem = 0;
    int idx = 0;
    int lef = (n - 1) % (k - 1) + 1;
    if(lef) //多出的lef个先合并
    {
        while(idx < lef)
           tem += a[idx++];
        tot += tem;
        Q.push(tem);
    }
    while(1)
    {
        tem = 0;
        for(int i = 0; i < k; ++i)
        {
            if(idx < n && (Q.empty() || a[idx] < Q.front()))
                tem += a[idx++];
            else
                tem += Q.front(), Q.pop();
        }
        tot += tem;
        if(tot > m) return false;
        if(idx >= n && Q.empty())
            break;
        Q.push(tem);
    }
    return tot <= m;
}
int main()
{
    scanf("%d",&t);
    for(int cas = 1; cas <= t; ++cas)
    {
        scanf("%d%d",&n, &m);
        for(int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        sort(a, a + n);
        int l = 2, r = n;
        int mid;
        while(l <= r)
        {
            mid = (l + r) / 2;
            if(judge(mid))
            {
                res = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        printf("Case #%d: %d\n", cas, res);
    }
    return 0;
}

E.Reasoning test(模拟)

题意：
给出10个问题，他们之间有相互限制的条件，问满足这些限制条件的每个问题的答案是多少。

思路：
因为只要提交答案，本地枚举每种情况，然后把限制条件堆到一个函数里judge一下就好了。
(比赛时都是手推的，这是江苏省公安厅网络安全小组的官方微博“江苏网警”发布的“2018年刑侦专题推理试题”，看来大家都有当刑警的潜力啊。)

Mycode：

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1e6+7;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int a[15];
char ch[] = {'A','B','C','D'};
void out()
{
    for(int i = 1; i <= 10; ++i)
        cout << ch[a[i]-1];
    cout << endl;
}
bool judge()
{
    if(a[2] != (a[5]+1)%4+1)    return false;

    if(a[3] == 1)
    {
        if(a[3] == a[6])    return false;
        if(a[3] == a[2])    return false;
        if(a[3] == a[4])    return false;
    }
    else if(a[3] == 2)
    {
        if(a[6] == a[2])    return false;
        if(a[6] == a[3])    return false;
        if(a[6] == a[4])    return false;
    }
    else if(a[3] == 3)
    {
        if(a[2] == a[3])    return false;
        if(a[2] == a[4])    return false;
        if(a[2] == a[6])    return false;
    }
    else if(a[3] == 4)
    {
        if(a[4] == a[2])    return false;
        if(a[4] == a[3])    return false;
        if(a[4] == a[6])    return false;
    }

    if(a[4] == 1 && a[1] != a[5])   return false;
    if(a[4] == 2 && a[2] != a[7])   return false;
    if(a[4] == 3 && a[1] != a[9])   return false;
    if(a[4] == 4 && a[6] != a[10])   return false;

    if(a[5] == 1 && a[5] != a[8]) return false;
    if(a[5] == 2 && a[5] != a[4]) return false;
    if(a[5] == 3 && a[5] != a[9]) return false;
    if(a[5] == 4 && a[5] != a[7]) return false;

    if(a[6] == 1)
    {
        if(a[2] != a[4])    return false;
        if(a[2] != a[8])    return false;
    }
    else if(a[6] == 2)
    {
        if(a[1] != a[6])    return false;
        if(a[1] != a[8])    return false;
    }
    else if(a[6] == 3)
    {
        if(a[3] != a[10])    return false;
        if(a[3] != a[8])    return false;
    }
    else if(a[6] == 4)
    {
        if(a[5] != a[9])    return false;
        if(a[5] != a[8])    return false;
    }

    int A, B, C, D;
    A = B = C = D = 0;
    for(int i = 1; i <= 10; ++i)
    {
        if(a[i] == 1)  ++A;
        if(a[i] == 2)  ++B;
        if(a[i] == 3)  ++C;
        if(a[i] == 4)  ++D;
    }
    int minn = -1;
    if(A < B && A < C && A < D)   minn = 1;
    if(B < A && B < C && B < D)   minn = 2;
    if(C < A && C < B && C < D)   minn = 3;
    if(D < A && D < B && D < C)   minn = 4;
    if(a[7] == 1 && minn != 3)    return false;
    if(a[7] == 2 && minn != 2)    return false;
    if(a[7] == 3 && minn != 1)    return false;
    if(a[7] == 4 && minn != 4)    return false;

    if(a[8] == 1 && abs(a[1]-a[7]) == 1)    return false;
    if(a[8] == 2 && abs(a[1]-a[5]) == 1)    return false;
    if(a[8] == 3 && abs(a[1]-a[2]) == 1)    return false;
    if(a[8] == 4 && abs(a[1]-a[10])== 1)    return false;

    bool flag = (a[1] == a[6]);
    if(flag)
    {
        if(a[9] == 1)
        {
            if(a[6] == a[5])
                return false;
        }
        if(a[9] == 2)
        {
            if(a[10] == a[5])
                return false;
        }
        if(a[9] == 3)
        {
            if(a[2] == a[5])
                return false;
        }
        if(a[9] == 4)
        {
            if(a[9] == a[5])
                return false;
        }
    }
    else
    {
        if(a[9] == 1)
        {
            if(a[6] != a[5])
                return false;
        }
        if(a[9] == 2)
        {
            if(a[10] != a[5])
                return false;
        }
        if(a[9] == 3)
        {
            if(a[2] != a[5])
                return false;
        }
        if(a[9] == 4)
        {
            if(a[9] != a[5])
                return false;
        }
    }

    int maxx = -1;
    if(A > B && A > C && A > D)   maxx = 1;
    if(B > A && B > C && B > D)   maxx = 2;
    if(C > A && C > B && C > D)   maxx = 3;
    if(D > A && D > B && D > C)   maxx = 4;
    int dif = abs(maxx - minn);
    if(a[10] == 1 && dif != 3)    return false;
    if(a[10] == 2 && dif != 2)    return false;
    if(a[10] == 3 && dif != 4)    return false;
    if(a[10] == 4 && dif != 1)    return false;
    return true;
}
void DFS(int idx, int val)
{
    a[idx] = val;
    if(idx == 10)
    {
        if(judge())
            out();
        return ;
    }
    for(int i = 1; i <= 4; ++i)
        DFS(idx+1, i);
}
int main()
{
    //DFS(0,0);
    cout << "BCACACDABA" << endl;
    return 0;
}

F.陆历川让你A个题

题意：
问n的阶乘末尾有多少个0。

思路：
将n的阶乘进行质因数分解后可以发现，实际影响末尾0的个数的只有因子2和5。而n的阶乘分解质因数后2的个数必定小于等于5的个数，因此只查询有多少个5就可以了。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1e6+7;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int t, res, n;
int main()
{
	cin >> t;
	while(t--)
	{
		res = 0;
		cin >> n;
		while(n)
		{
			n /= 5;
			res += n;
		}
		cout << res << endl;
	}
	return 0;
}

G.请回答Alice和Bob

请移步2017 省赛 山东 A Return of the Nim 【博弈】【Nim+Wythoff】。

H.强哥要置你于死地

题意：
强哥有n把枪，每个枪有3个属性，当一把枪的这三个属性都大于某一把枪的这三个属性时就称这把枪能完胜那把枪。问有这些枪分别能完胜多少把其他的枪。

思路：
三位偏序裸题。

题目原型：
BZOJ-3262: 陌上花开

队友补过了，目前不想补。

Donate comment here
0%