[ABC271D] Flip and Adjust Solution

更好的阅读体验戳此进入

题面

给定 $n$$n$ 张卡片，正面是 $a_i$$a_i$，背面是 $b_i$$b_i$，给定 $S$$S$ 要求构造方案钦定这 $n$$n$ 张卡片选择正面的数或反面的数，使得求和后洽等于 $S$$S$，无解输出 No，反之输出 Yes 并输出任意方案。

Solution

一般的思路都是 DP 同时记录决策点然后最后跑一遍答案，不过这样还需要动脑，本题范围较小不如暴力一点，我们直接在 DP 过程中的每一个状态记录所有牌的正反，最开始的思路是开一个 bitset 这样多出来的复杂度是 $O({\displaystyle \frac{n}{w}})$$O(\dfrac{n}{w})$ 也就是 $O(1)$$O(1)$，不过仔细一想这东西直接开个 basic_string < char > 无脑维护就行了，这样转移会多一个复制的 $O(n)$$O(n)$，空间也会多一个 $O(n)$$O(n)$，最终时空复杂度都是 $O(n^{2}S)$$O(n^2S)$，刚好 1e8。

转移显然：

然后中间判断一下是否能转移，也就是 dp[i][j].size() 是否为 $i$$i$，以及 $j-a_i\ge 0$$j - a_i \ge 0$ 和 $j-b_i\ge 0$$j - b_i \ge 0$ 即可。

Code

xxxxxxxxxx
61
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template < typename T = int >
24
inline T read(void);
25

26
int N, S;
27
int A[110], B[110];
28
basic_string < char> dp[110][11000];
29

30
int main(){
31
    N = read(), S = read();
32
    for(int i = 1; i <= N; ++i)A[i] = read(), B[i] = read();
33
    dp[1][A[1]] += 'H', dp[1][B[1]] += 'T';
34
    for(int i = 2; i <= N; ++i)
35
        for(int j = 0; j <= S; ++j){
36
            if(j - A[i] >= 0 && (int)dp[i - 1][j - A[i]].size() == i - 1)dp[i][j] = dp[i - 1][j - A[i]] + 'H';
37
            if(j - B[i] >= 0 && (int)dp[i - 1][j - B[i]].size() == i - 1)dp[i][j] = dp[i - 1][j - B[i]] + 'T';
38
        }
39
    if((int)dp[N][S].size() != N)printf("No\n"), exit(0);
40
    printf("Yes\n");
41
    for(auto v : dp[N][S])printf("%c", v);
42
    printf("\n");
43
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
44
    return 0;
45
}
46

47
template < typename T >
48
inline T read(void){
49
    T ret(0);
50
    int flag(1);
51
    char c = getchar();
52
    while(c != '-' && !isdigit(c))c = getchar();
53
    if(c == '-')flag = -1, c = getchar();
54
    while(isdigit(c)){
55
        ret *= 10;
56
        ret += int(c - '0');
57
        c = getchar();
58
    }
59
    ret *= flag;
60
    return ret;
61
}

UPD

update-2023_02_09 初稿。

update-2023_02_09 修改一些不符合规范的地方。（另外他这个 “句子末尾应加句末句号（全角）” 我实在是没找到哪里缺句号了，只能在 “初稿” 这个非句子的词语后加了个句号。