2020-08-07 16:48 已编辑门头沟学院 Java

关注

Codeforces Round #654 (Div. 2)

A.Magical Sticks

题意：

给 $n$ 个长度为 $1 \sim n$ 的木棒，木棒可以拼接在一起。问最多可以拼接出多少根长度相等的木棒。

题解：

最终都拼成长度为 $n$ 的， $1$ 和 $n-1$ 组合， $2$ 和 $n-2$ 组合...最终答案为 $\lfloor \frac{n-1}{2} \rfloor+1$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    ll n;
    scanf("%lld", &n);
    printf("%lld\n", (n - 1) / 2 + 1);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.

题意：

规定每个周期为 $1 \sim r$ 天，你可以从任意一天开始连续涂色 $n$ 天，询问可以形成多少种不同的形状
图片说明

题解：

可以分成 $n \leq r$ 和 $n > r$ 两种情况。
当 $n \leq r$ 时， $i\geq n$ 都只有一种形状，而 $i < n$ ，有 $i$ 个形状，因此答案为 $\frac{(n-1)n}{2}+1$
当 $n > r$ 时， $i <= r$ 都有 $i$ 个形状，因此答案为 $\frac{r(r+1)}{2}$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    ll n, r;
    scanf("%lld%lld", &n, &r);
    if (n <= r)
        printf("%lld\n", n * (n - 1) / 2 + 1);
    else
        printf("%lld\n", r * (r + 1) / 2);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

题意：

有 $a$ 个食物 $1$ 和 $b$ 个食物 $2$ ，有 $n$ 个客人 $1$ 和 $m$ 个客人 $2$ ，客人 $1$ 每人会吃一个当前数量较多的那个食物，客人 $2$ 每人会吃一个当前数量较少的那个食物，判断是否存在一种排列方式使得每个客人都能吃到食物

题解：

可以知道至多有 $min(a,b)$ 个客人 $2$ 可以吃到食物，且客人 $2$ 全吃数量较少的那种食物才能取到最大值，因此将客人 $2$ 排在最前面，客人 $1$ 全排在后面，如果 $min(a,b) \geq m \ \&\& \ a+b \leq n+m$ 则每个客人都能吃到

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    ll a, b, n, m;
    scanf("%lld%lld%lld%lld", &a, &b, &n, &m);
    if (min(a, b) >= m && a + b >= n + m)
        puts("Yes");
    else
        puts("No");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Grid-00100

题意：

给定一个 $n*n$ 的全 $0$ 矩阵，现在要将 $k$ 个位置填为 $1$ 。定义矩阵 $A$ 的 $f(A)=(max(R)-min(R))^{2}+(max(C)-min(C))^{2}$ ，其中 $R_i$ 为第 $i$ 行中 $1$ 的数量， $C_j$ 为第 $j$ 列中 $1$ 的数量，现在要求 $f(A)$ 最小，输出最小的方案

题解：

可以发现在一个位置放 $1$ ，对该行和该列的贡献都为 $1$ ，为了使贡献最小，那么应该尽量放到不同行和不同列，所以每次可以在不同行不同列放 $1$ ，同时可以发现 $f(A)=0、2$ ，当 $k%n=0$ 时， $f(A)=0$ 否则为 $2$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n, k;
    scanf("%d%d", &n, &k);
    printf("%d\n", k % n ? 2 : 0);
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = n - 1; j >= 0; j--)
            printf("%d", (i + j) % n * n + i < k);
        puts("");
    }
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

E1. Asterism (Easy Version)

题意：

给定 $n$ 个怪兽，每个怪兽有 $a_i$ 个糖果，一开始有 $x$ 个糖果，现在依次和怪兽比糖果数，如果 $x\geq a_i$ ，则获胜，糖果数 $x+1$ 。 $f(x)$ 为初始有 $x$ 个糖果，对怪兽的出场顺序进行排序，能全胜的排序数。同时给定一个质数 $p$ ，如果 $f(x) \%p \ne 0$ 则输出这个 $x$ ，其中 $(2 \leq p \leq n \leq 2000,1 \leq a_i \leq 2000)$ 。

题解：

对 $a_n$ 进行排序，首先可以确定 $x \geq max(a_i)$ 时均不行，因为此时 $f(x)=n!$ ，而 $n \geq p$ ，因此 $f(x)$ 一定包含 $p$ 。
那么由于 $a_i \leq 2000$ 不妨枚举 $x$ ，对于每个 $x$ ，可以确定在 $i$ 位置的值为 $x+i-1$ ，那么二分可得 $\leq x+i-1$ 的数记为 $pos$ ，那么该位置可以放置的数为 $pos-i+1$ 个，那么 $f(x)=\prod_{i=1}^{n}(pos-i+1)$ ，因此只要对每个位置判断一下 $(pos-i+1) \% p$ 是否为 $0$ 即可。

#include <bits/stdc++.h>
using namespace std;
int a[2005];
vector<int> ans;
int main()
{
    int n, p;
    scanf("%d%d", &n, &p);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    for (int x = 1; x < a[n]; x++)
    {
        int flag = 1;
        for (int i = 1; i <= n; i++)
        {
            int pos = upper_bound(a + 1, a + n + 1, x + i - 1) - a - 1;
            if ((pos - i + 1) % p == 0)
            {
                flag = 0;
                break;
            }
        }
        if (flag)
            ans.push_back(x);
    }
    printf("%d\n", ans.size());
    for (auto i : ans)
        printf("%d ", i);
    puts("");
    return 0;
}

E2.Asterism (Hard Version)

题意：

E2和E1的题意相同， $(2 \leq p \leq n \leq 10^{5},1 \leq a_i \leq 10^{9})$ 。

题解：

因为 $a_i \leq 10^{9}$ ，所以不可能再去枚举 $x$ 了，其实从E1的结果可以发现答案都为连续的数，最开始的那个数也很好确定就为 $max(a_i-i+1)$ ，那么只要确定最大的数即可。想到如果 $x$ 很大，答案就是 $n!$ ，那么如果 $x \geq a_p$ ，那么至少前 $p$ 个数可以随意取，因此答案一定包含 $p!$ ，由此可以想到上界就是最多前 $p-1$ 个数可以自由移动，但是第 $p$ 个数要固定，那么想想什么时候第 $p$ 个数固定，就是 $i \geq p$ 时， $min(a_i-i+p)$ ，因此答案为 $max(a_i-i+1) \sim min(a_i-i+p)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005];
int main()
{
    ll n, p, ans1 = 0, ans2 = 2e9;
    scanf("%lld%lld", &n, &p);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
    {
        ans1 = max(ans1, a[i] - i + 1);
        if (i >= p)
            ans2 = min(ans2, a[i] - i + p);
    }
    printf("%lld\n",max(ans2 - ans1, 0ll));
    for (int i = ans1; i < ans2; i++)
        printf("%lld ", i);
    return 0;
}