codeforces educational round 73 div2 ABCD

A. 2048 Game

Description

给出n个2的幂次数，问能否累加得到2048

Solution

从小往上累加。

B. Knights

Description

Solution

贪心构造。

奇数位和偶数位放置不同就行了。

C. Perfect Team

Description

给出三个数，$c,m,x$代表每种选手的个数。

每三个人组一队，每队要求至少有一个c，一个m。

问最多能组多少支队伍。

Solution

显然最多只能组成$min(c,m)$只队伍。

这是在$x geq min(c,m)$的情况下能取到这个值。

在$x lt min(c,m)$时，还有限制条件是$res leq frac{c+m+x}{3}$

相当于有$x$队是$1:1:1$,然后剩下的c和m随机12/21配对

  1 #include <algorithm>
  2 #include <numeric>
  3 #include <cctype>
  4 #include <cmath>
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <cstring>
  8 #include <iostream>
  9 #include <map>
 10 #include <queue>
 11 #include <set>
 12 #include <stack>
 13 #if __cplusplus >= 201103L
 14 #include <unordered_map>
 15 #include <unordered_set>
 16 #endif
 17 #include <vector>
 18 #define lson rt << 1, l, mid
 19 #define rson rt << 1 | 1, mid + 1, r
 20 #define LONG_LONG_MAX 9223372036854775807LL
 21 #define pblank putchar(' ')
 22 #define ll LL
 23 #define fastIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
 24 using namespace std;
 25 typedef long long ll;
 26 typedef long double ld;
 27 typedef unsigned long long ull;
 28 typedef pair<int, int> P;
 29 int n, m, k;
 30 const int maxn = 1e5 + 10;
 31 template <class T>
 32 inline T read()
 33 {
 34     int f = 1;
 35     T ret = 0;
 36     char ch = getchar();
 37     while (!isdigit(ch))
 38     {
 39         if (ch == '-')
 40             f = -1;
 41         ch = getchar();
 42     }
 43     while (isdigit(ch))
 44     {
 45         ret = (ret << 1) + (ret << 3) + ch - '0';
 46         ch = getchar();
 47     }
 48     ret *= f;
 49     return ret;
 50 }
 51 template <class T>
 52 inline void write(T n)
 53 {
 54     if (n < 0)
 55     {
 56         putchar('-');
 57         n = -n;
 58     }
 59     if (n >= 10)
 60     {
 61         write(n / 10);
 62     }
 63     putchar(n % 10 + '0');
 64 }
 65 template <class T>
 66 inline void writeln(const T &n)
 67 {
 68     write(n);
 69     puts("");
 70 }
 71 template <typename T>
 72 void _write(const T &t)
 73 {
 74     write(t);
 75 }
 76 template <typename T, typename... Args>
 77 void _write(const T &t, Args... args)
 78 {
 79 write(t), pblank;
 80  _write(args...);
 81 }
 82 template <typename T, typename... Args>
 83 inline void write_line(const T &t, const Args &... data)
 84 {
 85    _write(t, data...);
 86 }
 87 int main(int argc, char const *argv[])
 88 {
 89 #ifndef ONLINE_JUDGE
 90     freopen("in.txt","r", stdin);
 91     // freopen("out.txt","w", stdout);
 92 #endif
 93     int t = read<int>();
 94     while(t--){
 95         ll c = read<ll>(), m = read<ll>(), x = read<ll>();
 96         ll res = min(c, m);
 97         res = min(res, (c + m + x) / 3);
 98         writeln(res);
 99     }
100     return 0;
101 }

View Code

D. Make The Fence Great Again

Description

给出两个序列对应篱笆的高度和对应篱笆高度增加的代价。

要求序列内相邻篱笆的高度不同的最小代价。

Solution

一开始想二分，想到最后也没想出个所以。

容易得到序列内的值最多不会增加超过两次。

$2,2,3$如果第二个2的代价最小，那它也只增加两次，其他情况都是小于两次的。

这样想就容易想到经典dp走楼梯，当前楼梯可以由之前楼梯走一步或两步得到，当然由于题目特殊这里0步也阔以。

而且需要为每一步加上一个走的代价。最后求一个最小值。

$dp[i][j]$代表当前第i个值需要加j次满足题意的最小代价。

那么$dp[i][j]$可以由$dp[i-1][k]$转移得到，当且仅当$a[i]+j!=a[i-1]+k$

  1 #include <algorithm>
  2 #include <numeric>
  3 #include <cctype>
  4 #include <cmath>
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <cstring>
  8 #include <iostream>
  9 #include <map>
 10 #include <queue>
 11 #include <set>
 12 #include <stack>
 13 #if __cplusplus >= 201103L
 14 #include <unordered_map>
 15 #include <unordered_set>
 16 #endif
 17 #include <vector>
 18 #define lson rt << 1, l, mid
 19 #define rson rt << 1 | 1, mid + 1, r
 20 #define LONG_LONG_MAX 9223372036854775807LL
 21 #define pblank putchar(' ')
 22 #define ll LL
 23 #define fastIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
 24 using namespace std;
 25 typedef long long ll;
 26 typedef long double ld;
 27 typedef unsigned long long ull;
 28 typedef pair<int, int> P;
 29 int n, m, k;
 30 const int maxn = 3e5 + 10;
 31 template <class T>
 32 inline T read()
 33 {
 34     int f = 1;
 35     T ret = 0;
 36     char ch = getchar();
 37     while (!isdigit(ch))
 38     {
 39         if (ch == '-')
 40             f = -1;
 41         ch = getchar();
 42     }
 43     while (isdigit(ch))
 44     {
 45         ret = (ret << 1) + (ret << 3) + ch - '0';
 46         ch = getchar();
 47     }
 48     ret *= f;
 49     return ret;
 50 }
 51 template <class T>
 52 inline void write(T n)
 53 {
 54     if (n < 0)
 55     {
 56         putchar('-');
 57         n = -n;
 58     }
 59     if (n >= 10)
 60     {
 61         write(n / 10);
 62     }
 63     putchar(n % 10 + '0');
 64 }
 65 template <class T>
 66 inline void writeln(const T &n)
 67 {
 68     write(n);
 69     puts("");
 70 }
 71 template <typename T>
 72 void _write(const T &t)
 73 {
 74     write(t);
 75 }
 76 template <typename T, typename... Args>
 77 void _write(const T &t, Args... args)
 78 {
 79 write(t), pblank;
 80  _write(args...);
 81 }
 82 template <typename T, typename... Args>
 83 inline void write_line(const T &t, const Args &... data)
 84 {
 85    _write(t, data...);
 86 }
 87 ll a[maxn], b[maxn];
 88 ll dp[maxn][3];
 89 int main(int argc, char const *argv[])
 90 {
 91 #ifndef ONLINE_JUDGE
 92     freopen("in.txt","r", stdin);
 93     // freopen("out.txt","w", stdout);
 94 #endif
 95     int t = read<int>();
 96     while(t--){
 97         n = read<int>();
 98         for (int i = 1; i <= n;i++)
 99             a[i] = read<ll>(), b[i] = read<ll>(), dp[i][0] = dp[i][1] = dp[i][2] = 1e18+10;
100         for (int i = 1; i <= n;i++)
101             for (int j = 0; j <= 2;j++)
102                 for (int k = 0; k <= 2;k++)
103                     if (a[i]+j!=a[i-1]+k)
104                         dp[i][j] = min(dp[i][j], dp[i - 1][k] + j * b[i]);
105         writeln(min(min(dp[n][0], dp[n][1]), dp[n][2]));
106     }
107     return 0;
108 }

View Code