2020-03-10发表2020-12-20更新ICPC/CCPC / Contests / Codeforces13 分钟读完 (大约1900个字)

Educational Codeforces Round 83

A. Two Regular Polygons

Solution

原问题等价于 $m$ 能否整除 $n$.

Code

>folded

#include<algorithm>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

int T, n, m;

int main(){
    read(T);
    while(T--){
        read(n, m);
        if(n % m)   puts("NO");
        else    puts("YES");
    }
    return 0;
}

B. Bogosort

Solution

倒序排序即可。

Code

>folded

#include<algorithm>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

int T, n, a[105];
bool cmp(int A, int B){ return A > B; }

int main(){
    read(T);
    while(T--){
        read(n);
        for(int i = 1; i <= n; i++) read(a[i]);
        sort(a+1, a+n+1, cmp);
        for(int i = 1; i <= n; i++) printf("%d ", a[i]);
        putchar(10);
    }
    return 0;
}

C. Adding Powers

Solution

把每一个数表示成 $k$ 进制数，若不能表示成 $k$ 进制或有两个 $k$ 进制数同时存在某一位，输出 NO。

Code

>folded

#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

int T, n;
LL a, k;
bool b[100];

inline bool div(LL x){
    if(!x)  return true;
    int i; LL t = 1;
    for(i = 1; ; i++){
        if(t * k > x || t * k < 0)  break;
        t *= k;
    }
    for(int j = i - 1; j >= 0; j--, t /= k){
        if(x >= t){
            if(b[j])    return false;
            b[j] = true;
            x -= t;
        }
    }
    if(x > 0)   return false;
    return true;
}

int main(){
    read(T);
    while(T--){
        read(n, k);
        memset(b, 0, sizeof b);
        bool ok = true;
        for(int i = 1; i <= n; i++){
            read(a);
            if(!div(a)) ok = false;
        }
        if(!ok) puts("NO");
        else    puts("YES");
    }
    return 0;
}

D. Count the Arrays

Solution

推一波式子。

枚举最高点 $k$，设其值为 $r\ (n-1\leq r\leq m)$，则从 $1\sim r-1$ 中选出 $n-2$ 个数，有 $C_{r-1}^{n-2}$ 种选法；然后从这 $n-2$ 个数之中选一个数重复一遍，有 $C_{n-2}^1$ 种选法；现在得到了 $n-1$ 个数（$1$ 个重复），从除开重复的 $n-3$ 个数中选 $k-2$ 个放在 $k$ 之前，其余的自然放在 $k$ 之后，共 $C_{n-3}^{k-2}$ 种选法。故答案为：

$\sum\limits_{k=2}^{n-1}\sum\limits_{r=n-1}^m C_{r-1}^{n-2}C_{n-2}^1C_{n-3}^{k-2}=(n-2)\cdot\left[\sum\limits_{k=2}^{n-1}C_{n-3}^{k-2}\right]\cdot\left[\sum\limits_{r=n-1}^mC_{r-1}^{n-2}\right]=(n-2)\cdot2^{n-3}\cdot C_{m}^{n-1}$

组合数预处理阶乘及其逆元即可。

Code

>folded

#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const LL MOD = 998244353;

int n, m;
LL fac[200005], invfac[200005], ans;

LL fpow(LL bs, LL idx){
    LL res = 1;
    bs %= MOD;
    while(idx){
        if(idx & 1) (res *= bs) %= MOD;
        (bs *= bs) %= MOD;
        idx >>= 1;
    }
    return res % MOD;
}

inline LL C(LL a, LL b){ return fac[a] * invfac[b] % MOD * invfac[a-b] % MOD; }

int main(){
    fac[0] = 1, invfac[0] = 1;
    for(int i = 1; i <= 200000; i++){
        fac[i] = fac[i-1] * i % MOD;
        invfac[i] = fpow(fac[i], MOD - 2);
    }
    read(n, m);
    printf("%lld\n", n == 2 ? 0 : (n - 2) * fpow(2, n-3) % MOD * C(m, n-1) % MOD);
    return 0;
}

E. Array Shrinking

Solution

区间 dp. 设 $dp[i][j]$ 表示 $a[i\cdots j]$ 的最小长度，那么枚举中间的断点进行转移：$dp[i][j]=dp[i][k]+dp[k+1][j]$（不考虑合并）；我们只在 $dp[i][k]=dp[k+1][j]=1$ 且可以合并的情况下考虑合并，因为所有的合并都一定可以拆成若干长度为 $1$ 的项的合并。

Code

>folded

#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 505;

int n, a[N], dp[N][N], v[N][N];

int main(){
    memset(dp, 0x7f, sizeof dp);
    read(n);
    for(int i = 1; i <= n; i++){
        read(a[i]);
        dp[i][i] = 1;
        v[i][i] = a[i];
    }
    for(int l = 1; l <= n; l++){
        for(int i = 1; i <= n; i++){
            int j = i + l;
            if(j > n)   break;
            for(int k = i; k < j; k++){
                if(dp[i][k] == 1 && dp[k+1][j] == 1 && v[i][k] == v[k+1][j]){
                    dp[i][j] = 1;
                    v[i][j] = v[i][k] + 1;
                } else  dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
            }
        }
    }
    printf("%d\n", dp[1][n]);
    return 0;
}

F. Attack on Red Kingdom

G. Autocompletion

Solution

题目的输入方式其实自然构成了一棵 Trie 树。我们按字典序 $dfs$ 这棵 Trie 树，维护每个点的答案。具体的，当前点的答案至少是上一个点的答案 $+1$（即在上一个点之后输入一个字符）；然后如果当前点在 $S$ 中，它也有可能来自其某个祖先的 autocompletion，考虑怎么处理这部分。

我们对每个点记录它的列表中第一个还没被遍历到的点是列表的第几个点，所以初始情况是所有点的记录均为 $1$。随后，凡遍历到一个 $S$ 中的点，就将它的所有祖先以及它自己的记录 $+1$，表示以后的点想要使用 autocompletion 功能时，必须要在列表中花费一秒走过这个点；由于我们是按照字典序遍历的，所以这些 $+1$ 累加起来就是走过已经遍历过的点一共需要花费的时间。处理完当前点之后，把当前点答案加入记录，意思是从这个点往下转移时先要加上到达这个点的时间。这样遇到下一个 $S$ 中的点时，用其所有祖先的最小记录值更新答案即可。

上述过程涉及到区间加与区间求最小值，可以开线段树做。线段树的下标选用树的深度最为方便（用 $dfs$ 序也可，实现上稍微麻烦一点）。

Code

>folded

#include<algorithm>
#include<cstdio>
#include<vector>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 1000005;

int n, k, ans[N], a[N];
bool mark[N];
struct Node{
    char ch; int id;
    Node(char ch, int id): ch(ch), id(id) {}
    bool operator < (const Node &A) const{
        return ch < A.ch;
    }
};
vector<Node> trie[N];

struct segTree{
    int l, r, mn, lazy;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
inline void pushup(int id){
    tr[id].mn = min(tr[lid].mn, tr[rid].mn);
}
inline void pushdown(int id){
    if(tr[id].l == tr[id].r)    return;
    if(tr[id].lazy){
        tr[lid].lazy += tr[id].lazy;
        tr[lid].mn += tr[id].lazy;
        tr[rid].lazy += tr[id].lazy;
        tr[rid].mn += tr[id].lazy;
        tr[id].lazy = 0;
    }
}
void build(int id, int l, int r){
    tr[id].l = l, tr[id].r = r;
    tr[id].mn = 1;
    if(tr[id].l == tr[id].r)    return;
    build(lid, l, mid);
    build(rid, mid+1, r);
    pushup(id);
}
void add(int id, int l, int r, int val){
    pushdown(id);
    if(tr[id].l == l && tr[id].r == r){
        tr[id].lazy += val;
        tr[id].mn += val;
        return;
    }
    if(r <= mid)    add(lid, l, r, val);
    else if(l > mid)    add(rid, l, r, val);
    else    add(lid, l, mid, val), add(rid, mid+1, r, val);
    pushup(id);
}
int query(int id, int l, int r){
    pushdown(id);
    if(tr[id].l == l && tr[id].r == r)  return tr[id].mn;
    if(r <= mid)    return query(lid, l, r);
    else if(l > mid)    return query(rid, l, r);
    else    return min(query(lid, l, mid), query(rid, mid+1, r));
}
void setVal(int id, int pos, int val){
    pushdown(id);
    if(tr[id].l == tr[id].r){
        tr[id].mn = val;
        tr[id].lazy = 0;
        return;
    }
    if(pos <= mid)  setVal(lid, pos, val);
    else    setVal(rid, pos, val);
    pushup(id);
}

void dfs(int x, int f, int dep){
    if(x){
        ans[x] = ans[f] + 1;
        if(mark[x]){
            ans[x] = min(ans[x], query(1, 1, dep - 1));
            add(1, 1, dep, 1);
        }
        add(1, dep, dep, ans[x]);
    }
    for(auto to: trie[x])   dfs(to.id, x, dep+1);
    setVal(1, dep, 1);
}

int main(){
    read(n);
    build(1, 1, n+1);
    for(int i = 1; i <= n; i++){
        int p; char ch[2]; read(p); scanf("%s", ch);
        trie[p].push_back(Node(ch[0], i));
    }
    for(int i = 0; i < n; i++)
        sort(trie[i].begin(), trie[i].end());
    read(k);
    for(int i = 1; i <= k; i++){
        read(a[i]);
        mark[a[i]] = true;
    }
    dfs(0, -1, 1);
    for(int i = 1; i <= k; i++) printf("%d ", ans[a[i]]);
    return 0;
}

Educational Codeforces Round 83

http://xyfjason.github.io/blog-xcpc/2020/03/10/Educational-Codeforces-Round-83/

作者

xyfJASON

发布于

2020-03-10

更新于

2020-12-20

许可协议

#Codeforces

Educational Codeforces Round 83

A. Two Regular Polygons

Solution

Code

B. Bogosort

Solution

Code

C. Adding Powers

Solution

Code

D. Count the Arrays

Solution

Code

E. Array Shrinking

Solution

Code

F. Attack on Red Kingdom

G. Autocompletion

Solution

Code

作者

发布于

更新于

许可协议

评论

分类

最新文章

标签