2020.7.19 排位赛（二）

2020/7/19 排位赛（二）

A Colliding Balls

solution

两个球碰撞的条件： xi * ui = yj * vj;
每个球在碰撞后会消失，一个球如果能和多个球碰撞，那么首先会和坐标值最小的碰撞。
用muiltiset。

code

/*******************
Problem:
Author:CXY1999
Status:Coding
Head Vision 2.1
*******************/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<set>
#include<cmath>
#include<queue>
#include<utility>
#include<algorithm>

#define pb push_back
#define BG begin()
#define ED end()
typedef long long LL;
using namespace std;
multiset<LL> s;

int main() {
    ios::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        LL l, r;
        cin >> l >> r;
        s.insert(l * r);
    }
    int Ans = 0;
    for (int i = 0; i < m; i++) {
        LL l, r;
        cin >> l >> r;
        if (s.count(l * r)) {
            multiset<LL>::iterator t = s.find(l * r);
            s.erase(t);
            Ans++;
        }
    }
    cout << Ans << endl;
}

B Awkwardness Minimization

solution

交叉着排，剩余的放两边。然而不会证明…
思路：可以先猜出一个解，然后看交换任意两个结果会不会更优/差。
以后遇到这类问题可以打表，打表，打表！

code

#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define MP make_pair
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
int T;
string str;
long long he(ll tail,ll size)
{
    long long ans=(1+tail)*size/2;
    return ans;
}
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>str;
        ll cntb=0,cntg=0;
        for(ll i=0; i<str.size(); i++)
        {
            if(str[i]=='b')
                cntb++;
            else
                cntg++;
        }
        long long ans=0;
        ll dis=abs(cntb-cntg);
        ll cnt=min(cntb,cntg);
        for(ll i=1; i<=cnt; i++)
        {
            ans+=(i*2-1)*((cnt-i+1)*2-1);
            //    数值        个数
        }
//		cout<<"temp:"<<ans<<endl;
        if(cntb!=cntg)
        {
            ll g0=he(cnt*2-1,cnt);
            ans+=g0;
            dis--;    
            ans+=g0*(dis/2)*2+cnt*he(dis/2,dis/2)*2;
            if(dis%2==1)
                ans+=g0+cnt*(dis/2+1);
//
//	//		ans+= (1+cnt*2-1)*cnt/2*dis+cnt*( 1+(dis/2) )
//			ans+= he(1+cnt*2-1,cnt)*dis+cnt*he((dis-1)/2,(dis-1)/2)*2;
//				//     累加和  * 个数     + 多增加cnt个数
//	//		ans+= he(1+cnt*2-1,cnt)*dis+cnt*(dis/2);
//			if(dis%2==0)
//				ans+=cnt+dis/2+1;
        }
        cout<<ans<<endl;
    }
    return 0;
}
/*
7
gb
bgg
bbgg
bbbggg
bbbgb
bbbggggggggggg
bbbgggg

//
1
2
6
19
6
139 ? ggggg bgbb ggggg

*/

C Special Graph Construction

solution

设顶点数为 n,则边数 m = n*3/2；
把每个连通块看成一个顶点的话，图是一个有 k 条边，k+1 个顶点的树。
- k>=1
  要想整个图是一个二分图，则去掉桥后，每个连通块是一个二分图。在树的叶子节点连通块内，有一个顶点的度数为2（因为去掉了桥边），其他顶点度数为3，显然不能构成二分图（二分图两边点集的度数和相等）。所以至少得去掉一个边，对于一个节点数大于1（即k>=1)的树来说，叶子节点至少为2，所以说至少得去掉两条边才能保证是二分图，即f(G)>=2.
- k=0
  直接输出样例
构造
构造图见官方题解

code

#include <bits/stdc++.h>

using namespace std;

int main() {
    int k;
    scanf("%d", &k);
    if (k == 0) {
        printf("6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
0
");
        return 0;
    }
    int n = 10 + (k - 1) * 6, m = n * 3 / 2;
    printf("%d %d
", n, m);
    for (int i = 1; i < 5; ++i) {
        printf("%d %d
", i, i + 1);
    }
    printf("1 5
");
    printf("1 3
2 4
");

    for (int i = 6; i < 10; ++i) {
        printf("%d %d
", i, i + 1);
    }
    printf("6 10
");
    printf("6 8
7 9
");

    int now = 5, n1 = 11;
    for (int i = 1; i < k; ++i) {
        printf("%d %d
", now, n1);
        for (int j = n1; j < n1 + 5; ++j) {
            printf("%d %d
", j, j + 1);
        }
        for (int j = 0; j < 3; ++j) {
            printf("%d %d
", n1 + j, n1 + j + 3);
        }
        now = n1 + 5;
        n1 = now + 1;
    }
    printf("%d %d
", now, 10);
    printf("2 2 9
");
    return 0;
}

D Minimum Variance

solution

要求: 方差的最小值 * n² = n * （平方的和） - （和的平方）.

正解
直接枚举平均值，然后计算方差的最小值，直接计算会超时，要用到扫描线。
看不懂的解法
先从最小平均值开始，不断迭代。其实原理和扫描线算法是一样的。

code

正解

#include <bits/stdc++.h>
using namespace std;
const int N = 50000 + 10;

int n, sz[N];
vector<int> vec[N];
vector< pair<int,int> > issues[N];
typedef long long LL;

LL sum = 0, sum2 = 0;
void rep(LL x, LL y) {
    sum2 -= x*x, sum -= x;
    sum2 += y*y, sum += y;
}

LL getAns() {
    return sum2 * n - sum * sum;
}
LL ans = 1e18;
LL tackle() {
    sum2 = 0, sum = 0;
    for (int i = 1; i <= n; i ++) {
        sum += vec[i][0];
        sum2 += 1LL * vec[i][0] * vec[i][0];
        // printf("# %lld
", vec[i][0]);
    }
   //  printf("ans = %lld
", getAns());
    ans = min(ans, getAns());
    for (int i = 1; i <= 50000; i ++) {
        for (auto p: issues[i]) {
            rep(p.first, p.second);
        }
        ans = min(ans, getAns());
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &sz[i]);
        for (int j = 0; j < sz[i]; j ++) {
            int x; scanf("%d", &x);
            vec[i].push_back(x);
        }
        sort(vec[i].begin(), vec[i].end());
    }
    // RIG
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j + 1 < vec[i].size(); j ++) {
            int l = vec[i][j], r = vec[i][j+1];
            if ((r - l) % 2 == 0) {
                issues[(l+r)/2].push_back(make_pair(vec[i][j], vec[i][j+1]));
            } else {
                issues[(l+r+1)/2].push_back(make_pair(vec[i][j], vec[i][j+1]));
            }
        }
    }
    tackle();
    // LEF
    for (int i = 1; i <= 50000; i ++) issues[i].clear();
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j + 1 < vec[i].size(); j ++) {
            int l = vec[i][j], r = vec[i][j+1];
            if ((r - l) % 2 == 0) {
                issues[(l+r)/2+1].push_back(make_pair(vec[i][j], vec[i][j+1]));
            } else {
                issues[(l+r+1)/2].push_back(make_pair(vec[i][j], vec[i][j+1]));
            }
        }
    }
    tackle();
    cout << ans << endl;
}

其他

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
const int N = 5e4 + 10;
vector<pii> T[N];

int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n; cin >> n;
    vector<int> v;
    ll d2 = 0, d = 0;
    for(int i = 0; i < n; i++) {
        int sz; cin >> sz;
        v.resize(sz);
        for(auto &e : v) cin >> e;
        sort(all(v));
        for(int i = 0; i + 1 < sz; i++) {
            int t = (v[i] + v[i + 1] + 1) / 2;
            T[t].emplace_back(v[i], v[i + 1]);
        }
        d2 += (ll) v[0] * v[0];
        d += v[0];
    }
    ll ans = n * d2 - d * d;
    for(int i = 0; i < N; i++) {
        if(T[i].empty()) continue;
        for(auto &e : T[i]) {
            d -= e.fi;
            d2 -= (ll) e.fi * e.fi;
            d += e.se;
            d2 += (ll) e.se * e.se;
        }
        ans = min(ans, n * d2 - d * d);
    }
    cout << ans << '
';
    return 0;
}

E Colorful Balloons (搁置)

要用到fft。

F Recover Array

solution

分成三个一组，先查询这一组的和 sum;

sum = 3 或 sum = 0 则这一组的值就全知道了（查询次数为1）；
sum = 1, 随机查询三个位置中的一个，设值为 x ；
- x = 1, 则其余两个值为0（查询次数为2）；
- x = 0，则还得再查询一次（查询次数为3）；
sum = 2, 与 sum = 1 同理。

可以证明这样能在9e4次查询内求出结果的概率非常大（我不会证qwq）。

code

#include <bits/stdc++.h>

using namespace std;
int n = 1e5;
int a[100010];

int ask(int l, int r) {
    int res;
    printf("1 %d %d
", l, r);
    fflush(stdout);
    scanf("%d", &res);
    return res;
}

int main() {
    srand(time(0));
    for (int i = 1; i + 2 <= n; i += 3) {
        int sum = ask(i, i + 2);
        if (sum == 3) {
            a[i] = a[i + 1] = a[i + 2] = 1;
        } else if (sum == 0) {
            a[i] = a[i + 1] = a[i + 2] = 0;
        } else {
            int r = rand() % 3;
            int r2 = (r + 1) % 3, r3 = (r + 2) % 3;
            a[i + r] = ask(i + r, i + r);
            if (a[i + r] && sum == 1) {
                a[i + r2] = a[i + r3] = 0;
            } else if (!a[i + r] && sum == 2) {
                a[i + r2] = a[i + r3] = 1;
            } else {
                a[i + r2] = ask(i + r2, i + r2);
                a[i + r3] = sum - a[i + r2] - a[i + r];
            }
        }
    }
    a[n] = ask(n, n);
    printf("2");
    for (int i = 1; i <= n; ++i) {
        printf(" %d", a[i]);
    }
    fflush(stdout);
}

G Train or Walk

solution

签到题

code

#include <bits/stdc++.h>
using namespace std;
int ps[20010];
int main() {
    int T; scanf("%d", &T);
    while(T--) {
        int n,a,b,c,d,p,q,y;
        scanf("%d%d%d%d%d%d%d%d", &n,&a,&b,&c,&d,&p,&q,&y);
        for(int i = 1; i<=n; ++i)
            scanf("%d", &ps[i]);
        int ans = abs(ps[b]-ps[a])*p;
        int tmp = abs(ps[c]-ps[a])*p;
        if(tmp>y) {
            tmp = 2e9;
        }else {
            tmp = y;
            tmp+=abs(ps[d]-ps[c])*q;
            tmp+=abs(ps[b]-ps[d])*p;
        }
        printf("%d
",min(ans,tmp));
    }
    return 0;

}

H Substring Matching (搁置)

本场比赛最难的题，不会。好像是动态规化+单调队列。

I Direct Segments (搁置)

好像是2-sat的板子

K Chef and Diamonds

一个非常不错的期望题，我一开始只想出来了一个O(n)的算法，超时，我想着优化，结果是一开始的思路就错了。

solution

n个巧克力，q个钻石。
考虑一个巧克力的位置，可能在第0个钻石后面第1个钻石前面，1个钻石后面第2个钻石前面…q个钻石后面，巧克力在q个钻石后面的概率为1/(q+1)，则总共n个钻石，在q个钻石后面的巧克力个数的期望是 n * （1/（q+1).
则去除q个钻石所需次数的期望是 n+q - n * (1/(q+1)).

code

#include <bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
int T;
int main() {
    scanf("%d", &T);
    while(T--){
        db n,q;
        scanf("%lf%lf", &n,&q);
        printf("%.9lf
",n+q-(q/(n+1)));
    }
}

L Analytics Load Jobs

solution

一个题意比较复杂的二分答案，读懂题意就能做了。

code

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,K,J;
int id[N],c[N][3];
bool pd(int lim) {
    int cntJ = 0, cntK;
    for(int i = 1; i <= id[0]; ++i) {
        ++cntJ; cntK = 0;
        int t1 = c[i][1],t2= c[i][2];
        if(t2&&lim<2) return 0;
        if(t1&&lim<1) return 0;
        while(t1||t2){
            ++cntK;
            int t = lim;
            while(t>=2&&t2) {
                t-=2; --t2;
            }
            while(t&&t1) {
                --t; --t1;
            }
        }
        if(cntK > K) {
            cntJ+=ceil((double)(cntK-K)/K);
        }
    }
    return cntJ<=J;
}
int main() {
    int T; scanf("%d", &T);
    while(T--) {
        memset(id, 0, sizeof(id));
        memset(c,0,sizeof(c));
        scanf("%d%d%d", &n,&K,&J);
        for(int i = 1; i<=n; ++i) {
            int x,y; scanf("%d%d", &x,&y);
            if(!id[x]) id[x] = ++id[0];
            ++c[id[x]][y];
        }
        int l = 1,r = 2*n,mid,ans;
        while(l<=r) {
            mid = (l+r)/2;
            if(pd(mid)){
                ans = mid; r = mid-1;
            }else l = mid+1;
        }
        printf("%d
",ans);
    }
}