Pinely Round 4 (Div. 1 + Div. 2)
发挥到极致了，写出了两题
A. Maximize the Last Element
对于每个满足他左边的数的个数和他后面的数的个数都是奇数的数，取最大值即可。
# include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// # define int long long
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
const int N = 105;
int n;
signed main ()
{
int T; scanf ("%d", &T);
while (T -- )
{
scanf ("%d", &n);
int mx = 0;
for (int i = 1; i <= n; i ++ )
{
int x; scanf ("%d", &x);
if ((i - 1) % 2 == 0 && (n - i) % 2 == 0) mx = max (mx, x);
}
printf ("%d\n", mx);
}
return 0;
}
B. AND Reconstruction
对于每个位置 \(i\)，他与前面位置的公共部分为 \(b_{i-1}\)，与后面公共部分是 \(b_i\)。所以这个位置至少是 \(b_{i-1} | b_i\)。如果这个时候不满足，就判定误解。如果满足，那么构造就是这个啦。
# include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// # define int long long
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
const int N = 100005;
int n;
int b[N], a[N];
signed main ()
{
int T; scanf ("%d", &T);
while (T -- )
{
scanf ("%d", &n);
for (int i = 1; i < n; i ++ ) scanf ("%d", &b[i]);
a[1] = b[1], a[n] = b[n - 1];
for (int i = 2; i < n; i ++ ) a[i] = b[i - 1] | b[i];
bool flag = 1;
for (int i = 1; i < n; i ++ )
{
if ((a[i] & a[i + 1]) != b[i])
{
flag = 0;
break;
}
}
if (!flag)
{
printf ("-1\n");
continue;
}
for (int i = 1; i <= n; i ++ ) printf ("%d ", a[i]);
printf ("\n");
}
return 0;
}
C. Absolute Zero
看到 \(n\le 2\times 10^5,k\le 40\)，就很容易想到拆位。首先，如果序列中有两个数机奇偶性不同，就肯定无法把整个序列变成 \(0\)，因为这两个数永远差着一个 \(1\)。所以，如果存在两个奇偶性不同的数，就判定无解。否则，就从大到小的每一个二进制位进行操作即可。
# include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// # define int long long
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
const int N = 200005;
int n;
int a[N];
signed main ()
{
int T; scanf ("%d", &T);
while (T -- )
{
scanf ("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf ("%d", &a[i]);
bool flag = 0;
for (int i = 2; i <= n; i ++ )
{
if (a[i] % 2 != a[1] % 2)
flag = 1;
}
if (flag)
{
printf ("-1\n");
continue;
}
if (a[1] % 2 == 0)
{
printf ("31\n");
for (int i = 29; i >= 0; i -- ) printf ("%d ", (1ll << i));
printf ("1\n");
}
else
{
printf ("30\n");
for (int i = 29; i >= 0; i -- ) printf ("%d ", (1ll << i));
printf ("\n");
}
}
return 0;
}
D. Prime XOR Coloring
玄学题，我知道构造方法，但是我不知道怎么想到的题。
那么我就只能给出构造方法以及证明了。
构造方法
- \(n=1\)：
1 - \(n=2\)：
1 2 - \(n=3\)：
1 2 2 - \(n=4\)：
1 2 2 3 - \(n=5\)：
1 2 2 3 3 - \(n\ge 6\)：
2 3 4 1 2 3 4 1 2 3 4 1 ...
证明
首先，\(n\le 5\) 的十分好证。
对于 \(n\ge 6\) 的情况，如果两个点颜色相同，那么他们异或起来一定是 \(4\) 的倍数，不是质数，所以没有边。
证毕。
# include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// # define int long long
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
signed main ()
{
int T; scanf ("%d", &T);
while (T -- )
{
int n; scanf ("%d", &n);
if (n == 1) printf ("1\n1\n");
else if (n == 2) printf ("2\n1 2\n");
else if (n == 3) printf ("2\n1 2 2\n");
else if (n == 4) printf ("3\n1 2 2 3\n");
else if (n == 5) printf ("3\n1 2 2 3 3\n");
else
{
printf ("4\n");
for (int i = 1; i <= n; i ++ ) printf ("%d ", i % 4 + 1);
printf ("\n");
}
}
return 0;
}