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
//强制在线