牛客周赛 round34（第一次写题解qwq）

C 小红的数字拆解

思路：没啥好讲的，这题主要就考查了cmp 重载排序
直接上代码：

#include<bits/stdc++.h>
 
using namespace std;
 
bool cmp(const string& a, const string& b) {  
    if (a.size() != b.size()) {  
        // 如果长度不同，则长度更大的数字更大  
        return a.size() < b.size();  
    }  
    // 如果长度相同，则逐位比较  
    for (size_t i = 0; i < a.size(); ++i) {  
        if (a[i] != b[i]) {  
            // ASCII值较小的字符表示的数字更大（因为是从左到右逐位比较的）  
            return a[i] < b[i];  
        }  
    }  
    // 如果所有位都相同，则两个数字相等  
    return false;  
} 

vector<string>m;
 
 
int main()
{
    string c;
    cin >> c;
    string num ;
    int cnt = 0, flag = 0, i = 0;
    for(int i=0;c[i];i++)
    {
        if((c[i]-'0')%2)num.push_back(c[i]);
        else if(num.size()==0&&c[i]=='0'){m.push_back("0");num.clear();}
        else if(num.size()!=0&&c[i]=='0'){num.push_back(c[i]);m.push_back(num);num.clear();}
        else if(!((c[i]-'0')%2))
        {
            num.push_back(c[i]);
            m.push_back(num);
            num.clear();
        }
    }
    sort(m.begin(),m.end(),cmp);
    
     
    for (int i = 0; i < m.size(); i++)cout<<m[i]<<'\n';
    return 0;
}

D 小红的陡峭值

题目描述：

小红定义一个数组的陡峭值为相邻两数差的绝对值之和。

现在小红拿到了一个长度为n的、仅由正整数组成的数组，但她有一些元素看不清了，只记得数

组的陡峭值恰好等于 1。小红希望你能还原整个数组，你能帮帮她吗？(看不清的元素输入为0）

本题大体思路： 找出整个数组中的最大值ma与最小值mi，用vectorv1,v2分别存储最大值与最小值出现时的序号，（这里需要注意mi不能取0),然后进行以下分类讨论：

1.若ma-mi>1,显然不满足陡峭值为1的条件

2.若ma-mi==1,进行以下分类讨论：

(1)若最大数所出现的最后的序号小于最小数最先出现的序号，则将v1.back()以前的数全部填充为ma,以后的数全部填充为mi

(2)若最小数所出现的最后的序号小于最大数最先出现的序号，则将v2.back()以前的数全部填充为mi，以后的数全部填充为ma

(3)其余情况均为不可能还原整个数组的情况（陡峭值必定大于1）

3.若ma==mi,进行以下分类讨论:

(1)所有数全部为的情况:

 自由填充，只需满足陡峭值为1即可

(2)左右两端的数全部非0的情况

 不能满足陡峭值等于1的条件

(2)左右两端一端非0，另一端为0的情况

 令为0的一端等于ma+1,其余位置填充ma

(3)左右两端均为0的情况

 令任意一端为ma+1,其余位置填充ma

4.输出

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int c[N];
vector<int>v1, v2;

int main()
{
    int n, ma = 0, mi = 2e9;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> c[i]; ma = max(ma, c[i]);
        if (c[i] != 0)mi = min(mi, c[i]);
        if(i==n-1&&mi==2e9)mi=0;
    }

    if (ma - mi == 1)
    {
        for (int i = 0; i < n; i++)
        {
            if (c[i] == ma)v1.push_back(i);
            else if (c[i] == mi)v2.push_back(i);
        }
        if (v1.back() < v2[0])
        {
            for (int i = 0; i <= v1.back(); i++)cout << ma << ' ';
            for (int i = v1.back() + 1; i < n; i++)cout << mi << ' ';
        }
        else if (v2.back() < v1[0])
        {
            for (int i = 0; i <= v2.back(); i++)cout << mi << ' ';
            for (int i = v2.back() + 1; i < n; i++)cout << ma << ' ';
        }
        else {
            cout << "-1";
            return 0;
        }
    }
    else if (ma == mi)
    {
        if (ma == 0)
        {
            for (int i = 0; i < n-1; i++)cout << "1" << ' ';
            cout<<"2";
            return 0;
        }
        if (c[0] == ma && c[n - 1] == ma)
        {
            cout << "-1";
            return 0;
        }
        else if (c[0] == ma && c[n - 1] != ma)
        {
            for (int i = 0; i < n - 1; i++)cout << ma << ' ';
            cout << ma + 1;
        }
        else {
            cout << ma + 1 << ' ';
            for (int i = 0; i < n - 1; i++)cout << ma << ' ';
        }
    }
    else {
        cout << "-1";
    }
    return 0;
}

E 小红的树形dp

题目描述:
小红拿到了一棵树，每个节点上有一个字符，每个节点上的字符为'd'、'p'、'?'这三种。 现在请你将所有'?'字符变成'd'或者'p'字符，需要满足任意两个相邻节点的字符不同。你能帮帮她吗
大体思路：题目标题在诱导你往树形dp的方向想，实际上根本不用，这是一个染色二分图的模板题。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
vector<int>q[N];
char c[N];

bool ok = true;//用ok来判断是否能生成这样一个树

void dfs(int n, int fa)//n为当前节点,fa为父节点，该函数的操作为从n节点开始向下遍历
{
  char now = c[n];
  for (auto borwin : q[n])
  {
      if (borwin != fa)//防止往回走
      {
          if (c[borwin] == now)
          {
              ok = false;
              return;
          }
          else c[borwin] = 'd' + 'p' - now;
          dfs(borwin, n);
      }
  }
}

int main()
{
  int n, u, v, pos = 0;
  cin >>n>> c + 1;
  for (int i = 1; i < n; i++)//树的初始化(无向)
  {
      cin >> u >> v;
      q[u].push_back(v); q[v].push_back(u);
  }
  for (int i = 1; i <= n; i++)//查找一个不是'?'的点
  {
      if (c[i] != '?') { pos = i; break; }
  }
  if (pos == 0)c[1] = 'd', pos = 1;//若全是'?'则令第一个为'd'
  dfs(pos, 0);//pos即为当前点，从一个非'?'字符开始bfs
  if (ok)
  {
      for (int i = 1; i <= n; i++)cout << c[i];
  }
  else cout << "-1";
  return 0;
}