week3

2021-08-01

第三周

A_Polycarp_and_Coins（cf）

链接：

https://codeforces.com/contest/1551/problem/0

思路：

经典if else，由于需要用1分2分拼，所以结果与3的倍数有关，分类讨论即可

俺是一坨垃圾代码QWQ:

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int x;
        cin >>x;
        if(x%3==0)
        {
            cout << x / 3 << " " << x / 3 << endl;
        }
        else
        {
            if((x+1)%3==0)
            cout << x / 3 << " " << x / 3 + 1 << endl;
            else
                cout << x / 3 + 1 << " " << x / 3 << endl;
        }
    }
}

Wonderful_Coloring_1（cf）

链接：

https://codeforces.com/contest/1551/problem/B1

思路：

我起手，一把秒了，就俩颜色，我说我是乱涂的，同一个字符3个以上就没法涂了，剩下能涂的全部打上标记，问的是红色能涂上几个，除2即可

俺是一坨垃圾代码QWQ:

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string str;
        cin >> str;
        int cnt = 0;
        map<char, int> mp;
        for (int i = 0; i < str.size();i++)
        {
            mp[str[i]]++;
            if(mp[str[i]]<=2)
                cnt++;
        }
        cout << cnt / 2 << endl;
    }
    return 0;
}

Wonderful_Coloring_2（cf）

链接：

https://codeforces.com/contest/1551/problem/B2

思路：

我起手，一把被秒了，赛场上的两题选手，赛后看完题解重拳出击！！！其实就是一个贪心（其实赛场上也想到了贪心涂色，不过没长手，越写越乱就没了）。将结果数组全部标记为零（未涂色），如果被涂色的数字能在k种颜色下被涂色，就记录好坐标及对应的数字扔到优先队列里（vector排个序也可，目的是防止同一个数字被涂上相同的颜色），不能被涂色的，需要记录下不能被涂色的数字的个数（非常重要，这破题的一大坑点）。接下来就只需要在去掉不能涂色的数字里的k倍个数里，按顺序涂色就好辣!

俺是一坨垃圾代码QWQ:

int main()
{
    fast;
    int t;
    cin >> t;
    while(t--)
    {
        int n, k;
        cin >> n >> k;
        vector<int> num(n + 1);
        vector<int> res(n + 1);
        map<int, int> mp;
        priority_queue<pair<int, int>> q;
        int cha = 0;
        for (int i = 0; i < n;i++)
        {
            cin >> num[i];
            mp[num[i]]++;
            if(mp[num[i]]<=k)
            {
                q.push(make_pair(num[i], i));
            }
            else
                cha++;
        }
        for (int i = 1,color=1; i <= ((n-cha) / k) * k;i++)
        {
            res[q.top().second] = color;
            color++;
            q.pop();
            if(color>k)
                color = 1;
        }
        for (int i = 0; i < n;i++)
            cout << res[i] << " ";
        cout << endl;
    }
    return 0;
}
````
## Interesting Story（cf）
---
### 链接：
https://codeforces.com/contest/1551/problem/C
### 思路：
这题蛮有意思的，只有五个字母，我们可以用一个二维vector，i是第几个字母，j是第几行字符串的该字母的期望（当前字母的数量减去其他字母的数量），使用vector<int> arr[5];这种花式建法，在算结果时先将期望从大到小排个序，然后挨个加统计次数，直到加到小于等于零结束，最大的统计次数就是答案辣Σ(⊙▽⊙a... 
#### 俺是一坨垃圾代码QWQ:
```c++
int main()
{
    fast;
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        int mx = 0;
        cin >> n;
        string x;
        vector<int> arr[5];
        for (int i = 0; i < n;i++)
        {
            cin >> x;
            int ar[5] = {};
            for (int j = 0; j < x.size();j++)
            {
                ar[x[j] - 'a']++;
            }
            for (int j = 0; j < 5;j++)
            {
                arr[j].push_back(ar[j] - (x.size() - ar[j]));
            }
        }
        for (int i = 0; i < 5;i++)
        {
            sort(arr[i].rbegin(), arr[i].rend());
            int cnt = 0,now=0;
            for (int j = 0; j < n;j++)
            {
                if(now+arr[i][j]>0)
                {
                    cnt++;
                    now += arr[i][j];
                }
                else
                    break;
            }
            mx = max(mx, cnt);
        }
        cout << mx << endl;
    }
}

Binary Decimal（cf）

链接：

https://codeforces.com/contest/1544/problem/A

思路：

虽然没有参赛资格，但我还是要做，想看看大佬们的a题长啥样。不得不说，这题挺有趣的，在经过自己手划拉几个数据后，惊讶地发现答案应该就是每一位的最大一位，太绝了。看了一眼别人的码，确实是这么一肥事。

俺是一坨垃圾代码QWQ:

int main()
{
    fast;
    int t;
    cin >> t;
    while(t--)
    {
        int x,res=0;
        cin >> x;
        while(x)
        {
            res = max(res, x % 10);
            x /= 10;
        }
        cout << res << endl;
    }
}

LR Constraints（at）

链接：

https://atcoder.jp/contests/arc124/tasks/arc124_a

思路：

这踏马是A题？我直接疑惑，四十分钟才想出来怎么做。题目比较抽象，大概就是第k位置如果是L则当前位置的i是最左侧的i，R同理是最右，统计所有的排列情况。其实就是当前位置能放几种卡片，然后然后乘法定律一乘就完了

俺是一坨垃圾代码QWQ:

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> v(n+1);
    vector<bool> vis(n+1);
    for (int i = 1; i <= k;i++)
    {
        char ch;
        int x;
        cin >> ch >> x;
        if(ch=='L')
        {
            vis[x] = 1;
            v[x] = 1;
            for (int j = x; j <= n;j++)
            {
                if(vis[j])
                    continue;
                else
                    v[j]++;
            }
        }
        else if(ch=='R')
        {
            vis[x] = 1;
            v[x] = 1;
            for (int j = x; j>=0;j--)
            {
                if(vis[j])
                    continue;
                else
                    v[j]++;
            }
        }
    }
    long long res = 1;
    for (int i = 1; i <= n;i++)
    {
        res = (res%MOD * v[i]%MOD) % MOD;
    }
    cout << res%MOD;
}

XOR Matching 2（at）

链接：

https://atcoder.jp/contests/arc124/tasks/arc124_b

思路：

a数组与b数组的值挨个异或，如果值相等就输出该值。先将两个数组去重，保证不会有相同的数字异或的值干扰结果。
将之后的异或值全部存入map中统计数量，如果大于等于数组长度，就代表该值能够被匹配。输出即可

俺是一坨垃圾代码QWQ:

int main()
{
    int n;
    cin>>n;
    vector<int>a(n);
    vector<int>b(n);
    map<int,int> lly;
    for (int i = 0; i < n;i++)
        cin >> a[i];
    
    for (int i = 0; i < n;i++)
        cin >> b[i];
    set<int> t(a.begin(),a.end());
    a.assign(t.begin(), t.end());
    set<int> t1(b.begin(),b.end());
    b.assign(t1.begin(), t1.end());
    if(a.size()!=b.size())
    {
        cout << 0;
        return 0;
    }
    for (int i = 0; i < a.size();i++)
    {
        for (int j = 0; j < a.size();j++)
        {
            lly[a[i] ^ b[j]]++;
        }
    }
    int cnt = 0;
    vector<int> res;
    for(auto i:lly)
    {
        if(i.second>=a.size())
        {
            cnt++;
            res.push_back(i.first);
        }
    }
    cout << cnt<<endl;
    for(auto i:res)
        cout << i << endl;
}

Arithmetic Array（cf）

链接：

https://codeforces.com/contest/1537/problem/A

思路：

加一起，小于n的话可以随便加1个数使平均值为1，大于等于n的加上和-n个0就好啦

俺是一坨垃圾代码QWQ:

int main()
{
    fast;
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin>>n;
        int res = 0, x;
        for (int i = 0; i < n;i++)
        {
            cin >> x;
            res += x;
        }
        if(res<n)
            cout << 1 << endl;
        else
        {
            if(res)
            cout << res-n<<endl;
        }
    }
}

Bad Boy（cf）

链接：

https://codeforces.com/contest/1537/problem/B

思路：

蕨了，为了使走的步数最大，当然是放在角落啦，输出两个对角就行了，不要太简单

俺是一坨垃圾代码QWQ:

int main()
{
    fast;
    int t;
    cin >> t;
    while(t--)
    {
        int n, m, i, j;
        cin >> n >> m >> i >> j;
        cout << 1 << " " << 1 << " " << n << " " <<m<<endl;
    }
    return 0;
}

Challenging Cliffs（cf）

链接：

https://codeforces.com/contest/1537/problem/C

思路：

先排好序，找到相邻差最小的两个数，放在两边，中间用第二个数右面的构造，再用第一个数左面的构造，这样困难值最高

俺是一坨垃圾代码QWQ:

int main()
{
    fast;
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        vector<int> hill(n);
        for (int i = 0; i < n;i++)
            cin >> hill[i];
        sort(hill.begin(), hill.end());
        if(n==2)
        {
            cout << hill[0] << " " << hill[1] << endl;
            continue;
        }
        int mn = (int)1e9,now=0;
        for (int i = 0;i<n-1;i++)
        {
            if(abs(hill[i]-hill[i+1])<mn)
            {
                mn = abs(hill[i] - hill[i + 1]);
                now = i;
                if(mn==0)
                    break;
            }
        }
        cout << hill[now+1] << " ";
        for (int i = now + 2; i < n;i++)
            cout << hill[i] << " ";
        for (int i = 0; i <=now;i++)
            cout << hill[i] << " ";
        cout << endl;
    }
}

D_Deleting_Divisors.（cf）

链接：

https://codeforces.com/contest/1537/problem/D

思路：

博弈题，经过推导可得出结论，先手拿奇数，后手必赢；先手拿奇数*偶数的偶数，先手必赢；先手拿偶数*偶数（2^n）,如果n为奇数后手胜，偶数先手胜

俺是一坨垃圾代码QWQ:

int bitset(int x)
{
    return x & -x;
}
int main()
{
    fast;
    int t;
    cin>>t;
    while(t--)
    {
        int x;
        cin >> x;
        if(x&1)
            cout << "Bob" << endl;

        else
        {
            if(x!=bitset(x))
                cout << "Alice" << endl;
            else
            {
                int now = 2,i;
                for (i = 1;;i++)
                {
                    if(now==x)
                        break;
                    now *= 2;
                }
                if(i&1)
                    cout << "Bob" << endl;
                else
                    cout << "Alice" << endl;
            }
        }
    }
}