Codeforces 628(Div.2)

A题

题意：给你一个数x，求a和b，使得$lcm(a,b)+gcd(a,b)=x$。

思路：这道题的话，直接令a=1,b=x−1，这样$lcm(a,b)=x−1$,$gcd(a,b)=1$，公式成立。

AC代码：

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

B题

题意：给一个长度为n的数组，可以把给定的数组再次接到数组后面使数组长度加n。这个操作可以执行无数次，问能形成的最长上升序列。

思路：这道题的话，因为是严格上升子序列，所以每个数至多被选择一次。最后答案即为数组中互不重复的数字个数。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
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];
        sort(a + 1, a + n + 1);
        int sum = 0;
        for (int i = 1; i <= n; i++)
        {
            if (a[i] != a[i - 1])
                sum++;
        }
        cout << sum << endl;
    }
    return 0;
}

C题

题意：给出你一棵树，但是权值并没有分配，让你构造一种分配的方法来使每一种$u–>v$，即两个节点的路径所经过的权值mex最大值最小。

思路：这道题的话，首先先说一下mex的含义，mex这个东西，返回值是这个东西里面出现的最小非负整数，即$mex(1,3)=0$,$mex(0,2)=1$。然后我们用贪心的思路，在输入时记录每个节点被连接的次数，次数越多代表越多的路径会经过它，那么这时候把这条路径改为最大可以赋予的权值就可以使整体的mex尽可能小。又因为要求按输入顺序输出，所以我们是两遍sort，一遍比较节点访问次数来分配权值，一遍比较最初的顺序复原。

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
struct node
{
    ll u, v;
    ll num;
    ll val;
    ll pos;
} edge[maxx];
ll vis[maxx];
ll n;
bool cmp(node a, node b)
{
    a.num = min(vis[a.u], vis[a.v]);
    b.num = min(vis[b.u], vis[b.v]);
    return a.num < b.num;
}
bool cmp1(node a, node b)
{
    return a.pos < b.pos;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(vis, 0, sizeof(vis));
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
    {
        cin >> edge[i].u >> edge[i].v;
        edge[i].pos = i;
        vis[edge[i].u]++;
        vis[edge[i].v]++;
    }
    sort(edge + 1, edge + n, cmp);
    for (int i = 1; i <= n - 1; i++)
        edge[i].val = i - 1;
    sort(edge + 1, edge + n, cmp1);
    for (int i = 1; i <= n - 1; i++)
        cout << edge[i].val << endl;
    return 0;
}

赏

×

纯属好玩

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

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