kakaの博客

你所热爱的，就是你的生活

0%

Codeforces Round 755 (Div. 2)

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.2k 阅读时长 ≈ 2 分钟

比赛链接:https://codeforces.ml/contest/1589

A. Mathematical Addition

$$\frac{x}{u}+\frac{y}{v}=\frac{x+y}{u+v}$$

化简得:

$$\frac{x}{y}=-\frac{u^2}{v^2}$$

1
2
3
4
5
6
void solve() {
    int T; cin >> T; while (T--) {
        ll u, v; cin >> u >> v;
        cout << u * u << ' ' << - v * v << endl;
    }
}

B. Coloring Rectangles

考虑构造尽量多的1*3的块，剩下1或2行再累计上去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int get(int x) {
    return (x-1)/3+1;
}
void solve() {
    int T; cin >> T; while (T--) {
        int n, m; cin >> n >> m;
        int ans = 1e9;
        if (n == 1) cout << get(m) << endl;
        else if (m == 1) cout << get(n) << endl;
        else {
            if (n % 3 == 0 || m % 3 == 0) {
                cout << n * m / 3 << endl;
            } else {
                ans = min(ans, n/3*m+n%3*get(m));
                ans = min(ans, m/3*n+m%3*get(n));
                cout << ans << endl;
            }
        }
    }
}

C. Two Arrays

每个a中的值都可与b中的一些值匹配，跑一遍最大匹配即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int a[N], b[N], match[N], vis[N];
vector<int> g[N];
bool dfs(int x) {
    for (auto v : g[x]) {
        if (!vis[v]) {
            vis[v] = 1;
            if (!match[v] || dfs(match[v])) {
                match[v] = x;
                return true;
            }
        }
    }
    return false;
}
void solve() {
    int T; cin >> T; while (T--) {
        int n; cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> b[i];
        for (int i = 1; i <= n; i++) g[i].clear(), match[i] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i]==b[j] || a[i]+1==b[j]) g[i].push_back(j);
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            memset(vis, 0, sizeof vis);
            if (dfs(i)) ans++;
        }
        if (ans == n) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

D. Guess the Permutation

首先要找到开始的i点，这里可以直接二分，当逆序数为0说明前mid个数是ordered。

然后得到i点后，设f(l,r)为$[l,r]$中逆序数的个数，那么f(l,n)-f(l+1,n)为$[l+1,n]$中小于a[l]的个数，因此$j=a[l]=f(i,n)-f(i+1,n)+i+1$

那么因此类推，$k=f(j,n)-f(j+1,n)+j$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ll print(int l, int r) {
    printf("? %d %d\n",l, r);
    fflush(stdout);
    ll x; cin >> x;
    return x;
}
void solve() {
    int T; cin >> T; while (T--) {
        int n; cin >> n;
        int a, b, c;
        int l = 1, r = n;
        ll x;
        while (l < r) {
            int mid = (l + r) >> 1;
            x = print(1, mid);
            if (x > 0) r = mid;
            else l = mid + 1;
        }
        a = l - 1;
        b = print(a, n)-print(a+1,n)+a+1;
        c = b + print(b, n)-print(b+1,n);
        printf("! %d %d %d\n", a, b, c);
        fflush(stdout);
    }
}
相关文章推荐