比赛链接：Dashboard - 3.17 周赛 - Codeforces

B

水题

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n<=3)cout<<1;
    else cout<<n-2;
    return 0;
}

D

字符串模拟水题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;

int n,m;
string s[30];
map<string,pair<int,int>>mp;//映射的序号、有几个翻译
set<string>ppp;
int cnt=0;
string str[21][100005];
bool check[21][100005];
int cor[21],all[21];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>s[i],ppp.insert(s[i]);
    cin>>m;
    for(int i=0;i<m;i++)
    {
        string x,y;
        string flag;
        cin>>x>>y>>flag;
        
        if(ppp.find(x)==ppp.end())continue;

        if(mp[x].first==0)
        {
            mp[x].first=++cnt;
        }

        str[mp[x].first][++mp[x].second]=y;

        all[mp[x].first]++;

        if(flag=="correct")cor[mp[x].first]++;
    }

    long long cr=1,al=1;
    bool f=1;
    for(int i=0;i<n;i++)
    {
        if(mp[s[i]].second>1)f=0;
        cr*=cor[mp[s[i]].first];
        al*=all[mp[s[i]].first];
    }
    if(f==0)
    {
        cout<<cr<<" correct\n"<<al-cr<<" incorrect";
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            cout<<str[mp[s[i]].first][1]<<" ";
            if(cor[mp[s[i]].first]==0)f=0;
        }
        if(f)cout<<"\ncorrect";
        else cout<<"\nincorrect";
    }
    return 0;
}

H

题意：给定 $a,b,c,d$ ，其中 $d$ 可以分配给 $a,b,c$ ，求 $a^2+b^2+c^2+7\times min(a,b,c)$ 的最大值。

假设 $a\geq b\geq c$ ，若不考虑 $min(a,b,c)$ ，那么一定是将 $d$ 全部分配给 $a$ 使结果最大。

若考虑 $min(a,b,c)$ ，那么将 $d$ 同时分配给 $a$ 和 $c$ 可以使结果变大。假设分配 $k$ 给 $a$ ，且 $c$ 不大于 $b$ 。（若 $c=b$ 了，那么需要同时增加 $c$ 和 $b$ 才能改变最后一项，不优）那么此时增加的值为：
$$
delta=[(a+d-k)^2+b^2+(c+k)^2+7\times (c+k)]-[a^2+b^2+c^2+7\times c]
$$
化简后得到：
$$
delta=2k^2+(7-2a-2d+2c)k+2ad+d^2
$$
得到的是一个二次函数，分析可知当对称轴大于0时， $d\geq 4$ 时。因 $c$ 需小于 $b$ ，而当 $d\geq 4$ 时满足：$2\times \frac{2a+2d-2c-7}{4}\geq b-c=k$ ，故此时最大值即在 $k=0$ 时取到。若 $d<4$ ，直接枚举。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# include <bits/stdc++.h>

using namespace std;
typedef long long LL;
LL d;
LL a[4];

int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        cin >> a[1] >> a[2] >> a[3];
        cin >> d;

        sort(a + 1, a + 1 + 3, greater<LL>());

        if(d >= 4) 
        {
            cout << (a[1] + d) * (a[1] + d) + a[2] * a[2] + a[3] * a[3] + 7 * min(a[2] , a[3]) << '\n';
        }
        else
        {
            LL res = (a[1]) * (a[1]) + a[2] * a[2] + a[3] * a[3] + 7 * min(a[2] , a[3]);
            for(int i = 0; i <= d; i ++)
                for(int j = 0; j <= d; j ++)
                {
                    int k = d - i - j;
                    if(k>=0)
                    {
                        LL ans = (a[1] + i) * (a[1] + i) + (a[2] + j) * (a[2]+j) + (a[3]+k) * (a[3]+k) + 7 * min(a[1] + i, min(a[2] +j , a[3]+k));
                        if(ans > res)res = ans;
                    }
                }
            cout << res << '\n';
        }
    }
    return 0;
}

math

I

题意：一台电脑容量为 $c$ ，现在有 $n$ 个程序，每个程序下载需要容量 $d$ ，安装需要容量 $s$ ，每个程序在下载后安装时，占的容量会马上从 $d$ 转换成 $s$ 。问最多能下载多少个程序，并打印出下载顺序。

首先考虑对于两个程序 $d_1,s_1$ 与 $d_2,s_2$ ，若先安装第二个，那么需要满足：
$$
s_2+d_1\leq s_1+d_2
$$
即：
$$
d_2-s_2\geq d_1-s_1
$$
因此全部按照 $d-s$ 进行排序，此时选择顺序一定是按照这个顺序，因此可以线性背包解决。

考虑设状态为 $dp[i][j]$ ，第二位表示安装好程序后占用的空间。状态转移方程为：
$$
dp[i][j]=max(dp[i-1][j],dp[i-1][j-s[i]]+1)
$$
但是需注意限制条件：$c-(j-s[i])\geq d[i]$ ，因为第一步下载时要保证空间足够。

打印路径时从后往前一个一个对比从那个状态转移来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e4+5;

struct Node
{
	int d,s,id;
}a[MAXN];

int f[505][MAXN],n,V;

bool cmp(const Node a, const Node b)
{
    return (a.d - a.s) > (b.d - b.s);
}

int main()
{
	// freopen("1.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin>>n>>V;

    for(int i=1;i<=n;i++)
    {
        cin >> a[i].d >> a[i].s;
        a[i].id = i;
    }

    sort(a+1,a+n+1,cmp);
    memset(f,0,sizeof(f));

    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=0;j--)
        {
            f[i][j] = f[i-1][j];
            if(V-(j-a[i].s) < a[i].d) continue;
            if(j < a[i].s) continue;
            f[i][j] = max(f[i-1][j], f[i-1][j-a[i].s]+1);
        }
    }

    int Max = 0, v = 0;
    for(int i=0;i<=V;i++)
    {
        if(f[n][i] > Max)
        {
            Max = f[n][i];
            v = i;
        }

    }
    cout << f[n][v] << "\n";
    if(f[n][v] == 0)return 0;
    int q[MAXN],cnt = 0;
    for(int i=n;i>=1&&v>0;i--)
    {
        if(f[i][v] == f[i-1][v-a[i].s]+1 && v-a[i].s>=0)
        {
            q[++cnt] = a[i].id;
            v -= a[i].s;	
        }
    }

    for(int i=cnt;i>=1;i--)
    {
        cout << q[i] << " ";
    }
	cout<<endl;
	return 0;
}

greedy，dp

K

题意：有 $n$ 个人参加锦标赛（$n\leq 4096$），两两对决，赢家进入下一轮，输家直接淘汰。每个人有一个能力值，当能力值为 $a_i$ 的人与 $a_j$ 的人对决，赢得概率是 $\frac{a_i}{a_i+a_j}$。若人数不是2的幂次，首先进行一次预选淘汰一部分人使总人数为2的幂次再进行正式比赛。现请求出一种初始对决的位置安排，使1号获胜的概率最大，输出获胜概率。

好恶心的dp

  1. 首先考虑如何安排位置能够使1号获胜概率最大。

    策略：除了1之外所有人从小到大排序，若需要淘汰 $x$ 个人，那么选能力最强的 $2x$ 个人进行预选。

    $proof$ ：若离1号越近的人能力越强，那么在越近的回合中1号获胜的概率就越小；若能力强的人离1号远，那么在更后的回合中1号才会遇到他，而此时能力强的人坚持到这个回合会乘上一个概率，那么1号赢的概率就越大。

    同时若需要预选，那么淘汰能力值强的一定是好的。

  2. 然后考虑如何得到最终的概率。

    可以得到第 $k$ 轮比赛中选手 $p$ 可能会与 $2^{k-1}$ 个人进行比赛，而这 $2^{k-1}$ 个人来自离 $p$ 相邻的块 $S$ 中；设状态为 $dp[p][k]$ 表示选手 $p$ 赢得第 $k$ 轮的概率，那么有状态转移方程：
    $$
    dp[p][k]=dp[p][k-1]\sum_{i\in S}\frac{a[p]}{a[p]+a[i]}dp[i][k-1]
    $$
    初始 $dp[p][0]=1$ 。

    需要注意若需要进行预选赛，那么把总人数当做 $2^x$ ，只是在进行过预选选上来的位置打上标记，若遍历到这点时，要分别计算这个位置包含的两个人的贡献。同时，需要预选的选手的 $dp[p][0]$ 设置为预选赛胜的概率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
using namespace std;

int n;
int s[5000];
int ns[5000];
double dp[5000][20];
bool d[5000];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i];
    sort(s+2,s+n+1);
    

    int lft=n-pow(2,int(log2(n)));
    n=pow(2,int(log2(n)));

    for(int i=n-lft+1;i<=n;i++)
    {
        d[i]=1;
    }

    for(int i=1;i<=n;i++)
    {
        if(d[i]==0)dp[i][0]=1;
        else
        {
            int num=(n-lft)+(i-(n-lft))*2-1;
            dp[num][0]=1.0*s[num]/(s[num]+s[num+1]);
            dp[num+1][0]=1.0*s[num+1]/(s[num]+s[num+1]);
        }
    }

    for(int k=1;k<=int(log2(n));k++)
    {
        for(int p=1;p<=n;p++)
        {
            int x;
            int pw=pow(2,k);

            if(p%pw==0)
            {
                x=1+(p-1)/pw*pw;
            }
            else
            {
                int tmp1=p-p/pw*pw;
                if(tmp1>pw/2) x=1+p/pw*pw;
                else x=pw/2+1+p/pw*pw;
            }
            

            for(int i=x;i<x+pow(2,k-1);i++)
            {
                if(d[p]==0 && d[i]==0)
                {
                    dp[p][k]+=dp[p][k-1] * s[p]/(s[p]+s[i]) * dp[i][k-1];
                }
                if(d[p]==0 && d[i]!=0)
                {
                    int num=(n-lft)+(i-(n-lft))*2-1;
                    dp[p][k]+=dp[p][k-1] * s[p]/(s[p]+s[num]) * dp[num][k-1];
                    dp[p][k]+=dp[p][k-1] * s[p]/(s[p]+s[num+1]) * dp[num+1][k-1];
                }
                if(d[p]!=0 && d[i]==0)
                {
                    int num=(n-lft)+(p-(n-lft))*2-1;
                    dp[num][k]+=dp[num][k-1] * s[num]/(s[num]+s[i]) * dp[i][k-1];
                    dp[num+1][k]+=dp[num+1][k-1] * s[num+1]/(s[num+1]+s[i]) * dp[i][k-1];
                }
                if(d[p]!=0 && d[i]!=0)
                {
                    int nump=(n-lft)+(p-(n-lft))*2-1;
                    int numi=(n-lft)+(i-(n-lft))*2-1;
                    dp[nump][k]+=dp[nump][k-1] * s[nump]/(s[nump]+s[numi]) * dp[numi][k-1];
                    dp[nump][k]+=dp[nump][k-1] * s[nump]/(s[nump]+s[numi+1]) * dp[numi+1][k-1];
                    dp[nump+1][k]+=dp[nump+1][k-1] * s[nump+1]/(s[nump+1]+s[numi]) * dp[numi][k-1];
                    dp[nump+1][k]+=dp[nump+1][k-1] * s[nump+1]/(s[nump+1]+s[numi+1]) * dp[numi+1][k-1];

                }
            }
        }
        
    }

    cout<<fixed<<setprecision(15)<<dp[1][int(log2(n))];
    return 0;
}

dp