A. Left-handers, Right-handers and Ambidexters

题意

\(l\)个左撇子，\(r\)个右撇子，\(a\)个两手均可。要组成一支队伍，里面用左手的人数与用右手的人数相等，问队伍最大人数。

Code

#include <bits/stdc++.h>

#define F(i, a, b) for (int i = (a); i < (b); ++i)

#define F2(i, a, b) for (int i = (a); i <= (b); ++i)

#define dF(i, a, b) for (int i = (a); i > (b); --i)

#define dF2(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long LL;

int main() {

    int l,r,a;

    scanf("%d%d%d", &l,&r,&a);

    if (l-r>=a) printf("%d\n", r+a<<1);

    else if (r-l>=a) printf("%d\n", l+a<<1);

    else {

        int z=l-r;

        if ((z+a)&1) --a;

        int y=(z+a)>>1, x=a-y;

        printf("%d\n", (l+x)*2);

    }

    return 0;

}

B. Intercepted Message

题意

两个序列\(a,b\)，总和相等，将\(a,b\)分别切成\(k\)段，对应段的子序列和相等。问最多能切成多少段。

思路

贪心

Code

#include <bits/stdc++.h>

#define F(i, a, b) for (int i = (a); i < (b); ++i)

#define F2(i, a, b) for (int i = (a); i <= (b); ++i)

#define dF(i, a, b) for (int i = (a); i > (b); --i)

#define dF2(i, a, b) for (int i = (a); i >= (b); --i)

#define maxn 1000010

using namespace std;

int a[maxn], b[maxn];

typedef long long LL;

int main() {

    int n,m;

    LL s1=0, s2=0;

    scanf("%d%d",&n,&m);

    F(i, 0, n) scanf("%d", &a[i]);

    F(i, 0, m) scanf("%d", &b[i]);

    int i=0, j=0, tot=-1;

    while (true) {

        if (s1==s2) {

            ++tot;

            if (i==n||j==m) break;

            s1=0; s2=0;

            s1 += a[i++], s2+= b[j++];

        }

        else if (s1<s2) s1 += a[i++];

        else s2 += b[j++];

    }

    printf("%d\n", tot);

    return 0;

}

C. Zebras

题意

一个\(01\)串，将其拆分成若干个格式为\(0101...010\)的（开头结尾均为\(0\)，中间交替），每个串中的\(01\)与原序列中的先后顺序相同。要求给出方案。

思路

两个\(set\)分别记录\(0\)的位置和\(1\)的位置，配合\(lower\_bound\)使用。

结束条件：

\(0\)的\(set\)为空
\(1\)的\(set\)为空
\(1\)的\(set\)与前一次不发生变化

Code

#include <bits/stdc++.h>

#define F(i, a, b) for (int i = (a); i < (b); ++i)

#define F2(i, a, b) for (int i = (a); i <= (b); ++i)

#define dF(i, a, b) for (int i = (a); i > (b); --i)

#define dF2(i, a, b) for (int i = (a); i >= (b); --i)

#define maxn 400010

using namespace std;

char s[maxn];

set<int> st[2];

vector<int> v[maxn];

typedef long long LL;

int main() {

    scanf("%s", s);

    int len = strlen(s);

    F(i, 0, len) {

        if (s[i]=='0') st[0].insert(i);

        else st[1].insert(i);

    }

    int cnt=-1;

    int count=0, temp=-1;

    while (true) {

        if (st[1].size()==temp || !st[0].size() || !st[1].size()) {

            if (st[1].size()) puts("-1");

            else {

                printf("%d\n", cnt+1+st[0].size());

                F2(i, 0, cnt) {

                    printf("%d ", v[i].size());

                    for (auto x : v[i]) printf("%d ", x+1); puts("");

                }

                for (auto x : st[0]) printf("%d %d\n", 1, x+1);

            }

            break;

        }

        temp = st[1].size();

        int cur=0, x=-1;

        ++cnt;

        while (true) {

            auto it = st[cur].lower_bound(x);

            if (it == st[cur].end()) {

                if (cur==0) {

                    st[1].insert(x);

                    v[cnt].pop_back();

                }

                break;

            }

            else {

                v[cnt].push_back(*it);

                x = *it;

                st[cur].erase(it);

                cur = !cur;

            }

        }

    }

    return 0;

}

D. A Leapfrog in the Array

题意

思路

找呀找呀找规律。

元素\(x\)跳\(k\)次的步长分别为\((2(n-x)+1)*(1,2,4,8,...\)，

所以跳\(k\)次后的位置为\(2x-1-(2(n-x)+1)(2^{k+1}-1)=(2x-1-2n)*2^{k+1}+2n\)，

所以\(P_{k+1}=(2x-1-2n)*2^{k+2}+2n\)，

所以\(P_{k}=P_{k+1}/2+n\)

于是可以从当前位置一路往后推，推到下标为奇数为止。

Code

#include <bits/stdc++.h>

#define F(i, a, b) for (int i = (a); i < (b); ++i)

#define F2(i, a, b) for (int i = (a); i <= (b); ++i)

#define dF(i, a, b) for (int i = (a); i > (b); --i)

#define dF2(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long LL;

LL n; int q;

LL calc(LL x) {

    if (x&1) return (x+1)>>1;

    return calc(n+(x>>1));

}

int main() {

    scanf("%I64d%d", &n,&q);

    while (q--) {

        LL x, ans;

        scanf("%I64d", &x);

        printf("%I64d\n", calc(x));

    }

    return 0;

}

E. Data Center Maintenance

具体见 http://www.cnblogs.com/kkkkahlua/p/8541916.html

反思

开学打了两场均一塌糊涂。

挺多原因吧，包括各种外界环境以及干扰啥的，心态也浮躁，也可能是这几天睡得都比较晚，归根到底还是菜。

就今天这场而言，

\(A,B\)写得都很慢，

\(C\)题一开始因为输出格式错误在\(pretest\ 1\)都挂了好几次，后来\(T\)了一次，然后想到用\(set\)还挺高兴的，结果不明原因的一直\(RE\)，本地一直跑也跑不出问题，就只能放弃了。

比赛结束麻烦同学跑才发现st[cur].erase(it); x = *it; // 别人家的IDE

我也是很强了，\(erase\)完还去取它的值。

\(C\)题没辙了就去看\(D\)题，还挺快就找到了初步的规律，也就是找到了\(P_k\)，然而没有化简，于是就愣没看出来能怎么用。明明是这么棒的递推啊。

心浮气躁。可以的。

暂时的状态看起来不太能打了...。

等稍微进入正轨吧。学习上要忙的事情也是很多啊。

有闲情的话可以打打virtual，然后等天时地利人和。

再菜也还是要努力地活下去呢。

晚安晚安。

巴特西

Codeforces Round #469 Div. 2 A B C D E

A. Left-handers, Right-handers and Ambidexters

题意

Code

B. Intercepted Message

题意

思路

Code

C. Zebras

题意

思路

Code

D. A Leapfrog in the Array

题意

思路

Code

E. Data Center Maintenance

反思

最新文章

热门文章