成信天梯赛补题

(Updated: )
算法 › 补题

L1-6

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
#include<bits/stdc++.h>
using namespace std;
/*
 * 给定日期计算距离1349-06-28多少天
 * 就是找一个基准日期0001-01-01, 算距离它有多少天, 然后做差就行了
 */

int is_leap(int y){
    return ((y % 4 ==0 && y % 100 != 0) || y % 400 == 0) ;
}

int mons[]{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int getToday(int y, int m, int d) {
    int total = 0;

    for(int i = 1;i < y; ++i) total += 365 + is_leap(i);

    for(int i = 1;i < m; ++i) total += (i == 2 ? is_leap(y) : 0) + mons[i];

    total += d;

    return total;
}

signed main() {
    int y, m, d; char c, cc;
    cin >> y >> c >> m >> cc >> d;
    int total_len = getToday(y, m, d);
    int base_len = getToday(1349, 6, 28);

    int len = total_len - base_len;

    if(len == 0) cout << "jiu shi today.";
    else if(len > 0) cout << "hai cha " << len << " day!";
    else if(len < 0) cout << "guo qv le " << -len << " day?";
    return 0;
}

L1-8

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
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
/*
 * 给定 n, m, k分别代表有 n 项, 每项有 m 个 p_i 值, 每个 p_i 最大为 k
 * 给定 s_i p_i1 p_i2 ... p_im
 * 其中 p_ij = -1 代表未定值, 可以赋值 0~k, n * m <= 4e5
 *
 * 求是否可以赋值后满足:
 * 1. 当 s_i > s_j 时, p_i 的和 > p_j 的和
 * 2. 当 s_i = s_j 时, p_i 的和 与 p_j 的和没有固定大小关系
 *
 * 题解:
 * 这是复杂的模拟题, 构造结构体存每个的值
 * 每项可以算出 p_i和的上限和下限 (mn, mx), 其中 mn 就是未定项全取0, mx 就是全取 k
 * 按照 s 排序, 每一项都尽量取最大值, 对于第 i 项, 如果上一项的最大值 -1 > mn_i , 那么第 i 项就可以取上一项的最大值-1, 否则就不满足题意
 * 注意如果上一项和当前项的 s 是一样的, 那么他们最大值也可以一样
 */
struct People{
    int id, s, mn, mx;
    vector<int> p;
    People(){}
    People(int n):p(vector<int> (n)){}
    bool operator < (const People& a)const {
        if(s != a.s) return s > a.s;
        return mx > a.mx;
    }
};

void deal(){
    int n, m, k; cin >> n >> m >> k;
    vector<People> peo(n, People(m));
    for(int i = 0;i < n; ++i) {
        peo[i].id = i;
        cin >> peo[i].s;
        int mx = 0, mn = 0;
        for(int j = 0;j < m; ++j) {
            cin >> peo[i].p[j];
            if(peo[i].p[j] != -1) mn += peo[i].p[j];
            else mx += k;
        }
        peo[i].mn = mn;
        peo[i].mx = mx + mn;
    }
    sort(peo.begin(), peo.end());

    int cur = peo[0].mx;
    for(auto &p : peo[0].p) if(p == -1) p = min(k, cur);

    for(int i = 1;i < n; ++i) {
        if(peo[i].s != peo[i-1].s) cur --;

        if(cur < peo[i].mn) {
            cout << "No\n";
            return;
        }

        cur = min(peo[i].mx, cur);
        int dec = cur - peo[i].mn;

        for(auto &p : peo[i].p){
            if(p ==-1) p = min(dec, k), dec -= min(dec, k);
        }
    }
    cout << "Yes\n";
    sort(peo.begin(), peo.end(), [](const People& a, const People& b) {
        return a.id < b.id;
    });

    for(int i = 0;i < n; ++i){
        for(int j = 0;j < peo[i].p.size();++j) cout << (j ? " " : "") << peo[i].p[j] ;
        cout << endl;
    }
}

void solve(){
    int t; cin >> t;
    while(t--) deal();
}

L2-1

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
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
/*
 * 有一棵树, 多连了一条边就成了环,
 * 给定边, 求删除哪个边可以把环还原成树,
 * 有多个边就删除最大的编号的边
 * 题解:
 * 我想错了, 这实际上是个并查集, 如果合并的两个端点都是同一个并查集中的内容, 那么就会形成环, 同时这个边就是最大编号的边
 */

const int N = 1e5 + 10;
int fa[N];

void init(){
    for(int i = 1;i < N; ++i) fa[i] = i;
}

int find(int x){
    if(x != fa[x]) return fa[x] = find(fa[x]);
    return fa[x];
}

void merge(int x, int y) {
    fa[find(x)] = find(y);
}

void solve(){
    init();
    int n; cin >> n;
    int x, y;

    int idx = 0;
    for(int i = 1; i <= n ;++i) {
        cin >> x >> y;
        if(find(x) == find(y)) {
            idx = i;;
            cout << idx << endl;
            return;
        }
        merge(x, y);
    }
}

L2-4

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
#include <queue>
#include <vector>
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
/*
 * n 个节点的图, 每个节点有一个权值, 连接节点间的边也有权值,
 * 求从节点 s 到节点 d的最短路径的数量, 和在最短路径中能够收集的最大权值和
 * 题解:
 * dijistra的变形
 * 在从当前点, 也就是循环的节点中, 当前节点就是当前节点的最短路, 那么从当前节点到其他节点如果比其他节点的最短路段, 就更新最短路, 同时入队
 * 如果和其他节点的距离一样, 那么就更新路径数量和最大权值和
 */
constexpr int N = 5e4 + 10;
struct Edge{
    int u, w;
};

struct Node {
    int id, dis;
    Node(){}
    Node(int id, int dis):id(id), dis(dis){}
    bool operator < (const Node & a)const {
        return dis > a.dis;
    }
};

vector<Edge> e[N];
int dis[N], path[N], cnt[N], member[N];
void dijistra(int s, int d){
    priority_queue<Node> q;
    memset(dis, 0x3f, sizeof(dis));
    q.push({s, 0});
    dis[s] = 0;
    path[s] = 1;
    cnt[s] = member[s];

    while(!q.empty()) {
        int id = q.top().id, dist = q.top().dis; q.pop();
        if(id == d) {
            return;
        }
        if(dis[id] < dist) continue;


        for(auto &[u, w] : e[id]) {
            if(dist + w < dis[u]) {
                dis[u] = dist + w;
                path[u] = path[id];
                cnt[u] = member[u] + cnt[id];
                q.push({u, dis[u]});
            }else if(dist + w == dis[u]) {
                path[u] += path[id];
                cnt[u] = max(cnt[u], member[u] + cnt[id]);
            }
        }
    }
}

void solve(){
    int n, m, s, d; cin >> n >> m >> s >> d;
    for(int i = 0;i < n; ++i) cin >> member[i];
    for(int i = 0;i < m; ++i)  {
        int u, v, w; cin >> u >> v >> w;
        e[u].push_back({v,w});
        e[v].push_back({u, w});
    }

    dijistra(s, d);
    cout << path[d] << ' ' << cnt[d]  ;

}

signed main() {
    hello;

    solve();

    world;
}

L3-1

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
#include <climits>
#include <pthread.h>
#include <vector>
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
/*
 * 从节点 1 出发, 遍历所有节点(每个节点恰好访问一次), 最后到达节点 n , 求路径总权值的最小值
 * 给u v 代表 节点u, v之间有边
 * 题解:
 * 旅行商问题
 * 注意状态压缩 dp[mask][i] 表示走过了 mask , 最后到达节点 i
 * 注意题目使用 1-base 的节点, 需要转换为 0-base 的节点
 * 状态转移中, 可以检查确保 从 j 到 i 的转移时, dp[mask ^ (1<><i)][j] 需要存在
 */

constexpr int N = (1 << 18 ) + 10;
int edge[20][20], dp[N][20];

void solve(){
    int n, m, h; cin >> n >> m >> h;
    for(int i = 1;i <= m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        u--;v--;
        edge[u][v] = edge[v][u] = w;
    }
    for(int i = 0;i < 1LL<<n; ++i) for(int j = 0;j < n; ++j) dp[i][j] = LLONG_MAX;
    dp[1][0] = 0;

    for(int mask = 1; mask < 1LL<< n; ++mask) {
        for(int i = 0; i < n; ++i) {
            for(int j = 0;j < n; ++j) {
                if(j != i && (mask >> j) & 1 && edge[i][j] && dp[mask ^ (1<<i)][j] < dp[0][0]) {
                    dp[mask][i] = min(dp[mask][i], dp[mask ^ (1<<i)][j] + edge[i][j]);
                }
            }
        }
    }

    int csu = dp[(1<<n)-1][n-1];
    if(csu > h) {
        cout << "No\n";
        cout << csu - h + 1;
    }else {
        cout << "Yes\n";
        cout << h - csu;
    }
}

signed main() {
    hello;

    solve();

    world;
}

L3-2

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

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

/*
 * 计算最少插入多少个字符让这个字符串成为**回文序列**
 */

constexpr int N = 4568;
int dp[N][N];
void solve(){
    int n; cin >> n;
    string s; cin >> s;
    string t = s;
    s = "0"+s;
    reverse(t.begin(), t.end());
    t = "0"+t;
    for(int i = 1; i <= n; ++i) dp[0][i] = dp[i][0] = i;

    for(int i = 1;i <= n; ++i){
        for(int j = 1;j <= n; ++j){
            if(s[i] == t[j]) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = min(dp[i-1][j], dp[i][j-1])+1;
        }
    }
    cout << dp[n][n]/2;
}

signed main() {
    hello;
    solve();

    world;
}