总题目传送门

A. Filling Diamonds

思路

• 分析：cf的老套路了，一看 \(n<=1e9\),根本没法求，只能找规律，在找规律的时候，注意利用之前的的结论，例如在数n = 3组合方案数的时候，可以利用 n==2时的结论

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
void fre() { freopen("A.txt","r",stdin); freopen("Ans.txt","w",stdout); }
const int mxn = 3005;

int main()
{
    /* fre(); */
    int t;
    scanf("%d", &t);
    while(t --)
    {
        int n;
        cin >> n;
        cout << n << endl;
    }


    return 0;
}

B. Sorted Adjacent Differences

思路

• 题意：给我们一个长度为n的序列a，问我们经过重新的排序后，能否使序列满足：\(|a_2 - a_1|=<|a_3-a_2|=<|a_4-a_3|=<....<=|a_n-a_{n-1}|\)

• 分析：上式所要表达的意思是：在重新排列过后的序列相邻的元素之间的差值要 非严格逐渐差值增大，我先对序列a从小到大排序，要想相邻的树逐渐增大 那么我们可以 从a中间位置往两边位置开始每次选择对称位置的一对元素放到序列前面，，循环此操作就能构造出符合要求的序列了

分析

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
void fre() { freopen("A.txt","r",stdin); freopen("Ans.txt","w",stdout); }
const int mxn = 2e5;
int ar[mxn];

int main()
{
    /* fre(); */
    int t;
    scanf("%d", &t);
    while(t --)
    {
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; i ++)
            scanf("%d", &ar[i]);
        sort(ar + 1, ar + 1 + n);

        int tm = 0;
        if(n%2)
            printf("%d ", ar[n/2+1]), tm = 1;

        for(int i = n/2; i >= 1; i --)
            printf("%d %d ", ar[i], ar[n - i + 1 ]);
        printf("\n");
    }


    return 0;
}

C. Powered Addition

思路

• 给我们一个n个元素的序列ar，我们可以对这个序列进行无限次操作，对于第i次操作我们可任意选择ar中的一些元素，把这些被选中的元素都加上 \(2^{i-1}\),问我们要最少经过多少次操作就能把这个序列变非严格递增的序列？
• 分析：既然我们可以任意选择需要的元素进行加值操作，那么我们要关注的需要 增加值最多的那个元素，因为一但 需要增加值最多的那个元素都 已经被 经过“加值操作”之后边成的递增，那么其它需要增加值的元素 就一定可以实现递增，而要找到差值最小的那个数的差值，只需要用 前缀和维护一下就行了

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
void fre() { freopen("A.txt","r",stdin); freopen("Ans.txt","w",stdout); }
#define ll long long 
#define INF 0x3f3f3f3f
const int mxn = 2e5;
int ar[mxn];
ll pref[35];
int pmx[mxn];


int main()
{
    /* fre(); */
    pref[1] = 1;
    for(int i = 2; i <= 31; i ++)
        pref[i] = pref[i - 1] * 2;
    for(int i = 2; i <= 31; i ++)
        pref[i] += pref[i - 1];

    int t;
    scanf("%d", &t);
    while(t --)
    {
        int n;
        scanf("%d", &n);
        pmx[0] = -INF;
        int cha = 0;
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d", &ar[i]); 
            pmx[i] = max(pmx[i - 1], ar[i]);
            if(i != 1 && ar[i] < pmx[i - 1])
                cha = max(cha, abs(ar[i] - pmx[i - 1]));
        }

        int pos = lower_bound(pref + 1, pref + 1 + 31, cha) - pref;
        if(cha == 0)
            pos = 0;
        printf("%d\n", pos);
    }


    return 0;
}

D. Edge Weight Assignment

思路

• 题意：给我有n（n>3）个节点的形成的“树”,树上的边是没有权值的，现在我们可以给这棵树的上的边上分配权值，是任意 两叶子节点 之间的边上的权值相互异或最终的结果为0，在满足上述的要求的基础上，这棵树的所有的边上数字种类最多、最少有多少个？

• 思路：有两种思路，这两种思路的本质相同，只不过在dfs的过程初始时的根结节点不同

  • 第一种思路：以度为1的节点即叶节点作为根结点进行搜索
    1.对于最小值：只有所有叶子节点到我们选择的根节点（它其实也是一个叶子节点），之间路径的中包含的边树（即深度）均为偶数的时候，这个时候最小 数字种类 为1（我们可以把所有的边都 赋上一个相同的权值），否则的话最小只能为3
    2.对于最大值，两种思路的求法思路都是一样的，首相我能考虑 某个节点x，它有多个子节点且这些子节点都是叶节点，由于这些叶子节点的所处的高度是相同的，所以这些叶节点与父节点x之间的边上的数字是相同的，相当于这多个叶子节点与父亲节点x之间边贡献的数字种类就是只是 1，因此我们只需要保留x节点的一个叶子结点（即一条边），剩下x的叶子结点（剩下的边）都是多余的。而除了 “叶子节点与它们的父节点之间的边”意外的边我填任意数字都可以，因此这些边每条边贡献的数字的种类都是1，所以最终的最大数字种类是：总的边数（n-1） - 多余的叶子形成的边

  • 对于第二种思路：我们选择的根结点是非叶子结点，

  1. 求最小值，要想是最小值为1,那么所以点叶子所在的深度 都是同奇偶才能为1（因为样任意两个叶子结点之间的区间距离均为偶数，这个时候你可以在看看 第一种思路的求最小值的d的思路，是不是感觉一毛一样），否只能为3
  2. 对于最大值，请看第一种思路的最大值方法

思路1代码

#include<vector>
#include<iostream>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
void fre() { freopen("A.txt","r",stdin); freopen("Ans.txt","w",stdout); }
#define ll long long 
#define INF 0x3f3f3f3f
const int mxn = 3e5;

vector<int> G[mxn];
int tot[mxn];
int mnf = 1;

void dfs(int u, int f, int d)       //u当前正在讨论的节点，f为u的前一个节点，d为u节点的深度，跟节点的深度 d = 0
{
    if(G[u].size() == 1 && d % 2) mnf = 3;
    
    for(auto v : G[u])
        if(v != f) 
            dfs(v, u, d + 1);
}


int main()
{
    /* fre(); */
    int n;
    scanf("%d", &n);
    int u, v;
    for(int i = 1; i < n; i ++)
    {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    int mxf = n - 1;
    for(int i = 1; i <= n; i ++)
        if(G[i].size() == 1) tot[G[i][0]] ++;
    for(int i = 1; i <= n; i ++)
        if(tot[i] > 1) mxf -= tot[i] - 1;   //如果某个节点有多个叶节点，这个多个叶子节点上的数字完全相同，所以要把叶子结点上重复的 数字 减去

    for(int i = 1; i <= n; i ++)
        if(G[i].size() == 1) { dfs(i, -1, 0); break;}
    printf("%d %d\n", mnf, mxf);
    
    return 0;
}

思路2代码

#include<vector>
#include<iostream>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
void fre() { freopen("A.txt","r",stdin); freopen("Ans.txt","w",stdout); }
#define ll long long 
#define INF 0x3f3f3f3f
const int mxn = 3e5;
int head[mxn];
int du[mxn], deep[mxn], cnt[mxn];
struct Edge
{
    int v, next;
} edge[mxn];
int tot = 0;
void Add(int u, int v)
{
    edge[++ tot] = (Edge){ v, head[u] }; 
    head[u] = tot;
}

int odd, even;
void dfs(int u, int f)
{
    if(u != f)              //在刚开始的时候不要 根节点的深度为1，让它从深度0开始
        deep[u] = deep[f] + 1;
    if(du[u] == 1)
    {
        if(deep[u] & 1)     //统计从root节点出发到根结的 深度是奇数还是偶数
            even = 1;
        else 
            odd = 1;
        cnt[f] ++;
    }

    for(int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].v;
        if(v != f)
            dfs(v, u);
    }
}

int main()
{
    /* fre(); */
    int n;
    scanf("%d", &n);
    int u, v;
    for(int i = 1; i < n; i ++)
    {
        scanf("%d %d", &u, &v);
        Add(u, v), Add(v, u);
        du[u] ++, du[v] ++;
    }

    int r;
    for(int i = 1; i <= n; i ++)
        if(du[i] != 1)              //从不是叶节点的一个节点开始深搜
        {
            r = i;
            break;
        }
    dfs(r, r);
    int sur_leave = 0;
    for(int i = 1; i <= n; i ++)
        if(cnt[i])
            sur_leave += cnt[i] - 1;
    if(odd + even == 1)
        printf("1");
    else
        printf("3");
    printf(" %d\n", n - 1 - sur_leave);

    return 0;
}

Codeforces Round #633 (Div. 2)（A～D）

原文：https://www.cnblogs.com/lql-nyist/p/12783113.html