首页 > 其他分享 >2022杭电多校9

2022杭电多校9

时间:2022-09-23 15:44:30浏览次数:98  
标签:杭电多校 题意 fa int void ++ 2022 top

J. Sum Plus Product

题意

给定一个长度为n的数组,每次随机拿出两个数使其变成 (a + b + a * b)再放回数组,最终数组中只剩下一个数,求剩余数字的期望是多少。

分析:

模拟一下就会发现 合并的顺序并不重要

比如 a1 a2 a3 和 a3 a1 a2

两者最后答案都是 a1a2a3 + a1a2 + a2a3 + a1a3 + a1 + a2 + a3

void solve()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
    int last = a[1];
    for(int i = 2 ; i <= n ; i ++ ) 
        last = (last + a[i] + last * a[i] % mod) % mod;
    cout << last << endl;
}

G. Matryoshka Doll

题意:

分析:

void slove() {
    cin >> n >> k >> r;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n; i++) {
        L[i] = 0;
        for (int j = i - 1; j >= 1; j--)
            if (abs(a[i] - a[j]) < r) {
            L[i]++;
        }
    }
    for (int i = 0; i <= n + 2; i++)for (int j = 0; j <= n + 2; j++)dp[i][j] = 0;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j - 1] + ((ll)dp[i - 1][j] * (j - L[i])) % mod;
            dp[i][j] %= mod;
        }
    }
    cout << dp[n][k] << endl;
}

H. Shortest Path in GCD Graph

题意

给定一张完全图节点1-n,每两个点i, j之间的边长为gcd(i, j),有若干个询问,每次给定两个节点i和j,求i和j的最短路,以及最短路的条数。

分析

板子题目 https://www.cnblogs.com/wzxbeliever/p/16206695.html

const int N = 1e7 + 10;
int primes[N];
bool st[N];         
int minp[N];
void get_primes(int n) {
    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i, minp[i] = i;
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            minp[primes[j] * i] = primes[j];
            if (i % primes[j] == 0) break;
        }
    }
}
namespace qjhz {
    int p[100],cnt;
    void prime(int n) {
        cnt = 0;
        while (n != 1) {
            p[++cnt] = minp[n];
            int pr = minp[n];
            while (n%pr == 0) {
                n /= pr;
            }
        }
        return;
    }
    ll solve(ll r) {
        ll res = 0;
        for (int i = 1; i < (1 << cnt); i++) {
            int kk = 0;
            ll div = 1;
            for (int j = 1; j <= cnt; j++) {
                if (i&(1 << (j - 1))) {
                    kk++;
                    div *= p[j];
                }
            }
            if (kk % 2)
                res += r / div;
            else
                res -= r / div;
        }
        return r - res;
    }


    map<set<int>, int>mp;
    int calc(int n, int a, int b) {
        set<int>v;
        prime(a);
        for (int i = 1; i <= cnt; i++)v.insert(p[i]);
        prime(b);
        for (int i = 1; i <= cnt; i++)v.insert(p[i]);
        cnt = 0;
        for (int x : v) {
            p[++cnt] = x;
        }
        if (mp.count(v))return mp[v];
        return mp[v] = solve(n);
    }

}



int n, m;
void slove() {
    cin >> n >> m;
    get_primes(n);
    for (int i = 1; i <= m; i++) {
        int a, b; cin >> a >> b;
        if (gcd(a, b) == 1) {
            cout << "1 1" << endl;
        }
        else if (gcd(a, b) == 2) {
            int ans = qjhz::calc(n, a, b);
            cout << 2 << " " << ans + 1 << endl;
        }
        else {
            int ans = qjhz::calc(n, a, b);
            cout << 2 << " " << ans << endl;
        }
    }
}

C. Fast Bubble Sort

题意

分析

单调栈 :

先考虑第一个小问题,如何找到第一次跳跃的位置?也就是第一个在右边大于自己的数,很显然这是一个基础单调栈问题,我们从后往前推一遍即可。

累计答案:

我们发现对于一个数想要往后跳,每次跳一次,我们要累积答案最简单的方法就是一直往后跳迭代下去即可。但是显然时间复杂度是不允许的,但是其实这个思路很像我们在求lca时的树上倍增的跳跃法。

树上倍增:

我们设R[i]为当前数跳跃一次能够到达的点,用单调栈即可。v[i]表示从当前位置i跳跃到终点需要的次数,我们从后往前迭代一遍即可预处理出全部数组。

for(int i = n ; i ; i -- )
    {
        v[i] = v[R[i]];
        if(R[i] > i + 1) v[i] ++ ;
        fa[i][0] = R[i];
        for(int j = 1 ; j <= 20 ; j ++ )
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }

和树上倍增一样的跳即可,注意如果终点没到的话说明下一次跳可能会出界,也就是答案还需要多加一次。

const int N = 1e5 + 10 , INF = 0x3f3f3f3f, mod = 998244353;
int n, m, a[N], k, r;
int stk[N], top, R[N];
int fa[N][25], v[N];

void solve()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
    for(int i = 0 ; i < n + 10 ; i ++ )
        for(int j = 0 ; j < 21 ; j ++ ) fa[i][j] = n + 1;
    a[n + 1] = INF;
    top = 0;
    stk[++ top] = n + 1;
    for(int i = n ; i ; i -- )
    {
        while(top && a[stk[top]] <= a[i]) top -- ;
        R[i] = stk[top];
        stk[++ top] = i;
    }
    v[n + 1] = 0;
    for(int i = n ; i ; i -- )
    {
        v[i] = v[R[i]];
        if(R[i] > i + 1) v[i] ++ ;
        fa[i][0] = R[i];
        for(int j = 1 ; j <= 20 ; j ++ )
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }
    
    for(int i = 1 ; i <= m ; i ++ )
    {
        int l, r;
        cin >> l >> r;
        int u = l;
        for(int k = 20 ; k >= 0 ; k -- )
        {
            if(fa[u][k] <= r)
                u = fa[u][k];
        }
        int res = v[l] - v[u];
        if(r != u) res ++ ;
        cout << res << endl;
    }
}

先看这个题:https://uoj.ac/problem/143

题意:

给出一个的数列,将其重新排列,使得其等差子序列的数目最小。输出一种可能的排列后的数列

分析:

通过构造可以使得不存在长度为3的等差子序列。

{s, k, t} 三个数为等差,等价于:s + t = 2 * k。此时{s, t}必须是奇偶性相同的两个数。

按照奇偶性分开后,则只会在奇数或者偶数内部产生等差的三元组,此时分治。

然后又可以得到如下关系:

三个奇数{2s+1, 2k+1, 2t+1}满足:(2s + 1) + (2t + 1) = 2 * (2k + 1)

三个偶数{2s, 2k, 2t}满足:(2s) + (2t) = 2 * (2k)

上面两个式子都等价为 s + t = 2 * k,所以将所有的数整除掉2之后和原问题一样。

如果把所有奇数放到所有偶数的左面,那么就不会出现 “奇-偶-奇” 或 “偶-奇-偶” 的情况。

对于 “奇-奇-奇” 或 “偶-偶-偶” 的情况,将所有 ai 变为 ai/2不影响判断,因此将所有数除以2后重复这个过程即可。

由于一个数除以 logn 次就会变成1,因此这个过程只需要进行 logn 次。

每一层都只会处理 n 个数,时间复杂度 O(nlogn)

#include <cstdio>
int a[510] , p[510] , t[510];
void solve(int l , int r , int x)
{
    if(!x || l >= r) return;
    int i , b = l , e = r;
    for(i = l ; i <= r ; i ++ )
    {
        if(a[p[i]] & 1) t[b ++ ] = p[i];
        else t[e -- ] = p[i];
    }
    for(i = l ; i <= r ; i ++ ) a[p[i]] >>= 1 , p[i] = t[i];
    solve(l , e , x - 1) , solve(b , r , x - 1);
}
int main()
{
    int n , i;
    scanf("%d" , &n);
    for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]) , p[i] = i;
    solve(1 , n , 30);
    for(i = 1 ; i <= n ; i ++ ) printf("%d " , p[i]);
    return 0;
}

A. Arithmetic Subsequence

分析

根据上个题目 只要不出现三个相同的数 一定能构造出不含等差子序列的数组

构造就和上一个题目一模一样

标签:杭电多校,题意,fa,int,void,++,2022,top
From: https://www.cnblogs.com/wzxbeliever/p/16722958.html

相关文章

  • Pycharm2022.1.3安装教程(免费)
    pycharm的下载安装及使用以我的Pycharm2022.1.3为例首先去官网下载professtional(专业版)版本2022.1.3版本Pycharm软件https://www.jetbrains.com/pycharm/我们下载......
  • 2022.9.17:ICPC网络赛第一场
    突然意识到正式赛这个版块没有更新过什么,就打算写一个赛后总结开场跟榜开\(C\),跟队友讨论了好一会儿,\(20\)分钟才意识到和叶子结点有关,qgn上机,没看代码,觉得啥问题,结果......
  • 论文被 AIMLSystems 2022 接受
    论文被AIMLSystems2022接受我们的论文“Q-commerce的地址位置校正系统”已在2022年10月12日至15日举行的第二届AI-ML系统国际会议(AIMLSystems'22)上被业......
  • 详细解析11月前能影响加息的数据 点阵图带来的情绪开始缓解 — 2022.9.23
    详细解析11月前能影响加息的数据点阵图带来的情绪开始缓解—2022.9.23九月份的加息结束,以及点阵图带来的终端利率走势,风险市场的情绪持续反而出现了乐观的局面,随着凌晨......
  • 今日热门表情包精选2022-09-23-985
    今日热门表情包精选款鸡涌,把心都给你我什么都看见了不行我受不了这委屈(橘猫)不说了要去搬砖了孤寡之王七夕蛤蟆之寡王点我叫到你朋友自闭表情包沙雕熊猫头哎!我.哎.呵呵......
  • 2022.9.21———HZOI【CSP-S模拟8】游寄
    \(Preface\)评价:最近网络流学魔怔了感觉学长很喜欢\(AtCoder\)。。。其实题的质量似乎确实很好\(Rank34/43\)\(5pts+10pts+5pts+0pts=20pts\)话说只要水到55p......
  • 2022-09-23 Avoid mutating a prop directly since the value will be overwritten w
    父组件给子组件传值,提示子组件不能直接修改父组件传递过来的值,完整报错: Avoidmutatingapropdirectlysincethevaluewillbeoverwrittenwhenevertheparentcom......
  • 2022.9.20———HZOI【CSP-S模拟7】游寄
    Preface$\(Rank36/43\)\(20pts+0pts+50pts+0pts=70pts\)\(\mathfrak{T1}\序列问题\)一个\(cdq\),我没学\(cdq\),而且我连暴力\(dp\)都没打,因为我连暴力\(dp\)都......
  • Jenkins 20220922笔记本2
                                  ......
  • 2022.9.19———HZOI【CSP-S模拟6】游寄
    \(Preface\)试验一下难度。———Au爷沈队(学长)这句话,我理解为“铈囐镒䪗䁪鑟”。\(Rank24/43\)\(80pts+9pts+0pts+0pts=89pts\)\(\mathfrak{T1}\玩水\)......