Codeforces 633(Div.2)

A题

题意：给你n个菱形方块拼成的多边形，然后问你有多少种方法可以由一个菱形通过旋转，翻转，移动得到。

思路：这道题的话，通过读题不难发现，n个菱形就有n种方法。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
const int mod = 1000000009;
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        cout << n << endl;
    }
    return 0;
}

B题

题意：给你一个数组，要求重新排列后，相邻元素的绝对值递增。

思路：这道题的话，我们重新排列之后，将数组倒着一小一大存入即可。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
const int mod = 1000000009;
using namespace std;
int a[maxx], b[maxx];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        sort(a + 1, a + n + 1);
        int ans = 1;
        int cnt = n;
        for (int i = n; i >= 1; i--)
        {
            if ((n - i) % 2 == 0)
                b[i] = a[ans++];
            if ((n - i) % 2 == 1)
                b[i] = a[cnt--];
        }
        for (int i = 1; i <= n; i++)
        {
            cout << b[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

C题

题意：给一个数组，你可以在第x秒给一些元素加上2的x−1次方 ,问多少秒后数组可以变成一个不递减序列。

思路：这道题的话，我们找到数组中一组前后差最大的元素，然后判断需要加几秒即可。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
const int mod = 1000000009;
using namespace std;
int a[maxx];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        int minn = a[n];
        int flag = 0, ret = 0;
        for (int i = n - 1; i >= 1; i--)
        {
            if (a[i] > minn)
                flag = 1, ret = max(ret, a[i] - minn);
            else
                minn = min(a[i], minn);
        }
        if (!flag)
            cout << 0 << endl;
        else
        {
            int x = 1, cnt = 0;
            while (ret > 0)
            {
                ret -= x;
                x *= 2;
                cnt++;
            }
            cout << cnt << endl;
        }
    }
    return 0;
}

D题

题意：现在给你一颗无根树，然后给无根树每一条边赋值，要求任意两个叶子节点的路径上的边的权值异或和为0，求填写方案中权值种类的最大值和最小值。

这道题的话，我们先考虑最小值，最好的情况就是全部都是1，那么最小值就为1，但是如果有两个叶子结点之间的距离为奇数的话，异或的结果就不为1，参考样例2，这时候的最小值就为3。判断叶子节点之间的距离奇偶性一个比较好的方法就可以统计所有的深度，如果又有奇数又有偶数的话，就肯定有两个叶子结点之间距离为偶数再来考虑最大值，我们可以试着将所有边权构造为不能的数，但是这样会出现一种情况就是一个父亲节点连接多个叶子，这样是不可能的，这时候答案就为n−1−x，x为符合要求的父亲节点所连接的叶子节点数。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
const int mod = 1000000009;
using namespace std;
vector<ll> G[maxx];
vector<ll> ans;
ll deep[maxx], vis[maxx];
int dfs(ll u, ll pre)
{
    deep[u] = deep[pre] + 1;
    vis[u] = pre;
    for (auto v : G[u])
    {
        if (G[v].size() == 1)
            ans.push_back(u);
        if (v == pre)
            continue;
        dfs(v, u);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, u, v;
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    deep[0] = -1;
    dfs(1, 0);
    ll f = 0, cnt = 0, tot = 0;
    for (int i = 1; i <= n; i++)
    {
        if (G[i].size() == 1 && deep[i] % 2 == 0)
            cnt++;
        if (G[i].size() == 1 && deep[i] % 2)
            tot++;
    }
    if (cnt >= 1 && tot >= 1)
        f = 1;
    if (f != 0)
        cout << "3 ";
    else
        cout << "1 ";
    sort(ans.begin(), ans.end());
    ll ma = n - 1;
    for (int i = 0; i < ans.size(); i++)
        if (i)
        {
            if (ans[i] == ans[i - 1])
                --ma;
        }
    cout << ma;
    return 0;
}

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦