首页 > 其他分享 >Codeforces Round #837 (Div. 2)

Codeforces Round #837 (Div. 2)

时间：2022-12-16 19:11:49浏览次数：65  
标签：med 837 int Codeforces cin ++ ans Div _##

A. Hossam and Combinatorics (CF 1771 A)

题目大意

给定一个长度为\(n\)的数组\(a\)，问有多少个数对其差的绝对值等于该数组的极差。

解题思路

若最大值和最小值相等，则答案为\(n \times ( n - 1 )\)

否则就为最大值个数和最小值个数的乘积的两倍（顺序有关的数对）

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        map<int, int> cnt;
        FOR(i, 0, n){
            int x;
            cin >> x;
            cnt[x] ++;
        }
        if (cnt.size() == 1){
            cout << 1ll * cnt.begin()->second * (cnt.begin()->second - 1) << '\n';
        }else
            cout << 1ll * cnt.begin()->second * cnt.rbegin()->second * 2 << '\n';
    }

    return 0;
}

B. Hossam and Friends (CF 1771 B)

题目大意

给定一个数组，其值为\(1..n\)。以及给定 \(m\)条规则，第\(i\) 条规则规定\(l_i, r_i\)不能同时在一个数组。

问有多少个连续的子数组不违反这 \(m\)条规则。

解题思路

固定一个右端点，考虑合法的子数组的左端点，是一个从右端点往左的一个连续的区间。

随着子数组的右端点不断向右移动，会发现其合法的子数组的最小左端点是不断往右移动的。其左端点可继承上一状态。

因此可采用双指针法维护。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        int l = 1;

        vector<vector<int>> edge(n + 1);
        FOR(i, 0, m){
            int u, v;
            cin >> u >> v;
            if (u > v)
                swap(u, v);
            edge[v].push_back(u);
        }

        LL ans = 0;
        for(int i = 1; i <= n; ++ i){
            for(auto v : edge[i]){
                if (l <= v)
                    l = v + 1;
            }
            ans += 0ll + max(0, i - l + 1);
        }
        cout << ans << '\n';
    }

    return 0;
}

C. Hossam and Trainees (CF 1771 C)

题目大意

给定\(n\)个数字 \(a_i\)，若存在一对 \(a_i,a_j\)不互质，则输出 \(YES\)，否则输出 \(NO\)。

解题思路

对这\(n\)个数质因数分解，记录其中出现过的质数即可。

若某个质数再次出现则为\(YES\)，否则为 \(NO\)。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)

const LL p_max = 1E6 + 100;
LL pr[p_max], p_sz;
void get_prime() {
    static bool vis[p_max];
    FOR (i, 2, p_max) {
        if (!vis[i]) pr[p_sz++] = i;
        FOR (j, 0, p_sz) {
            if (pr[j] * i >= p_max) break;
            vis[pr[j] * i] = 1;
            if (i % pr[j] == 0) break;
        }
    }
}

set<int> cnt;
bool get_factor(LL x) {
    LL t = sqrt(x + 0.5);
    for (LL i = 0; pr[i] <= t; ++i)
        if (x % pr[i] == 0) {
            if (cnt.find(pr[i]) != cnt.end())
                return true;
            cnt.insert(pr[i]);
            while (x % pr[i] == 0) {
                x /= pr[i];
            }
        }
    if (x > 1) {
        if (cnt.find(x) != cnt.end())
            return true;
        cnt.insert(x);
    }
    return false;
}

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    get_prime();
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        bool ok = false;
        cnt.clear();
        FOR(i, 0, n){
            int x;
            cin >> x;
            ok |= get_factor(x);
        }
        if (ok)
            cout << "YES\n";
        else 
            cout << "NO\n";
    }

    return 0;
}

D. Hossam and (sub-)palindromic tree (CF 1771 D)

题目大意

给定一棵树，节点有字母。点\(u\)到点 \(v\)的路径表示成其路径点的字母组成的字符串。

定义一个字符串的价值为该字符串长度最长的回文子序列（可不连续的）的长度。

问所有路径对应的字符串的价值的最大值。

解题思路

先考虑给定一个串\(s\)如何求出最长回文子序列。

设\(dp[i][j]\)表示子字符串 \(s[i,j]\)的最长回文子序列。

  • 如果\(s[i] == s[j]\)，则 \(dp[i][j] = dp[i + 1][j - 1] + 2\)
  • 否则 \(dp[i][j] = \max(dp[i + 1][j], dp[i][j - 1])\)

其时间复杂度为\(O(n^2)\)

再回到树上，由于字符串变成了路径，如果设\(dp[u][v]\) 表示一段路径，一端在点\(u\)，另一段在点 \(v\)，会发现转移是一样的（因为路径是唯一的，并且也是一维的）,\(+1, -1\)无非就是变成了其点的父亲或者某个儿子而已。

所以同样直接做即可。找儿子的话用了\(LCA\)以及倍增的方式（深度差减一），故时间复杂度为 \(O(n^2\log n)\)

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)

const int N = 2e3 + 8;
const int SP = 15;
vector<vector<int>> G;

int pa[N][SP];
int dep[N];
int dp[N][N];
int ans, n;
string s;

void dfs(int u, int fa) {
    pa[u][0] = fa; dep[u] = dep[fa] + 1;
    FOR (i, 1, SP) pa[u][i] = pa[pa[u][i - 1]][i - 1];
    for (int& v: G[u]) {
        if (v == fa) continue;
        dfs(v, u);
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int t = dep[u] - dep[v];
    FOR (i, 0, SP) if (t & (1 << i)) u = pa[u][i];
    FORD (i, SP - 1, -1) {
        int uu = pa[u][i], vv = pa[v][i];
        if (uu != vv) { u = uu; v = vv; }
    }
    return u == v ? u : pa[u][0];
}

int get_next(int u, int t){
    FOR (i, 0, SP) if (t & (1 << i)) u = pa[u][i];
    return u;
}

int solve(int u, int v){
    if (dp[u][v] != 0)
        return dp[u][v];
    if (u == v)
        return dp[u][v] = 1;
    int fa = lca(u, v);
    int nxtu = pa[u][0], nxtv = pa[v][0];
    if (u == fa){
        nxtu = get_next(v, dep[v] - dep[fa] - 1);
    }else if (v == fa){
        nxtv = get_next(u, dep[u] - dep[fa] - 1);
    }
    dp[u][v] = max(solve(nxtu, v), solve(u, nxtv));
    if (s[u] == s[v]){
        if (nxtu == v && nxtv == u)
            dp[u][v] = max(dp[u][v], 2);
        else 
            dp[u][v] = max(dp[u][v], solve(nxtu, nxtv) + 2);
    }
    return dp[u][v];
}

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        cin >> n >> s;
        G.clear();
        G.resize(n + 1);
        FOR(i, 1, n){
            int u, v;
            cin >> u >> v;
            -- u;
            -- v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(0, 0);
        ans = 0;
        for(int i = 0; i < n; ++ i)
            for(int j = 0; j < n; ++ j){
                ans = max(solve(i, j), ans);
            }
        cout << ans << '\n';
        memset(dp, 0, sizeof(dp));
    }

    return 0;
}

E. Hossam and a Letter (CF 1771 E)

题目大意

给定一个\(n\times m\)的格子，有完美格子，一般格子，坏格子。

先要选择一些格子，形成一个字母 \(H\)，要求

  • 格子排成两条垂直线和一条水平线
  • 垂直线两端对其
  • 水平线紧挨垂直线
  • 水平线不得再垂直线的两端
  • 不得选择坏格子，至多选择一个一般格子

问选的格子数的最大值。

解题思路

预处理每个格子往上往下延伸，分别不选择一般格子和只选择一个一般格子的最长延伸距离，然后枚举水平线的位置（一个行坐标，两个列坐标），对谁用了一般格子分类讨论下，取最大值即可。

预处理部分建议阅读jiangly代码，写得非常简洁美妙。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)

const int N = 4e2 + 8;

int n, m;
string s[N];
int up[2][N][N], down[2][N][N];
int ans;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; ++ i)
        cin >> s[i];
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j){
            if (s[i][j] == '#')
                continue;
            int med = 0;
            for(int k = i; k >= 0; -- k){
                if (s[k][j] == 'm'){
                    up[med][i][j] = i - k;
                    med ++;
                }else if (s[k][j] == '#'){
                    up[med][i][j] = i - k;
                    ++ med;
                    if (med == 1){
                        up[med][i][j] = i - k;
                        ++ med;
                    }
                    break;
                }
                if (med > 1)
                    break;
            }
            if (med == 0){
                up[med][i][j] = i + 1;
                ++ med;
            }
            if (med == 1){
                up[med][i][j] = i + 1;
                ++ med;
            }
            assert(med == 2);

            med = 0;
            for(int k = i + 1; k < n; ++ k){
                if (s[k][j] == 'm'){
                    down[med][i][j] = k - i - 1;
                    med ++;
                }else if (s[k][j] == '#'){
                    down[med][i][j] = k - i - 1;
                    ++ med;
                    if (med == 1){
                        down[med][i][j] = k - i - 1;
                        ++ med;
                    }
                    break;
                }
                if (med > 1)
                    break;
            }
            if (med == 0){
                down[med][i][j] = n - i - 1;
                ++ med;
            }
            if (med == 1){
                down[med][i][j] = n - i - 1;
                ++ med;
            }
            assert(med == 2);
        }

    ans = 0;
    for(int i = 1; i < n - 1; ++ i)
        for(int j = 1; j < m - 1; ++ j){
            int med = 0;

            for(int k = j; k < m - 1; ++ k){
                if (s[i][k] == '#')
                    break;
                med += (s[i][k] == 'm');
                if (med > 1)
                    break;

                auto check = [&](int up0, int up1, int down0, int down1){
                    int upp = min(up[up0][i][j - 1], up[up1][i][k + 1]);
                    int downn = min(down[down0][i][j - 1], down[down1][i][k + 1]);
                    if (upp > 1 && downn >= 1){
                        ans = max(ans, 2 * (upp + downn) + k - j + 1);
                    }
                };
                if (med){
                    check(0,0,0,0);
                }else{
                    check(1, 0, 0, 0);
                    check(0, 1, 0, 0);
                    check(0, 0, 1, 0);
                    check(0, 0, 0, 1);
                }
            }
        }
    cout << ans << '\n';

    return 0;
}

F. Hossam and Range Minimum Query (CF 1771 F)

题目大意

给定\(n\)个数字的数组\(a\)，以及\(q\)组询问。每组询问包含两个数 \(l,r\)，问 \(a[l..r]\)中出现次数是奇数的最小数是什么。

强制在线。

解题思路

多亏此题，我忽然对主席树的原理和写法彻底悟了（有的人以前只会口糊，然后交给队友写）

如果离线的话可以用莫队。

在线的话，由于需要维护任意区间内的信息，一般采用主席树，而主席树保存的是区间\([1, i]\)的信息，要得到区间 \([l,r]\)的信息的话，需要区间 \([1,r]\)的信息与区间 \([1,l - 1]\)的信息作差。

我们先对原数组离散化，然后建立一棵值域主席树。假设离散化为的个数为\(m\)个，考虑维护什么信息。

如果维护每个数的出现次数，那么作差的复杂度是\(O(m)\)，那复杂度至少是\(O(qm)\)，不可行。我们得让作差的复杂度为 \(O(1)\)或者 \(O(\log)\)

由于是出现奇数次，可以维护区间异或和，该异或和不为\(0\)意味着该区间一定有出现奇数次的数，但为\(0\)的话则不一定，会被精心构造的数据卡掉。

但由于我们想看的是数是否一样，而数的大小这一性质可以丢掉，这意味着我们可以对原数组进行一个随机映射，只要保证相同的数映射到相同的值即可。通常的做法就是将这些数随机映射到 \([0, 2^64)\)中，这样能够保证出现上述所说的情况的概率非常小。

拿映射后的值进行异或，然后在主席树上对答案进行二分，找到最小的异或值不为0的下标即可。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)

const int M = 2e5 + 8;
using ull = unsigned long long;

int n, m, q;

namespace tree {
#define mid ((l + r) >> 1)
#define lson l, mid
#define rson mid + 1, r
    const int MAGIC = M * 30;
    struct P {
        ull sum;
        int ls, rs;
    } tr[MAGIC] = {{0, 0, 0}};
    int sz = 1;
    int N(ull sum, int ls, int rs) {
        if (sz == MAGIC) assert(0);
        tr[sz] = {sum, ls, rs};
        return sz++;
    }
    int ins(int o, int x, ull v, int l = 1, int r = m) {
        if (x < l || x > r) return o;
        const P& t = tr[o];
        if (l == r) return N(t.sum ^ v, 0, 0); 
        return N((t.sum ^ v), ins(t.ls, x, v, lson), ins(t.rs, x, v, rson));
    }
    int query(int o1, int o2, int l = 1, int r = m) {
        if (tr[o1].sum == tr[o2].sum)
            return -1;
        if (l == r)
            return l;
        int ls1 = tr[o1].ls;
        int ls2 = tr[o2].ls;
        if (tr[ls1].sum != tr[ls2].sum)
            return query(ls1, ls2, lson);
        else 
            return query(tr[o1].rs, tr[o2].rs, rson);
    }
}

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);

    cin >> n;
    vector<int> a(n);
    for(auto &i : a)
        cin >> i;
    vector<int> rank = a;
    sort(rank.begin(), rank.end());
    rank.erase(unique(rank.begin(), rank.end()), rank.end());
    m = rank.size();

    vector<ull> h(m);
    vector<int> tree(n + 1);

    std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
    for(int i = 0; i < m; ++ i){
        h[i] = rng();
    }

    for(int i = 0; i < n; ++ i){
        int pos = lower_bound(rank.begin(), rank.end(), a[i]) - rank.begin();
        tree[i + 1] = tree::ins(tree[i], pos + 1, h[pos]);
    }

    cin >> q;
    int ans = 0;
    while(q--){
        int l, r;
        cin >> l >> r;
        l ^= ans;
        r ^= ans;

        -- l;
        ans = tree::query(tree[l], tree[r]);
        if (ans == -1)
            ans = 0;
        else 
            ans = rank[ans - 1];
        cout << ans << '\n';
    }
    return 0;
}

标签：med,837,int,Codeforces,cin,++,ans,Div,_##
From： https://www.cnblogs.com/Lanly/p/16988126.html

相关文章

  • div的使用
    div：盒子模型（块级元素）border：边框总写：border-color：边框颜色例：（顺时针顺序+对称原则）border-color：redblueyellowpink;分写：border-top-color:上边框颜色......
  • Codeforces Round #838 (Div. 2) D
    D.JourneytoUn'Goro题链考虑一个三元组内一定可以排除一个非0的xyz我们询问xz和yz要是gx==gy那么我们的z一定不是0否则gx=pxgy=py排除z要是gx！=gy那么......
  • Educational Codeforces Round 2
    EducationalCodeforcesRound2https://codeforces.com/contest/6003/6：ABDA.ExtractNumbers小模拟。把一个字符分成两部分输出，遇到';'或','视为单词分隔符，非负......
  • Codeforces Round #838 (Div. 2) D. GCD Queries
    题意有个长度为n的排列p，[0,1,2,...n-1]，你可以进行至多2*n次询问，每次询问两个i，j，返回gcd(pi,pj)，让你在规定时间内猜出0在哪两个位置之一思路这是一道交互题，询问的上限是2n......
  • Educational Codeforces Round 139 (Rated for Div. 2)
    EducationalCodeforcesRound139(RatedforDiv.2)数组开小，身败名裂场。CF1766AExtremelyRound直接前缀和递推预处理一下每个\(n\)的答案，询问直接输出即可。CF......
  • 一个新ACMer的刷题记录捏（Round.694） codeforces ABC
    A.StrangePartitionProblem-A-Codeforces  2022-12-1514:00:52​#include<bits/stdc++.h>#defineintlonglongconstintN=100010;usingnamespac......
  • div 常用样式记录
    div边框：  boder虚线：dashed 实线：solid  语法：<divstyle="border:2pxsolidred"></div>  上边框：border-top；下边框：border-bottom；左边框：border-left；右边框......
  • Educational Codeforces Round 136 (Rated for Div. 2)
    题目链接A核心思路：其实就是一个签到题没什么好说的，我们可以直接通过观察样例大胆猜测结论：也就是只有是一列的时候是完全孤立的。直接看代码吧.#include<bits/stdc++.h>......
  • Codeforces Round 793 div2 (A-D)
    A题，题意是给一个回文串，问有多少个字符删掉，还是一个回文串这个题看样例，肯定是从中间开始查相同字符的段长度，没啥难度代码：#include<bits/stdc++.h>usingnamespacest......
  • 最大公约数 GCD greatest common divisor
     辗转相除法#include<stdio.h>intmain(void){intm,n,r;scanf("%d%d",&m,&n);if(m<n){m=m^n;n=m^n;......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99