Kyooma's Blog

2022-09-23周赛

  • ~14.68K 字

题目来自2021-2022 ACM-ICPC Latin American Regional Programming Contest

y1s1题是真的难读, 英语水平捉急了…(由于当天有新生宣讲会, 这场只打了4h)

K - KIARA is a Recursive Acronym

签到

问在给出的 个字符串中否存在一个可以由 个字符串的首字符组成的串

但是不知道为啥被卡常了一发(

CODE
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef unsigned long long ull;
#define fi first
#define se second
const int N=1e6+10;
const int mod=1e9 + 7;
const int G=3;
const int GI=332748118;
const int MOD = 1e9 + 7;
const int INF=1e9;

int c[26];

void solve(){
    int n,i,j,x,y;
    cin >> n;
    vector<string> v;
    for(i = 0; i < n; i++){
        string s;
        cin >> s;
        c[s[0] - 'A'] = 1;
        v.push_back(s);
    }
    for(auto s : v){
        int ok = 1;
        for(char ch : s){
            if(!c[ch - 'A']) ok = 0;
        }
        if(ok){
            cout << "Y\n";
            return;
        }
    }
    cout << "N\n";
}
int main() {
    int T=1;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    while (T--) {
        solve();
    }
}

F - Fields Division

签到

给一张$n$点$m$边的连通图, 第$i$个点有$2^i$的权值, 需要将该图的点分成AB两部分, 使得各部分内部的点互相连通, 且两部分权值和尽可能相等, 若做不到相等的话使A部分权值大于B部分

SOLUTION

由于点权是$2^i$, 所以必定不可能做到两部分权值相等, 只需要A先拿$n$号点, B拿$n-1$号点及其所有与该点相连通的点, 剩余点全给A即可

(题目说有多解, 可是想了想不管怎么样这个解都是唯一的)

CODE
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef unsigned long long ull;
#define fi first
#define se second
const int N=3e5+10;
const int mod=1e9 + 7;
const int G=3;
const int GI=332748118;
const int MOD = 1e9 + 7;
const int INF=1e9;
int a[N],n;
int vis[N];
vector<int>e[N];
void dfs(int x){
    if(vis[x]) return;
    a[x]=1;
    vis[x]=1;
    for(auto i:e[x]){
        dfs(i);
    }
}
void solve(){
    int i,j,x,y,m;
    cin>>n>>m;
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    vis[n]=1;
    dfs(n-1);
    for(i=1;i<=n;i++){
        if(a[i]) printf("B");
        else printf("A");
    }
}
int main() {
    int T=1;
    while (T--) {
        solve();
    }
}

I - Invested Money

签到?

本该是签到题, 可是我们签了1h…(读题读不懂了….

给出今天是一周的第几天, 以及距离$n$次存款日过了几天

规定只能在存款后的每30天才能有一次取款机会, 若在周末则延迟到周一, 下一次取款日会在上一个可取款日的30日后, 询问距离最近的下一次取款日还需要几天

SOLUTION

只需反推出存款日, 然后分类讨论一下就行了

因为是这么循环的: 2 -> 4 -> 1 -> 3 -> 5 - > 1 -> …

CODE
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef unsigned long long ull;
#define fi first
#define se second
const int N=3e5+10;
const int mod=1e9 + 7;
const int G=3;
const int GI=332748118;
const int MOD = 1e9 + 7;
const int INF=1e9;

int calc(int m, int now){
    int x = m % 91;
    if(x == 0 && m){
        return 0;
    }else{
        if(now == 1){
            if(x <= 30){
                return 30 - x;
            }else if(x <= 60){
                return 60 - x;
            }else{
                return 91 - x;
            }
        }else if(now == 3){
            if(x <= 30){
                return 30 - x;
            }else if(x <= 61){
                return 61 - x;
            }else{
                return 91 - x;
            }
        }else{
            if(x <= 31){
                return 31 - x;
            }else if(x <= 61){
                return 61 - x;
            }else{
                return 91 - x;
            }
        }
    }
}

void solve(){
    int n,i,j,x,y,m,d,k,ans=100;
    string s;
    cin>>s>>n;
    if(s=="Mon") d=1;
    if(s=="Tue") d=2;
    if(s=="Wed") d=3;
    if(s=="Thu") d=4;
    if(s=="Fri") d=5;
    if(s=="Sat") d=6;
    if(s=="Sun") d=7;
    for(i=1;i<=n;i++){
        scanf("%d", &m);
        int now = (d - m) % 7;
        if(now <= 0) now += 7;
        if(now == 1 || now == 3 || now == 5){
            k = calc(m, now);
        }else{
            if(now == 2){
                if(m <= 30){
                    k = 30 - m;
                }else if(m <= 62){
                    k = 62 - m;
                }else{
                    k = calc(m - 62, 1);
                }
            }else{
                if(m <= 32){
                    k = 32 - m;
                }else{
                    k = calc(m - 32, 1);
                }
            }
        }
        ans = min(ans, k);
    }
    printf("%d",ans);
}
int main() {
    int T=1;
    while (T--) {
        solve();
    }
}

M - Most Ordered Way

给出$n$个工程, 每个工程需要做$t$分钟, 截止时间为$d$, 求一个字典序最小的合法序列, 或者无解

SOLUTION

贪心

显然, 若没有字典序最小的条件, 直接对$d$从小到大排序即可

但是需要字典序最小, 那么考虑贪心, 先对$d$从小到大排序, 求出一种可行解, 然后考虑能否改变某几个的顺序来做到使字典序变小

于是可以考虑让第$j$个元素排到第$i$个元素的前面, 那么收到影响的只有第$i$个和第$j$个之间的元素, 若改变顺序后该序列依旧合法, 那么就让第$j$个元素排到第$i$个元素的前面即可

稍微推一下就会发现合法的条件有两个: $sump + t_j \le d_p (i\le p \le j)$ 以及 $sum{i-1} + t_j \le d_j$

对于第一个式子, 只需要维护$sum_p - d_p$的最大值即可

时间复杂度: $O(n^2)$

CODE
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef unsigned long long ull;
#define fi first
#define se second
const int N=5000+10;
const int mod=1e9 + 7;
const int G=3;
const int GI=332748118;
const int MOD = 1e9 + 7;
const int INF=1e9;

struct node{
    int t, d, id;
    bool operator < (const node &p) const{
        return d < p.d;
    }
}a[N];

ll sum[N];

void solve(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &a[i].t, &a[i].d);
        a[i].id = i;
    }
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++){
        sum[i] = sum[i - 1] + a[i].t;
        if(sum[i] > a[i].d){
            puts("*");
            return;
        }
    }
    for(int i = 1; i <= n; i++){
        ll mx = sum[i] - a[i].d;
        int pi = i;
        for(int j = i + 1; j <= n; j++){
            if(a[j].id < a[pi].id){
                if(mx + a[j].t <= 0 && sum[i - 1] + a[j].t <= a[j].d){
                    pi = j;
                }
            }
            mx = max(mx, sum[j] - a[j].d);
        }
        if(pi != i){
            node tmp = a[pi];
            for(int j = pi; j > i; j--) a[j] = a[j - 1];
            a[i] = tmp;
            for(int j = 1; j <= n; j++){
                sum[j] = sum[j - 1] + a[j].t;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        printf("%d%c", a[i].id, i == n ? '\n' : ' ');
    }
}

/*
4
5 50
4 40
3 30
2 10
 */
int main() {
    int T=1;
    while (T--) {
        solve();
    }
}

J - Joining Pairs

给出一个网格图和$n$对点, 问是否存在一种画法使得$n$对点的连线不相交

SOLUTION

显然只有横跨了整个网格的线有可能会相交, 即两端点都在边界上的点对(以下只考虑这种点对)

于是可以顺时针遍历边界, 用一个栈存第一次遇到的点对, 当遇到这对点的第二个点时, 如果此时栈顶不是这点对的另一个点, 那必定是会产生相交的线的, 所以离散化后遍历即可

CODE
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef unsigned long long ull;
#define fi first
#define se second
const int N=1e5+10;
const int mod=1e9 + 7;
const int G=3;
const int GI=332748118;
const int MOD = 1e9 + 7;
const int INF=1e9;

struct node1{
    int id,x;
}a[N],c[N];
struct node2{
    int id,x;
}b[N],d[N];
bool cmp1(node1 x,node1 y){
    return x.x<y.x;
}
bool cmp2(node2 x,node2 y){
    return x.x>y.x;
}
int w,h;
int chk(int x,int y){
    if(x==0||x==w) return 1;
    if(y==0||y==h) return 2;
    return 0;
}
void solve(){
    int n,i,x,y,ans,x1,x2,y1,y2,c1,c2,c3,c4;
    cin>>w>>h>>n;
    c1=c2=c3=c4=0;
    for(i=1;i<=n;i++){
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        if(chk(x1,y1)&&chk(x2,y2)){
            if(chk(x1,y1)==1){
                if(x1==0) b[++c2]={i,y1};
                else c[++c3]={i,y1};
            }
            else{
                if(y1==0) a[++c1]={i,x1};
                else d[++c4]={i,x1};
            }
            if(chk(x2,y2)==1){
                if(x2==0) b[++c2]={i,y2};
                else c[++c3]={i,y2};
            }
            else{
                if(y2==0) a[++c1]={i,x2};
                else d[++c4]={i,x2};
            }
        }
    }
    sort(a+1,a+c1+1,cmp1);
    sort(c+1,c+c3+1,cmp1);
    sort(b+1,b+c2+1,cmp2);
    sort(d+1,d+c4+1,cmp2);
    stack<int>s;
    for(i=1;i<=c1;i++){
        x=a[i].id;
       // printf("%d ",x);
        if(!s.empty()&&s.top()==x){
            s.pop();
        }
        else{
            s.push(x);
        }
    }
    for(i=1;i<=c3;i++){
        x=c[i].id;
//        printf("%d ",x);
        if(!s.empty()&&s.top()==x){
            s.pop();
        }
        else{
            s.push(x);
        }
    }
    for(i=1;i<=c4;i++){
        x=d[i].id;
//        printf("%d ",x);
        if(!s.empty()&&s.top()==x){
            s.pop();
        }
        else{
            s.push(x);
        }
    }
    for(i=1;i<=c2;i++){
        x=b[i].id;
//        printf("%d ",x);
        if(!s.empty()&&s.top()==x){
            s.pop();
        }
        else{
            s.push(x);
        }
    }
    if(s.size()) printf("N");
    else printf("Y");
}

int main() {
    int T=1;
    while (T--) {
        solve();
    }
}

H - Hamilton - The Musical

给出$n$个点两两之间的距离$L{ij}$, 定义一个$n$的排列$p_1, p_2, …, p_n$的权值为$$\sum L{pi p{i+1}}$$

现规定$p_i=i$ $(i\mod2 = 0)$, 求最小的权值

SOLUTION

费用流, 题意可转化为对于剩下的奇数点, 还有奇数个位置做一个最小权的完美匹配, 所以可以直接跑费用流解决, 边权为$i$点在$j$位置时与左右两点的距离和

(复杂度手算了一下大概是$n^3$的, 而时限是0.5s, 没想到还真过了)

CODE
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
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pll;
const int N = 500 + 10, M = 1e6;
const ll inf = 1e15;

struct Edge{
    int to, ne;
    ll w, fee;
}e[M];

int head[N], idx;
int pre[N], id[N];
int s, t, n;
ll dist[N], flow[N], h[N];
bool vis[N];

void init(){
    idx = 0;
    memset(head, -1, sizeof(head));
}

void _add(int a, int b, ll c, ll fee){
    e[idx] = {b, head[a], c, fee};
    head[a] = idx++;
}

void add(int a, int b, ll c, ll fee){
    _add(a, b, c, fee);
    _add(b, a, 0, -fee);
}

int dij() {
    for(int i = 1; i <= n; i++){
        vis[i] = false;
        dist[i] = inf;
        flow[i] = inf;
    }
    dist[s] = 0;
    pre[t] = -1;
    priority_queue<pll, vector<pll>, greater<pll>> q;
    q.push({dist[s], s});
    while(!q.empty()){
        int x = q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x] = true;
        for(int i = head[x]; i != -1; i = e[i].ne){
            int to = e[i].to;
            ll w = e[i].w, fee = e[i].fee;
            if(w && dist[to] > dist[x] + h[x] - h[to] + fee){
                dist[to] = dist[x] + h[x] - h[to] + fee;
                flow[to] = min(flow[x], w);
                pre[to] = x;
                id[to] = i;
                q.push({dist[to], to});
            }
        }
    }
    return dist[t] != inf;
}

ll Minfee(){
    ll minfee = 0, maxflow = 0;
    while(dij()){
        for(int i = 1; i <= n; i++){
            h[i] += dist[i];
        }
        int now = t;
        maxflow += flow[t];
        minfee += flow[t] * h[t];
        while(now != s){
            e[id[now]].w -= flow[t];
            e[id[now] ^ 1].w += flow[t];
            now = pre[now];
        }
    }
    return minfee;
}

int dis[N][N];

void solve() {
    int pn;
    cin >> pn;
    for(int i = 1; i <= pn; i++){
        for(int j = 1; j <= pn; j++){
            cin >> dis[i][j];
        }
    }
    int m = (pn + 1) / 2;
    n = 2 * m + 2;
    t = n;
    s = n - 1;
    init();
    for(int i = 1, p = 1; i <= pn; i += 2, p++){
        add(s, p, 1, 0);
        add(p + m, t, 1, 0);
        for(int j = 1; j <= m; j++){
            int pre = (j - 1) * 2, now = pre + 2;
            if(pre == 0){
                add(p, j + m, 1, dis[i][now]);
            }else if(now > pn){
                add(p, j + m, 1, dis[i][pre]);
            }else{
                add(p, j + m, 1, dis[i][pre] + dis[i][now]);
            }
        }
    }
    ll ans = Minfee();
    cout << ans << '\n';
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // cin >> T;
    while (T--) solve();
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可