Codeforces Round #601 (Div. 2)

A. Changing Volume

签到。

Code

/*

 * Author:  heyuhhh

 * Created Time:  2019/11/19 22:37:33

 */

#include <bits/stdc++.h>

#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, b;

void run(){

    cin >> a >> b;

    int d = abs(a - b);

    int ans = 0;

    if(d >= 5) {

        ans += d / 5;

        d -= ans * 5;

    }

    if(d == 3 || d == 4) ans += 2;

    if(d == 2 || d == 1) ans += 1;

    cout << ans << '\n';

}

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. Fridge Lockers

形成环后贪心即可。

Code

/*

 * Author:  heyuhhh

 * Created Time:  2019/11/19 22:48:14

 */

#include <bits/stdc++.h>

#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 = 1005;

int n, m;

int a[N];

void run(){

    cin >> n >> m;

    for(int i = 1; i <= n; i++) cin >> a[i];

    if(n > m || n == 2) {

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

        return;

    }

    int ans = 0;

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

    m -= n;

    int mn1 = INF, mn2 = INF;

    int p1, p2;

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

        if(a[i] < mn1) {

            p2 = p1;

            p1 = i;

            mn2 = mn1;

            mn1 = a[i];

        } else if(a[i] < mn2){

            mn2 = a[i];

            p2 = i;

        }

    }

    ans += m * (mn1 + mn2);

    cout << ans << '\n';

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

        cout << p1 << ' ' << p2 << '\n';

    }

    for(int i = 2; i <= n; i++) cout << i << ' ' << i - 1 << '\n';

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

}

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. League of Leesins

确定两个数后第三个也就确定了。

所以\(map\)乱搞一下。

Code

/*

 * Author:  heyuhhh

 * Created Time:  2019/11/19 23:14:24

 */

#include <bits/stdc++.h>

#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 = 2e5 + 5;

int n;

int q[N][3];

map <pii, vector<int>> mp;

map <int, pii> mp2;

int cnt[N];

int b[N];

int s, e;

bool vis[N];

bool go(int pos, int last1, int last2) {

    dbg(pos, last1, last2);

    vis[last2] = 1;

    b[pos] = last2;

    if(pos == n) {

        if(last2 != e) return false;

        return true;

    }

    if(last1 > last2) swap(last1, last2);

    vector<int> nxt = mp[MP(last1, last2)];

    bool f = true, t = false;

    for(auto it : nxt) {

        dbg(pos, it);

        if(!vis[it]) {

            f = go(pos + 1, b[pos], it);

            t = true;

        }

    }

    dbg(f, t);

    return (f && t);

}

void run(){

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

        cin >> q[i][0] >> q[i][1] >> q[i][2];

        sort(q[i], q[i] + 3);

        mp[MP(q[i][0], q[i][1])].push_back(q[i][2]);

        mp[MP(q[i][1], q[i][2])].push_back(q[i][0]);

        mp[MP(q[i][0], q[i][2])].push_back(q[i][1]);

        mp2[q[i][0]] = MP(q[i][1], q[i][2]);

        mp2[q[i][1]] = MP(q[i][0], q[i][2]);

        mp2[q[i][2]] = MP(q[i][0], q[i][1]);

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

            ++cnt[q[i][j]];

        }

    }

    s = -1, e;

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

        if(cnt[i] == 1) {

            if(s == -1) s = i;

            else e = i;

        }

    }

    dbg(e);

    b[1] = s;

    vis[s] = 1;

    pii p = mp2[s];

    int nxt1 = p.fi, nxt2 = p.se;

    dbg(nxt1, nxt2);

    if(go(2, s, nxt1)) {

        for(int i = 1; i <= n; i++) cout << b[i] << " \n"[i == n];

    } else {

        memset(vis, 0, sizeof(vis));

        vis[s] = 1;

        go(2, s, nxt2);

        for(int i = 1; i <= n; i++) cout << b[i] << " \n"[i == n];

    }

}

int main() {

    ios::sync_with_stdio(false);

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

    cout << fixed << setprecision(20);

    while(cin >> n) run();

	return 0;

}

D. Feeding Chicken

模拟题。蛇形填数即可。注意一下细节，比方说当前要找\(cnt\)个，找完\(cnt\)个过后，不要及时修改答案变量，等到找到\(cnt+1\)个过后再修改。

Code

/*

 * Author:  heyuhhh

 * Created Time:  2019/11/20 0:05:52

 */

#include <bits/stdc++.h>

#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 = 105;

int n, m, k;

char s[N][N];

char ans[N][N];

int Max, Min;

int need, num;

char Get(int x) {

    if(x < 26) return x + 'a';

    x -= 26;

    if(x < 26) return x + 'A';

    x -= 26;

    return x + '0';

}

void go(int x, int y, int cnt, int d) {

    if(y == m + 1) {

        ++x; y = m; d = -1;

    }

    if(y == 0) {

        ++x; y = 1; d = 1;

    }

    if(x > n) return;

    if(s[x][y] == 'R') --cnt;

    if(cnt == -1) ++num;

    ans[x][y] = Get(num);

    if(cnt == -1) {

        if(--need >= 0) {

            go(x, y + d, Max - 1, d);

        } else {

            go(x, y + d, Min - 1, d);

        }

        return;

    }

    go(x, y + d, cnt, d);

}

void run(){

    cin >> n >> m >> k;

    int tot = 0;

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

        cin >> (s[i] + 1);

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

            if(s[i][j] == 'R') ++tot;

        }

    }

    Min = tot / k, Max = tot / k + 1;

    need = tot - k * Min;

    dbg(Min, need);

    num = 0;

    if(--need >= 0) go(1, 1, Max, 1);

    else go(1, 1, Min, 1);

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

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

            cout << ans[i][j];

        }

        cout << '\n';

    }

}

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;

}

E1. Send Boxes to Alice (Easy Version)

题意：

给出\(n\)个位置，每个位置上面有数\(a_i,0\leq a_i\leq 1\)。

现在执行一次操作为：将\(i\)位置上面的一个数放到\(i-1\)位置或者\(i+1\)位置（如果位置存在的话）。

问最少需要操作多少次，使得最终每个位置上面的数能够被\(k\)整除。

思路：

求出\(cnt=\sum a_i\)，显然根据\(cnt\)所有的质因子来分组求解即可。
因为如果找的两个数\(a,b\)满足\(a=kb\)，那么按\(b\)分组不会比按\(a\)分组差。
然后显然每组内要合为一堆，那么肯定是往中间的数移动。
每组根据中位数算贡献即可。

代码如下：

Code

/*

 * Author:  heyuhhh

 * Created Time:  2019/11/20 11:56:43

 */

#include <bits/stdc++.h>

#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;

int a[N];

ll gao(int d) {

    ll res = 0;

    int cur;

    for(int i = 1, j; i <= n; i = j)  {

        j = i + 1;

        if(a[i] == 1) {

            cur = 1;

            res -= i;

            while(j <= n && cur < d) {

                if(a[j] == 1) {

                    ++cur;

                    if(cur < (d + 1) / 2) res -= j;

                    else if(cur > (d + 1) / 2)  res += j;

                }

                ++j;

            }

        }

    }

    return res;

}

void run(){

    int cnt = 0;

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

        cin >> a[i];

        cnt += a[i];

    }

    if(cnt == 1) {

        cout << -1;

        return;

    }

    ll ans = 1e18;

    for(int i = 1; i * i <= cnt; i++) {

        if(cnt % i == 0) {

            if(i > 1) ans = min(ans, gao(i));

            if(cnt / i > 1) ans = min(ans, gao(cnt / i));

        }

    }

    cout << ans << '\n';

}

int main() {

    ios::sync_with_stdio(false);

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

    cout << fixed << setprecision(20);

    while(cin >> n) run();

	return 0;

}

E2. Send Boxes to Alice (Hard Version)

题意：

同E1，只是\(a_i\)的数据范围变为了\(0\leq a_i\leq 10^6\)。

思路：

还是要找最小质因子，但是之后统计答案的时候可能不会合成一堆。
对于一个数\(a\)，假设当前的最小质因子为\(d\)，根据贪心的思想，这个位置要满足能被\(d\)整除，肯定它往后面搬运\(d\% k\)个石子或者后面往它搬运\(k-d\% k\)个石子。
当当前位置满足过后，因为只会对下一个位置产生影响，所以下一个位置的值算上其影响，之后又是一个新的子问题。
所以最终答案即为\(\sum_{i=1}^n min(pre[i], d-pre[i])\)。

虽然代码不长，但思路感觉还是挺巧妙的。。子问题的转化这里感觉不好直接想到。

Code

/*

 * Author:  heyuhhh

 * Created Time:  2019/11/20 11:56:43

 */

#include <bits/stdc++.h>

#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 = 1e6 + 5;

int n;

int a[N];

ll gao(ll d) {

    ll res = 0, pre = 0;

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

        pre = (pre + a[i]) % d;

        res += min(pre, d - pre);

    }

    return res;

}

void run(){

    ll cnt = 0;

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

        cin >> a[i]; cnt += a[i];

    }

    if(cnt == 1) {

        cout << -1;

        return;

    }

    ll ans = 1e18;

    for(int i = 2; 1ll * i * i <= cnt; i++) {

        if(cnt % i == 0) {

            ans = min(ans, gao(i));

            while(cnt % i == 0) cnt /= i;

        }

    }

    if(cnt > 1) ans = min(ans, gao(cnt));

    cout << ans << '\n';

}

int main() {

    ios::sync_with_stdio(false);

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

    cout << fixed << setprecision(20);

    while(cin >> n) run();

	return 0;

}

巴特西

Codeforces Round #601 (Div. 2)

A. Changing Volume

B. Fridge Lockers

C. League of Leesins

D. Feeding Chicken

E1. Send Boxes to Alice (Easy Version)

E2. Send Boxes to Alice (Hard Version)

最新文章

热门文章