Educational Codeforces Round 83 (Rated for Div. 2)

A. Two Regular Polygons

签到。

Code

/*
 * Author:  heyuhhh
 * Created Time:  2020/3/9 22:39:05
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '
'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
  template <template<typename...> class T, typename t, typename... A> 
  void err(const T <t> &arg, const A&... args) {
  for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
  #define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
 
int n, m;
 
void run() {
    cin >> n >> m;
    if(n % m == 0) cout << "YES" << '
';
    else cout << "NO" << '
';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    int T; cin >> T;
    while(T--) run();
    return 0;
}

B. Bogosort

倒序排序即可。

Code

/*
 * Author:  heyuhhh
 * Created Time:  2020/3/9 22:40:42
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '
'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
  template <template<typename...> class T, typename t, typename... A> 
  void err(const T <t> &arg, const A&... args) {
  for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
  #define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
 
int n;
int a[N];
 
void run() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for(int i = n; i >= 1; i--) cout << a[i] << " 
"[i == 1];
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    int T; cin >> T;
    while(T--) run();
    return 0;
}

C. Adding Powers

因为(displaystyle k^0+k^1+cdots+k^t=frac{(1-k^{t+1})}{1-k}<k^{t+1})。
那么直接类似于二进制那样贪心就行。
细节见代码：

Code

/*
 * Author:  heyuhhh
 * Created Time:  2020/3/9 22:44:25
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '
'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
  template <template<typename...> class T, typename t, typename... A> 
  void err(const T <t> &arg, const A&... args) {
  for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
  #define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 30 + 5;
 
int n, k;
ll a[N];
ll powk[N << 1];
 
void run() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    powk[0] = 1;
    int t;
    for(int i = 1;; i++) {
        powk[i] = powk[i - 1] * k;
        if(powk[i] > 1e16) {
            t = i - 1; break;
        }
    }
    for(int i = t; i >= 0; i--) {
        ll Max = -1;
        int id;
        for(int j = 1; j <= n; j++) {
            if(a[j] > Max) {
                Max = a[j];
                id = j;
            }
        }   
        if(Max >= powk[i]) {
            a[id] -= powk[i];   
        }
    }
    for(int i = 1; i <= n; i++) {
        if(a[i] > 0) {
            cout << "NO" << '
';
            return;
        }   
    }
    cout << "YES" << '
';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    int T; cin >> T;
    while(T--) run();
    return 0;
}

D. Count the Arrays

题意：
要求构造数组，满足以下条件：

长度为(n)，值域范围为([1,m]);
当且仅当两个数相等；
满足前面严格递增，后面严格递减。

给出(n,m)，要求满足条件的数组个数。

思路：
注意第二个条件，那么这个数组不能只有单增或者单减，并且我们可以知道数组最大值至少为(n-1)。
考虑枚举最大值来计算个数：

[egin{aligned} &sum_{i=n-1}^msum_{j=1}^{n-2}{i-1choose j}cdot jcdot {i-1-jchoose n-j-2}\ =&sum_{i=n-1}^m(i-1)!sum_{j=1}^{n-2}frac{1}{(j-1)!(n-j-2)!}\ end{aligned} ]

那么枚举(i)，后半部分随便预处理一下就行。
代码如下：

Code

/*
 * Author:  heyuhhh
 * Created Time:  2020/3/9 23:22:46
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '
'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
  template <template<typename...> class T, typename t, typename... A> 
  void err(const T <t> &arg, const A&... args) {
  for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
  #define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5, MOD = 998244353 ;
 
int qpow(ll a, ll b) {
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;   
    }
    return res;   
}
 
int n, m;
int fac[N], inv[N];
int c[N];
 
void run() {
    cin >> n >> m;
    fac[0] = 1;
    for(int i = 1; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
    inv[N - 1] = qpow(fac[N - 1], MOD - 2);
    for(int i = N - 2; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
    for(int i = 1; i < n - 1; i++) {
        c[i] = (c[i - 1] + 1ll * inv[i - 1] * inv[n - i - 2] % MOD) % MOD;
    }
    int ans = 0;
    for(int i = n - 1; i <= m; i++) {
        int res = 1ll * fac[i - 1] * inv[i - n + 1] % MOD * c[n - 2]% MOD;
        ans = (ans + res) % MOD; 
    }
    cout << ans << '
';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

E. Array Shrinking

题意：
每次可以选择相邻的两个相等的数，将其合并为一个，并且值加一。
可以执行若干次上述操作，问最后最少剩下多少个数。

思路：
直接的想法就是贪心进行合并，但是向左、向右合并的情况太过于复杂，所以我们需要考虑(dp)。
注意到一段连续相等的数，若个数为奇数个，该操作就相当于会给其一个划分，然后左右两边各自合并。那么每个各自合并的部分都可以看作是向左或是向右在合并。
所以我们求出(f[l,r])表示([l,r])区间向左合并的最小可能数。
然后(dp)一遍枚举区间划分即可。
细节见代码：

Code

/*
 * Author:  heyuhhh
 * Created Time:  2020/3/9 23:48:13
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << '
'; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
  template <template<typename...> class T, typename t, typename... A> 
  void err(const T <t> &arg, const A&... args) {
  for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
  #define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 500 + 5;
 
int n;
int a[N];
int f[N][N], g[N];
int sta[N], top;
 
void run() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) {
        top = 0;
        for(int j = i; j <= n; j++) {
            int x = a[j];
            while(top && sta[top] == x) {
                --top; ++x;
            }
            sta[++top] = x;
            f[i][j] = top;
        }
    }
    memset(g, INF, sizeof(g));
    g[0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < i; j++) {
            g[i] = min(g[i], g[j] + f[j + 1][i]);   
        }
    }
    cout << g[n] << '
';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

还有一个(O(n^3))的区间(dp)的做法。
定义(dp[l,r])表示区间([l,r])是否能合并为一段，若不能(dp)值为(-1)，否则就为合并为一段过后的值。
之后再(dp)一遍枚举划分即可。