Codeforces Round #594 (Div. 2)lyh's blog

Codeforces Round #594 (Div. 2)题解。比赛地址

A Integer Points

给出一些直线，找出有多少个整数交点。
由于斜率只有1和-1两种，所以直接用奇偶性质扫一遍即可。

 
using namespace std;
int a, b, na, nb, op[100005];
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &a);
        na = nb = 0;
        for (int i = 1, x; i <= a; i++) {
            scanf("%d", &x), op[i] = x;
            if (x % 2)++na;
        }
        scanf("%d", &b);
        for (int i = 1, x; i <= b; i++) {
            scanf("%d", &x);
            if (x % 2)++nb;
        }
        long long ans = 0;
        for (int i = 1; i <= a; i++) {
            if (op[i] % 2)ans += nb;
            else ans += b - nb;
        }
        cout << ans << endl;
    }
    return 0;
}

B Grow The Tree

设横的长度为$x$，纵向为$y$，那么有$x+y=S$。
即最大化$x^2+(S-x)^2=S^2-2Sx+2x^2$，这是一个抛物线。但是需要横向与纵向不相邻，那么横向（或纵向）需要取$\lceil \frac {n} {2}\rceil$个，取最大的那一部分。

#include <bits/stdc++.h>
 
using namespace std;
int n, op[100005];
 
int main() {
    int t = 1;
    while (t--) {
        int s = 0, tmp = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)scanf("%d", op + i), s += op[i];
        sort(op + 1, op + n + 1, greater<int>());
        int num;
        if (n % 2 == 0)num = n >> 1;
        else num = n / 2 + 1;
        for (int i = 1; i <= num; i++)tmp += op[i];
        cout << 1ll * tmp * tmp + 1ll * (s - tmp) * (s - tmp) << endl;
    }
    return 0;
}

C Ivan the Fool and the Probability Theory

        经过合理的画图以及推理(?)，可以发现当第一行存在相邻的两个同色块时，这个图就固定了。我们先考虑这一种情况。
        有一种很无脑的做法是三维$DP$。令$dp[x][a][b]$表示第一行有$x$列，最左侧是不是同色块(a=0/1)，最左侧颜色(b=0/1)。这样方程很好列，直接可以求出第一种情况的值。
        另一种情况自然是首行黑白交替分布，考虑最左侧是黑色的方案数。令$dp[x]$表示$x$行时的方案数（与列的数量无关），那么如果下一行是白色，则就是$dp[x-1]$的情况，如果下一行是黑色，那么下下行就必须是白色，又回到$dp[x-2]$的情况，由此可得$dp[x]=dp[x-1]+dp[x-2]$。再考虑最左侧是白色的情况，乘一个2即可。

#include <bits/stdc++.h>
 
#define MOD (int)(1e9+7)
using namespace std;
int n, dp[100005], m, dp2[100005][2][2];
 
int main() {
    scanf("%d%d", &n, &m);
    dp[1] = 1, dp[2] = 2;
    for (int i = 3; i <= n; i++)dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
    dp2[1][0][0] = dp2[1][0][1] = 1;
    dp2[2][0][0] = dp2[2][0][1] = 2;
    dp2[2][1][0] = dp2[2][1][1] = 1;
    for (int i = 3; i <= m; i++) {
        dp2[i][0][0] = ((dp2[i - 1][0][0] - dp2[i - 1][1][0]) % MOD + dp2[i - 1][0][1]) % MOD;
        dp2[i][0][1] = ((dp2[i - 1][0][1] - dp2[i - 1][1][1]) % MOD + dp2[i - 1][0][0]) % MOD;
        dp2[i][1][0] = dp2[i - 2][0][1];
        dp2[i][1][1] = dp2[i - 2][0][0];
    }
    int sum = 0;
    for (int i = 2; i <= m; i++)sum = (sum + (dp2[i][1][0] + dp2[i][1][1]) % MOD) % MOD;
    cout << ((sum + 2ll * dp[n]) % MOD + MOD) % MOD << endl;
    return 0;
}

D1 The World Is Just a Programming Task (Easy Version)

给一个括号字符串，可以交换一次其中的两个字符，求最大的周期位移数。
对于这一题，由于$n$仅有500，我们大可$O(n^2)$暴力找出所有交换顺序，然后一个个判，从中找出最大值。在这里我们需要一个$O(n)$求周期位移数的方法，有很多。时间复杂度$O(n^3)$。

#include <bits/stdc++.h>
 
using namespace std;
int n, ans, a, b, s[505];
char op[505];
 
inline int solve() {
    int minn = 0x3f3f3f3f, tmp = 0, add = 0;
    s[0] = (op[0] == '(' ? 1 : -1), s[n] = 0x3f3f3f3f;
    for (int i = 1; i < n; i++)s[i] = s[i - 1] + (op[i] == '(' ? 1 : -1);
    if (s[n - 1] != 0)return 0;
    for (int i = n - 1; i >= 0; i--)s[i] = min(s[i], s[i + 1]);
    for (int i = 0; i < n; i++) {
        if (op[i] == '(')--add;
        else ++add;
        if (min(minn + (op[i] == '(' ? -1 : 1), s[i + 1] + add) >= 0)++tmp;
        minn = min(minn + (op[i] == '(' ? -1 : 1), 0);
    }
    return tmp;
}
 
int main() {
    scanf("%d%s", &n, op), ans = solve();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1, x; j < n; j++) {
            if (op[i] == op[j])continue;
            swap(op[i], op[j]), x = solve();
            if (x > ans)ans = x, a = i, b = j;
            swap(op[i], op[j]);
        }
    }
    cout << ans << endl << a + 1 << " " << b + 1;
    return 0;
}

D2 The World Is Just a Programming Task (Hard Version)

        这个题的难度就比较大了。
        首先注意这样一个问题，若将左括号看成1，右括号看成-1，可以得到一些前缀和，其中最小值的出现次数就是循环数（当然首先需要满足最后一个前缀和为0）。
        我们找到最小值所在的位置，把它作为首字符（易知这样不会影响答案）。这样做的好处是让最小值变为0。
        交换两个相同字符没有任何意义，若交换$i$位置的$)$和$j$位置的$($，会使$[i,j)$的前缀和值增加2，由于它不会使最小值从0变为其它，可知这种交换不会使答案更优。于是我们只需要考虑交换$($和$)$的情况，它会使$[i,j)$的前缀和值减去2。
        对于$[i,j)$中包含前缀和为0的子段情况，可知此时最小值将变为-2，并且数量一定不会增多，由此可知$[i,j)$应该位于两个相邻的前缀和零点之间。
        那么我们找到所有前缀和零点，遍历所有间隙，找到其中1（减去2后变为-1，为最小值）的数量，然后更新答案。
        由于2减去2得0，也可能成为最小值，所以我们还需要考虑这一种情况。和刚才的逻辑类似，这一次需要找出前缀和为1的点，然后从中找2的最大数量，然后更新答案即可。
        时间复杂度$O(n)$。（竟然硬生生地把复杂度降低了$n^2$这么多，算法真是太奇妙了）。

#include <bits/stdc++.h>
#define N 300005
#define inf 0x3f3f3f3f
using namespace std;
char op[N], tmp[N];
int n, s[N], ri[N], le[N], ans, s1[N], s2[N], s0, ansa, ansb;
vector<int> vvp;
int main()
{
    scanf("%d", &n);
    scanf("%s", tmp + 1);
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + (tmp[i] == '(' ? 1 : -1);
    int pos = min_element(s + 1, s + n + 1) - s;
    for (int i = pos + 1, j = 1; i <= pos + n; i++, j++)
        op[j] = tmp[(i - 1) % n + 1];
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + (op[i] == '(' ? 1 : -1);
    if (s[n] != 0)
    {
        printf("0\n1 1");
        return 0;
    }
    le[1] = (op[1] == ')' ? 1 : -inf);
    for (int i = 2; i <= n; i++)
        le[i] = (op[i] == ')' ? i : le[i - 1]);
    ri[n] = (op[n] == '(' ? 1 : inf);
    for (int i = n - 1; i >= 1; i--)
        ri[i] = (op[i] == '(' ? i : ri[i + 1]);
    vvp.push_back(0);
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == 0)
            ++s0, vvp.push_back(i);
        s1[i] = s1[i - 1] + (s[i] == 1);
        s2[i] = s2[i - 1] + (s[i] == 2);
    }
    ans = s0, ansa = 1, ansb = 1;
    for (int i = 0; i < vvp.size() - 1; i++)
    {
        if (le[vvp[i + 1]] > ri[vvp[i] + 1])
        {
            if (s1[le[vvp[i + 1]] - 1] - s1[ri[vvp[i] + 1] - 1] > ans)
            {
                ans = s1[le[vvp[i + 1]] - 1] - s1[ri[vvp[i] + 1] - 1];
                ansa = le[vvp[i + 1]], ansb = ri[vvp[i] + 1];
            }
        }
    }
    vvp.clear();
    for (int i = 1; i <= n; i++)
        if (s[i] == 1)
            vvp.push_back(i);
    for (int i = 0; i < vvp.size() - 1; i++)
    {
        if (s[vvp[i] + 1] < 1)
            continue;
        if (le[vvp[i + 1]] > ri[vvp[i] + 1])
        {
            if (s2[le[vvp[i + 1]] - 1] - s2[ri[vvp[i] + 1] - 1] + s0 > ans)
            {
                ans = s2[le[vvp[i + 1]] - 1] - s2[ri[vvp[i] + 1] - 1] + s0;
                ansa = le[vvp[i + 1]], ansb = ri[vvp[i] + 1];
            }
        }
    }
    printf("%d\n%d %d", ans, (ansa + pos - 1) % n + 1, (ansb + pos - 1) % n + 1);
    return 0;
}

E Queue in the Train

稍微难一点的模拟。
用一个队列模拟等待队列。又因为每一个用户在编号比其小的用户等待时不可入队，可以用一个优先队列模拟。于是两个队列就解决了问题。时间复杂度$O(nlogn)$。

#include <bits/stdc++.h>
 
using namespace std;
int n, t[100005], p, to[100005], at;
priority_queue<int, vector<int>, greater<> > pq;
deque<int> que;
long long now, ans[100005];
 
int main() {
    scanf("%d%d", &n, &p);
    for (int i = 1; i <= n; i++)scanf("%d", t + i), to[i] = i;
    sort(to + 1, to + n + 1, [&](int a, int b) {
        return t[a] == t[b] ? a < b : t[a] < t[b];
    });
    at = 1;
    while (at <= n) {
        now = t[to[at]], pq.push(to[at]);
        while (at + 1 <= n && t[to[at + 1]] == t[to[at]])pq.push(to[++at]);
        ++at;
        while (!que.empty() || !pq.empty()) {
            if (!pq.empty() && (que.empty() || pq.top() < que.back()))que.push_back(pq.top()), pq.pop();
            int top = que.front();
            que.pop_front(), ans[top] = now + p;
            while (at <= n && t[to[at]] <= now + p) {
                if ((pq.empty() || pq.top() > to[at]) && to[at] < que.back())que.push_back(to[at++]);
                else pq.push(to[at++]);
            }
            now += p;
        }
    }
    for (int i = 1; i <= n; i++)cout << ans[i] << " ";
    return 0;
}

F Catowice City

        给了一个二分图，求一个最大独立集，要求两侧必须都有点。
        显然编号为$i$的猫和人必须且仅能选一个。若选了一个人$i$，那么对于其对应的猫都不能选了，那么与这些猫编号相同的人就必须选，这样就可以从$i$开始，向这些人连一条有向边。建出图来之后，这样答案就是找一个闭合子图使得点数小于n。
        在图上跑tarjan强连通缩点，若全部缩为一个点，表示只能选一个包含所有点的闭合子图，答案即为No。否则，找到其中任何一个强连通分量都是一个合法的答案。
        题目不难，只是不好想。

#include <bits/stdc++.h>
#define N 1000005
using namespace std;
struct Edge
{
    int next, to;
} edge[N];
int head[N], cnt = 1, n, m, dfn[N], low[N], DFN, vis[N], color[N], COLOR;
stack<int> sta;
inline void add(int x, int y)
{
    edge[cnt].next = head[x], edge[cnt].to = y, head[x] = cnt++;
}
void tarjan(int x)
{
    if (dfn[x])
        return;
    dfn[x] = low[x] = ++DFN, vis[x] = 1, sta.push(x);
    for (int i = head[x]; i; i = edge[i].next)
    {
        if (!dfn[edge[i].to])
            tarjan(edge[i].to), low[x] = min(low[x], low[edge[i].to]);
        else if (vis[edge[i].to])
            low[x] = min(low[x], dfn[edge[i].to]);
    }
    if (dfn[x] == low[x])
    {
        int to;
        do
            to = sta.top(), sta.pop(), vis[to] = 0, color[to] = COLOR;
        while (to != x);
        ++COLOR;
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m), DFN = 0, COLOR = 1, cnt = 1;
        for (int i = 1; i <= n; i++)
            head[i] = 0, dfn[i] = low[i] = vis[i] = color[i] = 0;
        for (int i = 1, x, y; i <= m; i++)
            scanf("%d%d", &x, &y), add(x, y);
        for (int i = 1; i <= n; i++)
            tarjan(i);
        if (COLOR == 2)
        {
            printf("No\n");
        }
        else
        {
            int num = 0;
            for (int i = 1; i <= n; i++)
            {
                if (color[i] == 1)
                    vis[i] = 1, ++num;
            }
            printf("Yes\n");
            printf("%d %d\n", num, n - num);
            for (int i = 1; i <= n; i++)
                if (vis[i])
                    printf("%d ", i);
            printf("\n");
            for (int i = 1; i <= n; i++)
                if (!vis[i])
                    printf("%d ", i);
            printf("\n");
        }
    }
    return 0;
}