比赛链接

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(补题)

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

1. 频率最大的数一定在两端，且它们对答案产生的贡献与除了两端之外其他的数的位置无关。

2. 如果有多个频率最大的数，它们一定都排列在两端，且它们对答案的总贡献与它们在两端排列的相对位置无关。

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

#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;
}