首页 > 其他分享 >第33次CSP认证500分题解

第33次CSP认证500分题解

时间:2024-04-06 22:24:13浏览次数:23  
标签:return 33 题解 ++ int while read CSP getchar

近年来最简单的一次 \(CSP\) 认证,\(3\) 个小时现场满分直接拿下。

1、

没啥好说的,直接开桶拿下。

#include <bits/stdc++.h>
using namespace std;
#define N 1000010

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(); }
    return a = x * s; 
}

int n, m; 
map <int, int> g1; 
map <int, int> g2; 

int main(){
    read(n), read(m); 
    for(int i = 1; i <= n; i++){
        int l; read(l); 
        bitset <N> vis(0); 
        for(int j = 1; j <= l; j++){
            int x; read(x); 
            if(!vis[x]) g1[x]++, vis[x] = 1; 
            g2[x]++; 
        }
    }
    for(int i = 1; i <= m; i++){
        cout << g1[i] << " " << g2[i] << endl; 
    }
    return 0; 
}

2、

注意题目要求,不区分大小写,所以全部变成大写或者小写就行。剩下的开个 \(map\) 秒杀。

#include <bits/stdc++.h>
using namespace std;
#define N 1000010

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(); }
    return a = x * s; 
}

int n, m; 
set <string> s1, s2; 

int main(){
    read(n), read(m); 
    for(int i = 1; i <= n; i++){
        string s; cin >> s; 
        for(int j = 0; j < s.length(); j++){
            if(s[j] >= 'A' && s[j] <= 'Z'){
                s[j] = s[j] - 'A' + 'a'; 
            }
        }
        s1.insert(s); 
    }
    for(int i = 1; i <= m; i++){
        string s; cin >> s; 
        for(int j = 0; j < s.length(); j++){
            if(s[j] >= 'A' && s[j] <= 'Z'){
                s[j] = s[j] - 'A' + 'a'; 
            }
        }
        s2.insert(s); 
    }
    int num1 = 0, num2 = 0; 
    for(auto it : s1){
        auto it2 = s2.lower_bound(it); 
        if(it2 != s2.end() && (*it2) == it){
            num1++; 
        }
    }
    for(auto it : s2){
        s1.insert(it); 
    }
    num2 = s1.size(); 
    cout << num1 << endl << num2; 
    return 0; 
}

3、

题目说啥就做啥。这个高斯消元的过程就是个递归,每一层记录左上角坐标。(感觉比直接抄板子还简单)

#include <bits/stdc++.h>
using namespace std;
#define N 210

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(); }
    return a = x * s; 
}

int n, m; 
int T; 
 
double a[200][200], x[N]; 
const double eps = 1e-10; 
inline int sgn(double x){
    return (x > eps) - (x < -eps); 
}



void gauss(int x, int y){ //瀹革缚绗傜憴?
	// cout << x << " " << y << endl; 
    if(x >= n - 1 || y >= m - 1){
        return ; 
    }
    bool flag = 0; 
    for(int i = x; i < n; i++){
        if(abs(a[i][y]) > eps) flag =1; 
    } 
    if(!flag) gauss(x, y + 1); 
    else{
        if(abs(a[x][y]) <= eps){
            for(int j = x + 1; j < n; j++){
                if(abs(a[j][y]) > eps){
                    for(int k = y; k < m; k++){
                        swap(a[j][k], a[x][k]); 
                    }
                    break; 
                }
            }
        }
        for(int i = x + 1; i < n; i++){
            double k = a[i][y] / a[x][y]; 
            for(int j = y; j < m; j++){
                a[i][j] -= k * a[x][j]; 
            }
        }
        gauss(x + 1, y + 1); 
    }
    return ; 
}

int main(){
//	freopen("hh.txt", "r", stdin); 
    read(T); 
    while(T--){
        int n1; 
        read(n1); 
        set <string> s; 
        map <string, int> g;
        int cnt = 0; 
        memset(a, 0, sizeof(a)); 
        for(int i = 1; i <= n1; i++){
            string t; cin >> t;
            
            for(int j = 0; j < t.length(); ){
                string tmp = ""; 
                while(j < t.length() && isalpha(t[j])){
                    tmp.push_back(t[j]); 
                    j++;    
                }
                int x = 0; 
                while(j < t.length() && isdigit(t[j])){
                    x = x * 10 + (t[j] - '0'); 
                    j++; 
                }
                s.insert(tmp); 
                if(!g.count(tmp)) g[tmp] = cnt++; 
                a[g[tmp]][i-1] = x; 
            }
        }
        n = cnt, m = n1; 
        gauss(0, 0); 
        
        int sum = 0; 
        for(int i = 0; i < n; i++){
            bool flag = 0; 
            for(int j = 0; j < m; j++){
                if(abs(a[i][j]) >= eps) flag = 1; 
            }
            sum += flag; 
        }
        if(sum >= n1) cout << "N" << endl; 
        else cout << "Y" << endl; 

    }

    return 0; 
}

4、

有史以来最简单的第四题。可以发现,我们只关心水滴的坐标大小关系,并不关心其具体值是多少。所以,直接用 \(set\) 存下所有的坐标,每次用 \(lowerbound\) 查找目标水滴,然后再将其左右两端进行更新。如果有多个待删水滴,则使用一个优先队列,按照下标排序即可。

#include <bits/stdc++.h>
using namespace std;
#define N 210

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(); }
    return a = x * s; 
}

int c, m, n; 

struct node{
    int x, w; 

    bool operator < (const node &a) const{
        return x < a.x; 
    }

    bool operator == (const node &a) const{
        return x == a.x && w == a.w; 
    }
} ; 

set <node> s; 

int main(){
	// freopen("hh.txt", "r", stdin);  
    read(c), read(m), read(n); 
    for(int i = 1; i <= m; i++){
        int x, w; 
        read(x), read(w); 
        s.insert((node){x, w}); 
    }
//    cout << "-------" << endl; 
//    for(auto it : s){
//    	cout << it.x << " " << it.w << endl; 
//	}
    for(int i = 1; i <= n; i++){
        int p; read(p); 
        auto it = s.lower_bound((node){p, 0}); 
        auto tmp = *it; 
        s.erase(it); 
        tmp.w += 1; 
        s.insert(tmp); 
        set <int> q; 
        if(tmp.w >= 5){
            q.insert(tmp.x); // 寰呯垎鐐哥殑
        }
        while(!q.empty()){
//        	cout << "-------" << endl; 
            int x = (*q.begin()); q.erase(q.begin()); 
            // cout << x << endl; 
            auto it = s.lower_bound((node){x, 0}); 
            if(it != s.begin()){
                auto it1 = it; 
                it1--; 
                auto tmp1 = *it1; 
                s.erase(it1); 
                tmp1.w++; 
                s.insert(tmp1); 
                if(tmp1.w >= 5){
                    q.insert(tmp1.x); 
                }
            }
            auto it1 = it; 
            it1++; 
            if(it1 != s.end()){
                auto tmp1 = *it1; 
                s.erase(it1); 
                tmp1.w++;
                s.insert(tmp1); 
                if(tmp1.w >= 5){
                    q.insert(tmp1.x); 
                }
            }
            s.erase(it);
			
        }
        cout << s.size() << endl; 
    }
    return 0; 
}

5、

所有问题可以拆分成两个部分。先谈深度的维护问题。可以发现,需要经过的点的数量其实就是这个点现在的深度。又发现,我们可以单独维护其深度,因为每次合并可以视为将其所有子树的深度 \(-1\),所以求 \(dfn\),用树状数组或线段树维护即可。

接着是合并问题。首先考虑暴力合并形式,即每个点开一个 \(set\),合并时遍历所有的儿子,并将全部儿子的儿子插入当前点 \(set\)。超时的原因是合并点的次数过多。发现合并的内容是所有子树,所以考虑启发式合并。在合并时,我们不需要迁移重儿子的 \(set\)。为实现上述过程,考虑对每个点使用指针直接指向一个 \(set\)。修改时直接更改指针即可,避免了 \(set\) 的复制过程。

#include <bits/stdc++.h>
using namespace std;
#define N 500010
#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(); }
    return a = x * s; 
}

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 ; 
} 

set <int> *G[N]; 
set <int> s[N]; 
int n, m; 
int fa[N]; 
ll d[N]; 
int a[N]; 

int deth[N], siz[N], son[N];
int dfn[N], rev[N], id = 0;  

void dfs(int u, int father){
    deth[u] = deth[father] + 1;     
    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]) continue; 
        dfs(v, u); 
        siz[u] += siz[v]; 
        if(siz[v] > maxn){
            maxn = siz[v]; 
            son[u] = v; 
        }
    }
    return ; 
}

void dfs2(int u, int tp){
    dfn[u] = ++id; 
    rev[id] = u; 
    if(!son[u]) return ; 
    dfs2(son[u], son[u]); 
    for(int i = head[u]; i; i = t[i].next){
        int v = t[i].v; 
        if(v == son[u] || v == fa[u]) continue; 
        dfs2(v, tp); 
    }
    return ; 
}

struct Segment_tree{
    struct node{
        int val; 
        int tag; 
    } t[N << 2]; 

    #define lson (o<<1)
    #define rson (o<<1|1)

    inline void pushdown(int o, int l, int r){
        if(t[o].tag){
            int mid = l + r >> 1; 
            t[lson].tag += t[o].tag; 
            t[rson].tag += t[o].tag;
            t[lson].val += t[o].tag * (mid - l + 1); 
            t[rson].val += t[o].tag * (r - mid); 
            t[o].tag = 0; 
        }
        return ; 
    }

    inline void pushup(int o){
        t[o].val = t[lson].val + t[rson].val; 
        return ; 
    }

    void build(int o, int l, int r){
        if(l == r){
            t[o].val = a[rev[l]]; 
            return ; 
        }
        int mid = l + r >> 1; 
        build(lson, l, mid); 
        build(rson, mid + 1, r); 
        pushup(o);
        return ; 
    }

    void update(int o, int l, int r, int in, int end, int k){
        if(l > end || r < in) return ; 
        if(l >= in && r <= end){
            t[o].val += k * (r - l + 1); 
            t[o].tag += k; 
            return ; 
        }
        int mid = l + r >> 1; 
        pushdown(o, l, r); 
        update(lson, l, mid, in, end, k); 
        update(rson, mid + 1, r, in, end, k); 
        pushup(o);
        return ; 
    }

    int query(int o, int l, int r, int x){
        if(l > x || r < x) return 0; 
        if(l == r && l == x){
            return t[o].val; 
        }
        int mid = l + r >> 1; 
        pushdown(o, l, r); 
        return query(lson, l, mid, x) + query(rson, mid + 1, r, x); 
    }

} tree; 

signed main(){
    read(n), read(m); 
    for(int i = 2; i <= n; i++){
        int x; read(x);
        fa[i] = x; 
        s[fa[i]].insert(i); 
        addedge(fa[i], i); 
    }
    for(int i = 1; i <= n; i++){
        read(d[i]); 
        G[i] = (&s[i]); 
    }
    // G[0] = (&s[0]); 
    dfs(1, 0); 
    dfs2(1, 1); 
    for(int i = 1; i <= n; i++){
        a[i] = deth[i]; 
    }
    tree.build(1, 1, n);

    for(int i = 1; i <= m; i++){
        int opt; 
        read(opt); 
        if(opt == 1){
            int x; read(x); 
            if(G[x]->size() == 0){
                cout << 0 << " " << d[x] << endl; 
                continue; 
            }
            int maxn = -1; 
            for(auto it : (*G[x])){
                d[x] += d[it]; 
                if(siz[it] > maxn){
                    maxn = siz[it]; 
                    son[x] = it; 
                }
            }
            
            for(auto it : (*G[x])){
                if(it == son[x]) continue; 
                for(auto it1 : (*G[it])){
                    G[son[x]]->insert(it1); 
                }
            }

            G[x] = G[son[x]]; 

            tree.update(1, 1, n, dfn[x] + 1, dfn[x] + siz[x] - 1, -1); 
            cout << (*G[x]).size() << " " << d[x] << endl; 
        }
        else{
            int x; read(x); 
            cout << tree.query(1, 1, n, dfn[x]) << endl; 
        }
    }
    return 0; 
}  

标签:return,33,题解,++,int,while,read,CSP,getchar
From: https://www.cnblogs.com/wondering-world/p/18118023

相关文章

  • ABC348F 题解
    一些注意点:一看到这种题就应该往bitset的方向想。如果用bitset,就应该跳脱之前的思维,尝试从最朴素的暴力重新想起。看到这道题,发现直接做非常的不可做的样子,考虑bitset。我们可以先枚举左端点\(l\)。这样,当我们枚举\(j\)时,对于所有的\(k\)使得\(a_{k,j}=a_......
  • P3396 哈希冲突
    原题链接题解正常暴力解法如下:#include<bits/stdc++.h>usingnamespacestd;inta[150007];intmain(){intn,m;cin>>n>>m;for(inti=1;i<=n;i++)cin>>a[i];while(m--){charop;cin>>op;i......
  • 网站使用CDN出现ttf woff等字体跨域问题解决方案
    如果cdn域名+资源路径是可以通过浏览器url地址栏打开的那么一般是因为nginx配置的原因,找到nginx的配置文件添加以下代码:# 允许指定域名访问;location ~ .*.(eot|ttf|ttc|otf|eot|woff|woff2|svg)(.*) { add_header Access-Control-Allow-Origin http(s)://......
  • arch安装教程+部分问题解决
    arch安装教程+部分问题解决网络配置#进入iwctliwctl#获取device名称我这里是wlan0,后面注意wlan0替换成你自己devicedevicelist#扫描附近wifistationwlan0scan#获取所有可连接wifi名字stationwlan0get-networksstationwlan0connect[wifi名]#输入密码......
  • CF1149D Abandoning Roads 题解
    Description一张\(n\)个点\(m\)条边的无向图,只有\(a,b\)两种边权(\(a<b\)),对于每个\(i\),求图中所有的最小生成树中,从\(1\)到\(i\)距离的最小值。\(2\leqn\leq70,n-1\leqm\leq200,1\leqa<b\leq10^7\)。Solution先考虑一个最小生成树是什么样的形态,显然保留边权......
  • P10245 Swimming Pool题解
    P10245SwimmingPool题意给你四条边\(abcd\),求这四条边是否可以组成梯形。思路这显然是一道简单的普通数学题。判断是否能构成梯形只需看四条边是否能满足,上底减下底的绝对值小于两腰之和且大于两腰之差。证明过程如图,\(AB=a\),\(BC=b\),\(CD=c\),\(AD=d\)。过点\(D\)......
  • P10244 String Minimization 题解
    P10244StringMinimization题意给你四个长度为\(n\)的字符串,分别是\(abcd\)。你可以选择一个\(i\)然后交换\(a[i]\)和\(c[i]\),并交换\(b[i]\)和\(d[i]\)。求在\(a\)的字典序尽量小的前提下,\(b\)字典序最小是什么。思路本题并不难。只需要在\(a[i]>c[i]\)......
  • CF1929B Sasha and the Drawing 题解
    CF1929B题意给定一个\(n\timesn\)的正方形,已知正方形最多有\(4\timesn-2\)条对角线,要求要有至少\(k\)条对角线经过至少一块黑色方格,求至少要将几条对角线涂成黑色。分析分类讨论:当\(k<=4\timesn-4\)时,就只需要在上下两侧图就行,所以答案是\([\frac{k}{2}]\)。当......
  • CF301B Yaroslav and Time 题解
    CF301B这不最短路的板子题吗?思路用\(ak\)代表走到第\(k\)点时的可恢复单位时间的值。\(i\)到\(j\)的距离是\(\left(\left|xi-xj\right|+\left|yi-yj\right|\right)\timesd-ak\)。再打一下最短路代码,建议Floyd,因为短。ACCode#include<bits/stdc......
  • CF30D King's Problem? 题解
    CF30D题意有\(n+1\)个点,其中的\(n\)个点在数轴上。求以点\(k\)为起点走过所有点的最短距离,允许重复。思路有两种情况:\(k\)在数轴上(如图1)。\(k\)在第\(n+1\)个点上(如图2)。图1:图2:像第一种情况:一定存在数轴上某点\(k\),使得人先走遍\(1\simk\),回来,再走遍......