第八届ACM趣味程序设计竞赛第三场（正式赛）
A - 渐变字符串 (UESTC 1510 渐变字符串)
Source：LinPC
题解：首先预处理统计a-z字符的数量，根据渐变字符串的定义，由于总字符数较小，所以可以枚举渐变字符串的起点，然后找到由该起点起始的最大渐变字符串，然后从统计的字符中删除所用字符，如此循环操作至剩余字符数为0即可
B - 保护果实 (UESTC 1515 保护果实)
Source：cx大爷 missever
题解： 易得，只要最长的那条边的长度大于其它的边，那么就可以围成一个多边形，所以只需要维护当前的i条边中最长的那条边长度和其它边的长度和就好了
C - Little_Pro的driver朋友们和他的魔法 (UESTC 1514 Little_Pro的driver朋友们和他的魔法)
Little_Pro(小pro) 是 ProLights 的小号，哈哈
Source：ProLights
题解：贪心、字符串处理
对于 1010101...... (0 ~ n-1) 如果奇数的地方不是1就 ans1++， 如果偶数的地方不是0就 ans0++，
ans = max(ans0, ans1)； //min(ans0, ans1)次交换， ans - min(ans0, ans1) 次改变司机的好坏
然后再对 010101......(0 ~ n-1) 的情况跑一遍
2个ans取最小值
复杂度 O(n)
D - 扑克斗争 (UESTC 1509 扑克斗争)
Source：CS_LYJ1997
题解：根据题目所述规则，zhong_wang手上会有1-2张牌，而cfeitong手上会有1-13张牌。如果zhong_wang手上只有一张牌，则zhong_wang必胜；
如果zhong_wang手上有两张牌，则zhong_wang会先比较自己手上较大的牌和cfeitong手上最大的牌，
如果zhong_wang手上较大的牌cfeitong压不起，则zhong_wang先出较大的牌，再出较小的牌,zhong_wang获胜；
如果zhong_wang发现cfeitong能压住zhong_wang手中较大的那张牌，则zhong_wang先出手中较小的那张牌，留下较大的那张牌。
因为cfeitong能压得起zhong_wang手上较大的牌，必然能压起zhong_wang出的这张较小的牌，因为zhong_wang手上只剩下一张牌了，
则cfeitong肯定从大的往小的出，因此判断cfeitong手上是否有两张牌比zhong_wang剩下的那张牌小，如果存在则zhong_wang胜，不存在则cfeitong胜。
数据生成说明：
test01-02为样例
test03-09为手工制造数据
test10-39为电脑随机数据
数据丢在新生群里了
建议时间限制：3000/1000MS（Java/Others）
建议内存限制：65535/65535KB（Java/Others）
E - shallowdream and girl (UESTC 1516 shallowdream and girl)
Source：钟大爷 zhong_wang
题解：解题报告
分类讨论
存在较多情况，比如a,b,c某个数为0等等，需要很细心的讨论
这里介绍a>1,b>1,c>1时的情况
此时，对于任意x<=6，显然可以构造
对于x>6，如果x=a+2*b+3*c，显然可以构造，否则，必然还有若干个a,b,c没有使用，如剩余一个a，则可以通过x-a+a构造出x
所以对于1到a+2*b+3*c的所有整数均可以构造
原题是BNUOJ的52297,网上有很多不同的思路可供参考
数据生成说明
精心构造的毒瘤数据
建议设置的时间限制，内存限制
1000ms,65535KB
标程
A-AC代码中的一份
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#include<stdio.h> #include<string.h> int main() { int n,q=0,f[30]={0}; char a[1002]; scanf("%d",&n); scanf("%s",a); for (int i=0;i<n;i++) { int k; k=a[i]-'a'+1; f[k]++; } while (n!=0) { int i=1; while (f[i]==0) i++; int m=i; while(f[m]!=0){ f[m]--; m++; } q++; n=n-(m-i); } printf("%dn",q); return 0; }
B-标程
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#include <iostream> #include<cstdio> using namespace std; int a[1000005]; int main() { int n,i,m; int s; scanf("%d",&n); for(i = 0; i < n; i++) scanf("%d",&a[i]); if(n < 3) {printf("-1n"); return 0;} m = max(a[0],a[1]); s = min(a[0],a[1]); for(i = 2; i < n; i++) { if(a[i] > m) { s += m; m = a[i]; } else s += a[i]; if(s > m) break; } if(i < n) printf("%dn",i + 1); else printf("-1n"); return 0; }
C-标程
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 <iostream> #include <cstdio> #include <string> #include <cstring> using namespace std; typedef long long LL; const int maxn = 1e5 + 8; bool v[maxn]; int main() { #ifdef LOCAL freopen("36.in", "r", stdin); freopen("36.out", "w", stdout); int T = 1; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); string s, s1, s2; LL n, ans0 = 0, ans1 = 0, ans = 0; cin >> n; cin >> s; s1 = s; s2 = s; for(int i = 0; i < n; i++){ if(s[i] == '0'){ v[i] = 0; v[i] = 0; } else{ v[i] = 1; v[i] = 1; } } for(int i = 0; i < n; i++){ //cout << v[i] <<" "; if(i % 2 == 0){ if(v[i] == 0) ; else ans0++; } else{ if(v[i] == 1) ; else ans1++; } } //cout << endl; //cout <<ans0 << " " << ans1 << endl; ans = max(ans0, ans1); ans0 = ans1 = 0; for(int i = 0; i < n; i++){ //cout << v[i] <<" "; if(i % 2 == 0){ if(v[i] == 1) ; else ans0++; } else{ if(v[i] == 0) ; else ans1++; } } //cout <<ans0 << " " << ans1 << endl; ans = min(ans, max(ans0, ans1)); cout << ans << endl; #ifdef LOCAL //cout << endl; } #endif // LOCAL return 0; }
D-标程
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#include<stdio.h> #include<string.h> int convert(char c) { if (c>='3' && c<='9') return c-48; if (c=='T') return 10; if (c=='J') return 11; if (c=='Q') return 12; if (c=='K') return 13; if (c=='A') return 14; return 15; } int main() { int len1,len2,c1max,c2max,ans,cnt,i; char s1[5],s2[20]; scanf("%s",s1); scanf("%s",s2); len1=strlen(s1);len2=strlen(s2); if (len1==1) ans=1; else { c1max=convert(s1[len1-1]); c2max=convert(s2[len2-1]); if (c1max>=c2max) ans=1; else { cnt=0; for(i=0;i<len2;i++) if (convert(s2[i])<c1max) cnt++; if (cnt>=2) ans=1; else ans=0; } } if (ans) printf("zhong_wangn"); else printf("cfeitongn"); return 0; }
E-标程
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#include<bits/stdc++.h> #define clr(x,y) memset((x),(y),sizeof(x)) using namespace std; int a,b,c; int main(void) { scanf("%d%d%d",&a,&b,&c); int ans=0; if (a==0 || b==0 || c==0) { if (a==0 && b==0 && c==0) { ans=0; } else if ((a==0 && b==0) || (a==0 && c==0) || (b==0 && c==0)) { ans=a+b+c; } else { if (a==0) { if (b>1 && c>1) { ans=2*b+3*c-2; } else if (b>1 && c==1) { ans=2*b+1; } else if (c>1 && b==1) { ans=2*c+1; } else ans=3; } else if (b==0) { if (a>1 && c>1) { ans=a+3*c; } else if (a>1 && c==1) { ans=a+3*c; } else if (a==1 && c>1) { ans=2*c+1; } else ans=3; } else { ans=a+2*b; } } } else { ans=a+2*b+3*c; } printf("%dn",ans); }
Thank you!
------from ProLights
最后
以上就是愉快小猫咪最近收集整理的关于第八届ACM趣味程序设计竞赛第三场（正式赛）官方题解的全部内容，更多相关第八届ACM趣味程序设计竞赛第三场（正式赛）官方题解内容请搜索靠谱客的其他文章。
发表评论 取消回复