2018 Autumn 清北学堂普及刷题班 Day1 题解

十月 01, 2018 11098

不知不觉弄了个鼠标回来（雾

T1. 扑克牌

题面

【题目描述】

这天， 小 Q 来到了小杜家， 找小杜玩起了扑克牌的游戏。

扑克牌有 54 张牌， 分别是数字 A,2,3,4,5,6,7,8,9,10,J,Q,K，每种数字有 4 个花色， 分别为红桃， 黑桃， 方块， 梅花， 还有两张大王和小王。

这天小 Q 和小杜玩起来比大小的游戏， 两人各拿出一张扑克牌比大小， 很显然 3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王， 为了防止数字相同无法比较， 他们给花色也定了一个大小梅花<方块<黑桃<红桃， 规定先比较数字， 数字相同再比较花色， 由于他们只有一副扑克牌， 拿出的两张牌不可能相同， 所以一定能比出大小。

【输入描述】

第一行一个数字 T， 表示小 Q 和小杜玩的次数。

接下来 T 行， 每行两个用空格隔开的数字。

其中 1-13 分别表示梅花 A,2,3,4,5,6,7,8,9,10,J,Q,K。

其中 14-26 分别表示方块 A,2,3,4,5,6,7,8,9,10,J,Q,K。

其中 27-39 分别表示黑桃 A,2,3,4,5,6,7,8,9,10,J,Q,K。

其中 40-52 分别表示红桃 A,2,3,4,5,6,7,8,9,10,J,Q,K。

53 表示小王， 54 表示大王。

第一个数表示小 Q 的牌， 第二个数表示小杜的牌。

【输出描述】

输出共 T 行， 每行一个字母 Q 或者 D， Q 表示小 Q 赢， D 表示小杜赢。

Input / Output 格式 & 样例

输入格式 & 输出格式

见题面。

输入样例

1
2
3
2 1
1 13
1 53

输出样例

1
2
Q
D

样例解释 & 注意事项

【样例解释】

第一局小 Q 是梅花 A， 小杜是梅花 K， 所以小 Q 大

第二局小 Q 是梅花 A， 小杜是小王， 所以小杜大。

【数据范围】

对于 30%的数据， 扑克牌的范围在[1,13]。

对于 50%的数据， 不会出现大小王。

对于 100%的数据， 1<=T<=100。

解析

照题意模拟

这里有一个小技巧

你可以对读入的数字（必须保证数字不代表大、小王） mod\ 13

得到的新数字：

1
2
0 1 2 3 4 5 6 7 8 9 10 11 12
K A 2 3 4 5 6 7 8 9 10  J  Q

接着特判，把K改成13，把A改成14，把2改成15，把小王改成16，把大王改成17

最后直接比较新数字就行了

当新数字相同时依题意可直接比较原数字的大小

代码实现

（依然毒瘤风格）

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
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterator -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)
using namespace std;

/*  Constants Start  */

/*  Constants End  */

/*  Variants Start  */

/*  Variants End  */

namespace FastIO {
    void DEBUG(char comment[], int x) {
        cerr << comment << x << endl;
    }

    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }

    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}

namespace Solution {
	int queryNum(int x) {
		if (x <= 52) { 
			x %= 13;
			if (x == 0) x = 13;
			if (x == 1) x = 14;
			if (x == 2) x = 15;
			return x;
		} else return x - 52 + 15;
	}
	char Judge(int q, int d) {
		int qa = queryNum(q);
		int da = queryNum(d);
		if (qa == da) return q < d ? 'D' : 'Q';
		return qa < da ? 'D' : 'Q';
	}
} 

int main(int argc, char *const argv[]) {
    #ifdef HANDWER_FILE
    freopen("poker.in", "r", stdin);
    freopen("poker.out", "w", stdout);
    #endif
    using FastIO::getint;
    using FastIO::putint;
    int t = getint();
    while (t --> 0) {
    	int q = getint();
    	int d = getint();
    	cout << Solution::Judge(q, d) << endl;
	}
    return 0;
}



T2. 密码

题面

【题目描述】

小杜开始学习 C++， 小杜想进行一些练习， 于是小杜准备上某题库网站进行做题练习， 小杜发现这样的网站都需要进入注册之后， 才可以登录进行练习， 于是小杜准备注册一个账号。

在填写了一大堆信息之后， 网站要求小杜输入密码， 这让小杜犯了难， 网站对密码的有一定的要求， 密码只能包含大写字母， 小写字母， 并且必须包含至少一个大写字母， 至少一个小写字母， 那么对于小杜的密码， 是否符合该网站的要求呢？如果不符合网站的要求， 那么如何修改让密码变得符合要求呢，一次修改只能将密码的某一位修改成一个大写字母或小写字母， 如果有多个密码符合条件， 需要修改次数最少的， 对于修改次数相同的，输出字典序最小的（按 ASCII 码）

【输入描述】

第一行一个数字 T 表示数据组数。

接下来 T 行， 每行一个字符串表示小杜的密码。

【输出描述】

共 T 行。

若小杜的密码符合条件， 将密码直接输出即可， 否则输出修改后的密码 。

Input / Output 格式 & 样例

输入输出格式

见题面。

输入样例

1
2
3
2
abaCABA
qwerty

输出样例

1
2
abaCABA
Awerty

样例解释 & 注意事项

【数据范围】

对于 30%的数据， 只包含小写字母。
对于另外 20%的数据， 只包含大写字母。
对于 100%的数据， 1<=T<=100， 字符串长度不超过 100 并且大于等于 3，保证输入数据只包含大、小写字母。

解析

依然照题意模拟

我们贪心地认为字母A越靠前，字母a越靠后，整个字符串字典序就越小

那么本题分两种情况讨论：

  • 只含有大写字母
  • 只含有小写字母
  • 含有特殊字符并没有

对于只含有大写字母的情况，把字符串末尾修改成a即可。

对于只含有小写字母的情况，把字符串开头修改成A即可。

代码实现

（还是这种玄学码风

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
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterator -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)
using namespace std;

/*  Constants Start  */

/*  Constants End  */

/*  Variants Start  */

string s;

/*  Variants End  */

namespace FastIO {
    void DEBUG(char comment[], int x) {
        cerr << comment << x << endl;
    }

    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }

    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}

namespace Solution {
	bool Check(string str, int lenstr, bool &hasUpper, bool &hasLower) {
		hasUpper = false;
		hasLower = false;
		Forw (i, 0, lenstr) {
			if (isupper(str[i])) hasUpper = true;
			else if (islower(str[i])) hasLower = true;
			else return false;
		}
		if (hasUpper && hasLower) return true; 
		return false;
	}
	string Modify(string str, int lenstr, bool hasUpper, bool hasLower) {
		string ret = str;
		if (hasUpper == false && hasLower == false) {
			Forw (i, 0, lenstr - 1) ret[i] = 'A';
			ret[lenstr - 1] = 'a';
			ret[lenstr] = '\0'; 
		}
		if (hasUpper == false && hasLower) {
			ret[0] = 'A';
		}
		if (hasUpper && hasLower == false) {
			ret[lenstr - 1] = 'a';
		}
		if (hasUpper && hasLower) {
			Forw (i, 0, lenstr) {
				if (!isupper(ret[i]) && !islower(ret[i])) {
					ret[i] = 'A';
				}
			}
		}
		return ret;
	}
}

int main(int argc, char *const argv[]) {
    #ifdef HANDWER_FILE
    freopen("pass.in", "r", stdin);
    freopen("pass.out", "w", stdout);
    #endif
    int t = 0;
    cin >> t;
    while (t --> 0) {
    	cin >> s;
    	int lens = s.length();
    	bool hasUpper = false, hasLower = false;
    	if (Solution::Check(s, lens, hasUpper, hasLower)) cout << s << endl;
    	else cout << Solution::Modify(s, lens, hasUpper, hasLower) << endl;
	}
    return 0;
}


T3. 下棋

题面

【题目描述】

小 Q 拿出了一张 2 行 N 列的棋盘， 棋盘的每个位置可以放一颗黑棋或者一颗白棋。
若两个棋子颜色相同且位置相邻我们就认为这两个棋子连成了一片， 当然两个棋子都和另一个棋子连成一片， 我们也认为这两个棋子连成一片。
这天小杜突发奇想， 小杜想知道这个棋盘上有多少种放棋子的方法使得棋盘上的棋子片数为 K。
这个数目可能非常大， 请输出方法对 998244353 取模的结果。

【输入描述】

两个数 N 和 K， 用空格隔开。

【输出描述】

一个数字表示方案数。

Input & Output 格式 & 样例

输入输出格式

见题面。

输入样例

1
3 4

输出样例

1
12

样例解释 & 注意事项

【数据范围】

对于 30%的数据， 1<=N<=10,1<=K<=2N。
对于 50%的数据， 1<=N<=100,1<=K<=2N。
对于 100%的数据， 1<=N<=1000,1<=K<=2N。

解析

考场上死活没看出这是DP

我们设dp[i][j]=k表示前 2\times i 个格子，有 j 片，最后一个 2\times i 的格子的状态为 k\ (0 \le k \le 3)

那么只需要枚举下一个 2\times i 的状态 p\ (0 \le p \le 3) ，进行转移即可

转移有 4\times4=16 种方案，可以先判断加 0 片和加 1 片的情况，剩下的就是加 2 片的情况，代码会简洁不少

不要忘了最后 ans 要 mod\ 998244353

代码实现

（玄学码风无误了

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
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterator -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)
using namespace std;

/*  Constants Start  */

/*  Constants End  */

/*  Variants Start  */

/*  Variants End  */

namespace FastIO {
    void DEBUG(char comment[], int x) {
        cerr << comment << x << endl;
    }

    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }

    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}

namespace Solution {
	const int HA = 998244353;
	int Query(int x, int y) {
		if (x == y) return 0;
		if (x == 0) return 1;
		if (x == 3) return 1;
		if (y == 0) return 0;
		if (y == 3) return 0;
		return 2;
	} 
	
	const int MAXN = 2000 + 10;
	long long int f[MAXN][4];
	long long int x[MAXN][4];
	
	long long int Work(int n, int k) {
		f[1][0] = f[1][3] = 1;
		f[2][1] = f[2][2] = 1;
		Forw (i, 0, n - 1) {
			memset(x, 0, sizeof(x));
			For (j, 1, MAXN - 10) {
				Forw (xx, 0, 4) {
					Forw (y, 0, 4) {
						x[j + Query(xx, y)][y] += f[j][xx];
						x[j + Query(xx, y)][y] %= HA;
					}
				}
			}
			std::swap(f, x);
		}
		return (f[k][0] + f[k][1] + f[k][2] + f[k][3]) % HA;
	}
}

int main(int argc, char *const argv[]) {
    #ifdef HANDWER_FILE
    freopen("chess.in", "r", stdin);
    freopen("chess.out", "w", stdout);
    #endif
    int n = FastIO::getint();
    int k = FastIO::getint();
    FastIO::putint(Solution::Work(n, k), '\n');
    return 0;
}


T4. 堆积木

太蒻不写