2019 BUAA Summer Training 6 题解

Solved	A	B	C	D	E	F	G	H	I	J
8/10	Ø	O	.	O	O	O	Ø	O	.	Ø

O for passing during the contest
Ø for passing after the contest
! for attempted but failed
· for having not attempted yet

题目来源：2019牛客暑期多校训练营第十场

比赛链接

A

题目描述

有一个数列$a_i$，每次拿走一个元素$x_k$，不放回，当$\sum_k x_k>b$时立刻输掉，当$\sum_k x_k>a$时立刻获胜。问获胜的概率。

解题思路

$f[i][j]$为共选了$i$个数，总和为$j$的概率。通过背包很容易从“选到第$k$个数，共选了$i$个数，总和为$j$的概率”优化掉一个维度算出。

枚举最后选到的数字，删掉其对$f[i][j]$的贡献，计算完了再加回去即可。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 520
double f[N][N];
int x[N];
int n,a,b;
int main(){
    int i,j,k;
    scanf("%d%d%d",&n,&a,&b);
    for(i=1;i<=n;i++)scanf("%d",&x[i]);
    f[0][0]=1;
    for(k=1;k<=n;k++)
        for(i=k;i;i--)
            for(j=x[k];j<=a;j++)
                f[i][j]+=f[i-1][j-x[k]]*i/(n-i);
    double fz=0,fm=0;
    for(k=1;k<=n;k++){
        for(i=1;i<=n;i++)
            for(j=x[k];j<=a;j++)
                f[i][j]-=f[i-1][j-x[k]]*i/(n-i);
        for(i=0;i<n;i++)
            for(j=max(0,a-x[k]+1);j<=a;j++){
                fm+=f[i][j];
                if(j+x[k]<=b)fz+=f[i][j];
            }
        for(i=n;i;i--)
            for(j=x[k];j<=a;j++)
                f[i][j]+=f[i-1][j-x[k]]*i/(n-i);
    }
    printf("%.10f\n",fz/fm);
    return 0;
}

B

题目描述

斐波那契字符串，求第$n$到$n+10$个字符。

解题思路

分别处理每一个字符，不停递归到下标为$1$或$2$的情况。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int t;
char a[3][10]={"","COFFEE","CHICKEN"};
ll f[1010]={0,6,7};
void calc(ll res,int ind){
    if(ind<3){
        printf("%c",a[ind][res-1]);
        return;
    }
    if(res>f[ind-2])calc(res-f[ind-2],ind-1);
    else calc(res,ind-2);
}
int main(){
    int i,j;
    scanf("%d",&t);
    for(i=3;i<=58;i++)f[i]=f[i-1]+f[i-2];
    while(t--){
        int n;ll k;
        scanf("%d%lld",&n,&k);
        while(n>58)n-=2;
        ll sum=n>58?f[58]:f[n];
        for(j=0;j<10;j++){
            if(k>sum)break;
            calc(k,n);
            k++;
        }
        puts("");
    }
    return 0;
}

C

题目描述
解题思路
AC代码
点击
1
2

D

题目描述

韩信点兵？

解题思路

$ExCRT$板子。

AC代码

点击

def mul(a,b,mod):
    res = 0
    while(b>0):
        if(b%2==1):
            res = (res + a)%mod
        a = (a + a)%mod
        b //=2
    return res
 
gcd = 0
def exgcd(a, b):
    global gcd
    if (b == 0):
        gcd = a
        return 1,0
    x,y = exgcd(b,a%b)
    return y,x-a//b * y
 
 
def excrt(a,b,n):
    global gcd
 
    M = b[0]
    ans = a[0]
    x = 0
    for i in range(1,n):
        #print(M,b[i])
        x,y=exgcd(M, b[i])
        #print(x)
        B = b[i]
        c = (a[i] - ans % B + B) % B
        g = B // gcd
        x = mul(x, c // gcd, g)
        ans += x * M
        M *= g
        ans = (ans%M + M) % M
        #print(ans)
    return ans%M
 
def check(x,n,a,b):
    for i in range(n):
        if (x%b[i] != a[i]):
            return False
    return True
 
s = input().split()
n = int(s[0])
m = int(s[1])
a = []
b = []
for i in range(n):
    s = input().split()
    a.append(int(s[1]))
    b.append(int(s[0]))
 
now = excrt(a,b,n)
#print(now)
if (check(now,n,a,b)):
    if (now < m):
        print(now)
    else:
        print("he was probably lying")
else:
    print("he was definitely lying")

E

题目描述

希尔伯特排序。

解题思路

按题意模拟编号即可。

AC代码

点击

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include <vector>
#include <map>
#include <unordered_map>
using namespace std;
 
typedef long long ll;
const int ms = 1e6 + 10;
pair<ll, ll> pos[ms], val[ms];
ll cal(ll x, ll y, int k)
{
    if (k == 1)
    {
        if (x == 1 && y == 1) return 1;
        if (x == 1 && y == 2) return 4;
        if (x == 2 && y == 1) return 2;
        if (x == 2 && y == 2) return 3;
    }
    ll p = 1 << (k - 1);
    if (x > p&&y > p)
    {
        return p * p * 2 + cal(x - p, y - p, k - 1);
    }
    if (x > p&&y <= p)
    {
        return p * p + cal(x - p, y, k - 1);
    }
    if (x <= p && y <= p)
    {
        return p * p - cal(y, p - x + 1, k - 1) + 1;
    }
    y -= p;
    return p * p * 4 - cal(p - y + 1, x, k - 1) + 1;
}
int main()
{
    int n, k;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    /*for (int i = 1; i < 9; ++i)
    {
        for (int j = 1; j < 9; ++j)
        {
            printf("%d %d %lld\n", i, j, cal(i, j, 3));
        }
    }*/
    for (int i = 0; i < n; ++i)
    {
        cin >> pos[i].first >> pos[i].second;
        val[i].second = i;
        val[i].first = cal(pos[i].first, pos[i].second, k);
    }
     
    sort(val, val + n);
    for (int i = 0; i < n; ++i)
    {
        cout << pos[val[i].second].first << " " << pos[val[i].second].second << '\n';
    }
}

F

题目描述
解题思路
AC代码
点击
1
2

G

题目描述
给$n$个点，求一条把所有点分成两块，一边$\frac n2$个点的直线，使得距离这个直线最近的点到这条直线的距离最远。

解题思路
满足距离这个直线最近的点到这条直线的距离最远的直线，必定满足：它垂直于某两点连线，或者它平行于某两点连线。

很容易直观上理解，当直线两边各有一个点距离该直线相同时，能够最大化最小距离。假设某条直线两端最近的点$A,B$到直线的距离相等，且直线不为$AB$的垂直平分线，那么可以旋转这个直线使得最短距离增大。当然也有可能不能旋转，也即旋转会造成另一个点$C$到该直线的距离减小。于是$AC$平行或$BC$平行时，也可以最大化最小距离。

然后枚举斜率就完了。

AC代码
点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 310
int n;
double x[N],y[N],ans,d[N],k;
void calc(double k){
    int i;
    for(i=1;i<=n;i++)d[i]=(k*x[i]-y[i])/sqrt(1+k*k);
    sort(d+1,d+1+n);
    ans=max(ans,(d[n/2+1]-d[n/2])/2);
}
int main(){
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
            k=1.0*(y[j]-y[i])/(x[j]-x[i]),calc(k),
            k=-1/k,calc(k);
    printf("%.10f",ans);
    return 0;
}

H

题目描述

给一张图，判断是哪种六碳烷烃。

解题思路

直接根据度，叶子个数判断即可。

AC代码 - by qxforever

点击

#include <bits/stdc++.h>
using namespace std;
 
int g[12];
int f[7][7];
int cnt[9];
int T,n,m,u,v;
 
int check()
{
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=6;i++) cnt[g[i]]++;
    if(cnt[1]==4&&cnt[2]==1&&cnt[4]==1){
        return 0*printf("2,2-dimethylbutane\n");
    }
    if(cnt[1]==4&&cnt[3]==2) return 0*printf("2,3-dimethylbutane\n");
    if(cnt[1]==2&&cnt[2]==4) return 0*printf("n-hexane\n");
    int now;
    for(int i=1;i<=6;i++) if(g[i]==3) {now=i;break;}
    int c=0;
    for(int i=1;i<=6;i++){
        if(f[now][i]==1) c+=g[i];
    }
    if(c==5) return 0*printf("3-methylpentane\n");
    if(c==4) return 0*printf("2-methylpentane\n");
}
 
int main()
{
    cin >> T;
    while(T--){
        memset(g,0,sizeof(g));
        memset(f,0,sizeof(f));
        for(int i=0;i<5;i++){
            scanf("%d%d",&u,&v);
            g[u]++,g[v]++;
            f[u][v]=1,f[v][u]=1;
        }
        check();
    }
}

I

题目描述
解题思路
AC代码
点击
1
2

J

题目描述

把一堆木板切成$k$种高度，求切下来的最小面积。

解题思路

设$f[i][j]$表示砍了$i$次，到第$j$个的最小花费。于是有：$f[i][j]=min_{k=1}^{j-1}(f[i-1][k]+SumS_j-SumS_k-h_{k+1}(SumW_j-SumW_k)$，这是一个有决策单调性的转移方程，可以斜率优化，也可以分治处理。

（听说也可$wqs$二分，不会）

AC代码 - by qxforever

点击

#include <bits/stdc++.h>
#define f dp
using namespace std;
typedef long long ll;
const int maxn = 5e3+23;
ll dp[maxn][maxn],s[maxn],w[maxn];
int n,k;
struct T
{
    int w;
    int h;
    bool operator <(const T &a)
    {
        if(h!=a.h) return h<a.h;
        return w<a.w;
    }
}t[maxn];
 
inline ll cal(int i,int j,int k)
{
    return 1LL*dp[i-1][k]+(s[j]-s[k])-1LL*t[k+1].h*(w[j]-w[k]);
}
 
void solve(int k,int l,int r,int ql,int qr)
{
    if(l>r) return;
    int mid=(l+r)>>1,b=ql+1;
    for(int i=ql;i<mid&&i<=qr;i++)
        if(cal(k,mid,b)>cal(k,mid,i)) b=i;
    f[k][mid]=cal(k,mid,b);
    solve(k,l,mid-1,ql,b);
    solve(k,mid+1,r,b,qr);
}
 
int main()
{
    cin >> n >> k;
    for(int i=0;i<n;i++) scanf("%d%d",&t[i].w,&t[i].h);
    sort(t,t+n);
    s[0]=1LL*t[0].h*t[0].w,w[0]=t[0].w;
    for(int i=1;i<n;i++){
        s[i]=1LL*t[i].h*t[i].w+s[i-1];
        w[i]=t[i].w+w[i-1];
    }
    for(int i=0;i<n;i++) f[1][i]=s[i]-1LL*t[0].h*w[i];
    for(int i=2;i<=k;i++)
        solve(i,i-1,n-1,i-2,n-2);
    printf("%lld",f[k][n-1]);
}