Educational Codeforces Round 117 A-E

A. Distance

题意：给出 $B$ 点坐标 $bx,by$，要输出 $C$ 的坐标使得 $C$ 到原点，$C$ 到 $B$ 点的曼哈顿距离都为 $B$ 到原点的曼哈顿距离的一半。

分奇偶讨论即可

int n, m;
void solve() {
    int x, y;
    cin >> x >> y;
    int dis =(abs(x) + abs(y));
    if(dis % 2 == 0){
        if(abs(x) % 2 == 0){
            cout << x/2 << ' ' << y/2 << '\n';
        }else{
            cout << floor(x/2.0) << ' ' << ceil(y/2.0) << '\n';
        }
    }else{
        cout << "-1 -1\n";
    }
}

B. Special Permutation

题意：要构造一个 $n$ 的排列（$n$ 为偶数），使得左半边最小值为 $a$，右半边最小值为 $b$

左边取 $a$ 和尽可能大的值，右边取 $b$ 和尽可能小的值，因为 $n$ 只给了100，可以 $n^2$ 暴力，省去了分类讨论的麻烦

int n, m, s[maxn];
bool vis[maxn];

void solve() {
    int a, b;
    cin >> n >> a >> b;
    for(int i=1;i<=n;i++) vis[i] = 0;
    s[1] = a; vis[a] = 1;
    for(int i=2;i<=n/2;i++){
        for(int j=n;j>=a;j--){
            if(!vis[j] && j != b){
                s[i] = j;
                vis[j] = 1;
                break;
            }
            if(j == a){
                cout << "-1\n";
                return;
            }
        }
    }
    for(int i=n/2+1;i<=n;i++){
        for(int j=b;j>=1;j--){
            if(!vis[j]){
                s[i] = j;
                vis[j] = 1;
                break;
            }
            if(j == 1){
                cout << "-1\n";
                return;
            }
        }
    }
    for(int i=1;i<n;i++) cout << s[i] << ' ';
    cout << s[n] << '\n';
}

C. Chat Ban

题意：你要依次发送 $2k-1$ 条消息，每条消息的字符个数分别为 1,2,3…k,k-1…2,1，输入达到 $x$ 个字符时就会终止，问能发出几条消息（发一半也算）

分类讨论写比较麻烦，写一个计算发送前 $x$ 条消息需要的字符的函数 $f(x)$，然后二分答案即可。

ll k, x;
ll cntk(ll s){
    if(s <= k) return s*(s+1)/2;
    else{
        ll r = (2*k-1-s+k) * (s-k) / 2;
        return k*(k+1)/2 + r;
    }
}

void solve() {
    cin >> k >> x;
    ll l = 1, r = 2*k-1;
    while(l < r){
        ll mid = (l+r) / 2;
        if(cntk(mid) >= x){
            r = mid;
        }else{
            l = mid+1;
        }
    }
    cout << l << '\n';
}

D. X-Magic Pair

题意：有两个数字 $a,b$，可以一次操作将 $a=|a-b|$ 或 $b=|a-b|$，问能否凑出 $x$（$a$ 或 $b$ 等于 $x$ 都可，可以进行任意次操作）

用手模拟一下可以发现，当前为 $a,b$（假设 $a\lt b$），不论怎么操作一定会经过 $a,b-a$ 这个状态

那么可以用类似辗转相除法的办法处理，如果 $x$ 在 $a,b$ 之间且 $x\equiv b\pmod a$，则可行，否则变化为 $b%a,a$ 继续；

记得判余数为 $0$ 的情况

bool judge(ll a, ll b, ll x){
    if(a == 0 || b == 0) return 0;
    if(x == a || x == b) return 1;
    if(x > b) return false;
    if(b%a == x%a) return 1;
    return judge(b%a, a, x);
}

void solve() {
    ll a, b, x;
    string sout[2] = {"NO", "YES"};
    cin >> a >> b >> x;
    if(a > b) swap(a, b);
    cout << sout[judge(a, b, x)] << '\n';
}

E. Messages

题意：有 $n$ 个人，每个人有一个期望读到的信 $m_i$，和他将读的信数 $k_i$，每个人都会在信堆里等概率地随机抽取 $k_i$ 封信阅读（不会取走）。现在你可以选择将哪些信放进信堆，使得读到想读信的人数期望最大。

第一反应想到了二分答案，因为确定了要放信的数量后比较容易judge

---

考虑怎么计算：选择一共放 $m$ 封信时的最大期望

对于每个人来说，它读到想要的信的概率是 $\frac{min(k_i, m)}{m}$，我们可以对于每一封信，统计想读它的人的 $\min(k_i, m)$ 之和（记为 $tot$），那么选这封信的收益就是 $\frac{tot}{m}$ ；

将信按照 $tot$ 排序后选取前 $m$ 封就可以计算出最大期望了

---

然后很显然地发现，答案不具有单调性，二份答案X

输入数据保证了 $k\le20$，用手模拟了一下极端情况，大胆猜测选 $20$ 封左右信时收益达到阈值，再多选收益一定更低

然后暴力跑了 $m\le50$ 的情况，就过了！

int n;
int a[maxn], b[maxn];
bool apr[maxn];
vector<int> all;
ll tot[maxn];
double ans[maxn];
 
bool cmpf(ll x, ll y){ return x > y;}
 
double judge(int m){
    for(int i=1;i<=n;i++){
        tot[a[i]] += min(b[i], m);
    }
    sort(tot+1, tot+200000+1, cmpf);
    ll fz = 0;
    for(int i=1;i<=m;i++){
        fz += tot[i];
    }
    int i = 1;
    while(tot[i] > 0) tot[i++] = 0;
    return fz * 1.0 / m;
}
 
void solve() {
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i] >> b[i];
        if(!apr[a[i]]){
            all.push_back(a[i]);
            apr[a[i]] = 1;
        }
    }
    int p = 1;
    for(int i=1;i<=min(50, n);i++){
        ans[i] = judge(i);
        if(ans[i] > ans[p]) p = i;
    }
    cout << p << '\n';
    for(int i=1;i<=n;i++) tot[a[i]] += min(b[i], p);
    vector<pair<int, int>> vp;
    for(int v:all) vp.push_back({tot[v], v});
    sort(vp.begin(), vp.end());
    bool fg = false;
    while(p--){
        if(fg) cout << ' ';
        else fg = 1;
        cout << vp.back().second;
        vp.pop_back();
    }
    cout << '\n';
}