2021-12-15 CFS ROUDN 760 水题记录

2021-12-15 CFS ROUDN 760 水题记录

CFS ROUDN 753 水题记录

• Problem A - Polycarp and Sums of Subsequences
• Problem B - Missing Bigram
• Problem C - Paint the Array
• Problem D - Array and Operations
• Problem E - Singers' Tour
• Problem F - Reverse
• Problem G - Trader Problem
• **参考代码**

这里是平时水水比赛的流水账式思路记录，如果有值得研究的题则会另写详细题解。
点这里进入比赛

Problem A - Polycarp and Sums of Subsequences

---

Problem B - Missing Bigram

有点类似贪心

---

Problem C - Paint the Array

-题意思路
  需要求gcd，由于数据较小，算出奇数位的gcd和偶数位的gcd后分别去判断下是否满足题意即可。

---

Problem D - Array and Operations

-题意思路
  一道贪心，优先取大值，排序后花点心思实现代码即可。

---

Problem E - Singers’ Tour

-题意思路
   实际就是一道解方程的题目，这题对于方程组分析下就能算出答案。当时的一点推算：

---

Problem F - Reverse

---

Problem G - Trader Problem

---

期末了大概率不往下补了…

参考代码

#include 
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
void solveA()
{
    int t;
    cin >> t;
    int a[7];
    while (t--)
    {
        for (int i = 0; i < 7; i++)
        {
            cin >> a[i];
        }
        cout << a[0] << " " << a[1] << " ";
        if (a[0] + a[1] == a[2])
        {
            cout << a[3] << endl;
        }
        else
        {
            cout << a[2] << endl;
        }
    }
}

void solveB()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        string x[105];
        char c = 'b';
        int flag = -1;
        string ans = "";
        for (int i = 0; i < n - 2; i++)
        {
            cin >> x[i];
            if (i > 0)
            {
                if (c == x[i][0])
                {
                    ans += x[i][1];
                }
                else
                {
                    ans += x[i];
                }
            }
            else
            {
                ans = x[i];
            }
            c = x[i][1];
        }
        if (ans.size() != n)
        {
            ans += "b";
        }
        cout << ans << endl;
    }
}

void solveC()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        ll a[105];
        ll g1 = 0;
        ll g2 = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            if (i & 1)
                g1 = gcd(g1, a[i]);
            else
                g2 = gcd(g2, a[i]);
        }
        int flag = 1;
        for (int i = 2; i <= n; i += 2)
        {
            if (a[i] % g1 == 0)
            {
                flag = 0;
                break;
            }
        }
        if (flag)
        {
            cout << g1 << endl;
            continue;
        }
        flag = 1;
        for (int i = 1; i <= n; i += 2)
        {
            if (a[i] % g2 == 0)
            {
                flag = 0;
                break;
            }
        }
        if (flag)
        {
            cout << g2 << endl;
            continue;
        }
        cout << 0 << endl;
    }
}

void solveD()
{
    int t;
    cin >> t;
    while (t--)
    {
        // perform exactly 푘 operations with this array 푎 of 푛 integers
        int n, k;
        cin >> n >> k;
        int a[105];
        int score = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        sort(a + 1, a + 1 + n);
        for (int i = 1; i <= n; i++)
        {
            if (i <= n - 2 * k)
            {
                score += a[i];
            }
        }
        vector v;
        int pre = a[n];
        int cnt = 1;
        for (int i = n - 1; i >= n - 2 * k + 1; i--)
        {
            if (pre == a[i])
                cnt++;
            else
            { // 不同
                v.push_back(cnt);
                cnt = 1;
                pre = a[i];
            }
        }
        v.push_back(cnt);
        // 将多出来的重复数量放到cnt
        if (k > 0)
        { // k>0 才需要计算重复的数量
            sort(v.begin(), v.end());
            //cout<<"v[v.size() - 1]="<> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector b(n + 1);
        b.push_back(n);
        ll sumB = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> b[i];
            sumB += b[i];
        }
        vector a(n + 1);
        if ((2 * sumB) % ((1 + n) * n) != 0) // 保证sumA合法（不是小数）
        {
            cout << "NO" << endl;
            continue;
        }
        ll sumA = (2 * sumB) / ((1 + n) * n); // 全部累加，可由sumB求出sumA

        a[1] = sumA; // 后续loop减去
        int flag = 1;

        for (int i = 2; i <= n; i++)
        {

            a[i] = (sumA - b[i] + b[i - 1]) / n; // 核心推导式子
            a[1] -= a[i];
            if ((sumA - b[i] + b[i - 1]) % n != 0 || a[i] <= 0) // 能整除并且大于0才可作为计算
            {
                flag = 0;
                break;
            }
        }
        if (a[1] <= 0)
            flag = 0; // 这里别忘了判断
        if (flag)
        {
            cout << "YES" << endl
                 << a[1];
            for (int i = 2; i <= n; i++)
            {
                cout << " " << a[i];
            }
            cout << endl;
        }
        else
            cout << "NO" << endl;
    }
}

int main()
{
    solveD();
    return 0;
}