Educational Codeforces Round 33 (Rated for Div. 2) 题解

题目链接：http://codeforces.com/contest/893

A. Chess For Three

题意：判断给定的每局的胜者是否符合题意，第一局1和2参赛，3旁观，第二局上一局的胜者和3参赛，上一局的败者旁观，以此类推。

解法：直接模拟，看是否出现矛盾即可。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, a=1, b=2, c=3, d;
    scanf("%d", &n);
    while(n--){
        scanf("%d", &d);
        if(d==c){
            return 0*puts("NO");
        }
        if(d==a) swap(b, c);
        else swap(a, c);
    }
    puts("YES");
}

B. Beautiful Divisors

题意：题目给出了一个数n，让你从它的因子里面找出一个最大的美丽的数

解法：枚举美丽的数，然后与判断是否可以整除

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    LL n;
    scanf("%lld", &n);
    for(int i=18; i>=1; i--){
        if(n%(1LL*((1LL<<i)-1)*(1LL<<(i-1)))==0){
            return 0*printf("%lld\n",((1LL<<i)-1)*(1LL<<(i-1)));
        }
    }
}

C. Rumor

题意：每个字母传递一个人有一个代价，朋友之间传递不需要代价，问所有人都被传到需要多少代价。

解法：dfs维护每个联通快的最小值，然后求和。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
typedef long long LL;
vector <int> G[maxn];
int a[maxn];
bool vis[maxn];
LL ans = 0;
int dfs(int x){
    vis[x] = 1;
    int now = a[x];
    for(int v:G[x]){
        if(vis[v]) continue;
        now = min(now, dfs(v));
    }
    return now;
}
int main(){
    int n, m;
    scanf("%d%d", &n,&m);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    for(int i=1; i<=m; i++){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1; i<=n; i++){
        if(!vis[i]){
            ans += dfs(i);
        }
    }
    return 0*printf("%lld\n", ans);
}

D. Credit Card

题意：信用卡n天交易记录，第i天可能赚钱，可能赔钱，可以查账，赚钱后，帐户总余额不能超过上限，超过就不符合要求输出-1，查账的时候，不希望余额是负值，如果哪天赔钱后，可以去银行存任意数量的钱，把余额变成大于等于0.希望查账的日子都不会查到负数。

解法：考虑贪心，在每次存钱的时候可以存多点，这样赔钱数比较少的情况下，下次查账也是正值，不用去银行。维护后缀最大值可以办到，后缀最大值写挂了，WA了2发。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 1e5+10;
LL submax[maxn];
LL ans, a[maxn];
LL delta,sum[maxn];

int main(){
    LL n, d;
    scanf("%lld %lld", &n,&d);
    for(LL i=1; i<=n; i++) scanf("%lld", &a[i]), sum[i]=sum[i-1]+a[i];
    submax[n] = sum[n];
    for(LL i=n-1; i>=1; i--) submax[i] = max(sum[i], submax[i+1]);
    if(submax[1]>d) return 0*puts("-1");
    LL now = 0;
    for(LL i=1; i<=n; i++){
        if(a[i]) now += a[i];
        else{
            if(now>=0) continue;
            LL tt = submax[i]+delta;
            LL curadd = d-tt;
            now += curadd;
            delta += curadd;
            if(now<0) return 0*puts("-1");
            ans++;
        }
    }
    return 0*printf("%lld\n", ans);
}

E. Counting Arrays

题意：n个数拆成k个可以重复的数的乘积方案数

解法：对每个因子单独考虑，就会发现对于每一个质数因子来说，假设有x个，就相当于把x个数放在k个没有标号的桶里面，这个组合数是C(k+x-1,x)，最后还有考虑负数的情况i昂，就是C(2,n)+(4,n)+...+C(n, n)这样求和之后答案就是2^(n-1),乘起来就可以了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 7;
LL inv[maxn];
LL prime[maxn];
bool isprime[maxn];
int cnt = 0;
void init()
{
    for(int i=1; i<maxn; i++) isprime[i] = 1;
    for (LL i = 2; i < maxn; i++)
    {
        if (isprime[i])
        {
            for (LL j = i + i; j < maxn; j += i) isprime[j] = 0;
        }
    }
    for (int i = 2; i < maxn; i++) if (isprime[i]) prime[++cnt] = i;
}
vector <int> Get(int x)
{
    vector <int> ret;
    for (int i = 1; prime[i]*prime[i] <= x; i++)
    {
        int t = 0;
        while (x % prime[i] == 0)
        {
            t++;
            x /= prime[i];
        }
        if (t) ret.push_back(t);
    }
    if (x > 1) ret.push_back(1);
    return ret;
}
LL qsm(LL a, LL n)
{
    LL ret = 1;
    while (n)
    {
        if (n & 1) ret = ret * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ret;
}
LL C(LL n, LL m)
{
    m = n - m;
    LL ret = 1;
    for (LL i = 1; i <= m; i++) ret = ret * (n - i + 1) % mod * inv[i] % mod;
    return ret;
}
void predeal()
{
    init();
    inv[0] = inv[1] = 1;
    for (int i = 2; i < maxn; i++)
    {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }
}
int main()
{
    predeal();
    int q, x, y;
    scanf("%d", &q);
    while(q--){
        scanf("%d %d", &x,&y);
        vector <int> now = Get(x);
        LL ans = 1;
        for(int v:now){
            ans = ans * C(y+v-1, y-1) % mod;
        }
        ans = ans * qsm(2, y-1) % mod;
        if(ans < 0) ans += mod;
        printf("%lld\n", ans);
    }
    return 0;
}

F. Subtree Minimum Query

题意：一个有根树，每次查询x的祖先节点和x节点的距离小于等于y的所有点的值的最小值。

解法：dfs,按照深度动态建树，启发式合并即可。空间复杂度O(nlogn)，时间复杂度O(nlogn)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
const int maxm = maxn*40;
const int inf = 0x3f3f3f3f;
int a[maxn], dep[maxn];
vector <int> G[maxn];
int T[maxn], tot;
int val[maxm], ls[maxm], rs[maxm];
void push_up(int rt){
    val[rt] = min(val[ls[rt]], val[rs[rt]]);
}
void update(int pos, int v, int l, int r, int &rt){
    rt = ++tot;
    if(l==r){
        val[rt] = v;
        return;
    }
    int mid = (l+r)/2;
    if(pos <= mid) update(pos, v, l, mid, ls[rt]);
    else update(pos, v, mid+1, r, rs[rt]);
    push_up(rt);
}
int merge(int u, int v){
    if(!u) return v;
    if(!v) return u;
    int t = ++tot;
    ls[t] = merge(ls[u], ls[v]);
    rs[t] = merge(rs[u], rs[v]);
    if(ls[t]||rs[t]) push_up(t);
    else val[t] = min(val[u], val[v]);
    return t;
}
int query(int L, int R, int l, int r, int rt){
    if(!rt) return inf;
    if(L<=l&&r<=R) return val[rt];
    int mid = (l+r)/2;
    if(R<=mid) return query(L, R, l, mid, ls[rt]);
    else if(L>mid) return query(L, R, mid+1, r, rs[rt]);
    else return min(query(L,mid,l,mid,ls[rt]), query(mid+1,R,mid+1,r,rs[rt]));
}
void dfs(int u, int f){
    update(dep[u], a[u], 1, maxn-1, T[u]);
    for(int v:G[u]){
        if(v==f) continue;
        dep[v] = dep[u]+1;
        dfs(v, u);
        T[u] = merge(T[u], T[v]);
    }
}
int main(){
    val[0] = inf;
    int n, r;
    scanf("%d%d", &n,&r);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<n; i++){
        int u, v;
        scanf("%d%d", &u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dep[r] = 1;
    dfs(r, 0);
    int m, last = 0;
    scanf("%d", &m);
    for(int i=1; i<=m; i++){
        int p, q;
        scanf("%d%d", &p,&q);
        int x = (p+last)%n+1, y = (q+last)%n;
        printf("%d\n", last = query(dep[x], min(maxn-1, dep[x]+y), 1, maxn-1, T[x]));
    }
}