智算之道2020第三场初赛参考代码

布满荆棘的人生 2023-03-06 03:20 7阅读 0赞

# 题目 #

http://oj.csen.org.cn/contest/10?view=problems

# T1 #

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    { 
        int n, L, A, B, temp, V;
        cin >> n >> L >> A >> B;
    
        for(int i = 0; i < n; i++)
        { 
            int type, x;
            cin >> type;
            if(type == 1)
            { 
                cin >> x;
                temp = x;
            }
            else if(type == 2)
            { 
                cin >> x;
                V = x;
            }
            else if(type == 3)
            { 
                if(temp >= A && temp <= B && V >= L)
                { 
                    cout << temp << endl;
                }
                else
                { 
                    cout << "GG" << endl;
                }
            }
        }
        return 0;
    }

# T2 #

#include <cstdio>
    
    const int maxN = 4 * 100007;
    int a[maxN], b[maxN];
    int lastPosA[maxN], lastPosB[maxN];
    bool aHas[maxN], bHas[maxN];
    
    
    int main()
    { 
        //freopen("T2.txt", "r", stdin);
    
    
        int n;
        scanf("%d", &n);
    
        int cntA = 0, cntB = 0, posA = 1, posB = 1;
    
        //第一阶段，摸牌
        for(int i = 1, x; i <= 4 * n - 2; i++)
        { 
            scanf("%d", &x);
    
            if(i % 2)
            { 
                a[posA] = x;
                if(aHas[x])
                { 
                    cntA--;
                }
                else
                { 
                    cntA++;
                    lastPosA[x] = posA;
                }
    
                posA++;
                aHas[x] = !aHas[x];
            }
            else
            { 
                b[posB] = x;
                if(bHas[x])
                { 
                    cntB--;
                }
                else
                { 
                    cntB++;
                    lastPosB[x] = posB;
                }
    
                posB++;
                bHas[x] = !bHas[x];
            }
        }
    
        //第二阶段，抽对方的牌
        bool aliceTurn = true; //Alice先抽
        int ans = 0;
        int j = 1, k = 1;
        while(cntA && cntB)
        { 
            ans++;
            if(aliceTurn)//Alice抽Bob的牌
            { 
                while(j < posB)
                { 
                    if(bHas[b[j]] && lastPosB[b[j]] == j)
                    { 
                        bHas[b[j]] = false; //b[j]被Alice抽走
                        cntB--;
    
                        if(aHas[b[j]])
                        { 
                            cntA--;
                        }
                        else
                        { 
                            cntA++;
                            lastPosA[b[j]] = posA;
                            a[posA++] = b[j];
                        }
                        aHas[b[j]] = !aHas[b[j]];
                        j++;
                        break;
                    }
                    else
                    { 
                        j++;
                    }
                }//for
            }
            else //Bob抽Alice的牌
            { 
                while(k < posA)
                { 
                    if(aHas[a[k]])
                    { 
                        aHas[a[k]] = false; //a[k]被Bob抽走
                        cntA--;
    
                        if(bHas[a[k]])
                        { 
                            cntB--;
                        }
                        else
                        { 
                            cntB++;
                            lastPosB[a[k]] = posB;
                            b[posB++] = a[k];
                        }
    
                        bHas[a[k]] = !bHas[a[k]];
                        k++;
    
                        break;
                    }
                    else
                    { 
                        k++;
                    }
                }//while
            }
    
            aliceTurn = !aliceTurn;
        }//while
    
        printf("%d", ans);
    
        return 0;
    }

# T3 #

#include <cstdio>
    #include <algorithm>
    #include <vector>
    #include <iostream>
    using namespace std;
    
    inline int read()
    { 
        int x=0;
        char t = getchar();
        while(t>'9'||t<'0')
        { 
            t=getchar();
        }
    
        while(t>='0'&&t<='9')
        { 
            x=x*10+t-'0';
            t=getchar();
        }
    
        return x;
    }
    
    const int N = 600000 + 10;
    int n,k;
    vector<int> edge[N];
    int nodeCnt[N];
    
    bool cmp(const int x, const int y)
    { 
        return nodeCnt[x] < nodeCnt[y];
    }
    
    void dfs(int u)
    { 
        nodeCnt[u] = 1;
        for(int i=0; i<edge[u].size(); i++)
        { 
            int v = edge[u][i];
            dfs(v);
            nodeCnt[u] += nodeCnt[v];
        }
    
        sort(edge[u].begin(), edge[u].end(), cmp);
    }
    
    int main()
    { 
        freopen("T3.txt", "r", stdin);
    
        n = read();
        k = read();
    
        for(int v=2, fa; v<=n; v++)
        { 
            fa = read(); //v节点的父节点
            edge[fa].push_back(v);
        }
    
        dfs(1);
    
        typedef long long LL;
        LL ans = 0;
        for(int u=1; u<=n; u++)
        { 
            LL dist = 1;  //第一个子节点离父节点的距离是1
            for(int i=0; i<edge[u].size(); i++)
            { 
                ans += dist;
                int v = edge[u][i];
                dist += nodeCnt[v]; //为计算下一个子节点离父节点的距离作准备
            }
        }
    
        printf("%lld\n", (ans+1)*k);
    
        return 0;
    }

> 长按识别二维码加好友邀请进信息学竞赛群  
> ![在这里插入图片描述][20200804204746836.png]

[20200804204746836.png]: /images/20230208/cbc5a409001344babfcfd68159679f6a.png