2019.10.12

· · 个人记录

自闭了

T1:

秦师兄除了热衷于游戏开发，平时就爱好打打牌，中学时代外出比赛时就喜欢跟女生打牌， 并且经常不留痕迹地打赢牌打输，以至于机房小伙伴们都亲切地称他为“情愿输”，最近师兄 迷上了风靡全球的德州扑克。

德州扑克是一款风靡全球的扑克游戏。德州扑克一共有 52 张牌，没有王牌。每个玩家分 两张牌作为“底牌”，五张由荷官陆续朝上发出的作为公共牌。 摊牌阶段比大小的规则是，用自己的 2 张底牌和 5 张公共牌结合在一起，选出 5 张牌，不 论手中的牌使用几张（甚至可以不用手中的底牌），凑成最大的成牌，跟其他玩家比大小。比 牌先比牌型，大的牌型大于小的牌型

在这里我们简化了德克萨斯扑克的规则，消除花色对牌型的影响。

这里我们把牌型一般分 为 7 种，从大到小为：

1.四条：有四张同一点数的牌。 如：4 4 4 4 9

2.葫芦：三张同一点数的牌，加一对其他点数的牌。 如：3 3 3 10 10

3.顺子：五张顺连的牌。 如：5 4 3 2 A （此牌型为最小的顺子）

4.三条：仅有三张同一点数的牌，其余两张点数不同。 如：9 9 9 5 3

5 两对：两张相同点数的牌，加另外两张相同点数的牌。 如：K K 5 5 2

6.一对：仅有两张相同点数的牌。 如：10 10 9 4 2

7.高牌：不符合上面任何一种牌型的牌型，由单牌且不连续不同花的组成，以点数决定大 小。 如：A 10 9 5 3

若两个牌牌型相同，则比较点数，点数比较为从两副牌最大的牌到最小的牌依次开始比较 大小，若出现某张牌大于对手的牌，则获胜。如 A Q 8 8 3 和 A K 8 3 3，先比较最大的，两幅 都是 A，继续比较次大的，K>Q，则第二副牌获胜。

（注：通常情况下，点数比大小的方案为 A>K>Q>J>10>9>8>7>6>5>4>3>2，除了顺 子 5 4 3 2 A 中 A 作为比 2 还要小的值，顺子只能是 A,K,Q,J,10,9,8,7,6,5,4,3,2,A 该顺序中任意相 邻两张牌）

现在秦师兄拿到了自己的 2 张底牌和 5 张公共牌，他想问你可以凑成的最大的成牌是哪 5 张，并按照从大到小的顺序输出

SB模拟!!!,调了1.5h,这场直接炸了

思路:暴力枚举所有状态比较

code(没什么用,这种题就是练代码能力的):

#include<bits/stdc++.h>
using namespace std;
int a[10],ans[20],tmp[20],c1[20],c2[20];
char s[5];
int check=8,now;
bool flag5=1;
bool vis[10];
vector<int>num1[10],num2[10];
inline int change(char c)
{
    if(c=='A')return 14;
    if(c=='K')return 13;
    if(c=='Q')return 12;
    if(c=='J')return 11;
    return 233333;
}
inline char rechange(int x)
{
    if(x==14||x==1)return 'A';
    if(x==13)return 'K';
    if(x==12)return 'Q';
    if(x==11)return 'J';
    return 'c';
}
inline bool cmp(int x,int y){return x>y;}
inline void compare()
{
    int tot=0;
    for(int i=1;i<=7;i++)if(vis[i])tmp[++tot]=a[i];
    sort(tmp+1,tmp+5+1,cmp);sort(ans+1,ans+5+1,cmp);
    memset(c1,0,sizeof(c1));
    for(int i=1;i<=5;i++)num1[i].clear(),num2[i].clear();
    for(int i=1;i<=5;i++)
    {
        c1[tmp[i]]++;
        if(tmp[i]==14)c1[1]++;
    }
    for(int i=2;i<=14;i++)if(c1[i])num1[c1[i]].push_back(i);
    memset(c2,0,sizeof(c2));
    for(int i=1;i<=5;i++)
    {
        c2[ans[i]]++;
        if(ans[i]==14)c2[1]++;
    }   
    for(int i=2;i<=14;i++)if(c2[i])num2[c2[i]].push_back(i);
    bool flag=0,flag1=0,flag2=0;
    int k1=7,k2=7;

    if(num1[4].size())k1=1,flag1=1;
    else if(num1[3].size()&&num1[2].size())k1=2,flag1=1;
    if(!flag1)
    {
        bool flag3=1;
        int cnt=0;
        for(int i=1;i<=14;i++)if(c1[i]>1)flag3=0;
        if(flag3)
        {
            for(int i=14;i;i--)
                if(c1[i])
                {
                    cnt++;
                    if(cnt==5){k1=3,flag1=1;break;}
                }
                else cnt=0;
        }
    }
    if(!flag1)
    {
        if(num1[3].size())k1=4,flag1=1;
        else if(num1[2].size()>=2)k1=5,flag1=1;
        else if(num1[2].size())k1=6,flag1=1;
    }
    if(!flag1)k1=7,flag1=1;

    if(num2[4].size())k2=1,flag2=1;
    else if(num2[3].size()&&num2[2].size())k2=2,flag2=1;
    if(!flag2)
    {
        bool flag3=1;
        int cnt=0;
        for(int i=1;i<=14;i++)if(c2[i]>1)flag3=0;
        if(flag3)
        {
            for(int i=14;i;i--)
                if(c2[i])
                {
                    cnt++;
                    if(cnt==5){k2=3,flag2=1;break;}
                }
                else cnt=0;
        }
    }
    if(!flag2)
    {
        if(num2[3].size())k2=4,flag2=1;
        if(num2[2].size()>=2)k2=5,flag2=1;
        else if(num2[2].size())k2=6,flag2=1;
    }
    if(!flag2)k2=7,flag2=1;
    bool flag4=1;
    if(k1<k2)flag=1;
    else if(k1==k2)
    {
        sort(tmp+1,tmp+5+1);sort(ans+1,ans+5+1);
        if(k1==3)
        {
            if((c1[13]&&c1[14])||(c2[13]&&c2[14]))flag4=0;
            for(int i=1;i<=5;i++)if(tmp[i]==14&&flag4)tmp[i]=1;
            for(int i=1;i<=5;i++)if(ans[i]==14&&flag4)ans[i]=1;
            sort(tmp+1,tmp+5+1,cmp);sort(ans+1,ans+5+1,cmp);
            for(int i=1;i<=5;i++)if(tmp[i]>ans[i]){flag=1;break;}
        }
        else for(int i=1;i<=5;i++)if(tmp[i]>ans[i]){flag=1;break;}
    }
    if(flag)
    {
        check=k1;flag5=flag4;
        for(int i=1;i<=5;i++)ans[i]=(tmp[i]==1)?14:tmp[i];
    }
    for(int i=1;i<=5;i++)ans[i]=(ans[i]==1)?14:ans[i];
}
void dfs(int dep)
{
    if(dep==6){compare();return;}
    for(int i=1;i<=7;i++)
    {
        if(vis[i])continue;
        vis[i]=1;dfs(dep+1);vis[i]=0;
    }
}
int main()
{   
    for(int i=1;i<=7;i++)
    {
        scanf("%s",s+1);
        if(s[1]>='A'&&s[1]<='Z')a[i]=change(s[1]);
        else
        {
            int now=1,res=0;
            while(s[now]>='0'&&s[now]<='9')res=res*10+s[now]-'0',now++;
            a[i]=res;
        }
    }
    dfs(1);
    //printf("check::%d\n",check);
    //vis[4]=vis[2]=vis[3]=vis[5]=vis[6]=1;compare();
    if(check==3)for(int i=1;i<=5;i++)if(ans[i]==14&&flag5)ans[i]=1;
    sort(ans+1,ans+5+1,cmp);
    for(int i=1;i<=5;i++)
        if(ans[i]<=10&&ans[i]!=1)cout<<ans[i]<<' ';
        else cout<<rechange(ans[i])<<' ';
    return 0;
}

T2:

秦师兄作为一个游戏专家，他最近迷上了一款帝国战争为主题的即时策略游戏。为了扩大 自己的疆域，秦师兄需要在自己建设的帝国内组建一支部队投入战斗。

秦师兄手下有n个士兵，每个士兵有一个战斗力a_i。他打算从中挑选出至少K个士兵组成一支部队，并在选出的士兵中挑选出一个作为队长。然而秦师兄并不关心部队的战斗力。他只希 望部队的混乱度最小。混乱度的定义为：所有士兵的战斗力与队长的战斗力之差的平方和。

秦师兄想知道最小的混乱度是多少。

右端点r,左端点l自然为r-K+1,考虑当前区间为[l,r],选的队长为x,则混乱度为:

\sum\limits_{i=l}^{r}{(a_i-a_x)} =\sum\limits_{i=l}^{r}a_i^2 \ +\sum\limits_{i=l}^{r}a_x^2\ -2*a_x*\sum\limits_{i=l}^{r}{a_i}

用两个前缀和维护a_i和a_i^2即可

考虑枚举右端点,贪心选取接近[l,r]区间平均值的数,这个可以二分O(Nlog^N)

考虑序列是单调不减的,因此平均值是单调的,所以队长的选取有决策单调性,双指针维护即可

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+10;
int n,K;
int a[maxn],sum1[maxn];
int ans=4253453345425343342;
int sum2[maxn];
inline int calc(int l,int r,int x){return sum2[r]-sum2[l-1]+K*a[x]*a[x]-2*a[x]*(sum1[r]-sum1[l-1]);}
signed main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    scanf("%lld%lld",&n,&K);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)sum1[i]=sum1[i-1]+a[i],sum2[i]=sum2[i-1]+a[i]*a[i];
    for(int i=K,j=1;i<=n;i++)
    {
        while(j<i-K+1)j++;
        while(calc(i-K+1,i,j)>=calc(i-K+1,i,j+1)&&j<i)j++;
        ans=min(ans,calc(i-K+1,i,j));
    }
    printf("%lld",ans);
    return 0;
}

T3:

别看秦师兄平时一副热爱打游戏的样子,但在信息学计数题上的造诣可谓是颇深，你看在这 次模拟赛中，他就除了这样一道计数题。

秦师兄觉得图论很有趣。因此有一个n个点的有向图，编号从 1 到n，所有边的长度都是 1。

秦师兄还想融合一些数论元素。因此 i 向 j 连边当且仅当 i 整除 j。请注意一个正整数必定 整除它自身，因而秦师兄允许了自环的存在。 秦师兄觉得还不够好，因为所有的正整数都整除 0。

于是她新建了一个编号为 0 的点，并 让 1−n 的所有点都向 0 连一条长度为 1 的边。

秦师兄现在很满意。她写下了下面 4 个问题交给你来解决。

  1. 求出从 1 到q1，且长度恰为 2 的路径个数。

  2. 求出从 1 到 0，且长度不大于q2的路径个数。

  3. 求出从 1 到 0，没有经过重复的点，且长度不大于q3的路径个数。

  4. 令一条路径的权值为它经过的所有的点的编号之和。求出 (问题 3.)中所有路径的权值 和。

所有问题的答案对 10^9 + 7 取模。秦师兄不希望你爆零，因此设置了部分分。请注意最后 的部分分设定。

每个测试点的问题 1、4 各占 20% 的分数，2、3 各占 30%的分数。 请保证你的输出文件完整（包含 4 个整数），否则不能得分。

依次解决每一问:

第一问:路径长度为2,中途只会经过一个点,这个点显然是q1的的约数,求出q1的约数个数即可,注意特判0,0的答案是n

O(\sqrt{N})

第二问:

设f[i][j]表示从i到0距离为j的方案数

f[i][j]+=f[k*i][j-1] O(N^2)

第三问:

设g[i][j]表示表示从i到0不经过自环,距离为j的方案数,h[i][j]表示表示表示从i到0不经过自环,距离为j的点权和

发现不走自环最多走log_2^N级别的路程,于是j的枚举边界为log_2^N

O(N(log_2^N)^2)

结合以上算法可以得到72pts

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
const int mod=1e9+7;
int n,q1,q2,q3,ans1,ans2,ans3,ans4;
int f[10100][10100],g[maxn][30],h[maxn][30];
signed main()
{
    scanf("%lld%lld%lld%lld",&n,&q1,&q2,&q3);
    //problem 1
    for(int i=1;i*i<=q1;i++)if(q1%i==0){ans1++;if(q1!=i*i)ans1++;}
    if(!q1)ans1=n;
    if(n>100000){printf("%lld 0 0 0",ans1);return 0;}
    //problem 2
    if(n<10000&&q2<=10000)
    {
        for(int i=1;i<=n;i++)f[i][1]=1;
        for(int j=2;j<=q2;j++)
            for(int i=1;i<=n;i++)
                for(int k=1;k*i<=n;k++)
                    f[i][j]=(f[i][j]+f[k*i][j-1])%mod;
        for(int i=0;i<=q2;i++)ans2=(ans2+f[1][i])%mod;
    }
    //problem 3/4
    int t=(int)log(n)+5;
    for(int i=1;i<=n;i++)g[i][1]=1,h[i][1]=i;
    for(int j=2;j<=min(q3,t+1);j++)
        for(int i=1;i<=n;i++)
            for(int k=2;k*i<=n;k++)
                g[i][j]=(g[i][j]+g[k*i][j-1])%mod,h[i][j]=((h[i][j]+h[k*i][j-1])%mod+g[k*i][j-1]*i%mod)%mod;
    for(int i=0;i<=min(t+1,q3);i++)ans3=(ans3+g[1][i])%mod,ans4=(ans4+h[1][i])%mod;
    printf("%lld %lld %lld %lld",ans1,ans2,ans3,ans4);
    return 0;
}

考虑用第三问的答案推出第二问的答案

设有一条从1到0,长为4k的路径,设第i个点出现了x_i次,那么这条路径延伸出的第二问路径即

根据插板法: $=\sum\limits_{i=k}^{q2}C_{i-1}^{k-1}

根据组合恒等式:

=C_q2^k

于是O(N(log_2^N)^2)解决了这个问题

以上做法能拿到84pts

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
const int mod=1e9+7;
int n,q1,q2,q3,ans1,ans2,ans3,ans4;
int C[35],inv[35];
int f[maxn][30],g[maxn][30];
signed main()
{
    scanf("%lld%lld%lld%lld",&n,&q1,&q2,&q3);
    //problem 1
    for(int i=1;i*i<=q1;i++)if(q1%i==0){ans1++;if(q1!=i*i)ans1++;}
    if(!q1)ans1=n;
    if(n>100000){printf("%lld 0 0 0",ans1);return 0;}
    //problem 3/4
    int t=(int)log(n)+10;
    for(int i=1;i<=n;i++)f[i][1]=1,g[i][1]=i;
    for(int j=2;j<=t;j++)
        for(int i=1;i<=n;i++)
            for(int k=2;k*i<=n;k++)
                f[i][j]=(f[i][j]+f[k*i][j-1])%mod,g[i][j]=((g[i][j]+g[k*i][j-1])%mod+f[k*i][j-1]*i%mod)%mod;
    for(int i=0;i<=min(t,q3);i++)ans3=(ans3+f[1][i])%mod,ans4=(ans4+g[1][i])%mod;
    //problem 2
    C[0]=inv[1]=1;
    for(int i=2;i<=t;i++)inv[i]=(mod-mod/i)%mod*inv[mod%i]%mod;
    for(int i=1;i<=t;i++)C[i]=C[i-1]*inv[i]%mod*(q2-i+1+mod)%mod;
    //for(int i=1;i<=t;i++)printf("test::%lld %lld\n",C[i],inv[i]);
    for(int i=1;i<=min(q2,t);i++)ans2=(ans2+f[1][i]*C[i]%mod)%mod; 
    printf("%lld %lld %lld %lld",ans1,ans2,ans3,ans4);
    return 0;
}

考虑正解:

考虑DP到i,那么i能到达的节点有1*i,2*i,3*i...(n/i)*i,将这些点重新编号,那么就是1,2,3...(n/i)

code: ``` #include<bits/stdc++.h> using namespace std; #define int long long const int maxn=1e5+10; const int maxm=1e7+50; const int mod=1e9+7; int n,q1,q2,q3,ans1,ans2,ans3,ans4,tot; int id[maxm],pos[maxn],C[30],inv[30]; int f[maxn][30],g[maxn][30]; signed main() { scanf("%lld%lld%lld%lld",&n,&q1,&q2,&q3); //problem 1 for(int i=1;i*i<=q1;i++)if(q1%i==0){ans1++;if(q1!=i*i){ans1++;}} if(!q1)ans1=n; //problem 3/4 int t=log2(n)+1; for(int l=1,d,r;l<=n;l=r+1)id[d=n/l]=++tot,pos[tot]=d,r=n/d; for(int i=1;i<=tot;i++)f[i][1]=1,g[i][1]=1; for(int j=1;j<t;j++) { for(int i=1;i<=tot;i++) { int x=pos[i]; for(int l=2,d,r;l<=x;l=r+1) { d=x/l,r=x/d; int len=r-l+1; f[i][j+1]=(f[i][j+1]+len*f[id[d]][j]%mod)%mod; g[i][j+1]=(g[i][j+1]+len*(l+r)/2%mod*g[id[d]][j]%mod+len*f[id[d]][j]%mod)%mod; } } } for(int i=1;i<=min(q3,t);i++)ans3=(ans3+f[1][i])%mod,ans4=(ans4+g[1][i])%mod; //problem 2 inv[1]=C[0]=1; for(int i=2;i<=t;i++)inv[i]=(mod-mod/i)%mod*inv[mod%i]%mod; for(int i=1;i<=t;i++)C[i]=C[i-1]*inv[i]%mod*(q2-i+1)%mod; for(int i=1;i<=t;i++)ans2=(ans2+C[i]*f[1][i])%mod; printf("%lld %lld %lld %lld",ans1,ans2,ans3,ans4); return 0; } ```