每天两道 CodeForces 构造/思维题 （day5）

@[TOC]

题目1 Plus and Multiply

题目链接 Plus and Multiply

题目大意：

思路：构造+数学

我们可以得到n的两种表达式

• 第一次操作是x*a : n = a^x + b * y
• 第一次操作是x+b：n = (1 + b) * a^x + b * y ==> n = b * (a^x + y) + a^x

我们有两个未知量x和y，我们可以枚举其中一个变量，看另一个变量有没有对应的值，如果枚举y的话时间复杂度太大，而且不方便求x。所以我们可以选择枚举x，求y。

这里我们要特判a==1的情况，否则会死循环。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e6 + 10;
void solve()
{
    ll n, a, b;
    cin >> n >> a >> b;
    int f = 0;
    if ((n - 1) % b == 0)
    {
        f = 1;
    }
    else if (a == 1)
    {
        f = 0;
    }
    else
    {
        ll k = a;
        while (k <= n)
        {
            if ((n - k) % b == 0)
            {
                f = 1;
                break;
            }
            else
                k = k * a;
        }
    }
    if (f)
        puts("Yes");
    else
        puts("No");
    return;
}
signed main()
{
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

题目2 Minimum Ties

题目链接 Minimum Ties

题目大意：

有n个球队，每个球队之间都要打一场球赛，赢得加3分，输出得0分，平局都不得分，问什么样得比赛结果能够让每个队的分数相同，并且平局数量尽可能少

思路：构造+数学

每个队之间都要打一局，那么要是每个队的分数相同，那么必须每个队赢得局数和输的局数要相同，并且能不平局就不平局。这里分两种情况

• n 是奇数，那么每个队要打n-1场，也就是偶数场，那么可以让每个队赢输个占一半
• n 是偶数，那么每个队就要打奇数场，所以肯定有平局，为了使平局数量最少，拿那就尽量每个人只打一场平局。并且为了使总体平局数量最小，那么只需要n/2场平局就可以了

思路已经清晰了，那么就是如何具体实现了

这里我用了一个二维数组a用来表示每局的情况

• a[i][j]==n 表示还没有进行比赛
• a[i][j]==0&&i!=j表示这场是平局
• a[i][j]==0&&i==j是用来记录每个队已经获得的分数，初始为0
• a[i][j]==1 ：i 球队赢了，j 球队输了
• a[i][j]==-1：j 球队赢了，i 球队输了

当n为偶数时，我们只需要让每个奇数球队和这个奇数+1的偶数球队打成平局就好

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1e6 + 10;
int a[110][110];
void solve()
{
    int n;
    cin >> n;
    if (n == 2)
    {
        cout << 0 << endl;
        return;
    }
    // 初始化a数组
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            a[i][j] = n;
            if (i == j)
                a[i][j] = 0;
        }
    // 处理平局
    if (n % 2 == 0)
    {
        for (int i = 1; i <= n; i += 2)
        {
            a[i][i + 1] = 0;
            a[i + 1][i] = 0;
        }
    }
    // 处理每一场比赛
    for (int i = 1; i <= n; i++)
    {
        // a1 表示球队i赢的比赛数量，a2表示输的
        int a1 = 0, a2 = 0;
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                continue;
            if (a[i][j] == 1)
                a1++;
            else if (a[i][j] == -1)
                a2++;
            // 如果i和j还没有进行比赛，并且j的分数不小于0，并且i还可以赢
            else if (a[i][j] == n && a[j][i] == n && a[j][j] >= 0 && a1 < (n - 1) / 2)
            {
                a[i][j] = 1;
                a[i][i]++;
                a[j][i] = -1;
                a[j][j]--;
                a1++;
            }
            // 如果i和j还没有进行比赛，并且j的分数不大于0，并且i只能必须要输了
            else if (a[i][j] == n && a[j][i] == n && a[j][j] <= 0 && a2 < (n - 1) / 2)
            {
                a[i][j] = -1;
                a[i][i]--;
                a[j][i] = 1;
                a[j][j]++;
                a2++;
            }
        }
    }
    // for (int i = 1; i <= n; i++)
    // {
    //     for (int j = 1; j <= n; j++)
    //         cout << a[i][j] << " ";
    //     cout << endl;
    // }
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
            cout << a[i][j] << " ";
    }
    cout << endl;
    return;
}
signed main()
{
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}