这一场是在 2019-11-17 13:39 CST 打的
是打完南京南昌回来后的第一场Team Round,当然了,选题性质是恢复信心训练。
一共解了BKICJAEFH九道题。
有一个小插曲就是我a了第一个水题的时候wqr_和dqy已经切了四道题😭(我神经病了用scanf输入字符,ljlct不会)
B - SpongeBob SquarePants
签到
1 | /* _ _ _ |
K - Help The Support Lady
思路：dqy写的
1 |
|
I - To Crash Or Not To Crash
思路：wqr写的
1 | /* _ _ _ |
C - I Don’t Want To Pay For The Late Jar!
dqy写的
1 |
|
J - Kitchen Plates
题意：
给你abcde五个盘子，给你五个关系，根据给的关系依此输出盘子（从小到大）
思路：
确实可以暴力，然而我第一反应就是拓扑排序，然后敲完之后很长很长一段时间陷入很迷的状态，后来才发现是我用scanf用不对？？。。在我低迷的时候dqy和wqr说杀鸡焉用牛刀这不随便乱搞。。。btw，判断impossible就是有无环，检查序列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
using namespace std;
const int maxn = 6;
int ver[maxn], nxt[maxn], head[maxn], deg[maxn], a[maxn];
int tot , cnt, n, m;
char c[3];
void add(int x, int y){
ver[++tot] = y,nxt[tot] = head[x],head[x] = tot;
deg[y]++;
}
void topo(){
queue<int >q;
for(int i = 1; i <= n;i++){
if(deg[i] == 0)q.push(i);
}
while(q.size()){
int x = q.front();
q.pop();
a[++cnt] = x;
//cout << "x ==== " << x << " a["<< cnt << "] ===== " <<a[cnt] << endl;
for(int i = head[x]; i ; i = nxt[i]){
int y = ver[i];
if(--deg[y] == 0)q.push(y);
}
}
}
int main(){
n = 5;
m = 5;
for(int i = 0; i < m;i++){
scanf("%s", c);
if(c[1] == '<')add(c[0] - 'A' + 1, c[2] - 'A'+1);
else add(c[2] - 'A'+1,c[0]-'A'+1);
/*int x, y;
cin >> x >> y;
add(x,y);*/
}
topo();
// cout << cnt << endl;
if(cnt < 5)cout << "impossible\n";
else {
for(int i = 1; i <= cnt;i++)
cout << (char)('A'+a[i]-1);
}
}
A - Mental Rotation
题意：
给你一个方形图案，给一系列右旋转或者左旋转操作，要求输出操作后的图案
思路：
模拟，模拟带师wqr写的。观察到最多只有右旋90，180，270度这三种，处理完所有的操作后模拟旋转就行。
1 | /* _ _ _ |
E - Optimal Slots
题意：
给一个总时间T，再给N个时间，要求选取一些时间ti，使得总和sum不超过T且尽量接近T，如果有多种方案，就输出输入顺序早的方案。
思路：
dqy 写的 倒着遍历 set vector 组合技
1 |
|
题解2：
转化成01背包的思想
过程：
设d[i][j] 为能否从i到N这段中选取一些组成j,为1可行，为零不可行。考虑转移方程，从大到小枚举j,d[i][j] |= d[i+1][j-t[i]],找到一个最大的j，使得d[1][j] = 1, 那么ans = j。然后从大到小枚举i,如果由d[i+1][sum-t[i]] == 1,那么选取ti。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
using namespace std;
const int maxn = 24 * 8;
int d[52][maxn], a[51];
int main() {
int T, n;
for (int i = 1; i <= 51; i++)
d[i][0] = 1;
while (cin>>T && T) {
cin>>n;
for (int i = 1; i<= n; i++) {
cin>>a[i];
for (int j = 1; j <= T; j++)
d[i][j] = 0;
}
for (int j = 1; j <= T; j++)
d[n + 1][j] = 0;
for (int i = n; i; i--) {
for (int j = T; j >= a[i]; j--)
d[i][j] |= d[i + 1][j - a[i]];
for (int j = T; j; j--)
d[i][j] |= d[i + 1][j];
}
int sum = T;
while (!d[1][sum])
sum--;
int ans = sum;
int p = 1;
queue<int> q;
while (sum > 0) {
if (a[p] <= sum) {
if (d[p + 1][sum - a[p]])
q.push(a[p]), sum -= a[p];
}
p++;
}
while (!q.empty()) {
printf("%d ", q.front());
q.pop();
}
printf("%d\n", ans);
}
}
//others：https://blog.csdn.net/ccsu_cat/article/details/93400147
F - Military Class
题意：
有2N个士兵站成两排，现在要求上面一排的士兵和下面一排的士兵一一配对组成N队，要求配对的两个士兵，他们的位置相差不能超过e，而且有K队士兵互相讨厌，他们不能配对在一起。要求输出配对总方案数。
解法：
观察到e很小，2e+1最大也就是9。考虑用状压dp。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
using namespace std;
using ll = long long;
const int maxn = 2005;
const int mod = 1e9+7;
int n , e, kk , ans;
typedef pair <int , int > P;
set<P> s;
int dp[maxn][maxn];
/*int mul(int a , int b){
int ret = 0;
while(b){
if(b & 1)
ret = (ret+a)%mod;
a=(a << 1)%mod;
b = b >> 1;
}
return ret;
}*/
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> e >> kk;
int ee = 2*e+1;
int all = (ll(1) << ee);
for(int i = 0; i < kk;i++) {
int a, b;
cin >> a >> b;
//s.insert(make_pair(a, b));
if(abs(a - b) <= e)s.insert(make_pair(a, b));
}
dp[0][0] = 1;
for(int i = 1; i <= n;i++){
for(int j = 0; j < all; j++){
for(int k = 0; k < ee;k++){
if(i + k - e <= 0)continue;
if(i + k - e > n)continue;
if(s.find(P{i, i+k-e}) != s.end())continue;
int t = j >> 1;
if(t & (1ll << k))continue;
dp[i][t | (1ll << k)] = (dp[i][t | (1ll << k)] + dp[i-1][j] ) % mod;
}
}
}
for(int i = 0; i < all;i++){
//cout << "dp[n][" << i << "] ===== "<< dp[n][i] << endl;
ans += dp[n][i];
ans %= mod;
}
cout << ans << endl;
}
H - Are You Safe?
题意：
给定n个点，求出这些点构成的凸包，然后逆时针输出，另外还有q次询问，每次询问一个点是否在凸包里
思路：wqr现学现卖，orz！
1 |
|