不怕失败的人比不失败的人强

第一题 乘除操作

题目意思：给定数字n,k 求最小的大于x且是k倍数的数

解题思路：首先我们可以发现最小的x且要大于n我们就需要查看n里面有多少个k
然后再加上一个就好了也就是除法中下取整之后乘回去

时间复杂度；o(1)

void solve()
{
    cin>>n>>k;
    int ans=n/k*k+k;
    cout<<ans<<endl;
    return ;
}

第二题 稍稍思考

题目意思： 给定你一个年份最近的下一个年份是多少可以满足和当前年份每一天的星期都是完全一样的

解题思路：这个题目咋一看似乎奇奇怪怪不知道如何下手,这个时候我们就需要深入思考题目的意思
我们可以发现要和当前年份的每一天日期完全一样的话必须属于同一种年份也就是平年对平年闰年对闰年
接着我们不妨思考每一天的日期都是一样的也就是我今年第一天是星期1对应的那一年也要是星期1，似乎就
可以来操作了,也就是不妨规定当前年份就是星期1,我们要找到和当前年份天数一样且第一天都是星期1的
直接简单模拟即可

时间复杂度；o(1)

// 注意闰年不是直接加28 因为会有72这种年份最后100 的时候并不是闰年
void solve()
{
    cin>>n;
    bool ok1=false;
    if(n%400==0||(n%4==0 and n%100!=0)){
        ok1=true;
    }// 判断当前的年份

    int ans=1;
    n++;
    while(n){

        bool ok=false;
        if(n%400==0||(n%4==0 and n%100!=0)){
            ans+=366;
            ok=true;
        }
        else ans+=365;

        ans%=7;
        if(ans==0) ans=7;
        if(ok == ok1 and ans==1){// 表示达到了目标
            cout<<n<<endl;
            return ;
        }
        n++;
    }
    return ;
}

第三题 简单公倍数

题目意思：给定序列1-n,对于a倍数可以选择这个点得到贡献p,倍数可以选择这个点得到贡献q
每个点只能算一次贡献(q||p||没有)

解题思路：也就是我们可以直接把a的倍数全部加上p，b的倍数全部加上q，再减去公共部分乘以最小的min(q,p)
就是最优解a,b公倍数是lcm(a,b),不要脑袋宕机和我一样直接写a*b

时间复杂度：o(1)

int lcm(int a,int b){
    return a/__gcd(a,b)*b;
}
void solve()
{
    cin>>n>>a>>b>>p>>q;
    int ans1=n/a;
    int ans2=n/b;
    int ans3=n/lcm(a,b);
    int res=ans1*p+ans2*q-ans3*min(q,p);
    cout<<res<<endl;
    return ;
}

第四题 矩阵快速幂

矩阵快速幂

题目意思：每一个f[i]=a*f[i-1]+b,f[0]=x然后不停的的嵌套

解题思路：这不就巧了吗这n的复杂度是1e18,我们明显发现是一个迭代的题并且无法直接推出答案这个时候就要使用
矩阵快速幂,就是如果每一个式子都可以由上一次的式子再满足系数固定的情况下推理出来那就是矩阵快速幂可以解决
的问题, 对于初始的时候是 {x,1} 我们依据前行乘后列--> 可以构造出来对面是
{
    {a,0},
    {b,0}
}
接着上板子即可

void solve()
{
    int a,b,x;
    cin>>a>>b>>n>>x;
    int f[N][N]={x,1};
    int A[N][N]={
        {a,0},
        {b,1}
    };
    auto mul = [&](int c[][N],int a[][N],int b[][N]){
       static int tmp[N][N];
       memset(tmp,0,sizeof tmp);
       for(int i=0;i<N;i++)
          for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)
                tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%mod;

        memcpy(c,tmp,sizeof tmp);
        return ;
    };

    while(n){
        if(n&1) mul(f,f,A);
        n>>=1;
        mul(A,A,A);
    }
    cout<<f[0][0]<<endl;

    return ;
}

第四题 概率dp+状态压缩+倒序dp

题目意思 ： n个人喜欢公主，给定每个人互相战斗的矩阵,每一回合你可以安排任意两个人互相battle
求最后你(1)号选手赢到最后的概率

解题思路：首先我们发现数据范围特别的小那么就考虑是不是需要使用状态状态压缩，那么我们如何定义状态
转移方程(不重不漏并且可以转移成为了核心)我们可以考虑定义的状态为当前需要战胜的人中j为擂主最后1获胜的
概率也就是倒序求dp;
那么也就是当前从01开始转移每一个人为擂主可以自己赢也可以下一个人赢之和就是总共的贡献

时间复杂度：o(2^n * n^2)

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

double w[N][N],dp[1<<N][N];
// 表示当前擂主是j需要挑战的集合为i最后获胜的是1
int n;

int main(){

    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>w[i][j];

    dp[0][1]=1;// 入口

    for(int i=1;i < 1<<n ;i++){

        for(int j=1;j<=n;j++)
            if(i&(1<<j-1)^1){// 表示当前几何里面没有j
                for(int k=1;k<=n;k++){// 表示当前集合里面有k
                    if(i>>(k-1)&1){
                        dp[i][j]=max(dp[i][j],w[j][k]*dp[i^(1<<k-1)][j]+w[k][j]*dp[i^(1<<k-1)][k]);                        
                    }
                }
            }
    }
    double ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,dp[((1<<n)-1)^(1<<i-1)][i]);
    cout<<fixed<<setprecision(7)<<ans<<endl;
    return 0;
}