Educational Codeforces Round 83 补题

发表于 更新于 分类于 阅读次数：

最近越打越菜，补题
Educational Codeforces Round 83 (Rated for Div. 2)

A. Two Regular Polygons

思路

没什么好说的，当$n$能被$m$整除的时候，$m$边形所有顶点一定可以与$n$边形重合。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int t,n,m;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        if(n%m)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
    return 0;
}

B. Bogosort

题意

给你一个数组，排列元素，使得任意一对元素$a_i$与$a_j$，$i−a_i≠j−
a_j$。输出任一可行解即可。

思路

当$i<j$时，如果令$a_i≥a_j$的话，不等式一定成立，所以从大到小排序即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
int a[maxn];
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+n+1,greater<int>());
        for(int i=1;i<=n;i++)
            cout<<a[i]<<' ';
        cout<<endl;
    }
    return 0;
}

C. Adding Powers

题意

对于一个大小为$n$的全0数组，能否进行以下操作，使得这个数组变为目标数组

  • 第$i$次操作时，可以对当前数组任意元素加上$k^i$，或者跳过
  • 操作数$i$从$0$开始计数

思路

贪心，对于目标数组的每一个元素$a_i$，找到这个数用$k$的幂之和的表示方法，如果其中一个幂使用了两次，则为NO；若出现其他元素使用过的幂，则也为NO。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
ll a[maxn],rec[maxn];
int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        map<ll,ll> mp;
        ll k;
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        bool flag=1;
        for(int i=1;i<=n;i++)
        {
            while(a[i]>0)
            {
                ll now=1;
                while(now*k<=a[i])
                    now*=k;
                if(mp[now])
                {
                    flag=0;
                    break;
                }
                mp[now]++;
                a[i]-=now;
            }
        }
        cout<<(flag?"YES":"NO")<<endl;
    }
    return 0;
}

D. Count the Arrays

题意

计算符合要求的数组的数量：

  1. 数组元素个数为$n$
  2. 每个元素范围$[1,m]$
  3. 数组内有且仅有一对元素相等
  4. 数组有一下标$i$，$i$及之前元素严格递增，$i$及其后元素严格递减。

思路

组合数学，套一个$Lucas$板子。

  1. 在$m$个数中挑出$n-1$个数，最大的数作为中间塔顶。
  2. 剩下的$n-2$个数挑出来一个，左右各分配一个。
  3. 其余的$n-3$个元素每个有左/右两种可能

所以答案为：
$C_m^{n-1}\times (n-2)\times 2^{n-3}$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5,inf=0x3f3f3f3f,mod=998244353;
//#define lowbit(x) ((x) & -(x))//<<setiosflags(ios::fixed)<<setprecision(9)
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
    read(oth...);
}
ll POW(ll a,ll b,ll p)
{
    ll ans = 1;
    while(b){
        if(b&1)
            ans = (ans%p*a%p) % p;
        a = (a%p*a%p) % p;
        b >>= 1;
    }
    return ans%p;
}
ll C(ll n,ll m,ll p)
{
    if(m > n)return 0;
    if(m == n)return 1;
    if(m > n - m)m = n - m;
    ll a = 1, b = 1 ;
    for(ll i = 0 ; i < m ; i++){
        a = a * (n - i) % p;
        b = b * (i + 1) % p;
    }
    return a * POW(b,p-2,p) % p;
}
ll lucas(ll n,ll m,ll p){//C(n,m)%p
    if(m == 0)
        return 1;
    return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
}
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    ll n,m,ans=0;
    cin>>n>>m;
    if(n==2)
    {
        cout<<0<<endl;
        exit(0);
    }
    cout<<lucas(m,n-1,mod)*(n-2)%mod*POW(2,n-3,mod)%mod<<endl;
    return 0;
}

E. Array Shrinking

题意

一个长度为$n$的数组$a$，对于任一元素$a_i$，若有$a_i=a_{i+1}$，则可用$a_i+1$来替换这两个元素，求数组变化后的最小长度。

思路

读完题就感觉是区间DP，可惜我不会……
用$dp[l][r]$来表示区间$[l,r]$合并后的值，$dp[l][r]=0$时说明这一区间无法连续合并。
$f[i]$表示到下标$i$的合并后的最小长度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=505,inf=0x3f3f3f3f,mod=1000000007;
//#define lowbit(x) ((x) & -(x))//<<setiosflags(ios::fixed)<<setprecision(9)
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
    read(oth...);
}
int dp[maxn][maxn],f[maxn];
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>dp[i][i];
    for(int len=2;len<=n;len++)//长度
    {
        for(int l=1;l<=n;l++)//起点
        {
            int r=l+len-1;//终点
            if(r>n)
                break;
            for(int k=l;k<r;k++)//枚举分割点
            {
                if(dp[l][k]&&dp[l][k]==dp[k+1][r])
                    dp[l][r]=dp[l][k]+1;
            }
        }
    }
    memset(f,inf,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            if(dp[j+1][i])//j+1到i可以合成一块
                f[i]=min(f[i],f[j]+1);
    cout<<f[n]<<endl;
    return 0;
}

F、G估计不会，以后再补吧……