2022.09.13 模拟赛小结

题面

PDF链接

(这个链接只是为了自己方便找，页面设置权限了，不要尝试访问)

更好的阅读体验戳此进入

（建议您从上方链接进入我的个人网站查看此 Blog，在 Luogu 中图片会被墙掉，部分 Markdown 也会失效）

赛时思路

T1

原题 LG-P1772 [ZJOI2006] 物流运输

是一道 DP + 最短路，赛时没想到 DP，嗯写了个 Dijk + 随机化微小扰动 + 卡时，当然最后寄掉了。

Code

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

4
#define npt nullptr
5

6
/******************************
7
abbr
8

9
******************************/
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 percent){return rndd(1, 100) <= percent;}
16

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

21
bitset < 110 > wharf[22];
22
int blocked[22];
23

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

27
struct Edge{
28
    Edge* nxt;
29
    int to;
30
    int val;
31
    void* operator new(size_t);
32
    Edge(Edge* nxt, int to, int val):nxt(nxt), to(to), val(val){;}
33
    Edge(void) = default;
34
}eData[410];
35
void* Edge::operator new(size_t){static Edge* P = eData; return ++P;}
36
Edge* head[22];
37

38
int N, M, K, E;
39

40
bool vis[22];
41
ll dis[22];
42
void Dijk(int);
43

44
priority_queue < 
45
    pair < ll, int > /*distance, vertex*/,
46
    vector < pair < ll, int > >,
47
    // [](pair < int, int > x, pair < int, int > y) ->bool{
48
    // }
49
    greater < pair < ll, int > >
50
 > vert;
51
int main(){
52
    freopen("plan.in", "r", stdin);
53
    freopen("plan.out", "w", stdout);
54
    N = read(), M = read(), K = read(), E = read();
55
    for(int i = 1; i <= E; ++i){
56
        int f = read(), t = read(), val = read();
57
        if(f == t)continue;
58
        head[f] = new Edge(head[f], t, val);
59
        head[t] = new Edge(head[t], f, val);
60
    }
61
    int D = read();
62
    while(D--){
63
        int p = read(), a = read(), b = read();
64
        for(int i = a; i <= b; ++i)wharf[p][i] = true;
65
    }
66
    for(int i = 1; i <= M; ++i)blocked[i] = wharf[i]._Find_next(0);
67
    ll ans(0);
68
    ll lastcost(-1);
69
    for(int i = 1; i <= N; ++i){
70
        Dijk(i);
71
        ll cost = dis[M];
72
        ans += cost;
73
        if(i != 1 && cost != lastcost)ans += K;
74
        lastcost = cost;
75
    }
76
    while((double)clock() / CLOCKS_PER_SEC < 0.7){
77
        for(int i = 1; i <= M; ++i){
78
            for(auto j = head[i]; j; j = j->nxt){
79
                if(rnddd(10))j->val *= 1.05;
80
            }
81
            blocked[i] = wharf[i]._Find_next(0);
82
        }
83
        ll anss(0);
84
        ll lastcostt(-1);
85
        for(int i = 1; i <= N; ++i){
86
            Dijk(i);
87
            ll costt = dis[M];
88
            anss += costt;
89
            if(i != 1 && costt != lastcostt)anss += K;
90
            lastcostt = costt;
91
        }
92
        ans = min(ans, anss);
93
    }
94
    printf("%lld\n", ans);
95
    // fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
96
    return 0;
97
}
98

99

100
void Dijk(int day){
101
    bool block[22];
102
    memset(block, false, sizeof(block));
103
    for(int i = 1; i <= M; ++i){
104
        if(day == blocked[i]){
105
            block[i] = true;
106
            if(blocked[i] <= N)blocked[i] = wharf[i]._Find_next(blocked[i]);
107
        }
108
    }
109
    memset(vis, false, sizeof(vis));
110
    for(int i = 1; i <= M; ++i)dis[i] = LLONG_MAX / 2ll - 10ll;
111
    dis[1] = 0ll;
112
    vert.push(make_pair(dis[1], 1));
113
    while(!vert.empty()){
114
        int p;
115
        tie(ignore, p) = vert.top();
116
        vert.pop();
117
        if(vis[p] || block[p])continue;
118
        vis[p] = true;
119
        for(auto i = head[p]; i; i = i->nxt){
120
            if(dis[p] + i->val < dis[i->to]){
121
                dis[i->to] = dis[p] + i->val;
122
                if(!vis[i->to])vert.push(make_pair(dis[i->to], i->to));
123
            }
124
        }
125
    }
126
}
127

128
template<typename T>
129
inline T read(void){
130
    T ret(0);
131
    short flag(1);
132
    char c = getchar();
133
    while(c != '-' && !isdigit(c))c = getchar();
134
    if(c == '-')flag = -1, c = getchar();
135
    while(isdigit(c)){
136
        ret *= 10;
137
        ret += int(c - '0');
138
        c = getchar();
139
    }
140
    ret *= flag;
141
    return ret;
142
}
143

144
/*
145

146
5 5 10 8
147
1 2 1
148
1 3 3
149
1 4 2
150
2 3 2
151
2 4 4
152
3 4 1
153
3 5 2
154
4 5 2
155
4
156
2 2 3
157
3 1 1
158
3 3 3
159
4 4 5
160

161
*/

T2

原题是 LG-P1768 天路。

赛时写了个 $n$$n$ 次 Dijkstra，然后还是重载的一大堆符号，似乎假掉了，Luogu 上过了一个点其他全部 RE，数据下不了暂时不知道什么原因。

Code

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

4
#define npt nullptr
5

6
/******************************
7
abbr
8

9
******************************/
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

16
typedef unsigned int uint;
17
typedef unsigned long long unll;
18
typedef long long ll;
19

20
template<typename T = int>
21
inline T read(void);
22

23
struct Node{
24
    int v, p;
25
    Node(int v, int p):v(v), p(p){;}
26
    Node(void) = default;
27
    bool operator < (const Node d)const{/////////////////////
28
        if(!this->p || !this->v)return true;
29
        if(!d.p || !d.v)return false;
30
        double x = (double)this->v / (double)this->p;
31
        double y = (double)d.v / (double)d.p;
32
        return x < y;
33
    }
34
    bool operator > (const Node d)const{/////////////////////
35
        if(!this->p || !this->v)return false;
36
        if(!d.p || !d.v)return true;
37
        double x = (double)this->v / (double)this->p;
38
        double y = (double)d.v / (double)d.p;
39
        return x > y;
40
    }
41
    Node operator + (Node d){
42
        return Node(this->v + d.v, this->p + d.p);
43
    }
44
    void operator = (Node d){
45
        this->p = d.p;
46
        this->v =d.v;
47
    }
48
};
49

50
struct Edge{
51
    Edge* nxt;
52
    int to;
53
    Node val;
54
    void* operator new(size_t);
55
    Edge(Edge* nxt, int to, Node val):nxt(nxt), to(to), val(val){;}
56
    Edge(void) = default;
57
}eData[21000];
58
void* Edge::operator new(size_t){static Edge* P = eData; return ++P;}
59
Edge* head[7500];
60

61
int N, M;
62

63
bool vis[22];
64
Node dis[22];
65
void Dijk(int);
66

67

68

69
priority_queue < 
70
    pair < Node, int >/*value, vertex*/,
71
    vector < pair < Node, int > >,
72
    less < pair < Node, int > >
73
> vert;
74

75
int main(){
76
    freopen("road.in", "r", stdin);
77
    freopen("road.out", "w", stdout);
78
    N = read(), M = read();
79
    for(int i = 1; i <= M; ++i){
80
        int f = read(), t = read(), v = read(), p = read();
81
        if(f == t)continue;
82
        head[f] = new Edge(head[f], t, Node(v, p));
83
    }
84
    Node ans(0, 0);
85
    for(int i = 1; i <= N; ++i){
86
        Dijk(i);
87
        if(dis[i] > ans)ans = dis[i];
88
        // printf("No.%d  %.3lf\n", i, (double)dis[i].v / (double)dis[i].p);
89
    }
90
    if(!ans.v || !ans.p)printf("-1\n");
91
    else printf("%.1lf\n", (double)ans.v / (double)ans.p);
92

93
    // fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
94
    return 0;
95
}
96

97

98
void Dijk(int S){
99
    memset(vis, false, sizeof(vis));
100
    // memset(dis, 0x3f, sizeof(dis));
101
    for(int i = 1; i <= N; ++i)dis[i].v = 0, dis[i].p = 0x3f3f3f3f;
102
    dis[S] = Node(0, 0);
103
    vert.push(make_pair(dis[S], S));
104
    while(!vert.empty()){
105
        int p;
106
        tie(ignore, p) = vert.top();
107
        vert.pop();
108
        if(vis[p])continue;
109
        vis[p] = true;
110
        if(p == S)vis[p] = false;
111
        for(auto i = head[p]; i; i = i->nxt){
112
            if(dis[p] + i->val > dis[i->to]){
113
                dis[i->to] = dis[p] + i->val;
114
                if(!vis[i->to])vert.push(make_pair(dis[i->to], i->to));
115
            }
116
        }
117
    }
118
}
119

120
template<typename T>
121
inline T read(void){
122
    T ret(0);
123
    short flag(1);
124
    char c = getchar();
125
    while(c != '-' && !isdigit(c))c = getchar();
126
    if(c == '-')flag = -1, c = getchar();
127
    while(isdigit(c)){
128
        ret *= 10;
129
        ret += int(c - '0');
130
        c = getchar();
131
    }
132
    ret *= flag;
133
    return ret;
134
}
135

136
/*
137

138
5 6
139
1 2 1 1
140
4 1 6 2
141
5 4 8 1
142
2 3 2 2
143
5 2 4 1
144
3 5 6 4
145

146
*/

T3

原题是：CF510D Fox And Jumping。

差为 1 即可全部覆盖的性质找到了，但是裴蜀定理不太熟悉，没给它转化为 gcd 为 1，所以最后只能打了个暴力。

xxxxxxxxxx
80
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

8
/******************************
9
abbr
10

11
******************************/
12

13
using namespace std;
14

15
mt19937 rnd(random_device{}());
16
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
17

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

22
#define int ll
23

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

27
int N;
28
int len[310], pri[310];
29
ll ans(LLONG_MAX);
30
void bfs(){
31
    queue < pair < int, int > >q;
32
    q.push(make_pair(0, 0));
33
    while(!q.empty()){
34
        int cur, cpri;
35
        tie(cur, cpri) = q.front();
36
        q.pop();
37
        if(cur == 1){
38
            ans = min(ans, cpri);
39
        }
40
        for(int i = 1; i <= N; ++i){
41
            q.push(make_pair(cur + len[i], cpri + pri[i]));
42
            q.push(make_pair(cur - len[i], cpri + pri[i]));
43
        }
44
        if((double)clock() / CLOCKS_PER_SEC > 1.8){
45
            if(ans == LLONG_MAX)printf("-1\n");
46
            else printf("%lld\n", ans);
47
            exit(0);
48
        }
49
    }
50
}
51
signed main(){
52
    freopen("jump.in", "r", stdin);
53
    freopen("jump.out", "w", stdout);
54
    N = read();
55
    for(int i = 1; i <= N; ++i)len[i] = read();
56
    for(int i = 1; i <= N; ++i)pri[i] = read();
57
    // int dep(0);
58
    bfs();
59
    // printf("%lld\n", ans);
60
    // fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
61
    return 0;
62
}
63

64

65

66
template<typename T>
67
inline T read(void){
68
    T ret(0);
69
    short flag(1);
70
    char c = getchar();
71
    while(c != '-' && !isdigit(c))c = getchar();
72
    if(c == '-')flag = -1, c = getchar();
73
    while(isdigit(c)){
74
        ret *= 10;
75
        ret += int(c - '0');
76
        c = getchar();
77
    }
78
    ret *= flag;
79
    return ret;
80
}

T4

原题是：HDU 6611 K Subsequence。

我不会

正解

T1

还挺显然的，简单改了一下没过，咕咕咕

T2

大概是二分答案然后 SPFA 找环，emmmm，这个找时间再弄一下，SPFA 没怎么写过，暂时先咕掉。

T3

正解是状压 DP，因为质因数最多好像就八个。不过这道题可以用 map 优化直接切掉，并且复杂度似乎还是正确的。。。

T4

拆点 + 费用流，挺难我不会，还得再看看费用流。

UPD

update-2022_09_13 初稿