首页 > 其他分享 >Educational Codeforces Round 33 (Rated for Div. 2)

Educational Codeforces Round 33 (Rated for Div. 2)

时间:2023-07-16 19:56:29浏览次数:46  
标签:Educational Rated 33 res ll cnt st int mod

Educational Codeforces Round 33 (Rated for Div. 2)

https://codeforces.com/contest/893
昨日vp,今日补完F
D贪心,思路值得学习;
E组合数学推式子,式子不难,关键在于模型抽象
F主席树,调了老半天,关键在于要理解查询函数的含义,确定什么时候能返回。

A. Chess For Three

居然卡了快十分钟,关键是要把模拟的过程想清楚,变量的更新到底是怎么操作的

#include <bits/stdc++.h>

using namespace std;

int find (int a, int b) {
    for (int i = 1;  i <= 3; i++) {
        if (i != a && i != b)   return i;
    }
    return 0;
}

int main () {
    int n;
    cin >> n;
    int c = 3, a = 1, b = 2;
    bool suc = true;
    while (n --) {
        int x;
        cin >> x;
        if (c == x) suc = false;
        if (!suc)   continue;
        a = x, b = c, c = find (a, b);
        //cout << a << ' ' << b << ' ' << c << endl;
        
    }
    if (suc)    cout << "YES";
    else    cout << "NO";
}

B. Beautiful Divisors

暴力模拟

#include <bits/stdc++.h>

using namespace std;

bool check (int x) {
    if (x == 1) return true;
    string s;
    //cout << x << ' ';
    while (x > 0) {
        s += char(x % 2 + '0');
        x /= 2;
    }
    //cout << s << endl;
    if (s.size () % 2 == 0) return false;
    int k = s.size () / 2;
    for (int i = 0; i < k; i++) {
        if (s[i] != '0')    return false;
    }
    for (int i = k; i < s.size (); i++) {
        if (s[i] != '1')    return false;
    }
    return true;
}

int main () {
    vector<int> v;
    int n, cnt = 0;
    cin >> n;
    for (int i = 1; i * i <= n; i++) {
        if (n % i ==  0) {
            v.push_back (i);
            if (i != n / i) v.push_back (n / i);
        }
    }
    
    sort (v.begin (), v.end (), greater<int>());
    //for (auto i : v)    cout << i << ' ';cout << endl;
    for (auto i : v) {
        if (check (i)) {
            cout << i << endl;
            break;
        }
    }
}

C. Rumor

暴力模拟,累加每个连通块内的最小点

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 1e5 + 5, M = N * 2;
ll ans, n, m, a[N];
int h[N], e[M], ne[M], idx;
bool vis[N];

void add (int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

ll bfs (int st) {
    //vis[st] = true;
    ll res = a[st];
    queue <int> q;
    q.push (st);

    //cout << st << ' ';
    while (!q.empty ()) {
        int t = q.front ();
        q.pop ();
        if (vis[t]) continue;
        vis[t] = true;
    
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            res = min (res, a[j]);
            q.push (j);
            //cout << j << ' ';
        }
    }
    //cout << endl;
    return res;
}

int main () {
    memset (h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    while (m --) {
        int x, y;
        cin >> x >> y;
        add (x, y), add (y, x);
    }
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        ans += bfs (i);
    }
    cout << ans << endl;
}

//累加每个连通块内的最小点

D. Credit Card

学习贪心思路,用两个变量模拟
上下界贪心约束

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 1e5 + 5;
ll n, m, x, l, r, cnt;

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        if (cnt == -1)   continue;
        l += x, r += x;
        if (l > m) {
            cnt = -1;
            continue;
        }
        r = min (r, m);
        if (x == 0) {
            if (l < 0)  l = 0;
            if (r < 0)  r = m, cnt++;
        }
    }

    cout << cnt << endl;
}

//把负的最大的变为m
//上下界

E. Counting Arrays

推导过程:https://www.luogu.com.cn/blog/rated/solution-cf893e
关键在于插板法的理解

// LUOGU_RID: 115646202
#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 1e6 + 25, mod = 1e9 + 7; //注意要稍微开大一点,因为是y+d-1
ll fact[N], infact[N], pw[N], ans;

ll qmi(ll a, ll k, ll p){
    ll res = 1;
    while(k){
        if(k & 1)
            res = (ll)res * a % p;
        a = (ll)a * a % p;
        k >>= 1;
    }
    return res;
}

ll C (int a, int b) {
    if (a < b)  return 0;
    return fact[a] * infact[b] % mod * infact[a - b] % mod;
}

void init () {
    pw[0] = 1;
    for (int i = 1; i < N; i++)     pw[i] = (pw[i-1] * 2) % mod;
    fact[0] = infact[0] = 1;
    for(int i = 1; i < N; i++){
        fact[i] = (ll)fact[i-1] * i % mod;
        infact[i] = (ll)infact[i-1] * qmi(i, mod - 2,mod) % mod;
    }
}


int main () {
    init ();
    int q, x, y;
    cin >> q;

    while (q--) {
        cin >> x >> y;
        ans = 1;
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                int d = 0;
                while (x % i == 0)  x /= i, d++;
                (ans *= C (d + y - 1, y - 1) % mod) %= mod;
            }
        }
        if (x > 1)  (ans *= C (y, y - 1) % mod) %= mod;
        (ans *= pw[y-1]) %= mod;
        cout << ans << endl;
    }

    //cout << log2 (1e6) << endl;
}

F. Subtree Minimum Query

主席树维护限定区间的最小值
要注意的细节都在注释里面,注意query函数的含义和返回条件
调了快一天,这就是数据结构的魅力

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 100005, M = N * 2;
int a[N], n, q, ans, k, x;
int h[N], e[M], ne[M], idx;
int dep[N], dfn[N], sz[N], idx2;
int p[N], root[N], cnt;

void add (int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs (int u, int fa) {
    dep[u] = dep[fa] + 1; //节点深度
    sz[u] = 1, dfn[u] = ++idx2; //子树大小,dfs序
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa)    continue;
        dfs (j, u);
        sz[u] += sz[j];
    }
}

struct Node {
    int l, r, cnt;
}st[N * 64]; //4N + NlogN

int insert (int u, int l, int r, int x, int v) { //在版本u节点下标范围为[l,r]的树上插入下标为x,权值为v的点
    int p = ++cnt;
    st[p] = st[u];
    if (l == r) {
        st[p].cnt = v;
        return p;
    }
    int mid = l + r >> 1; 
    if (x <= mid)    st[p].l = insert (st[u].l, l, mid, x, v);
    else    st[p].r = insert (st[u].r, mid + 1, r, x, v);
    st[p].cnt = min(st[st[p].l].cnt, st[st[p].r].cnt);
    return p;
}

int query (int u, int l, int r, int ql, int qr) { //目前查找的是版本u,节点下标范围为[l,r]的树,要求下标在[ql,qr]范围内
    if (l >= ql && r <= qr) return st[u].cnt; //注意该行的判断条件;查找的坐标范围为[ql,qr],故满足就返回,而无需l==r递归到叶节点,因为st[u].cnt已经存储了[l,r]的区间最小值了
    int mid = l + r >> 1, res = 1e9;
    if (ql <= mid)   res = min(res, query (st[u].l, l, mid, ql, qr)); //答案落在左区间
    if (qr > mid)    res = min(res, query (st[u].r, mid + 1, r, ql, qr)); //答案落在右区间
    return res;
}

bool cmp (int x, int y) {
    return dep[x] < dep[y];
}

signed main () {
    st->cnt = 1e9;
    memset (h, -1, sizeof h);
    scanf ("%lld%lld", &n, &q);
    for (int i = 1; i <= n; i++)    scanf ("%lld", &a[i]);
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf ("%lld%lld", &a, &b);
        add (a, b), add (b, a);
    }
    dfs (q, 0);
    for (int i = 1; i <= n; i++)    p[i] = i; //映射下标,因为后面要根据dfs序来插入
    sort (p + 1, p + n + 1, cmp); 
    for (int i = 1; i <= n; i++) { //按深度建树
        int id = p[i]; //当前插入的点真正的下标
        root[dep[id]] = insert (root[dep[p[i-1]]], 1, n, dfn[id], a[id]); //版本更新
    }
    scanf ("%lld", &q);
    while (q--) {
        scanf ("%lld%lld", &x, &k);
        x = (x + ans) % n + 1, k = (k + ans) % n;
        int tt = min (dep[x] + k, dep[p[n]]); //tt为当前版本
        ans = query (root[tt], 1, n, dfn[x], dfn[x] + sz[x] - 1); //dep[x]版本以前一定没有深度超过dfn[x]的点所以无需使用前缀差
        printf ("%lld\n", ans);
    }
}

// x k
//强制在线

标签:Educational,Rated,33,res,ll,cnt,st,int,mod
From: https://www.cnblogs.com/CTing/p/17558403.html

相关文章

  • Educational Codeforces Round 137 (Rated for Div. 2)
    EducationalCodeforcesRound137(RatedforDiv.2) A.Passwordvoidsolve(){intn=read();for(inti=1;i<=n;i++)intx=read();cout<<combination(10-n,2)*6<<'\n';//puts(ans>0?"YES":"NO");......
  • PPT|智慧实验室物联网解决方案P33
    ......
  • 133.什么是Proxy
    133.什么是Proxy?Proxy用于修改某些操作的默认行为,等同于在语言层面做出修改,所以属于一种“元编程”,即对编程语言进行编程。Proxy可以理解成,在目标对象之前架设一层“拦截”,外界对该对象的访问,都必须先通过这层拦截,因此提供了一种机制,可以对外界的访问进行过滤和改写。Prox......
  • 洛谷 P3372 【模板】线段树 1
    题目传送门题目描述如题,已知一个数列,你需要进行下面两种操作:1.将某一个数加上x2.求出某区间每一个数的和输入格式第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。接下来M行每行包含3......
  • CF339 题解
    CF339题解这套题虽然是div2,但是具有一定的价值,这套题作为典型的div2题目,全套5道题都几乎用暴力方法解决,但是为什么这样是对的?令人深思。A红题,把个位数提出来再排序就好了。#include<bits/stdc++.h>usingnamespacestd;constintN=105;chars[N];intn,num[N],tot=0......
  • Oracle学习笔记:parallel并行处理 --转载 https://blog.csdn.net/w892824196/article/
    在使用oracel查询时,可以通过并行提高查询速度。例如:select/*+parallel(a,6)*/count(1)fromtable_namea;强行启用并行度来执行当前SQL。加上这个说明之后,可以强行启用Oracle的多线程处理功能,提高效率。但本身启动这个功能,也是要消耗资源与性能的。所有,一般都会在返回记......
  • P3393 逃离僵尸岛
    P3393逃离僵尸岛-洛谷 多源BFS---------->把所有直接占领点压入队列,bfs求解距离#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#defineendl"\n"#defineintlonglongconstintN=5e5+5;std::vector<int>edge[N];intn,m,k,s,cost......
  • CF1336C(挺重要的区间dp)
    KaaviandMagicSpell-洛谷|计算机科学教育新生态(luogu.com.cn)我们直接考虑如何构造出来的字符串,这个字符串显然只能每次最左端加或者最右端加入。对于第一个字符,显然每个位置都够能放置,且有两种方案。接着下一个字符加入它的左端或者右端,依次类推。令dp[i][j]为s(1......
  • ARC133F FWT 做法
    看见网上题解都是“二维生成函数”,就来传一下这个做法(问题可以转化为:\(n\)枚硬币,每次随机翻一枚,求最后正面朝上硬币个数的期望。把这个过程看作XOR卷积,并且需要卷积的两个数组有特性:在popcount相同的位置值相同。这样只要对这种特殊的数组能做fwt就做完了。于是现在要......
  • Educational Codeforces Round 151 (Rated for Div. 2)
    D.RatingSystem题目大意玩家的初始积分为0,该玩家连续进行\(n\)场比赛,每场比赛可升高或降低玩家的积分(\(a_i\))。你可以设置一个\(k\)值,比赛过程中玩家的积分不会低于\(k\)(若有一场比赛会使玩家的积分低于\(k\),比赛后玩家的积分会被强制变为\(k\))。找到一个\(k\),使经过\(n\)......