2022.12.23 模拟赛小结

2022.12.23 模拟赛小结更好的阅读体验戳此进入赛时思路T1CodeT2CodeT3Code正解T1CodeT2CodeT3CodeUPD

更好的阅读体验戳此进入

赛时思路

T1

$10\texttt{pts}$ 暴力跑路。

Code


xxxxxxxxxx
106
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

22

23

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

27
int N;
28
int a[210000];
29
int ans(INT_MAX);
30
bitset < 12 > vis;
31
bitset < 12 > exist[12];
32
bool flag(true);
33
int cnt(0);
34
basic_string < int > cur;
35

36
struct Edge{
37
    Edge* nxt;
38
    int to;
39
    OPNEW;
40
}ed[1100000];
41
ROPNEW(ed);
42
Edge* head[12];
43

44
void dfs_vis(int p, int fa = 0){
45
    vis[p] = true, ++cnt;
46
    for(auto i = head[p]; i; i = i->nxt){
47
        if(SON == fa)continue;
48
        if(vis[SON]){flag = false; return;}
49
        dfs_vis(SON, p);
50
    }
51
}
52
bool Check(void){
53
    memset(head, 0, sizeof head);
54
    for(int i = 0; i <= 11; ++i)exist[i].reset();
55
    vis.reset();
56
    int tot = cur.size();
57
    if(tot <= 1)return true;
58
    for(auto p : cur){
59
        int mn(INT_MAX), mnp(-1);
60
        for(auto q : cur)
61
            if(q != p && (a[p] ^ a[q]) < mn)mn = a[p] ^ a[q], mnp = q;
62
        if(exist[p][mnp])continue;
63
        exist[p][mnp] = exist[mnp][p] = true;
64
        head[p] = new Edge{head[p], mnp};
65
        head[mnp] = new Edge{head[mnp], p};
66
    }flag = true, cnt = 0; dfs_vis(cur.front());
67
    return flag && cnt == tot;
68
}
69
void dfs(int p = 1){
70
    if(p > N){
71
        if(Check())ans = min(ans, N - (int)cur.size());
72
        return;
73
    }
74
    dfs(p + 1);
75
    cur += p;
76
    dfs(p + 1);
77
    cur.pop_back();
78
}
79

80
int main(){
81
    freopen("star.in", "r", stdin);
82
    freopen("star.out", "w", stdout);
83
    N = read();
84
    if(N > 10)printf("qwq\n"), exit(0);
85
    for(int i = 1; i <= N; ++i)a[i] = read();
86
    dfs();
87
    printf("%d\n", ans);
88
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
89
    return 0;
90
}
91

92
template < typename T >
93
inline T read(void){
94
    T ret(0);
95
    int flag(1);
96
    char c = getchar();
97
    while(c != '-' && !isdigit(c))c = getchar();
98
    if(c == '-')flag = -1, c = getchar();
99
    while(isdigit(c)){
100
        ret *= 10;
101
        ret += int(c - '0');
102
        c = getchar();
103
    }
104
    ret *= flag;
105
    return ret;
106
}

T2

原题 LG-P3747 [六省联考 2017] 相逢是问候。

cc0000 贴心地给了 exEular，但是依然没想出来，只能有一点思路，具体是在没搞出来。但是实际上好像难度也不算是太离谱，比较显然，不过细节比较多。

$30\texttt{pts}$ 跑路。

Code


xxxxxxxxxx
101
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

22
#define MOD P
23

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

27
int N, M, P, C;
28
int a[51000];
29

30
ll qpow(ll a, ll b){
31
    ll ret(1), mul(a);
32
    while(b){
33
        if(b & 1)ret = ret * mul % MOD;
34
        b >>= 1;
35
        mul = mul * mul % MOD;
36
    }return ret;
37
}
38

39
class SegTree{
40
private:
41
    ll tr[210000 << 2];
42
    #define LS (p << 1)
43
    #define RS (LS | 1)
44
    #define MID ((gl + gr) >> 1)
45
public:
46
    void Pushup(int p){
47
        tr[p] = (tr[LS] + tr[RS]) % MOD;
48
    }
49
    void Build(int p = 1, int gl = 1, int gr = N){
50
        if(gl == gr)return tr[p] = a[gl] % MOD, void();
51
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
52
        Pushup(p);
53
    }
54
    void Modify(int pos, int p = 1, int gl = 1, int gr = N){
55
        if(gl == gr)return tr[p] = qpow(C, tr[p]), void();
56
        if(pos <= MID)Modify(pos, LS, gl, MID);
57
        else Modify(pos, RS, MID + 1, gr);
58
        Pushup(p);
59
    }
60
    ll Query(int l, int r, int p = 1, int gl = 1, int gr = N){
61
        if(l <= gl && gr <= r)return tr[p];
62
        if(l > gr || r < gl)return 0;
63
        return (Query(l, r, LS, gl, MID) + Query(l, r, RS, MID + 1, gr)) % MOD;
64
    }
65
}st;
66

67
int main(){
68
    freopen("candle.in", "r", stdin);
69
    freopen("candle.out", "w", stdout);
70
    N = read(), M = read(), P = read(), C = read();
71
    for(int i = 1; i <= N; ++i)a[i] = read();
72
    st.Build();
73
    while(M--){
74
        int opt = read();
75
        if(opt == 0){
76
            int l = read(), r = read();
77
            for(int i = l; i <= r; ++i)st.Modify(i);
78
        }else{
79
            int l = read(), r = read();
80
            printf("%lld\n", st.Query(l, r));
81
        }
82
    }
83
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
84
    return 0;
85
}
86

87
template < typename T >
88
inline T read(void){
89
    T ret(0);
90
    int flag(1);
91
    char c = getchar();
92
    while(c != '-' && !isdigit(c))c = getchar();
93
    if(c == '-')flag = -1, c = getchar();
94
    while(isdigit(c)){
95
        ret *= 10;
96
        ret += int(c - '0');
97
        c = getchar();
98
    }
99
    ret *= flag;
100
    return ret;
101
}

T3

原题 CF802O April Fools' Problem (hard)。

正解确实没想到，不过一个比较显然的费用流应该不难想，因为确实很显然。。。

$k$ $70\texttt{pts}$ 部分分。

Code


xxxxxxxxxx
106
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(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

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

22

23

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

27
struct Edge{
28
    Edge* nxt;
29
    Edge* rev;
30
    int to;
31
    ll flow;
32
    ll c;
33
    OPNEW;
34
}ed[30000];
35
ROPNEW(ed);
36
Edge* head[2100];
37

38
const int S = 2001, RS = 2002, T = 2003, RT = 2004;
39
int N, K;
40
ll a[2100], b[2100];
41
Edge* edg[2100];
42
ll dis[2100];
43
ll cflow[2100];
44
bitset < 2100 > inq;
45
ll ans(0);
46

47
bool SPFA(void){
48
    memset(dis, 0x3f, sizeof dis);
49
    memset(edg, false, sizeof edg);
50
    queue < int > cur;
51
    dis[RS] = 0, cflow[RS] = 0x3f3f3f3f, inq[RS] = true;
52
    cur.push(RS);
53
    while(!cur.empty()){
54
        // printf("searching %d\n", cur.front());
55
        int p = cur.front(); cur.pop(); inq[p] = false;
56
        for(auto i = head[p]; i; i = i->nxt){
57
            if(i->flow <= 0 || dis[SON] <= dis[p] + i->c)continue;
58
            dis[SON] = dis[p] + i->c, cflow[SON] = min(cflow[p], i->flow), edg[SON] = i;
59
            if(!inq[SON])cur.push(SON), inq[SON] = true;
60
        }
61
    }return edg[RT];
62
}
63
void MCMF(void){
64
    while(SPFA()){
65
        ans += dis[RT] * cflow[RT];
66
        for(int p = RT; p != RS; p = edg[p]->rev->to)
67
            edg[p]->flow -= cflow[RT], edg[p]->rev->flow += cflow[RT];
68
    }
69
}
70
void add(int s, int t, int flow, int c){
71
    head[s] = new Edge{head[s], npt, t, flow, c};
72
    head[t] = new Edge{head[t], npt, s, 0, -c};
73
    head[s]->rev = head[t], head[t]->rev = head[s];
74
}
75

76
int main(){
77
    freopen("letter.in", "r", stdin);
78
    freopen("letter.out", "w", stdout);
79
    N = read(), K = read();
80
    for(int i = 1; i <= N; ++i)a[i] = read();
81
    for(int i = 1; i <= N; ++i)b[i] = read();
82
    add(RS, S, K, 0), add(T, RT, K, 0);
83
    for(int i = 1; i <= N; ++i){
84
        add(S, i, 1, a[i]), add(i, T, 1, b[i]);
85
        if(i <= N - 1)add(i, i + 1, 0x3f3f3f3f >> 1, 0);
86
    }while(SPFA())MCMF();
87
    printf("%lld\n", ans);
88
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
89
    return 0;
90
}
91

92
template < typename T >
93
inline T read(void){
94
    T ret(0);
95
    int flag(1);
96
    char c = getchar();
97
    while(c != '-' && !isdigit(c))c = getchar();
98
    if(c == '-')flag = -1, c = getchar();
99
    while(isdigit(c)){
100
        ret *= 10;
101
        ret += int(c - '0');
102
        c = getchar();
103
    }
104
    ret *= flag;
105
    return ret;
106
}

正解

补题暂时咕掉了，laterrrr 回来补。

T1

Code


xxxxxxxxxx
1
1

T2

Code


xxxxxxxxxx
1
1

T3

Code


xxxxxxxxxx
1
1

UPD

update-2022_12_24 初稿