Codeforces Round #293 左右的简单题

做不了《高考必刷卷》，那就做做这个吧。

实际上是在洛谷 RMJ 做的题。

Codeforces Round 292 (Croc Champ 2013 - Round 1)

大概就是这样。

A. SMSC

简单模拟。

查看代码

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int T[1000005], C[1000005];
int inq, maxx;

int main(void) {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> T[i] >> C[i];
    for (int i = 1; i <= n; ++i) {
        if (i > 1) inq = max(0, inq - (T[i] - T[i - 1]));
        inq += C[i];
        maxx = max(inq, maxx);
    }
    cout << T[n] + inq << ' ' << maxx << endl;
    return 0;   
}

B. Network Topology

Portal.

好像还是模拟。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int n, m;
vector <int> G[100005];

bool check_ju(void) {
    int flag = 0;
    for (int i = 1; i <= n; ++i)
        if (G[i].size() != 1) {
            ++flag;
            if (flag >= 2) return false;
        }
    return flag == 1;
}

bool check_lian(void) {
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= n; ++i)
        if (G[i].size() == 1) ++cnt1;
        else if (G[i].size() == 2) ++cnt2;
        else return false;
    return cnt1 == 2 && cnt2 == n - 2;
}

bool check_huan(void) {
    for (int i = 1; i <= n; ++i)
        if (G[i].size() != 2) return false;
    return true;
}

int main(void) {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    if (m != n && m != n - 1) puts("unknown topology");
    else if (m == n - 1) {
        if (check_ju()) puts("star topology");
        else if (check_lian()) puts("bus topology");
        else puts("unknown topology");
    } else {
        if (check_huan()) puts("ring topology");
        else puts("unknown topology");
    }
    return 0;
}

C. Beautiful IP Addresses

Portal.

应该还是模拟。

查看代码

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;

int flag = 0;
int tot = 0;
vector <string> v;

bool check(const string &s, int l, int r) {
    if (s[l] == '0') return r == l + 1;
    int x = 0;
    for (int i = l; i < r; ++i)
        x = x * 10 + s[i] - '0';
    return 0 <= x && x <= 255;
}

void addIP(const string &s) {
    int n = s.length();
    for (int i = 1; i <= 3; ++i)
        for (int j = i + 1; j <= i + 3; ++j)
            for (int k = j + 1; k <= j + 3; ++k)
                if (1 <= n - k && n - k <= 3 && check(s, 0, i) && check(s, i, j) && check(s, j, k) && check(s, k, n))
                    v.emplace_back(s.substr(0, i) + "." + s.substr(i, j - i) + "." + s.substr(j, k - j) + "." + s.substr(k, n - k));
}

void dfs(int x, string s, int n, int state) {
    if (x == n) {
        if (state != flag) return;
        addIP(s);
        return;
    }
    if (x * 2 >= n) {
        if (state != flag) return;
        dfs(x + 1, s + s[n - x - 1], n, state);
        return;
    }
    for (int i = 0; i < 10; ++i)
        if (flag & (1 << i)) dfs(x + 1, s + char(i + '0'), n, state | (1 << i));
}

int main(void) {
    ios::sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        flag |= (1 << x);
    }
    if (n <= 6) {
        for (int i = 4; i <= 12; ++i)
            dfs(0, "", i, 0);
    }
    cout << v.size() << '\n';
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] << '\n';
    return 0;
}

Codeforces Round #178 (Div.2)

好像还是这样。

A. Shaass and Oskols

Portal.

就是模拟。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;

int n, m;
int a[105];

int main(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        a[x - 1] += y - 1;
        a[x + 1] += a[x] - y;
        a[x] = 0;
    }
    for (int i = 1; i <= n; ++i)
        cout << a[i] << '\n';
    return 0;
}

B. Shaass and Bookshelf

Portal.

每本书要么是垂直放置，要么将来躺着。设 $f(i)$ 为竖卷的总厚度之和为 $i$ ，所用的最大宽度，那么转移的时候就是个 01 背包。

最后要求的是竖着的最小总厚度，那直接枚举判断是否合法，合法仅当当前的厚度要大于等于上面堆着的宽度。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;

int n, m, s = 0;
int t[105], w[105];
int f[205];

int main(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> t[i] >> w[i];
        m += t[i]; s += w[i];
        f[i] = f[i + n] = -1e9;
    }
    for (int i = 1; i <= n; ++i)
        for (int j = m; j >= t[i]; --j)
            f[j] = max(f[j], f[j - t[i]] + w[i]);
    for (int i = 0; i <= m; ++i)
        if (i >= s - f[i]) return printf("%d\n", i), 0;
    return 0;
}

C. Shaass and Lights

Portal.

有 $n(1\le n\le 10^3)$ 盏灯，有 $m$ 盏已经点亮，每次只能点亮与已经点亮的灯相邻的灯，求点亮所有灯的总方案数，答案对 $10^9+7$ 取模。