Educational Codeforces Round 117 (Rated for Div. 2)(Educational Codeforces Round 117 (Rated for Div. 2))

比赛链接

A. Distance

题目要求找出一个\((0,0)\)与\((x,y)\)之间曼哈顿距离的中点。

先判断距离是否存在,即曼哈顿距离是否是奇数。如果存在,可以从原点出发,先横着走,再竖着走,构造出中点的位置。

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

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

signed main()
{
    int t;cin >> t;
    while(t--)
    {
        int x,y;
        cin >> x >> y;
        if((x+y)&1)
        {
            cout << "-1 -1" << endl;
            continue;
        }
        int p = (x+y)/2;
        if(p<=x){
            cout << p << " 0" << endl;
        }
        else
        {
            cout << x << " " << p-x << endl;
        }
    }

	return 0;
}

B. Special Permutation

题目给出一个长度为偶数的排列,给出a,b要求排列左半边的最小值是a,右半边的最大值是b。

先判断是否有解,如果b比一半多一的元素小或者a比一半多一的元素大,无解。如果a,b在相同的半边,也无解。

如果有解,可以确定a,b在不同的半边。采用构造的方法,将排列降序然后交换a,b(如果需要)即可。

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

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

int k[10004];

signed main()
{
    int t;cin >> t;
    while(t--)
    {
        int n;cin >> n;
        for(int i=1;i<=n;++i)
            k[i] = n-i+1;
        int a,b;cin >> a >> b;
        if(b<n/2||a>n/2+1||(a<=n/2&&b<=n/2)||(a>n/2&&b>n/2))
        {
            cout << -1 << endl;
            continue;
        }
        if(a<b) swap(k[n-a+1],k[n-b+1]);
        for(int i=1;i<n;++i)
            cout  << k[i] << " ";
        cout << k[n] << endl;
    }

	return 0;
}

C. Chat Ban

应该属于一道比较明显的二分题。

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

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

int k[10004];

signed main()
{
    int t;cin >> t;
    while(t--)
    {
        ll k,x;
        cin >> k >> x;
        ll l = 1,r = 2*k-1;
        while(l<r)
        {
            ll mid = (l+r) >> 1;
            bool ok = 1;
            if(mid<=k){
                ll emo = mid*(mid+1)/2;
                if(emo>=x) ok = 0;
            }
            else{
                ll emo = k*(k+1)/2+(mid-k)*(k-1+2*k-mid)/2;
                if(emo>=x) ok = 0;
            }
            if(ok) l = mid + 1;
            else r = mid;
            //cout << "l " << l << "r "<< r << endl;
        }
        cout << l << endl;
    }

	return 0;
}

D. X-Magic Pair

题目给出a,b,每一次可以选一个变成a-b的绝对值,问能不能变换出x。

考虑到每操作一次,一定会用结果替代大的那个数,不然就循环了。那么考虑直接减减减,但是如果一个数很大的话肯定会T。这个时候想到了取模。因为一直减到最后可以看成取模的效果,而如果在减的过程中出现了x,那x一定与大的那个数同余。于是不断取模就可以了,类似gcd。

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

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

int k[10004];

signed main()
{
    int t;cin >> t;
    while(t--)
    {
        ll a,b,x;
        cin >> a >> b >> x;
        while(1)
        {
            if(a<b) swap(a,b);
            if(a==x){
                cout << "YES" << endl;
                break;
            }
            if(b==0)
            {
                cout << "NO" << endl;
                break;
            }
            if(a<x){
                cout << "NO" << endl;
                break;
            }
            if(a%b==x%b)
            {
                cout << "YES" << endl;
                break;
            }
            a = a % b;
        }
    }

	return 0;
}

E. Messages(补题)

每个学生都有一个必读消息m和最多阅读置顶消息数k,问置顶哪几条消息使得必读消息被读的期望数最大。

假定选择的消息数固定为t,那么就可以算出选择每个消息对结果贡献的期望。对于每个学生{m,k},则消息m可以对结果多贡献min(1,k/t)。然后选择贡献最多的前t个消息就是消息数为t情况下的最优解。

由于k不超过20,则将t从1到20枚举,比较得出全局最优解。

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

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 200005;

int n;
struct M
{
    ll v;
    int id;
} mes[maxn];
bool cmp(M a,M b)
{
    return a.v > b.v;
}
int m[maxn];
int k[maxn];
double ans;
vector<int> ansv;

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;++i)
    {
        cin >> m[i] >> k[i];
    }
    for(int t=1;t<=20;++t)
    {
        for(int i=1;i<maxn;++i)
        {
            mes[i].v = 0;
            mes[i].id = i;
        }
        for(int i=1;i<=n;++i)
        {
            if(k[i]>=t) mes[m[i]].v += t;
            else mes[m[i]].v += k[i];
        }
        sort(mes+1,mes+maxn,cmp);
        vector<int> tmp;
        ll a = 0;
        for(int i=1;i<=t;++i)
        {
            a += mes[i].v;
            tmp.push_back(mes[i].id);
        }
        if((double)a/t>ans)
        {
            ans = (double)a/t;
            ansv = tmp;
        }
    }
    cout << ansv.size() << endl;
    for(int i=0;i<ansv.size()-1;++i)
        cout << ansv[i] << " ";
    cout << ansv[ansv.size()-1] << endl;

	return 0;
}

F. Armor and Weapons(补题)

一开始有装备集\(A=\{1\},B=\{1\}\)每次可以从中选出\(a_i,b_j\),并将\(a_i+b_j\)放进A或B中,对于一些给定的{\(a_i,b_j\)},可以放\(a_i+b_j+1\),问最少多少次能得到\(a_n,b_m\)。

看了题解以后恍然大悟。首先选择肯定要选两个集合中最大的划算。然后这个题相当于BFS,求从状态{1,1}到{n,m}的最短路。在题解中,为了优化时间复杂度,将每次搜索到的一层(即步数相同的节点)从右上到左下进行排序,剔除掉同一列中较小的点,保证每一层访问的结点数为\(O(m)\),这样最慢以\(O(\log m)\)的速度接近m,然后再以\(\frac{n}{m}\)的速度接近n,复杂度\(O(m) \times O(\log m + \frac{n}{m})=O(m\log m+n)\)。

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

#define ll long long
typedef pair<int,int> P;
const int maxn = 1000005;
const ll mod = 1e9+7;

int n,m,q;
set<P> s;
vector<P> v;

bool cmp(P a,P b)
{
    if(a.first==b.first)
        return a.second > b.second;
    else
        return a.first > b.first;
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m ;
    cin >> q;
    int x,y;
    for(int i=1;i<=q;++i)
    {
        cin >> x >> y;
        s.insert(make_pair(x,y));
    }

    int step = 0;
    v.push_back(make_pair(1,1));
    while(1)
    {
        if(v[0]==make_pair(n,m)) break;
        vector<P> tmp;
        for(auto k : v)
        {
            int sum = k.first + k.second;
            if(s.count(k)) sum++;

            tmp.push_back(make_pair(min(sum,n),k.second));
            tmp.push_back(make_pair(k.first,min(sum,m)));
        }

        sort(tmp.begin(),tmp.end(),cmp);
        int y = 0;
        vector<P> tmp2;
        for(auto k : tmp)
        {
            if(k.second>y)
            {
                y = k.second;
                tmp2.push_back(k);
            }
        }
        step++;
        v = tmp2;
        /*cout << "step " << step << endl;
        for(auto k : v)
        {
            cout << k.first << " " << k.second << endl;
        }*/
    }
    cout << step << endl;

	return 0;
}

G. Max Sum Array(补题)

题解太妙了,感觉有两个关键点。

  • 频率最大的数一定在两端,且它们对答案产生的贡献与除了两端之外其他的数的位置无关。
  • 如果有多个频率最大的数,它们一定都排列在两端,且它们对答案的总贡献与它们在两端排列的相对位置无关。

根据上述两点采用递归的思想来解。

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

#define ll long long
const int maxn = 1000005;
const ll mod = 1e9+7;

int n;
ll num[maxn];
ll fac[maxn];
ll ansp = 1;
ll ansv = 0;

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    fac[0] = fac[1] = 1;
    for(int i=2;i<maxn;++i)
        fac[i] = (fac[i-1] * i) % mod;
    int a;
    ll total = 0;
    for(int i=1;i<=n;++i)
    {
        cin >> a;
        num[a]++;
        total += a;
    }
    for(int i=maxn-1;i>=2;--i)
    {
        ansp = fac[num[i]] * fac[num[i]] % mod * ansp % mod;
        ansv = (ansv + num[i]*(total-num[i])%mod*(i-1)%mod)%mod;
        num[i-2] += num[i];
        total -= 2 * num[i];
    }
    ansp = ansp * fac[num[1]] % mod;
    cout << ansv << " " << ansp << endl;

	return 0;
}
————————

Game link

A. Distance

The problem requires finding the midpoint of Manhattan distance between \ ((0,0) \) and \ ((x, y) \).

First judge whether the distance exists, that is, whether the Manhattan distance is odd. If it exists, you can start from the origin, walk horizontally and then walk vertically to construct the position of the midpoint.

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

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

signed main()
{
    int t;cin >> t;
    while(t--)
    {
        int x,y;
        cin >> x >> y;
        if((x+y)&1)
        {
            cout << "-1 -1" << endl;
            continue;
        }
        int p = (x+y)/2;
        if(p<=x){
            cout << p << " 0" << endl;
        }
        else
        {
            cout << x << " " << p-x << endl;
        }
    }

	return 0;
}

B. Special Permutation

The problem is to give an arrangement with an even length. Given a and B, it is required that the minimum value of the left half of the arrangement is a and the maximum value of the right half is B.

First judge whether there is a solution. If B is smaller than half of the elements or a is larger than half of the elements, there is no solution. If a and B are on the same half, there is no solution.

If you have a solution, you can determine that a and B are on different halves. Using the method of construction, the arrangement is in descending order, and then exchange a and B (if necessary).

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

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

int k[10004];

signed main()
{
    int t;cin >> t;
    while(t--)
    {
        int n;cin >> n;
        for(int i=1;i<=n;++i)
            k[i] = n-i+1;
        int a,b;cin >> a >> b;
        if(b<n/2||a>n/2+1||(a<=n/2&&b<=n/2)||(a>n/2&&b>n/2))
        {
            cout << -1 << endl;
            continue;
        }
        if(a<b) swap(k[n-a+1],k[n-b+1]);
        for(int i=1;i<n;++i)
            cout  << k[i] << " ";
        cout << k[n] << endl;
    }

	return 0;
}

C. Chat Ban

It should belong to an obvious dichotomy.

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

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

int k[10004];

signed main()
{
    int t;cin >> t;
    while(t--)
    {
        ll k,x;
        cin >> k >> x;
        ll l = 1,r = 2*k-1;
        while(l<r)
        {
            ll mid = (l+r) >> 1;
            bool ok = 1;
            if(mid<=k){
                ll emo = mid*(mid+1)/2;
                if(emo>=x) ok = 0;
            }
            else{
                ll emo = k*(k+1)/2+(mid-k)*(k-1+2*k-mid)/2;
                if(emo>=x) ok = 0;
            }
            if(ok) l = mid + 1;
            else r = mid;
            //cout << "l " << l << "r "<< r << endl;
        }
        cout << l << endl;
    }

	return 0;
}

D. X-Magic Pair

The question gives a and B, and you can choose an absolute value of A-B at a time, and ask if you can transform X.

Considering that each operation must replace the large number with the result, otherwise it will loop. Then consider direct subtraction, but if a number is large, it will definitely be t. At this time, I thought of taking the mold. Because it can be regarded as the effect of modulus until the end. If x appears in the process of subtraction, X must be congruent with the large number. So keep taking the mold, similar to GCD.

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

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 1111;

int k[10004];

signed main()
{
    int t;cin >> t;
    while(t--)
    {
        ll a,b,x;
        cin >> a >> b >> x;
        while(1)
        {
            if(a<b) swap(a,b);
            if(a==x){
                cout << "YES" << endl;
                break;
            }
            if(b==0)
            {
                cout << "NO" << endl;
                break;
            }
            if(a<x){
                cout << "NO" << endl;
                break;
            }
            if(a%b==x%b)
            {
                cout << "YES" << endl;
                break;
            }
            a = a % b;
        }
    }

	return 0;
}

E. Messages(补题)

Each student has a required message M and the maximum number of top messages K. ask which top messages make the maximum expected number of required messages to be read.

Assuming that the number of selected messages is fixed as t, the expectation of the contribution of each selected message to the result can be calculated. For each student {m, K}, message M can contribute more min (1, K / T) to the result. Then select the first t messages that contribute the most, which is the optimal solution when the number of messages is t.

Since K does not exceed 20, t is enumerated from 1 to 20 and compared to obtain the global optimal solution.

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

#define ll long long
#define ld long double
const ld pi = acos(-1);
const int maxn = 200005;

int n;
struct M
{
    ll v;
    int id;
} mes[maxn];
bool cmp(M a,M b)
{
    return a.v > b.v;
}
int m[maxn];
int k[maxn];
double ans;
vector<int> ansv;

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;++i)
    {
        cin >> m[i] >> k[i];
    }
    for(int t=1;t<=20;++t)
    {
        for(int i=1;i<maxn;++i)
        {
            mes[i].v = 0;
            mes[i].id = i;
        }
        for(int i=1;i<=n;++i)
        {
            if(k[i]>=t) mes[m[i]].v += t;
            else mes[m[i]].v += k[i];
        }
        sort(mes+1,mes+maxn,cmp);
        vector<int> tmp;
        ll a = 0;
        for(int i=1;i<=t;++i)
        {
            a += mes[i].v;
            tmp.push_back(mes[i].id);
        }
        if((double)a/t>ans)
        {
            ans = (double)a/t;
            ansv = tmp;
        }
    }
    cout << ansv.size() << endl;
    for(int i=0;i<ansv.size()-1;++i)
        cout << ansv[i] << " ";
    cout << ansv[ansv.size()-1] << endl;

	return 0;
}

F. Armor and Weapons(补题)

At the beginning, there are equipment sets \ (a = \ {1 \}, B = \ {1 \} \) from which you can select \ (a_i, b_j \) each time, and put \ (a_i + b_j \) into a or B. for some given {\ (a_i, b_j \)}, you can put \ (a_i + b_j + 1 \) and ask how many times you can get \ (a_n, b_m \).

After reading the solution, it suddenly dawned on me. First, be sure to choose the most cost-effective of the two sets. Then this problem is equivalent to BFS, finding the shortest path from state {1,1} to {n, m}. In the problem solution, in order to optimize the time complexity, the layers (i.e. nodes with the same number of steps) searched each time are sorted from top right to bottom left, and the smaller points in the same column are eliminated to ensure that the number of nodes accessed by each layer is \ (O (M) \), so that the slowest speed is \ (O (\ log m) \) close to m, and then close to N at the speed of \ (\ frac {n}{m} \), and the complexity is \ (O (m) \ times o (\ log m + \ frac {n}) {m})=O(m\log m+n)\)。

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

#define ll long long
typedef pair<int,int> P;
const int maxn = 1000005;
const ll mod = 1e9+7;

int n,m,q;
set<P> s;
vector<P> v;

bool cmp(P a,P b)
{
    if(a.first==b.first)
        return a.second > b.second;
    else
        return a.first > b.first;
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m ;
    cin >> q;
    int x,y;
    for(int i=1;i<=q;++i)
    {
        cin >> x >> y;
        s.insert(make_pair(x,y));
    }

    int step = 0;
    v.push_back(make_pair(1,1));
    while(1)
    {
        if(v[0]==make_pair(n,m)) break;
        vector<P> tmp;
        for(auto k : v)
        {
            int sum = k.first + k.second;
            if(s.count(k)) sum++;

            tmp.push_back(make_pair(min(sum,n),k.second));
            tmp.push_back(make_pair(k.first,min(sum,m)));
        }

        sort(tmp.begin(),tmp.end(),cmp);
        int y = 0;
        vector<P> tmp2;
        for(auto k : tmp)
        {
            if(k.second>y)
            {
                y = k.second;
                tmp2.push_back(k);
            }
        }
        step++;
        v = tmp2;
        /*cout << "step " << step << endl;
        for(auto k : v)
        {
            cout << k.first << " " << k.second << endl;
        }*/
    }
    cout << step << endl;

	return 0;
}

G. Max Sum Array(补题)

The solution is wonderful. I feel there are two key points.

  • The number with the largest frequency must be at both ends, and their contribution to the answer is independent of the position of other numbers except at both ends.
  • If there are multiple numbers with the largest frequency, they must be arranged at both ends, and their total contribution to the answer is independent of their relative position at both ends.

According to the above two points, we use the idea of recursion to solve it.

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

#define ll long long
const int maxn = 1000005;
const ll mod = 1e9+7;

int n;
ll num[maxn];
ll fac[maxn];
ll ansp = 1;
ll ansv = 0;

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    fac[0] = fac[1] = 1;
    for(int i=2;i<maxn;++i)
        fac[i] = (fac[i-1] * i) % mod;
    int a;
    ll total = 0;
    for(int i=1;i<=n;++i)
    {
        cin >> a;
        num[a]++;
        total += a;
    }
    for(int i=maxn-1;i>=2;--i)
    {
        ansp = fac[num[i]] * fac[num[i]] % mod * ansp % mod;
        ansv = (ansv + num[i]*(total-num[i])%mod*(i-1)%mod)%mod;
        num[i-2] += num[i];
        total -= 2 * num[i];
    }
    ansp = ansp * fac[num[1]] % mod;
    cout << ansv << " " << ansp << endl;

	return 0;
}