首页 > 其他分享 >CSP认证2022.12 452分题解

CSP认证2022.12 452分题解

时间：2024-03-06 23:55:40浏览次数：183  
标签：return int 题解 452 CSP id define ll it1

A、现值计算

题解

题目简单易懂，直接写就行了。

import math

n, i = map(float, input().split())
n = int(n)
a = list(map(int, input().split()))
ans = 0.00
for j in range(n + 1):
    ans = ans + math.pow(1 + i, -j) * a[j]
print(ans)

B、训练计划



题解

显然是个拓补排序的模板。正着做一遍，反着做一遍就行。

#include <bits/stdc++.h>
using namespace std;
#define N 400010
#define Log 20
#define ll long long
#define int long long

template <class T>
inline T read(T& a){
    T x = 0, s = 1;
    char c = getchar(); 
    while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + (c ^ '0'); c=  getchar(); }
    a = x * s; 
    return a; 
}

struct node{
    int u, v, w, next; 
} t[N], t1[N]; 

int head[N], head1[N]; 

int bian = 0, bian1 = 0; 
inline void addedge(int u, int v, int w){
    t[++bian] = (node){u, v, w, head[u]}, head[u] = bian; 
    return ; 
}

inline void addedge1(int u, int v, int w){
    t1[++bian1] = (node){u, v, w, head1[u]}, head1[u] = bian1; 
    return ; 
}

int n, m; 
int a[N]; 

int in[N], in1[N]; 
int dis[N]; 

void topo(){
    queue <int> q; 
    for(int i = 1; i <= n; i++){
        dis[i] = 1; 
        if(in[i] == 0) q.push(i); 
    }
    while(!q.empty()){
        int u = q.front(); q.pop(); 
        for(int i = head[u]; i; i = t[i].next){
            int v = t[i].v; 
            dis[v] = max(dis[v], dis[u] + a[u]); 
            in[v]--; 
            if(in[v] == 0) q.push(v); 
        }

    }
    return ; 
}

void topo1(){
    queue <int> q; 
    for(int i = 1; i <= n; i++)
        dis[i] = m - a[i] + 1; 
    for(int i = 1; i <= n; i++)
        if(in1[i] == 0) dis[i] = m - a[i] + 1, q.push(i); 
    while(!q.empty()){
        int u = q.front(); 
        q.pop();  
        for(int i = head1[u]; i; i = t1[i].next){
            int v = t1[i].v; 
            dis[v] = min(dis[v], dis[u] - a[v]);
            in1[v]--; 
            if(in1[v] == 0) q.push(v); 
        }
    }
    return ; 
}

signed main(){
    cin >> m >> n; 
    for(int i = 1; i <= n; i++){
        int x; cin >> x; 
        if(x == 0) continue; 
        addedge(x, i, 0); 
        in[i]++; 
        addedge1(i, x, 0); 
        in1[x]++; 
    }
    for(int i = 1; i <= n; i++){
        cin >> a[i]; 
        // cout << in[i] << endl; 
    }
        
    topo(); 
    // cout << "66666" << endl; 
    bool flag = 1; 
    for(int i = 1; i <= n; i++){
        cout << dis[i] << " "; 
        if(dis[i] + a[i] - 1 > m) flag = 0; 
    }
    cout << endl; 
    if(!flag) return 0; 
    topo1(); 
    for(int i = 1; i <= n; i++){
        cout << dis[i] << " "; 
        if(dis[i] + a[i] > m) flag = 0; 
    }
    return 0; 
}

C、JPEG解码



样例输入

16 11 10 16 24 40 51 61
12 12 14 19 26 58 60 55
14 13 16 24 40 57 69 56
14 17 22 29 51 87 80 62
18 22 37 56 68 109 103 77
24 35 55 64 81 104 113 92
49 64 78 87 103 121 120 101
72 92 95 98 112 100 103 99
26
2
-26 -3 0 -3 -2 -6 2 -4 1 -3 1 1 5 1 2 -1 1 -1 2 0 0 0 0 0 -1 -1

样例输出

62 65 57 60 72 63 60 82
57 55 56 82 108 87 62 71
58 50 60 111 148 114 67 65
65 55 66 120 155 114 68 70
70 63 67 101 122 88 60 78
71 71 64 70 80 62 56 81
75 82 67 54 63 65 66 83
81 94 75 54 68 81 81 87

题解

个人感觉应该是历史上最简单的一个第三题了。说啥做啥就行。唯一的难度就是填图。我这里使用的是\(dfs\)填图，用一个变量表示当前方向（右下、左上），同时判一下转向的边界即可。
四舍五入直接 \(M_{i, j} + 0.5\) 再强转 \(int\) 即可实现。

#include <bits/stdc++.h>
using namespace std;
#define N 400010
#define Log 20
#define ll long long

template <class T>
inline T read(T& a){
    T x = 0, s = 1;
    char c = getchar(); 
    while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + (c ^ '0'); c=  getchar(); }
    a = x * s; 
    return a; 
}

double Q[9][9]; 
int a[N]; 
double M[9][9]; 
double M1[9][9]; 
int n, T; 

void dfs(int x, int y, int id, int dir){
    if(x > 7 || y > 7) return ; 
    M[x][y] = a[id++]; 
    if(x == 0){
        M[x][y+1] = a[id++]; 
        dfs(x + 1, y, id, 2); 
        return ; 
    }
    if(x == 7){
        M[x][y+1] = a[id++]; 
        dfs(x - 1, y + 2, id, 1); 
        return ; 
    }
    if(y == 0){
        M[x+1][y] = a[id++]; 
        dfs(x, y + 1, id, 1); 
        return ; 
    }

    if(y == 7){
        M[x+1][y] = a[id++]; 
        dfs(x + 2, y - 1, id, 2); 
        return ; 
    }
    if(dir == 1){
        dfs(x - 1, y + 1, id, 1);
    }
    else dfs(x + 1, y - 1, id, 2); 
    return ; 
}

double f(int u){
    if(u == 0) return sqrt(0.5); 
    else return 1; 
}

signed main(){
    for(int i = 0; i <= 7; i++)
        for(int j = 0; j <= 7; j++)
            cin >> Q[i][j]; 
    cin >> n; 
    cin >> T; 
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    dfs(0, 0, 1, 1); 
    if(T == 0){
        for(int i = 0; i <= 7; i++){
            for(int j = 0; j <= 7; j++){
                cout << (int)M[i][j] << " "; 
            }
            cout << endl; 
        }
    }
    for(int i = 0; i <= 7; i++){
        for(int j = 0; j <= 7; j++){
            M[i][j] *= Q[i][j]; 
        }
    }
    if(T == 1){
        for(int i = 0; i <= 7; i++){
            for(int j = 0; j <= 7; j++){
                cout << (int)M[i][j] << " "; 
            }
            cout << endl; 
        }
    }

    for(int i = 0; i <= 7; i++){
        for(int j = 0; j <= 7; j++){
            for(int u = 0; u <= 7; u++){
                for(int v = 0; v <= 7; v++){
                    double Pi = acos(-1); 
                    M1[i][j] += f(u) * f(v) * M[u][v] * cos(Pi * (i + 0.5) * (double)u / 8.00) * cos(Pi * (j + 0.5) * (double)v / 8.00); 
                }
            }
            M1[i][j] /= 4.00; 
        }
    }
    for(int i = 0; i <= 7; i++){
        for(int j = 0; j <= 7; j++){
            M1[i][j] += 128; 
            // if(M1[i][j] >= 255) M1[i][j] = 255; 
            // if(M1[i][j] < 0) M1[i][j] = 0; 
        }
            
    }
    if(T == 2){
        for(int i = 0; i <= 7; i++){
            for(int j = 0; j <= 7; j++){
                int x = M1[i][j] + 0.5; 
                if(x >= 255) x = 255; 
                if(x < 0) x = 0; 
                cout << x << " "; 
            }
            cout << endl; 
        }
    }
    return 0; 
}

D、聚集方差


题解

先考虑对于一个节点，我们暴力的求出其所有儿子之后，会得到一个序列。根据定义我们发现，排序之后，一个数字的贡献只跟他左右两边的两个数有关。所以我们可以使用 \(multiset\) 来实现。
考虑一个节点的所有子树，这显然是一个树上合并问题。所以不妨使用 \(dsu on tree\), 保留重儿子，将所有轻儿子直接暴力插入到重儿子的 \(multiset\) 里面，插一下则重新计算一下（因为插入一个数只会影响其两侧的两个值的贡献）。

但是由于本人写的太丑了，居然 \(T\) 了，只能拿到65分。不过网上同思路的满分做法比较多，优化的地方就是在 \(set\) 中提前插入四个极大和极小值，这样可以极大地减小讨论的成本，然后勉强卡过去（毒瘤卡常出题人）

这里献上65分 \(TLE\) 丑陋的代码。

#pragma O(2)
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
#define int long long
#define set multiset

template <class T>
inline void read(T& a){
    T x = 0, s = 1;
    char c = getchar(); 
    while(!isdigit(c)){ if(c == '-')  s = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
    a = x * s;
    return ; 
}

int n, m; 
struct node{
    int u, v, next; 
} t[N << 1]; 
int head[N]; 

int bian = 0;
inline void addedge(int u, int v){
    t[++bian] = (node){u, v, head[u]}, head[u] = bian; 
    t[++bian] = (node){v, u, head[v]}, head[v] = bian; 
    return ; 
}
int a[N]; 

int siz[N], fa[N], son[N]; 

void dfs1(int u, int father){
    fa[u] = father; 
    siz[u] = 1; 
    int maxn = -1;  
    for(int i = head[u]; i; i = t[i].next){
        int v = t[i].v; 
        if(v != fa[u]){
            dfs1(v, u); 
            siz[u] += siz[v]; 
            if(siz[v] > maxn){
                maxn = siz[v]; 
                son[u] = v; 
            }
        }
    }
    return ; 
}

ll ans[N]; 

int get_min(int num, multiset <int> &s){
    auto it = s.lower_bound(num); 
    auto it1 = it; 
        auto it2 = it; 
        if(it != s.begin()) it1--; 
        it2++; 
        int ans = 0; 
        if(it2 == s.end()){
            if(it == s.begin()){
                ans = 0; 
            }
            else{
                ans = (ll)((*it) - (*it1)) * ((*it) - (*it1)); 
            }
        }
        else{
            if(it == s.begin()) ans = (ll)((*it) - (*it2)) * ((*it) - (*it2)); 
            else ans = min((ll)((*it) - (*it1)) * ((*it) - (*it1)), (ll)((*it) - (*it2)) * ((*it) - (*it2))); 
        }
    return ans; 
}

void dfs(int u, multiset <int> &s){
    if(son[u]) dfs(son[u], s); 
    s.insert(a[u]); 
    ll tmp = 0; 
    for(auto it  = s.begin(); it != s.end(); it++){
        auto it1 = it; 
        auto it2 = it; 
        if(it != s.begin()) it1--; 
        it2++; 
        if(it2 == s.end()){
            if(it == s.begin()){
                tmp = 0; 
            }
            else{
                tmp += (ll)((*it) - (*it1)) * ((*it) - (*it1)); 
            }
        }
        else{
            if(it == s.begin()) tmp += (ll)((*it) - (*it2)) * ((*it) - (*it2)); 
            else tmp += min((ll)((*it) - (*it1)) * ((*it) - (*it1)), (ll)((*it) - (*it2)) * ((*it) - (*it2))); 
        }
        // printf("6666\n");  
    }
    // printf("u: %d tmp: %d\n", u, tmp); 
    for(int i = head[u]; i; i = t[i].next){
        int v = t[i].v; 
        if(v == son[u] || v == fa[u]) continue; 
        set <int> s1; 
        dfs(v, s1); 
        for(auto num : s1){
            auto it = s.lower_bound(num); 
            if(it == s.begin()){
                tmp += (ll)((*it) - num) * ((*it) - num); 
                int x = (*it); 
                ll h = get_min(x, s); 
                tmp -= h; 
                s.insert(num); 
                h = get_min(x, s); 
                tmp += h; 
            }
            else if(it == s.end()){
                auto it1 = it; 
                it1--; 
                tmp += ((*it1) - num) * ((*it1) - num); 
                int x = (*it1); 
                ll h = get_min(x, s); 
                tmp -= h; 
                s.insert(num);
                h = get_min(x, s); 
                tmp += h; 
            }
            else{
                auto it1 = it; 
                it1--; 
                int x = *it1, x1 = *it; 
                ll h = get_min(*it1, s); 
                ll h1 = get_min(*it, s); 
                tmp -= h; tmp -= h1; 
                s.insert(num); 
                tmp = tmp + get_min(num, s) + get_min(x, s) + get_min(x1, s); 
            }
        }
    }
    ans[u] = tmp; 
    return ; 
}

signed main(){
    read(n); 
    for(int i = 2; i <= n; i++){
        int f; read(f); 
        addedge(f, i); 
    }
    for(int i = 1; i <= n; i++){
        read(a[i]); 
    }

    dfs1(1, 0); 
    
    multiset <int> s; 
    dfs(1, s); 
    for(int i = 1; i <= n; i++)
        printf("%lld\n", ans[i]);  
    return 0; 
}

E、星际网络


题解

在网上搜了一圈，居然没有找到一篇52分的题解。
题目扯了一大堆，其实就是将\([l_1, r_1]\)中的所有点向 \([l_2, r_2]\) 中的所有点连一条边，然后正反跑两次最短路就行了。
显然直接连边会爆炸。

所以就使用线段树优化建图。先将 \(1\) 号区间连向一个中继点，再将中继点连向 \(2\) 号区间，最后除以 \(2\) 就行。 （注意逆元）。

然而出题人非常的毒瘤，最短路中的边权会非常大。可以发现 \(b == 0\) 时开 \(long long\) 是可以存下的。所以此处仅实现了前 \(52\) 分的情况。
后 \(48\) 分其实就是对边权处理的一个子问题了。本人太懒就懒得写了。（做这些毒瘤题做累了）

52分代码：

#include <bits/stdc++.h>
using namespace std;
#define N 400010
#define Log 20
#define ll long long
#define y1 abdbsdhuhdwiuoh
#define int long long

template <class T>
inline T read(T& a){
    T x = 0, s = 1;
    char c = getchar(); 
    while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
    while(isdigit(c)){ x = x * 10 + (c ^ '0'); c=  getchar(); }
    a = x * s; 
    return a; 
}

struct node{
    int u, v; 
    ll w; 
    int next; 
} t[N * Log], t1[N * Log]; 
int head[N * Log]; 
int bian = 0; 
inline void addedge(int u, int v, ll w){
    t[++bian] = (node){u, v, w, head[u]}, head[u] = bian; 
    return ; 
}

int head1[N * Log]; 
int bian1 = 0; 
inline void addedge1(int u, int v, ll w){
    t1[++bian1] = (node){u, v, w, head1[u]}, head1[u] = bian1; 
    return ; 
}

int rc[N * Log], lc[N * Log]; 
int rootin = 0, rootout = 0; 
int id = 0; 

int n, m; 

#define lson rc[o]
#define rson lc[o]

void buildin(int &o, int l, int r){
    if(l == r){
        o = l; 
        return ; 
    }
    if(!o) o = ++id; 
    int mid = l + r >> 1; 
    buildin(lson, l, mid); 
    buildin(rson, mid + 1, r); 
    addedge(o, lson, 0); 
    addedge(o, rson, 0); 
    addedge1(lson, o, 0); 
    addedge1(rson, o, 0); 
    return ; 
}

void buildout(int &o, int l, int r){
    if(l == r){
        o = l;
        return ; 
    }
    if(!o) o = ++id; 
    int mid = l + r >> 1; 
    buildout(lson, l, mid); 
    buildout(rson, mid + 1, r); 
    addedge(lson, o, 0);
    addedge(rson ,o, 0);  
    addedge1(o, lson, 0); 
    addedge1(o, rson, 0); 
    return ; 
}

void update(int o, int l, int r, int in, int end, int val, ll k, int type){
    if(l > end || r < in) return ; 
    if(l >= in && r <= end){
        if(type == 1){
            addedge(o, val, k); 
            addedge1(val, o, k); 
        }
        else{
            addedge(val, o, k); 
            addedge1(o, val, k); 
        }
        return ; 
    }
    int mid = l + r >> 1;
    update(lson, l, mid, in, end, val, k, type); 
    update(rson, mid + 1, r, in, end, val, k, type); 
    return ; 
}

ll dis[N * Log * 2];
struct Point{
    ll dis; 
    int id; 

    bool operator < (const Point &a) const{
        return dis > a.dis; 
    }
} ; 
bool vis[N]; 

const ll mod = 1e9 + 7; 
ll qpow(ll a, ll b){
    ll sum = 1; 
    while(b){
        if(b & 1) sum = (sum * a) % mod; 
        b >>= 1ll; 
        a = (a * a) % mod; 
    }
    return sum; 
}

void dij(int s){
    memset(vis, 0, sizeof(vis)); 
    for(int i = 1; i <= id; i++)
        dis[i] = 1e16; 
    // cout << dis[1] << endl; 
    priority_queue <Point> q; 
    dis[s] = 0; 
    q.push((Point){0, s}); 
    while(!q.empty()){
        int now = q.top().id; q.pop(); 
        if(!vis[now]){
            vis[now] = 1; 
            for(int i = head[now]; i; i = t[i].next){
                int v = t[i].v; 
                if(dis[v] > dis[now] + t[i].w){
//                	printf("%lld\n", dis[v]); 
//                	printf("%lld\n", t[i].w); 
                    dis[v] = dis[now] + t[i].w; 
                    // cout << dis[v] << endl; 
                    if(!vis[v]) q.push((Point){dis[v], v}); 
                }
            }

        }
    }
    return ; 
}

ll dis1[N]; 
void dij1(int s){
    memset(vis, 0, sizeof(vis)); 
    for(int i = 1; i <= id; i++)
        dis1[i] = 1e16; 
    priority_queue <Point> q; 
    dis1[s] = 0; 
    q.push((Point){0, s}); 
    while(!q.empty()){
        int now = q.top().id; q.pop(); 
        // printf("now: %lld\n", now); 
        if(!vis[now]){
            vis[now] = 1; 
            for(int i = head1[now]; i; i = t1[i].next){
                int v = t1[i].v; 
                if(dis1[v] > dis1[now] + t1[i].w){
                    dis1[v] = dis1[now] + t1[i].w; 
                    if(!vis[v]) q.push((Point){dis1[v], v}); 
                }
            }

        }
    }
    return ; 
}

signed main(){
    //   freopen("hh.txt", "r", stdin); 
    //   freopen("out.txt", "w", stdout); 
    read(n), read(m); 
    id = n; 

    buildin(rootin, 1, n); 
    buildout(rootout, 1, n); 

    for(int i = 1; i <= m; i++){
        id++; 
        int l1, r1, l2, r2; ll a, b; 
        cin >> l1 >> r1 >> l2 >> r2 >> a >> b; 
        update(rootout, 1, n, l1, r1, id, a * qpow(2, b), 1); 
        update(rootin, 1, n, l2, r2, id, a * qpow(2, b), 2); 
    }

    dij(1); 
    dij1(1); 
    for(int i = 2; i <= n; i++){
        if(dis[i] >= 1e16 || dis1[i] >= 1e16) cout << -1 << " "; 
        else cout << ((dis[i] % mod + dis1[i] % mod) % mod * qpow(2, mod - 2)) % mod << " "; 
    }
    return 0; 
}

标签：return,int,题解,452,CSP,id,define,ll,it1
From： https://www.cnblogs.com/wondering-world/p/18057896

相关文章

  • .NET Core WebAPI项目部署iis后Swagger 404问题解决
    .NETCoreWebAPI项目部署iis后Swagger404问题解决前言之前做了一个WebAPI的项目，我在文章中写到的是Docker方式部署，然后考虑到很多初学者用的是iis，下面讲解下iis如何部署WebAPI项目。环境准备iisASPNETCoreModuleV2重点.NETCoreRuntimeiis的配置这里就不讲了，主要讲解......
  • 【转】[Java]引入Redisson可能会出现项目启动失败问题解决
    转自：https://blog.csdn.net/bengbuguang4321/article/details/121951650在启动项目时，Redisson自己会启动一个Redisson连接池，尝试连接redis，这时候如果遇到网络不通就会出现问题，因为redis连接不上，导致项目启动不了解决方法是：1、重新空实现了一个RedissonClient/***@ClassNa......
  • ABC323E Playlist 题解
    考虑第\(i\)时刻时，第\(j\)首歌刚好结束与第\(i-j\)时刻有关，因此设\(dp_{i,j}\)表示第\(i\)时刻第\(j\)首歌刚好结束的概率，那么\(dp\)转移方程为：\[dp_{i,j}=\sum\limits_{k=1}^ndp_{i-t_j,k}\]很容易想到记录\(\sum\limits_{j=1}^ndp_{i,j}\)的值为\(sum_i\)，......
  • 初三组合恒等式和二项式定理练习 题解
    A.多项式推柿子：\[\begin{aligned}&\sum\limits_{k=0}^{n}b_{k}(x-t)^{k}\\=&\sum\limits_{k=0}^{n}b_{k}\sum\limits_{i=0}^{k}\binom{k}{i}x^{i}(-t)^{k-i}\\=&\sum\limits_{0\leqslanti\leqslantk\leqslantn}\binom{k}{i}b_{......
  • 2023 CSP 游记
    目录\(\text{CSP-J}\)游记\(\text{CSP-S}\)游记\(\text{CSP-J}\)游记省流：\(\text{B}\)题挂了\(100\text{pts}\)，悲！\(\text{Day-INF}\)初赛\(75.5\)没考过几位大佬。\(\text{悲.jpg}\)\(\text{Day0}\)有点慌，去吃了顿饭，晚上的模拟赛就咕了。怕影响心态，没再......
  • 2024 联合省选 题解
    D1T1季风考虑要求\(\begin{cases}\sum\limits_{i=0}^{m-1}(x'_i+x_{i\bmodn})=x\\\sum\limits_{i=0}^{m-1}(y'_i+y_{i\bmodn})=y\\|x'_i|+|y'_i|\lek\end{cases}\)发现其等价于\(|x-\sum\limits_{i=0}^{m-1}x_{i\bmodn}|+|y-\sum\l......
  • Chests and Keys 题解
    题意：给定\(n,m\)表示存在\(n\)个宝箱和\(m\)把钥匙，第\(i\)把钥匙需要\(b_i\)元，第\(i\)个宝箱内部有\(a_i\)元。现在进行一场游戏，Bob是本场游戏的玩家，而Alice则是场景布置者，Alice可以给每个宝箱上一些锁（第\(j\)种锁需要第\(j\)种钥匙打开）如果Bob可以购......
  • Linux使用问题之长时间连接ssh不操作自动断开问题解决方案
    1.概要一般情况下，在使用SSHSecureShellClient的过程中，经常会遇到当用SSHSecureShell连接登录Linux后，如果几分钟没有任何操作，连接就会自动断开，提示Serverresponded"Connectionclosed."，必须重新登录才可以。2.原理主要由以下两个参数控制：ClientAliveInterval：指定了服......
  • springboot 应用程序 pom节点版本冲突问题解决思路
    springboot应用程序pom节点版本冲突问题解决思路一、首先 mavenhelper 查看是否有冲突 conflicts 二、allDenpendencies  查询如poi 查询冲突 ps: <scope>compile</scope>  compile:这是默认的依赖项范围。指定为compile的依赖项将在编译、测试和......
  • [AGC016D] XOR Replace 题解
    题意：一个序列\(a\)，一次操作可以将某个位置变成整个序列的异或和。求最少几步到达目标序列\(b\)。\(n\le10^5\)思路：见到这种题，第一步要去尝试把操作转化。稍微推一下可以发现，如果\(\oplus_{i=1}^na_i=s\)，则相当于一个\(n+1\)长序列，\(a_{n+1}=s\)，每次可以交换\(a......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99