第一场：

I（期望dp）：

题目：

我们有34种不同的牌，每种牌有四张牌。一共有136张牌。

起手我们有13张牌。每轮，我们摸一张，然后任意一张打出去。

我们保证起手的牌种，最多含有两张相同类型的牌。

我们目标为摸到牌后，手中达到由七种不同类型的牌组成的对子。

问：在最优决策下，达到目标状态的预期回合数

思路1：

记忆化搜索：

由不同的路径转移到一个相同的状态。我们每个手牌当前的状态，只需要算一次即可。

所有的单牌都是等价的。

状态表示：

集合：

f[i][j] i为卡池种剩余牌的数量，j为手中单牌的数量。

属性：概率

状态计算：

if(j!=1)

f[i][j]f[i][j]=(p1*(f(i-1,j)+1+p2*(f(i-1,j-2)+1)

else下一步我们如果抽到单牌。就到达目标状态了。因为我们是记忆化搜索。所以不同状态到达的目标值不同。

f[i][j]=(p1*(f(i-1,j)+1)+p2)

p1=(i-3*j)*inv(i) 抽到一张单牌，丢出去一张单牌。牌池-1，单牌没变
p2=3*j*inv(i) 抽到一张单牌并且，组成一个对子，牌池-1，单牌数量-2，算上刚摸到的牌

做:

1.初始化f一遍即可，因为记忆化搜索状态算一遍即可到达。

2.记录一下单牌的数量，然后记忆化搜索

3.如果当前状态被算过直径返回，如果j

4.因为需要取模，用到快速幂和逆元。计算状态

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int MOD = 1e9+7;
map<string,int>cnt;
int n;
int f[200][200];
int ji;

int qsm(int  x, int y)
{
    int ans=1, tmp = x;;
    while(y)
    {
        if(y&1) ans = ans * tmp % MOD;
        y >>= 1;
        tmp = tmp * tmp % MOD;
    }
    return ans;
}
int inv(int x)
{
    return qsm(x, MOD-2);
}

//i为卡池种剩余牌的数量，j为手中单牌的数量。
int dfs(int i,int j)
{ 

    if(f[i][j]!=-1)return f[i][j];

    if(j==0)return 0;

    int p1=(i-3*j)*inv(i)%MOD;//抽到一张单牌，丢出去一张单牌。
    int p2=3*j*inv(i)%MOD;//抽到一张单牌并且，组成一个对子。

    if(j==1)f[i][j]=(p1*(dfs(i-1,j)+1)%MOD+p2%MOD)%MOD;
    else f[i][j]=(p1*(dfs(i-1,j)+1)%MOD+p2*(dfs(i-1,j-2)+1))%MOD;

    return f[i][j];
}

void solved()
{
    cnt.clear();
    n=0;
    string s;
    cin>>s;
    for(int i=0;i<s.size();i+=2)
    {
        string te="";
        te+=s[i];
        te+=s[i+1];
        cnt[te]++;
    }

    for(auto x:cnt)
    {
        if(x.second==1)n++;
    }

    cout<<"Case #"<<++ji<<": "<<dfs(123,n)%MOD<<endl;

}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    memset(f,-1,sizeof f);//因为记忆化搜索，我们每次只需要算一遍所有状态即可

    while(t--)
    {
        solved();
    }
}

动态规划：

思路：

集合划分同上。

首先初始化边界，当j==1手中单牌数量只有一张时，

f[i][1]=(p1*f[i-1][1]+1)+p2

p2:下一次如果摸到能凑对，即到达目标

代码

    for(int i=1;i<=123;i++)
    {
        int p1=(i-3)*inv(i)%MOD;
        int p2=3*inv(i)%MOD;

        f[i][1]=(p1*(f[i-1][1]+1)%MOD+p2%MOD)%MOD;

    }

    for(int i=1;i<=123;i++)
        for(int j=3;j<=13;j+=2)
        {
            int p1=(i-3*j)*inv(i)%MOD;
            int p2=3*j*inv(i)%MOD;
            f[i][j]=(p1*(f[i-1][j]+1)%MOD+p2*(f[i-1][j-2]+1))%MOD;

        }

D：

题目：
给出墙壁内的圆，问你破坏的弧长最大。

思路：

证明可得：

当发射方向与圆心和发射点连线垂直时，弧长最大。

弧长为 弧度*r

代码

    while(t--)
    {
        double r;
        double x,y,d;
        cin>>r>>x>>y>>d;

        double u=sqrt(x*x+y*y);

        double a=acos((d+u)/r);
        double b=acos((d-u)/r);

        double c=pai-a-b;
        double ans=c*r;

        printf("%.12lf\n",ans);
    }

G：

题目：

给出一个n，问你1-n所有 数字，转化为字符串，问你字典序最大的数字是多少。

思路：

9开头肯定最大。

所以首先考虑比当前n少一位所有9组成的数字。

有一种可能n也是符合9开头的，两者比较求最大。

代码

signed main()
{
    string s;
    cin>>s;
    string ans;

    for(int i=0;i<s.size()-1;i++)
    {
        ans+='9';
    }

    if(ans>s)
        cout<<ans;
    else cout<<s;

    return 0;
}

A：

题目：

给出一些发电站和一些建筑。

目标为所有电站和建筑物联通在一起。

建筑物和电站存在一个半径，如果两者在半径内，不需要电线连接。

你有无限个电塔，电塔之间必须用电线相连。

问你最少花费多少电线，可以联通在一起。

思路：

我们假设所有的地方都建造一个电塔。

那么相交的所有建筑和发电站，构成一个区间。我们只需要连接区间与区间之间的电线。即可让所有的区间互通。

即在区间合并时，记录两个不相交区间的距离

代码

vector<PII>nums;
int main(){
    int n;
    cin>>n;

    while(n--)
    {
        int a,b;
        cin>>a>>b;
        nums.push_back({a-b,a+b});

    }

    sort(nums.begin(),nums.end());

    int ans=0;

    int st=nums[0].first,ed=nums[0].second;

    for(auto num:nums){

        if(num.first>ed){

            ans+=num.first-ed;
        st=num.first,ed=num.second;
        }
        else if(num.second>ed){
            ed=num.second;
        }
    }
    cout<<ans;
    return 0;
}

1