Codeforces Round 347 (Div. 1)

Posted on By 二价氢

A Rebus

题目大意

给定一个仅含加减法的数学表达式,要求将表达式中的问号换成的整数,使得表达式成立

做法

贪心一下,首先可以把所有的问号填上1,然后贪心地修改每一个数,使得答案和n尽量靠近,如果改完最后一个数还是不能使答案变成n就无解。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <cstdlib>
using namespace std;
vector<string> vec;
const int maxn = 1001;
int sgn[maxn], num[maxn];
int cur = 0;
int n;
int main()
{
    string buf;
    while (cin >> buf)
        vec.push_back(buf);
    for (int i = 0; i < vec.size(); i++)
    {
        if (vec[i] == "?")
        {
            if (i == 0 || vec[i - 1] == "+") sgn[i] = 1;
            else sgn[i] = -1;
        }
    }
    n = atoi(vec[vec.size() - 1].c_str());
    for (int i = 0; i < vec.size(); i++)
    {
        if (sgn[i] == 1) {
            num[i] = 1;
            cur++;
        } else if (sgn[i] == -1) {
            num[i] = 1;
            cur--;
        }
    }
    for (int i = 0; i < vec.size(); i++)
    {
        if (sgn[i] == -1) {
            if (cur > n) {
                cur++;
                num[i] = min(n, cur - n);
                cur -= num[i];
            }
        } else if (sgn[i] == 1) {
            if (cur < n) {
                cur--;
                num[i] = min(n, n - cur);
                cur += num[i];
            }
        }
    }
    if (cur != n) {
        printf("Impossible\n");
    } else {
        printf("Possible\n");
        for (int i = 0; i < vec.size(); i++) {
            if (vec[i] == "?")
            {
                if (i != 0) {
                    printf(" %d", num[i]);
                } else {
                    printf("%d", num[i]);
                }
            } else {
                printf(" %s", vec[i].c_str());
            }
        }
        printf("\n");
    }
    return 0;
}

B International Olympiad

题目大意

给定一个1989年之后的年份的缩写,缩写的规则是这个年份在1989年之后没有使用过的最短后缀,要求复原。

做法

知道,从1989年到1998年,用完了所有的一位缩写,从1999年到2098年用完了所有的两位缩写,接着从2099年到3098年用完了所有的三位缩写……以此类推,因此我们可以根据后缀的长度推出年份的范围,之后又能发现在9999年之后,后缀长度与年份长度之差不超过1,所以暴力一下就好。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n;
char buf[111];
char ans[111], tans[111];
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", buf);
        int yr = strlen(buf), tl = 0;
        for (int i = 4; i < yr; i++)
            tans[tl++] = buf[i];
        tans[tl] = 0;
        long long beg = 0, end = 0, e10 = 1;
        yr -= 4;
        while (yr--)
        {
            beg += e10;
            e10 *= 10;
            end += e10;
        }
        beg--;
        beg += 1989;end += 1989;
        for (int i = 0; i < 1000; i++) {
            sprintf(buf, "%d%s", i, tans);
            long long ttans = 0;
            sscanf(buf, "%lld", &ttans);
            if (beg <= ttans && ttans < end) {
                printf("%lld\n", ttans);
                break;
            }
        }
    }
    return 0;
}

C Graph Coloring

题目大意

给定一个图,最开始每条边都被染成了两种颜色中的一种,每次可以选择一个点,改变与这个点相连的所有边的颜色。问最少花多少次操作可以使所有边的颜色相同。

做法

我们知道以下两点事实,即

  1. 染色结果与顺序无关

  2. 每个点至多被选择一次

及一条推论:每条边之多被染色两次。

首先枚举两种颜色,即我们染色后整个图会变成哪种颜色,接着,对于某条边,我们知道如果它的颜色与最终的颜色相同,那么他的两个顶点要么全部被选择,要么都没被选择,而如果不同,则它的两个顶点中有且仅有一个被选择。

因而我们发现这是一个0/1染色的问题,我们可以通过DFS解决。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>

using namespace std;
const int maxn = 100000 + 1;

typedef pair<int, bool> pib;

#define v first
#define c second

int n, m, c[maxn];

vector<int> s[2], ts[2];
vector<pib> e[maxn];

bool dfs(int tar, int u)
{
    for (pib edg : e[u])
    {
        if (c[edg.v] == -1)
        {
            c[edg.v] = (c[u] ^ edg.c ^ tar);
            ts[c[edg.v]].push_back(edg.v);
            if (!dfs(tar, edg.v)) return false;
        } else {
            if (c[edg.v] != (c[u] ^ edg.c ^ tar))
                return false;
        }
    }
    return true;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v;
        char cc[3];
        cin >> u >> v >> cc;
        e[u].push_back(pib(v, cc[0] == 'B'));
        e[v].push_back(pib(u, cc[0] == 'B'));
    }
    
    bool res[2] = {1, 1};
    for (int t = 0; t < 2; t++)
    {
        memset(c, -1, sizeof(c));
        for (int i = 1; i <= n; i++)
        {
            if (c[i] == -1)
            {
                c[i] = 0;
                ts[0].push_back(i);
                res[t] = (res[t] && dfs(t, i));
                bool flg = (ts[0].size() > ts[1].size());
                s[t].insert(s[t].end(), ts[flg].begin(), ts[flg].end());
                ts[0].clear();
                ts[1].clear();
            }
        }
    }

    // I guess:
    // if res[0] = false then
    //   we must have res[1] = false

    int flg = ((res[0] && res[1]) ? (s[0].size() > s[1].size()) : (res[0] ? 0 : (res[1] ? 1 : -1)));
    if (~flg)
    {
        printf("%lu\n", s[flg].size());
        for (int v : s[flg])
            printf("%d ", v);
        printf("\n");
    } else {
        printf("-1\n");
    }
    return 0;
}