题解 | #牛客周赛29 A-E#

声明：

1. 本人未参加此次比赛。
2. 非本人AC的代码均会标注参考来源。

A-小红大战小紫

下面是代码部分

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    if(a == b) cout << "draw\n";
    else if(a > b) cout << "kou\n";
    else cout << "yukari\n";

    return 0;
}

B-小红的白日梦

思路

1. 注意题目，每次只能交换同一天的做梦时间
2. 贪心，能换到白天就尽量换到白天

以下是代码部分

#include <bits/stdc++.h>
using namespace std;

string s[2];

int main()
{
    int n, sum = 0;
    cin >> n >> s[0] >> s[1];
    for(int i = 0; i < n; i ++)
    {
      //这两者顺序不可交换
        if(s[0][i] == 'Y' && s[1][i] == 'Y') sum += 3;
        else if(s[0][i] == 'Y' || s[1][i] == 'Y') sum += 2;
    }
    cout << sum << endl;

    return 0;
}

C-小红的小小红

思路

• 截取出一组“xiaohong”, 再直接输出即可

以下是代码部分

#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
    cin >> s;
  //找到“xiao”
    int i = s.find("xiao");
  //删除
    s.erase(i, 4);
  //找到“hong”
    i = s.find("hong");
  //删除
    s.erase(i, 4);
  //直接输出
    cout << "xiaohong" << s << endl;

    return 0;
}

D-小红的中位数

思路

观察

1. 如果删除后数组内元素个数为奇数，那么中位数由一个元素决定。
2. 如果删除后数组内元素个数为偶数，那么中位数由两个元素决定。
3. 易得中位数只与靠近中间的几个元素有关。

方法

发现这两位讲得更好——宁宁也要爆wa， tangren

1. 首先复制出a[]有序后的数组b[]。
2. 当删除某个元素时，可以看成中间值在原数组的偏移（因为只删除一个元素，所以中间值只偏移半个单位——如果删除的是中间值另作讨论）
3. 根据n的奇偶差别，以及中间值偏移的方向进行一系列分类讨论即可。

以下是代码部分

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
double a[N], b[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        b[i] = a[i];//复制a[]到b[]中
    }
    sort(b + 1, b + n + 1);
    for(int i = 1; i <= n; i ++)
    {
        if(n & 1)//如果n为奇数
        {
          //当删除的元素偏小时
            if (a[i] <= b[n / 2])
                printf("%.1f\n", (b[n / 2 + 1] + b[n / 2 + 2]) / 2.0);
          //当删除的元素偏大时
            else if(a[i] > b[n / 2 + 2])
                printf("%.1f\n", (b[n / 2] + b[n / 2 + 1]) / 2.0);
          //删除一个元素后，数组元素个数变为偶数，所以中间值与相邻两个元素有关，分类讨论
          //当删除的为与中间值相关的偏小的元素时
            else if(a[i] == b[n / 2 + 1])
                printf("%.1f\n", (b[n / 2] + b[n / 2 + 2]) / 2.0);
          //当删除的为与中间值相关的偏大的元素时
            else if(a[i] == b[n / 2 + 2])
                printf("%.1f\n", (b[n / 2] + b[n / 2 + 1]) / 2.0);
        }
        else//如果n为偶数
        {
          //当删除的元素小或者为与原数组的中间值相关的偏小的元素时
            if(a[i] <= b[n / 2])
                printf("%.1f\n", 1.0 * b[n / 2 + 1]);
          //当删除的元素大或者为与原数组的中间值相关的偏大的元素时
            else
                printf("%.1f\n", 1.0 * b[n / 2]);
        }
    }

    return 0;
}

E-小红构造数组

注意事项

• 记得开

思路

拆解成若干个素数之积

• 筛——另一个题解解释的很好——重生之我是大菜狗，我就不解释了。

如何判断是否可以构造

• 可以想到插空排队“1”代表有人
• 加入一个队列时这样的： 1 1 1 1 1 1
• 如何使每个人互不相邻——只需要其他数插在1与1之间
• 所以只需要其他数的数量之和不小于 （1的数量）-1 即可
• 可以得出只需要 （众数的数量）(数的总数 + 1 / 2) —— keduoli

输出

• 按照队列插空的方法输出。
• 按数量从大到小排序。
• 先排偶数位的，再排奇数位的。有效避免相邻元素相等

以下是代码部分

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e6 + 10;
// len用来储存输出的长度， outLine用来储存需输出的数组
ll len, outLine[N];
//
typedef struct Map{
    ll key, value;
}Map;

Map mp[N];

bool cmp(Map a, Map b){return a.value > b.value;}

int main()
{
    ll x, ans = 0, cnt = 0;
    cin >> x;
    if(x == 1) return cout << "-1\n", 0;
    while(x % 2 == 0)//先排除2，利于减少下面的for（）循环次数
    {
        if(!cnt) cnt ++;
        ans ++, x /= 2, mp[cnt].key = 2, mp[cnt].value ++;
    }
    len += ans;
    for(ll i = 3; i * i <= x; i += 2)
    {
        ans = 0;
        if(x % i == 0) {
            ans = 0, cnt ++;
            mp[cnt].key = i;
            while (x % i == 0)
                x /= i, ans++, mp[cnt].value ++;
        }
        len += ans;
    }
    if(x > 1)//判断是否除尽，未除尽的需存储到数组中
    {
        len ++, cnt ++;
        mp[cnt].key = x, mp[cnt].value = 1;
    }
    sort(mp + 1, mp + 1 + cnt, cmp);//根据数量从大到小排序
    if(mp[1].value > (len + 1) / 2)
        cout << "-1\n";
    else
    {
        cout << len << endl;
        int temp = 1;
        for(int i = 0; i < len; i += 2)//储存于奇数位中
        {
            if(!mp[temp].value) temp ++;
            outLine[i] = mp[temp].key;
            mp[temp].value --;
        }
        for(int i = 1; i < len; i += 2)//储存于偶数位中
        {
            if(!mp[temp].value) temp ++;
            outLine[i] = mp[temp].key;
            mp[temp].value --;
        }
        for(int i = 0; i < len; i ++) cout << outLine[i] << " \n"[i == len - 1];
    }

    return 0;
}