Codeforces Round #608 (Div. 2)

A. Suits

签到。

Code

/*

 * Author:  heyuhhh

 * Created Time:  2019/12/15 17:16:33

 */

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <iomanip>

#define MP make_pair

#define fi first

#define se second

#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 << '\n'; }

  template<typename T, typename...Args>

  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }

#else

  #define dbg(...)

#endif

void pt() {std::cout << '\n'; }

template<typename T, typename...Args>

void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

//head

const int N = 1e5 + 5;

int a[4], e, f;

void run(){

    for(int i = 0; i < 4; i++) cin >> a[i];

    cin >> e >> f;

    int ans = 0;

    if(e > f) {

        int d = min(a[0], a[3]);

        ans += d * e;

        a[3] -= d;

        d = *min_element(a + 1, a + 4);

        ans += d * f;

    } else {

        int d = *min_element(a + 1, a + 4);

        ans += d * f;

        a[3] -= d;

        d = min(a[0], a[3]);

        ans += d * e;

    }

    cout << ans << '\n';

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

    run();

    return 0;

}

B. Blocks

因为最终只有可能全为黑或全为白，那么分两种情况进行翻转即可。

一开始只考虑了一种情况然后FST了...话说，如果我一开始考虑的是另一种情况进行翻转，样例都过了，那样的话就应该反应过来需要考虑两种情况了吧= =过题还是要看运气hhh

Code

/*

 * Author:  heyuhhh

 * Created Time:  2019/12/15 17:21:42

 */

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <iomanip>

#define MP make_pair

#define fi first

#define se second

#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 << '\n'; }

  template<typename T, typename...Args>

  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }

#else

  #define dbg(...)

#endif

void pt() {std::cout << '\n'; }

template<typename T, typename...Args>

void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

//head

const int N = 200 + 5;

char s[N], t[N];

int n;

void run(){

    cin >> (s + 1);

    strcpy(t + 1, s + 1);

    vector <int> ans;

    for(int i = 1; i < n; i++) {

        if(s[i] != 'W') {

            s[i] = 'W';

            s[i + 1] = (s[i + 1] == 'W' ? 'B' : 'W');

            ans.push_back(i);

        }

    }

    if(s[n] == 'W') {

        cout << sz(ans) << '\n';

        for(auto it : ans) cout << it << ' ';

        cout << '\n';

        return;

    }

    strcpy(s + 1, t + 1);

    ans.clear();

    for(int i = 1; i < n; i++) {

        if(s[i] != 'B') {

            s[i] = 'B';

            s[i + 1] = (s[i + 1] == 'B' ? 'W' : 'B');

            ans.push_back(i);

        }

    }

    if(s[n] == 'B') {

        cout << sz(ans) << '\n';

        for(auto it : ans) cout << it << ' ';

        cout << '\n';

        return;

    }

    cout << -1 << '\n';

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

    while(cin >> n) run();

    return 0;

}

C. Shawarma Tent

题意：

给出一个点\((s_x,s_y)\)，再给出\(n\)个点\((x_i,y_i)\)。

现在找到一个点\((x_0,y_0)\)，使得\(cnt\)最大。每当有一个点\((x_i,y_i)\)到点\((s_x,s_y)\)的最短曼哈顿距离经过\((x_0,y_0)\)时，\(cnt\)++。

最后输出\(cnt\)和\((x_0,y_0)\)。

思路：

显然，所有最短曼哈顿路径必然存在于一个矩形之内。

那么我们直接将所有以\((s_x,s_y),(x_i,y_i)\)为顶点的矩形画出来即可发现最优位置只可能存在于\((s_x,s_y)\)的四个方向上。

所以直接统计在哪个方向上最优即可。

Code

/*

 * Author:  heyuhhh

 * Created Time:  2019/12/15 17:28:16

 */

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <iomanip>

#define MP make_pair

#define fi first

#define se second

#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 << '\n'; }

  template<typename T, typename...Args>

  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }

#else

  #define dbg(...)

#endif

void pt() {std::cout << '\n'; }

template<typename T, typename...Args>

void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

//head

const int N = 1e5 + 5;

int n, sx, sy;

int d[4];

void run(){

    for(int i = 1; i <= n; i++) {

        int x, y; cin >> x >> y;

        if(x > sx) ++d[0];

        else if(x < sx) ++d[1];

        if(y > sy) ++d[2];

        else if(y < sy) ++d[3];

    }

    int mx = *max_element(d, d + 4);

    cout << mx << '\n';

    if(d[0] == mx) {

        cout << sx + 1 << ' ' << sy << '\n';

    } else if(d[1] == mx) {

        cout << sx - 1 << ' ' << sy << '\n';

    } else if(d[2] == mx) {

        cout << sx << ' ' << sy + 1 << '\n';

    } else {

        cout << sx << ' ' << sy - 1 << '\n';

    }

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

    while(cin >> n >> sx >> sy) run();

    return 0;

}

D. Portals

题意：

现在有\(n\)个堡垒，要从\(1\)到\(n\)逐个攻破。

起初带有\(k\)个士兵，每占领一个堡垒需要\(a_i\)的士兵，可以在每座堡垒中招募\(b_i\)的士兵。

在占领堡垒的过程中不会发生伤亡。每座堡垒有一个价值\(c_i\)，若派遣一个士兵去防守，那么可以获得\(c_i\)的价值。

防守的方式有两种：

占领一座堡垒之后可以就留下一名士兵；
图中存在某些单向通道\(u\rightarrow v,u>v\)，当你在\(u\)时可以派遣一名士兵前往\(v\)（每名士兵只能穿越通道最多一次）。

现在问能否占领所有的堡垒，若能，最大能获得多少的价值。

思路：

这题初看是个模拟题，仔细想其实不是个模拟题，...带有一些\(dp\)的性质在里面。

首先有个观察：

如果我要防守\(i\)堡垒，那么我肯定是在最后时刻派遣士兵过来最优。

正确性显然，如果我们在较早时刻派遣士兵进行防守，那么我们也可以将那个士兵留在后面再派遣。

那么图中现在只剩下最多\(n\)条边。

然后就考虑\(dp:\)令\(dp[i][j]\)表示当前在第\(i\)号堡垒，带有\(j\)个士兵能获得的最大价值。

因为招募这个条件有点特殊，我们不能就在\(i\)这个位置由\(j\rightarrow j+b_i\)转移，所以可以考虑再加一维状态表示招募与否，或者直接向\(i+1\)进行转移。

可以发现后者并不影响结果。因为即便得到当前的答案，后面也会继承当前的结果。

那么一种情况就是招募士兵：\(dp[i][j]\rightarrow dp[i+1][j+b_i]\)；

另一种情况就是派遣士兵回防：\(dp[i+1][j]\rightarrow dp[i+1][j-1]\)。

需要注意两个的顺序不能颠倒。

最终时间复杂度为\(O(5000\cdot n+n)\)。

Code

/*

 * Author:  heyuhhh

 * Created Time:  2019/12/16 10:45:39

 */

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <iomanip>

#define MP make_pair

#define fi first

#define se second

#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 << '\n'; }

  template<typename T, typename...Args>

  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }

#else

  #define dbg(...)

#endif

void pt() {std::cout << '\n'; }

template<typename T, typename...Args>

void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

//head

const int N = 5000 + 5;

int n, m, k;

int a[N], b[N], c[N];

int latest[N];

int dp[N][N];

void run(){

    for(int i = 1; i <= n; i++) {

        cin >> a[i] >> b[i] >> c[i];

    }

    for(int i = 1; i <= n; i++) latest[i] = i;

    for(int i = 1; i <= m; i++) {

        int u, v; cin >> u >> v;

        latest[v] = max(latest[v], u);

    }

    for(int i = 0; i <= n + 1; i++) {

        for(int j = 0; j < N; j++) {

            dp[i][j] = -INF;

        }

    }

    dp[1][k] = 0;

    for(int i = 1; i <= n; i++) {

        vector <int> costs;

        for(int j = 1; j <= i; j++) {

            if(latest[j] == i) costs.push_back(c[j]);

        }

        sort(all(costs));

        reverse(all(costs));

        for(int j = 0; j < N; j++) {

            if(j >= a[i] && dp[i][j] >= 0) {

                dp[i + 1][j + b[i]] = max(dp[i + 1][j + b[i]], dp[i][j]);

            }

        }

        for(auto x : costs) {

            for(int j = 0; j < N; j++) {

                if(dp[i + 1][j] >= 0) {

                    dp[i + 1][j - 1] = max(dp[i + 1][j - 1], dp[i + 1][j] + x);

                }

            }

        }

    }

    int ans = -1;

    for(int i = 0; i < N; i++) ans = max(ans, dp[n + 1][i]);

    cout << ans << '\n';

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

    while(cin >> n >> m >> k) run();

    return 0;

}

E. Common Number

题意：

定义函数\(f(x):\)

\[f(x)=\left\{
\begin{aligned}
\frac{x}{2}, \ \ \ &if\ x\ is\ even\\
x-1 \ \ \ &otherwise
\end{aligned}
\right.
\]

同时定义\(path(x)\)为\(f(x),f(f(x)),\cdots\)的所有值。

现在要找最大的一个\(y\)，满足\(1\)~\(n\)中，不少于\(k\)个数，有\(y\in path(x_i)\)。

思路：

观察得到若最终答案\(y\)为奇数时，合法的\(x\)为：\(y,\ \ 2\cdot y,2\cdot y+1,\ \ 2^2\cdot y,2^2\cdot y+1,2^2\cdot y+2,2^2\cdot y+3,\ \cdots\)。

同样能找到答案为偶数时的序列。

那奇数情况举例，若答案为奇数时，那么最终个数为\(1+2+4+\cdots\)，同时对应的数以\(y\cdot 2^0,y\cdot 2^1,\cdots\)为起点。

那么只需要找到最大的\(r,2^r\leq n\)，再计算出总长度即可得到答案为某个奇数时满足条件的\(x\)个数。

显然问题具有单调性，所以二分答案即可。

因为偶数的情况和奇数的情况有点小区别，所以分奇偶两种情况二分，最后取最大值即可。

Code

/*

 * Author:  heyuhhh

 * Created Time:  2019/12/15 17:45:31

 */

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <iomanip>

#define MP make_pair

#define fi first

#define se second

#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 << '\n'; }

  template<typename T, typename...Args>

  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }

#else

  #define dbg(...)

#endif

void pt() {std::cout << '\n'; }

template<typename T, typename...Args>

void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

//head

const int N = 1e5 + 5;

ll n, k;

ll qpow(ll a, ll b) {

    ll ans = 1;

    while(b) {

        if(b & 1) ans = ans * a;

        a = a * a;

        b >>= 1;

    }

    return ans;

}

bool chk(ll x) {

    ll cnt = 0;

    if(x & 1) {

        ll now = x, tmp = 1 + (x % 2 == 0);

        int k = 0;

        for(int i = 0; i < 61; i++) {

            if(now > n) {

                k = i - 1; now /= 2; tmp /= 2; cnt -= tmp;

                break;

            }

            cnt += tmp;

            now *= 2; tmp *= 2;

        }

        ll d = min(n - now + 1, tmp);

        cnt += d;

    } else {

        ll now = x, tmp = 2;

        int k = 0;

        for(int i = 0; i < 61; i++) {

            if(now > n) {

                k = i - 1; now /= 2; tmp /= 2; cnt -= tmp;

                break;

            }

            cnt += tmp;

            now *= 2; tmp *= 2;

        }

        ll d = min(n - now + 1, tmp);

        cnt += d;

    }

    return cnt >= k;

}

void run(){

    ll l = 2, r = n + 1, mid;

    ll ans = 1;

    while(l < r) {

        mid = (l + r) >> 1;

        if(mid & 1) ++mid;

        if(mid >= r) mid -= 2;

        if(mid < l) break;

        if(chk(mid)) {

            ans = mid;

            l = mid + 2;

        } else r = mid - 1;

    }

    l = 1, r = n + 1;

    while(l < r) {

        mid = (l + r) >> 1;

        if(mid % 2 == 0) ++mid;

        if(mid >= r) mid -= 2;

        if(mid < l) break;

        if(chk(mid)) {

            ans = max(ans, mid);

            l = mid + 2;

        } else r = mid - 1;

    }

    cout << ans << '\n';

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

    while(cin >> n >> k) run();

    return 0;

}

巴特西

Codeforces Round #608 (Div. 2)

A. Suits

B. Blocks

C. Shawarma Tent

D. Portals

E. Common Number

最新文章

热门文章