@[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是用来记录每个队已经获得的分数，初始为0a[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;
}
