首页 > 其他分享 >2024XJTUPC西安交通大学校赛VP题解

2024XJTUPC西安交通大学校赛VP题解

时间：2024-05-25 20:22:51浏览次数：25  
标签：const int 题解 cin long VP double using 校赛

每次vp都自闭，已成习惯，时间还是分配的不合理，debug时做太多无用功。
一键做题

A.交小西的礼物

输出 a + b + 2c + 3d 即可

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int mod = 998244353;
const int N = 1e5 + 7;
void solve()
{
    ll a,b,c,d;
    cin >> a>> b >> c>> d;
    cout << a + b + c*2 + d *3 << '\n';
}

C.榕树之心

直接按题目要求计算

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
const int N = 1e5 + 7;
const int mod = 998244353;

void solve()
{
    double x, y;
    cin >> x >> y;
    double x0 = 0.5 * x + 0.5 * y;
    double y0 = sqrt(3) * 0.5 * x - sqrt(3) * 0.5 * y;
    cout << fixed << setprecision(7) << x0 << " " << y0 << '\n';
}

B.转呀转

直接用半径和圆心角求弦长即可，注意sin中参数是弧度制

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int mod = 998244353;
const int N = 1e5 + 7;
const double pi = acos(-1.0);
void solve()
{
    double x, y;
    cin >> x >> y;
    double r = (x * x) + y * y;
    r = sqrt(r);
    double t;
    cin >> t;
    double v;
    cin >> v;
    v = 1.0 / v;
    double p = t / v;
    p = p - (int)p;
    double q = 1.0 - p;
    if (p > q)
        swap(p, q);
    double ans = p * pi;
    ans = sin(ans) * 2.0 * r;
    cout << fixed << setprecision(8) << ans << '\n';
}

F.Everyone’s ALL IN

预处理计算即可

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int mod = 998244353;
const int N = 1e6 + 7;
const double pi = acos(-1.0);
vector<int>g[N];
void solve()
{
    int n,m;
    cin>>n>>m;
    map<ll,ll>mp;
    for(int i=1;i<=n;i++)
    {
        ll x;
        cin>>x;
        g[x].push_back(i);
        mp[x]+=i;
    }
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        cout<<1ll*mp[x]*mp[y]<<endl;
    }
}

D.瑟莉姆的宴会

直接构造菊花图即可，对于每个点的正负贡献都计算一下，如果该点非负，即以该点为根构造菊花图

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int mod = 998244353;
const int N = 1e6 + 7;
const double pi = acos(-1.0);

void solve()
{
    int n,m;
    cin >> n >> m;
    vector<int>a(n + 1);
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        a[u]++,a[v]--;
    }
    int rt = 0;
    for(int i=1;i<=n;i++){
        if(a[i]>=0){
            rt = i;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(i==rt){
            cout << 0 << ' ';
        }else {
            cout << rt << " " ;
        }
    }
}

O.筛法

打表猜答案为\(n^{2}\),证明不会（

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int mod = 998244353;
const int N = 1e6 + 7;
const double pi = acos(-1.0);

void solve()
{
    ll n;
    cin >> n;
    cout << n * n << endl;
}

M.生命游戏

就直接暴力模拟即可，使用bfs模拟，若度为k进队列执行后删除，每个点最多进队一次
最后再使用遍历一遍图得到答案

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
const int N = 1e6 + 7;
const int mod = 998244353;
const double eps = 1e-9;
vector<int> s[N];
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> du(n + 1);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        s[u].push_back(v);
        s[v].push_back(u);
        du[u]++, du[v]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        if (du[i] == k)
        {
            q.push(i);
            du[i] = -1;
        }
    }
    vector<int> vis(n + 1);
    int ans = 0;
    while (q.size())
    {
        set<int> st;
        while (q.size())
        {
            int u = q.front();
            q.pop();
            vis[u] = 1;
            for (auto v : s[u])
            {
                if (du[v] == -1)
                    continue;
                du[v]--;
                if (du[v] == k)
                {
                    st.insert(v);
                }
                else
                {
                    if (st.count(v))
                        st.erase(v);
                }
            }
        }
        for (auto v : st)
        {
            q.push(v);
            du[v] = -1;
        }
    }
    auto bfs = [&](int u)
    {
        queue<int> qp;
        qp.push(u);
        vis[u] = 1;
        while (qp.size())
        {
            int now = qp.front();
            qp.pop();
            for (auto v : s[now])
            {
                if (!vis[v])
                {
                    qp.push(v);
                    vis[v] = 1;
                }
            }
        }
    };
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            bfs(i);
            ans++;
        }
    }
    cout << ans << '\n';
}

K.崩坏：星穹铁道

没玩崩铁导致的，读假题演了半小时（
一看数据范围加上求方案数自然想到矩阵快速幂
考虑如何构造矩阵
发现对于每一时刻，只需用当前所剩技能点进行转移即可，矩阵大小6*6
通过dfs构造矩阵，枚举初始技能点i，搜索经过四次（一轮）攻击后所到达的状态j有多少方案
得到转移矩阵后进行n/4次转移即可
最后要与初始状态相乘，也就是有k个技能点
由于n不一定是4的倍数，所以要再用dfs转移完余数的贡献

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
const int N = 1e6 + 7;
const int mod = 998244353;
const double eps = 1e-9;
#define int long long
struct Mat
{
    int v[130][130] = {0};
    int x, y;
    Mat() {}
    Mat(int _x, int _y) { x = _x, y = _y; }
    // 清空
    void zero()
    {
        memset(v, 0, sizeof(v));
        x = y = 0;
    }
    // 单位矩阵化
    void ones()
    {
        memset(v, 0, sizeof(v));
        for (int i = 0; i <= x; i++)
        {
            v[i][i] = 1;
        }
    }
    // 乘法
    void Mul(Mat a, Mat b)
    {
        zero();
        x = a.x, y = b.y;
        int c = a.y;
        for (int i = 0; i <= x; ++i)
        {
            for (int j = 0; j <= y; ++j)
            {
                for (int k = 0; k <= c; ++k)
                {
                    v[i][j] += (long long)a.v[i][k] * b.v[k][j] % mod;
                    v[i][j] %= mod;
                }
            }
        }
        return;
    }
    // 打印
    void show()
    {
        for (int i = 0; i <= x; i++)
        {
            for (int j = 0; j <= y; j++)
            {
                cout << v[i][j] << " ";
            }
            cout << '\n';
        }
    }
};
Mat operator*(const Mat &x, const Mat &y)
{
    Mat res;
    res.Mul(x, y);
    return res;
}
Mat ksm(Mat a, long long b)
{
    Mat x = a;
    x.ones();
    while (b)
    {
        if (b & 1)
            x = x * a;
        b >>= 1;
        a = a * a;
    }
    return x;
}
int ps[5];
Mat a(5, 5);
void dfs(int u, int i, int r, int lim)
{
    if (i == lim)
    {
        a.v[r][u]++;
        return;
    }
    if (ps[i] == 1)
    {
        u++;
        if (u > 5)
            u = 5;
        dfs(u, i + 1, r, lim);
    }
    if (ps[i] == 2)
    {
        if (u == 0)
            u++;
        else
            u--;
        dfs(u, i + 1, r, lim);
    }
    if (ps[i] == 3)
    {
        int v = u;
        v++;
        if (v > 5)
            v = 5;
        dfs(v, i + 1, r, lim);
        if (u != 0)
        {
            u--;
            dfs(u, i + 1, r, lim);
        }
    }
}
void solve()
{
    ll n, k;
    cin >> n >> k;
    for (int os = 1; os <= 4; os++)
    {
        cin >> ps[os];
    }
    for (int i = 0; i <= 5; i++)
    {
        dfs(i, 1, i, 5);
    }
    Mat p(0, 5);
    ll nm = n % 4;

    p.v[0][k] = 1;

    Mat res = p * ksm(a, n / 4);
    ll ans = 0;
    a.zero();
    a = Mat(5, 5);
    for (int i = 0; i <= 5; i++)
    {
        dfs(i, 1, i, n % 4 + 1);
    }
    for (int i = 0; i <= 5; i++)
    {
        ll sb = 0;
        for (int j = 0; j <= 5; j++)
        {
            sb += res.v[0][i] * a.v[i][j] % mod;
            sb %= mod;
        }
        ans += sb;
        ans %= mod;
    }
    cout << ans << '\n';
}

E.雪中楼

没想到题解期望难度这么高
看完题的第一想法就是直接模拟，考虑如何快速实现，我这里使用了一个双端链表
l记录左边编号，r记录右边编号，直接插入即可

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int mod = 998244353;
const int N = 2e5 + 7;
const double pi = acos(-1.0);
int l[N],r[N];
void solve()
{
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        int x;
        cin >> x;
        if(x == 0){
            int p = r[0];
            l[r[0]] = i;
            r[0] = i;
            l[i] = 0;
            r[i] = p;
        }else {
            int p = r[x];
            l[r[x]] = i;
            r[x] = i;
            l[i] = x;
            r[i] = p;
        }
    }
    int x = r[0];
    while(x!=0){
        cout << x << ' ';
        x = r[x];
    }
}

I.命令行

从写完E之后就一直在想这道题，感觉题目描述有些不清晰一直wa最后一个点，结束后看别人代码才发现坑点，如果串为空那么补全是集合T为所有指令串（空串是所有串的前缀?）
要求前缀考虑使用字典树，用cnt记录每个前缀有多少串经过，并记录有每个串的终点out
我们执行操作的时候记录当前指针p，使用p在字典树上移动，如果该节点不存在，此时p = -1，同时用一个k记录-1的个数，一个lst记录最后在字典树上的节点编号。当p=-1时，增加操作使k增加，退格操作同理，执行操作无解，补全操作也是没有行动。
考虑不是-1的情况，即当前输入串还在字典树上，如果是加入操作就直接执行，如果是删除操作，我们可以对于字典树上每个节点p都记录一个父亲节点，那么删除操作就是在字典树上跳父亲。
对于执行操作，如果当前p是终点out，那么输出out[p]，否则无解。
对于补全操作，一个最朴素的想法是在树上一直跳，直到有分叉为止，但是会被一个很长的串卡掉
考虑优化，我们在字典树预处理时再记录一下每个节点有哪些串经过in（可能有多个，但是不影响答案），再记录对于每个串的每个字母对应的节点mp，这样我们可以在补全操作时对于当前串二分，如果二分到的位置的节点的cnt小于最初的cnt就不行，这样就得到了补全后的节点p，此时即可通过此题

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
const int N = 5e6 + 7;
const int mod = 998244353;
// const int N = 1000050;
int trie[N][26]; // 所构造的查找树，其对应的值是子节点的编号，【它的编号】【子节点的字母】
// 等于0表示没有该字母；
int cnt[N]; // N是一个单词终点的编号，表示有无该单词（0表示没有）
int id;     // 结点计数器，初始值为0
// 每次插入和查询复杂度都是O(n)
int fa[N];
int in[N];
int out[N];
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<string> str(n + 1);
    vector<vector<int>> mp(n + 1);
    // in[0]=1;
    for (int i = 1; i <= n; i++)
    {
        cin >> str[i];
        int p = 0;
        mp[i].resize(str[i].size());
        in[p] = i;
        cnt[p]++;//记录0节点
        for (int j = 0; j < str[i].size(); j++)
        {
            int x = str[i][j] - 'a';
            if (trie[p][x] == 0)
                trie[p][x] = ++id;
            int suv = p;
            p = trie[p][x];
            fa[p] = suv;
            cnt[p]++;
            mp[i][j] = p;//每个字符对应节点
            in[p] = i;//每个节点被哪个经过
        }
        out[p] = i;//是否是一个串的终点
    }
    string TS;
    cin >> TS;
    int p = 0, lst = 0, k = 0;
    for (auto it : TS)
    {
        if (it == 'T')
        {
            if (p == -1)
            {
                continue;
            }
            int ls = cnt[p];//当前节点经过串个数
            int i = in[p];//经过当前节点的一个串的编号
            int l = 0, r = str[i].size() - 1;
            while (l < r)
            {
                int mid = (l + r + 1) >> 1;
                if (cnt[mp[i][mid]] >= ls)
                {
                    l = mid;
                }
                else
                {
                    r = mid - 1;
                }
            }
            if(cnt[mp[i][l]]<ls){//检查最终结果是否合法（主要针对空串情况）
                p = 0;
            }else
                p = mp[i][l];//跳到补全后的位置
        }
        else if (it == 'B')
        {
            if (p == 0)
                continue;
            if (p == -1)
            {
                k--;
                if (k == 0)//没有-1，当前输入又回到树上
                {
                    p = lst;
                }
            }
            else
            {
                p = fa[p];//跳父亲
            }
        }
        else if (it == 'E')
        {
            if (p != -1 && out[p])
            {
                cout << out[p] << ' ';
            }
            else
            {
                cout << -1 << ' ';
            }
            p = 0;//清空输入
            lst = 0;
            k = 0;
        }
        else
        {
            if (p == -1)
            {
                k++;
                continue;
            }
            int x = it - 'a';
            int suv = p;
            p = trie[p][x];
            if (!p)//开始没有对应节点
            {
                lst = suv;
                k++;
                p = -1;
            }
        }
    }
}

N.圣诞树

十分简单的启发式合并
一个贪心的想法是只要当前子树有k个不同，就对答案贡献
令1为根
对每个节点开一个set存子树中节点颜色，如果子树已经贡献答案则不进入set
合并时候从小到大合并，确保复杂度
整体复杂度\(O(nlog^{2}n)\)

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
const int N = 5e5 + 7;
const int mod = 998244353;
vector<int> s[N];
set<int> st[N];
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> col(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> col[i];
    }
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        s[u].push_back(v);
        s[v].push_back(u);
    }
    int ans = 0;
    auto dfs = [&](auto &dfs, int u, int fa) -> void
    {
        st[u].insert(col[u]);
        for (auto v : s[u])
        {
            if (v == fa)
                continue;
            dfs(dfs, v, u);
            if(st[v].size()>st[u].size()){
                swap(st[u],st[v]);//启发式合并
            }
            for(auto x:st[v]){
                st[u].insert(x);
            }
        }
        if (st[u].size() >= k)
        {
            ans++;
            st[u].clear();
        }
    };
    dfs(dfs,1,0);
    cout << ans << '\n';
}

标签：const,int,题解,cin,long,VP,double,using,校赛
From： https://www.cnblogs.com/qzhfx/p/18212962

相关文章

  • 题解【[SCOI2008] 配对】
    题目链接如果没有“配对数字不相同”的限制，将\(a,b\)数组排序后一一配对就能得到最小值。回到原题，考虑一种极端情况，\(\foralli\in[1,n],a_i=b_i\)即排序后全等。若\(n\)为偶数，一种显然的构造方法是：123456214365即分成两个两个一组，然后组内交换，这样跨越幅......
  • Xfce4桌面背景和桌面图标消失问题解决@FreeBSD
    问题：Xfce4桌面背景和桌面图标消失以前碰到过好几次桌面背景和桌面图标消失，整个桌面除了上面一条和下面中间的工具条，其它地方全是黑色的问题，但是这次重启之后也没有修复，整个桌面乌黑一片，啥都没有，用起来特别不得劲，于是开始修复。修复过程咨询文心，建议这样设置：检查壁纸设置：......
  • 【NOI2010】能量采集 题解
    【NOI2010】能量采集题解谨纪念我的第一道手推出来的莫反题。题目大意：已知\(n\)，\(m\)，求\(\sum\limits_{i=1}^n\sum\limits_{j=1}^m(2\cdot\gcd(i,j)-1)\)。首先变形一手：\[\sum\limits_{i=1}^n\sum\limits_{j=1}^m(2\cdot\gcd(i,j)-1)=2\sum\limits_{i=1}^n\sum\limits_{j=......
  • CF1973F Maximum GCD Sum Queries 题解
    题目链接点击打开链接题目解法首先想到枚举两个数列的$\gcd$，求最小代价两个数列的\(\gcd\)应该分别是\(a_1,b_1\)的因数或\(b_1,a_1\)的因数这样就把枚举范围缩小到了\(d(a_1)\timesd(b_1)\)，这求最小代价需要\(O(n)\)，不够快假设枚举的\(\gcd\)分别为\(x,y\)......
  • CF1909I Short Permutation Problem 题解
    这是一道*1900的黑。考虑枚举\(m\)，将\(<\fracm2\)和\(\ge\fracm2\)的数分开讨论。考虑相邻两个数\(a,b\(a>b)\)分别在\(\fracm2\)的两侧，则有\(b\gem-a\)。考虑将所有数按某种方法从小到大排序，以\(\min(x,m-x)\)为第一关键字，\(-x\)为第二关键字，则排列中......
  • 【达梦问题解决】to_date转换之【文字与格式字符串不匹配】
    【问题描述】因为要转换的值中包含了不属于时间格式的字符（T,Z），这可能是数据迁移时时间参数设置不对导致的。具体没有进行考究【问题解决】使用DATE分隔符解决【手册链接】格式符解释实际分隔符的处理办法【自定义转换函数】这里的自定函数是不完善的，因为我的数......
  • CF1939D Big Persimmon 题解
    题目链接点击打开链接题目解法什么神仙题/jy先把\(a_i\)都\(\times2\)，默认一开始先手比后手快\(1\)时间，可以避免两个人同时结束一个柿子的情况朴素的\(dp\)是显然的，令\(f_{l,r,det}\)表示当前剩下区间\([l,r]\)中的柿子，先手比后手快了\(det\)秒，先手最多能比后......
  • 充电桩——微信小程序，缴纳的1000元交易保障金，问题解答。
    1、小程序后台，申请退款保障金有一条不符合要求，无法退款。 2、咨询客服，能否退款然后再以公司名义缴纳保证金，等待回复：暂不支持对公转账，只能微信扫码支付缴纳哈。退保的话，支持退回对公账户。详情请查看小程序交易保证金管理规定https://developers.weixin.qq.com/miniprogram/de......
  • P5531 [CCO2019] Human Error 题解
    可能是一个比较劣的做法。但复杂度是对的。思路我们容易发现状态数非常的稀少。一个比较宽松的上限时\(3^{13}\)种状态由于每个点每走一步会吃掉一个棋子。所以实际的状态是远远达不到这个上限。那么我们可以直接设\(dp_{i,0/1,0/1}\)为在\(i\)状态下，目前是Justin......
  • Codeforces Global Round 12 C2. Errich-Tac-Toe (Hard Version) 题解 构造
    Errich-Tac-Toe(HardVersion)题目描述TheonlydifferencebetweentheeasyandhardversionsisthattokensoftypeOdonotappearintheinputoftheeasyversion.ErrichtogaveMonogonthefollowingchallengeinordertointimidatehimfromtakingh......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99