T1
题目描述
是否存在 \(3\) 个长度为 \(n\) 的 \([0,n)\) 的排列 \(a,b,c\)，使得 \(a_i+b_i=c_i \mod n\)。如果没有输出 -1，否则输出构造方案。
题解
如果 \(n\) 为奇数，不妨让 \(a，b\) 都是 \(0,1,2,3,\cdots\) 的排列即可。那么 \(c\) 一定也是一个排列
如果 \(n\) 为偶数，那么 \(a,b\) 所有数的和为 \(n(n-1)=0 \mod n\)，但是 \(c\) 的和为 \(\frac{n(n-1)}{2}=\frac{n}{2} \mod n\)，无解
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
//# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")
const int N = 100005;
template <typename T> inline T read ()
{
T s = 0; int w = 1; char c = getchar ();
for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
return s * w;
}
int n;
signed main ()
{
n = rd (int);
if (n % 2 == 0) { printf ("NO\n"); return 0; }
printf ("YES\n");
for (int i = 0; i < n; i ++ ) printf ("%d ", i); printf ("\n");
for (int i = 0; i < n; i ++ ) printf ("%d ", i); printf ("\n");
for (int i = 0; i < n; i ++ ) printf ("%d ", 2 * i % n); printf ("\n");
return 0;
}
T2
题目描述
给定一张 \(2^n-1\) 个点的完全图，你需要找出尽量多边互不相交的三元环，输出最优情况下的方案 。（这里的边互不相交不是平面上的相交，是没有两个三元环拥有同一条边）
题解
从构造的角度来思考：如果能构造出的答案达到上界，那么它一定是最优解
先把答案的上界算出来：\(\frac{(2^n-1)(2^n-2)}{6}\)。因为连续 \(3\) 个数中一定有一个是 \(3\) 的倍数，所以答案的上界是整数。
我们可以把点从 \(1\) 到 \(2^n-1\) 编号，把满足 \(x \oplus y \oplus z=0\) 的 \((x,y,z)\) 当做三元环。这种构造可以取到上界。
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
//# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")
template <typename T> inline T read ()
{
T s = 0; int w = 1; char c = getchar ();
for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
return s * w;
}
int n;
signed main ()
{
n = rd (int);
n = pow (2, n) - 1;
int m = n * (n - 1) / 6;
printf ("%d\n", m);
for (int i = 1; i <= n; i ++ )
{
for (int j = i + 1; j <= n; j ++ )
{
int k = 0 ^ i ^ j;
if (k > j) printf ("%d %d %d\n", i, j, k);
}
}
return 0;
}
T3
题目描述
给定一个 \(2n\) 个点的完全图，要把这些边分成 \(2n-1\) 组，每组 \(n\) 条边，且每条都是一个匹配（任意两条边没有公共点）
题解
把所有的点从 \(0\) 到 \(2n-1\) 编号。我们可以把 \(0\) 到 \(2n - 2\) 和 \(2n-1\) 分开考虑。
对于一组边 \((x,y)\) 满足 \(0\leq x < y < 2n-1\)，我们把他们扔到 \((x+y)\mod (2n-1)\) 这一组。
因为 \(2n-1\) 是奇数，所以每个 \(i\) 有且只有一个 \(k\) 使得 \(2k=i \mod 2n-1\)。所以把 \((k,2n-1)\) 这条边扔到 \(i\) 这一组里就行
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
//# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")
const int N = 2005;
template <typename T> inline T read ()
{
T s = 0; int w = 1; char c = getchar ();
for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
return s * w;
}
int n;
vector <pii> vec[N];
signed main ()
{
n = rd (int);
for (int i = 0; i < 2 * n - 1; i ++ )
{
for (int j = i + 1; j < 2 * n - 1; j ++ )
vec[(i + j) % (2 * n - 1)].push_back ({i, j});
}
for (int i = 0; i < 2 * n - 1; i ++ )
{
for (int k = 0; k < 2 * n - 1; k ++ )
{
if ((2 * k) % (2 * n - 1) == i)
vec[i].push_back ({k, 2 * n - 1});
}
}
// return 0;
for (int i = 0; i < 2 * n - 1; i ++ )
{
// cout << i << endl;
for (auto t : vec[i]) printf ("%d %d\n", t.fi + 1, t.se + 1);
printf ("\n");
}
return 0;
}
T4
题目描述
求将 \(n\) 个点的完全图划分成最多的生成树的数量，并输出一种构造方案
题解
一棵生成树有 \(n-1\) 条边，而原完全图只有 \(\frac{n(n-1)}{2}\) 条边，所以最多的生成树数量为 \(\left \lceil \frac{n}{2} \right \rceil\)
我们只需要考虑 \(n\) 为偶数的情况，因为 \(n\) 为奇数时可以从 \(n-1\) 的个点的构造方案中继承过来
假设最新加入的点是 \(i-1\)，\(i\)
首先，对 \(i-1\) 和 \(i\) 建一颗新树，连边方式如下：
- \(n-1 \to n\)
- 对于 \(1\) ~ \(n-2\)：奇数连 \(n\)，偶数连 \(n-1\)
还需要再之前的树上连上 \(n-1\) 和 \(n\)。对于之前的点：奇数连 \(n-1\)，偶数连 \(n\)。
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
//# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")
const int N = 2005;
template <typename T> inline T read ()
{
T s = 0; int w = 1; char c = getchar ();
for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
return s * w;
}
int n;
struct node { int u, v; };
vector <node> tr[N];
signed main ()
{
n = rd (int);
printf ("%d\n", n / 2);
if (n % 2 == 1)
{
for (int i = 1; i <= n / 2; i ++ )
tr[i].push_back ({i * 2, n});
}
for (int u = 2; u <= n; u += 2)
{
int v = u - 1;
tr[u / 2].push_back ({u, v});
for (int i = 2; i < u; i += 2)
{
int j = i - 1;
tr[u / 2].push_back ({i, v}); tr[u / 2].push_back ({j, u});
tr[i / 2].push_back ({i, u}); tr[i / 2].push_back ({j, v});
}
}
for (int i = 1; i <= n / 2; i ++ )
{
for (int j = 0; j < tr[i].size (); j ++ )
printf ("%d %d ", tr[i][j].u, tr[i][j].v);
printf ("\n");
}
return 0;
}