A.Filling Diamonds

题意：

给定个菱形，要将它们组成一个钻石，问所有的摆放方案
图片说明

题解：

其实可以发现每个钻石只有一个菱形是立着的，所以方案数就是一个钻石内能立着的位置数，可以发现刚好是
图片说明 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 3e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
void solve()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", n);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Sorted Adjacent Differences

题意：

给定一个数组，要求重新排列，使得相邻两个元素的差值单调不降。

题解：

先将升序排序，然后从中间开始分别从两边取一个数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[maxn];
void solve()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    int mid = n / 2 + 1;
    int l = mid - 1, r = mid + 1;
    printf("%d ", a[mid]);
    while (l >= 1 || r <= n)
    {
        if (l >= 1)
            printf("%d ", a[l--]);
        if (r <= n)
            printf("%d ", a[r++]);
    }
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Powered Addition

题意：

给你一个数组，你可以在第秒选一些元素让它们加，询问最短的时间使得数组变成单调不降

题解：

考虑到二进制的性质,那么这道题实际就是找，因此只需要

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[maxn];
void solve()
{
    int n, x, y, mx = 0;
    scanf("%d", &n);
    scanf("%d", &x);
    for (int i = 1; i < n; i++)
    {
        scanf("%d", &y);
        if (x > y)
            mx = max(mx, x - y);
        x = max(x, y);
    }
    printf("%d\n", (int)ceil(log2(mx + 1)));
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Edge Weight Assignment

题意：

给你一棵个节点的树，要求给每一条边一个权值，要满足任意两个叶节点的路径上的边的权值异或和为。询问最少和最多的种类

题解：

先考虑最少的情况，各个叶子节点到根的距离的奇偶性如果一样，那么所有边权都可以相等，只需要一种，否则的话只需要用三个数即可，如样例2
再考虑最多的情况，理想条件肯定是每一条边都填上不同的数字，那么最大值为，但是当个叶子节点连接同一个节点时，很明显这个叶子节点的邻边边必须填相同的数，我们在的基础上减即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
vector<int> G[maxn];
int ans;
int c[3], dep[maxn];
void dfs(int u, int fa)
{
    int cnt = 0;
    for (int v : G[u])
    {
        if (v == fa)
            continue;
        dep[v] = dep[u] + 1;
        if (G[v].size() == 1)
        {
            c[dep[v] & 1]++;
            cnt++;
        }
        else
            dfs(v, u);
    }
    if (cnt >= 2)
        ans -= cnt - 1;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int rt;
    for (int i = 1; i <= n; i++)
        if (G[i].size() > 1)
        {
            rt = i;
            break;
        }
    ans = n - 1;
    dfs(rt, 0);
    printf("%d %d\n", c[0] && c[1] ? 3 : 1, ans);
    return 0;
}

E.Perfect Triples

题意：

给定一个无限长的序列，每次将一个三元组加入，要求三元组满足：

  • 均不在中
  • 三元组是所有满足条件中字典序最小的

给定组询问，每次询问给定一个要求给出中的第的数，

题解：

显然是个结论题，打表找找规律
贴一下一位博主这题的打表结论，原博客戳我~
四进制下
001 002 003
//1行

010 020 030
011 022 033
012 023 031
013 021 032
//1<<2行

100 200 300
101 202 303
102 203 301
103 201 302
110 220 330
111 222 333
112 223 331
113 221 332

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll f[4] = {0, 2, 3, 1};
ll B(ll a) { return (a == 1) ? 2 : f[a & 3] | B(a >> 2) << 2; }
int main()
{
   int t;
   scanf("%d", &t);
   while (t--)
   {
      ll n, A[3];
      scanf("%lld", &n);
      ll d = 1;
      for (; n >= d; d <<= 2);
      d >>= 2;
      A[0] = d | ((n - d) / 3);
      A[1] = B(A[0]);
      A[2] = A[0] ^ A[1];
      printf("%lld\n", A[(n - d) % 3]);
   }
}