牛客练习赛89题解

#include <bitsdc++.h>
using namespace std;
int ans = 10;
char a[10];
char b[] = "cocacola";
inline void dfs(int pos, int move)
{
    if(pos == 8)
        return (void)(ans = min(ans, move));
    if(a[pos] == b[pos])
        dfs(pos + 1, move);
    else
    {
        for (int i = pos + 1; i <= 7; i++)
            if(a[i] == b[pos])
            { 
                swap(a[i], a[pos]);
                dfs(pos + 1, move + 1);
                swap(a[i], a[pos]);
            }
    }
}
int main()
{
    scanf("%s", a);
    dfs(0, 0);
    cout << ans << endl;
    return 0;
}

首先要明确题干中有两个限制条件

1. 墙不能穿过。

2. 除墙和终点外其余地方均有一个豆子

结合上述两个限制条件和样例一，不难得出，若一个人能从起点到达终点，则它可以获得$n$个豆子。

所以原问题就可以等价于：判断这两个人”能否达到终点，且路径不重合“。

由于人只能向下走或向右走，假设在第一行没有墙。所以在起点开始时，一个人向下走，一个人向右走。

先看这个向下走的人，当他在向下走的过程中碰到第一堵墙时，他就必须向右走。我们称这堵墙为第一列的特殊墙，其位置记为$(1,y_1)$。再看向右走的人，不然发现只有当他进入第三列后不会遇见任何一堵墙它才可以到达终点，我们称这堵墙为第三列的特殊墙,其位置记为$(3,y_3)$。

画图容易发现，当第二列的起始墙（分别记为$(2,y_2)、(2,y^{'}_2)$）夹在其余两列的特殊墙中间，即满足

这两个人才能到达终点

#include <iostream>
using namespace std;
int n,m;
int y1,y2,yy2,y3; 
int main()
{
    ios::sync_with_stdio(0); 
    cin >> n >> m;
    y1 = y2 = 1e6 + 5;
    int x,y;
    for (int i = 1;i <= m;i++)
    {
        cin >> x >> y;
        if (x == 1) y1 = min(y1, y);
        if (x == 3) y3 = max(y3, y);
        if (x == 2) y2 = min(y2, y), yy2 = max(yy2, y);
    }
    if ((y1 - 1 > yy2) && (y3 + 1 < y2)) cout<<"YES";
    else cout<<"NO";
    return 0;
}

我们可以轻松地发现这道题是一道dp的题目

对于整张图来说，总共有2*n-2地度数，由于每一个点都至少有一个度数，我们就只剩下n-2的度数可以进行自由分配

我们将每个点看做一个点加上一条没有连上其他点的边，然后在更新的时候将所有点联向当前树的叶子节点上，然后根据其度数做一下背包就好了

f[i] 表示树上已经有i 个点的最佳权值

假设度数为i的贡献为a[i]，当一个节点插入的时候，会损失a[1]的价值，增加a[i-j+1]的价值，所以转移方程为

f[i]=max(f[i],f[j]+a[i-j+1]-a[1]),1<=j<=i;

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define LL long long
const int MAXN=1e4+7;
const LL INF=1e18;
LL f[MAXN];
int a[MAXN];
int main()
{


    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(f,0x80,sizeof f);
        int cnt=0;
        int x=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d",a+i);
        }
        f[0]=0;
        for(int i=1;i<=n-1;i++)
        {
            for(int j=i;j<=n-2;j++)
            {
                f[j]=std::max(f[j],f[j-i]+1ll*a[i+1]-a[1]);
            }
        }
        LL ans=f[n-2]+1ll*n*a[1];
        std::cout<<ans<<std::endl;

    }

    return 0;
}

给出两个结论

1. 对 $x$ 进行质因数分解，若只含有质因子$2$和$5$，则$x$是不循环小数，即$f(x)=0$
2. 否则，$x $是循环的，且循环开始于小数点后第$1+\max\{p_2,p_5\}$位，其中，$p_2$表示表示质因数分解形式下$2$的指数项，$𝑝_5$表示质因数分解下$5$的指数项。即$f( x )=1+\max\{p_2,p_5\}$

首先，类似前缀和的思路，只要能求解$1$~ $r$的答案，相减就可以得到$[𝑙,𝑟]$的答案。下面，我们考虑一种类似容斥的做法，记$𝑐𝑛𝑡[𝑥][𝑦]$表示$1$~ $r$中$2^𝑥\times5^𝑦$的倍数有多少个。初始时$𝑐𝑛𝑡[𝑥][𝑦]=\frac{r}{2^𝑥\times5^𝑦}$，然后我们按照$(𝑥+𝑦)$的值从大到小遍历，每遍历到一组$(𝑥,𝑦)$，就对所有的$𝑖\leqslant𝑥;𝑗\leqslant𝑦$进行一次$𝑐𝑛𝑡[𝑖][𝑗]−=𝑐𝑛𝑡[𝑥][𝑦]$。这样，当继续往下遍历的时候，就能保证$𝑐𝑛𝑡[𝑥][𝑦]$总是能“恰好”被$2^𝑥\times5^𝑦$整除的数的个数（而不会被更大的数整除）。在遍历的时候顺便统计答案即可。

总复杂度$𝑂(⁡𝑇(\log_210^{15}×log_510^{15})^2⁡)$，足够通过本题（尽管代入左式算出来会有$1.5×10^8$的运算量，但由于上式复杂度估的很粗，偏大，实际上跑得很快）。

当然也可以使用二维树状数组继续优化，达到更优的复杂度。

结论二略证：首先，若$𝑥$无$2,5$因子，由欧拉降幂，$10^ℎ\equiv1(\mod⁡ 𝑥)$一定有解（由欧拉降幂），换言之，存在一个解$ℎ$和一个$𝑘$使得$𝑘𝑥=10ℎ−1$，因此我们可以通分：$\frac1x=\frac{k}{kx}=\frac{k}{10^h-1}$，则可以得出这是一个循环节长度为$ℎ$，循环节内容为$𝑘$的小数。例如$\frac17=\frac{142857}{999999}$，至于为什么一个数除以形如$99\cdots\cdots99$的数字会得到循环节为分子的无限循环小数，这个难以言传，但实际写一下竖式运算就会发现这个结论很对？总之，综上，若$𝑥$无$2,5$因子，由上述推导，一定有循环且一定在小数点后1位开始，此时有$𝑓(𝑥)=1$。

而对于有$2,5$因子的情况，我们乘以$\max⁡\{𝑝_2,𝑝_5\}$个10可以得到一个新的小数（这个小数分子可能不为1，但这没有影响，因为上一段的推导可以看出，分子只影响循环节的内容，不影响长度和开始位置），而此时，我们得到的小数是从小数点后第1位开始循环的，因此原数$𝑥$的$𝑓(𝑥)=1+\max⁡\{𝑝2,𝑝5\}$。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
int T;
const ll inf=1e15,mod=998244353;
ll l,r,cnt[55][32],num[55][32];
ll solve(ll x){
    memset(cnt,0,sizeof(cnt));
    rep(i,0,50){
        rep(j,0,25){
            if(num[i][j])    cnt[i][j]=x/num[i][j];
        }
    }
    ll ret=0;
    per(k,0,75){
        rep(i,0,min(k,50)){
            int j=k-i;
            if(j>25)    continue;
            if(cnt[i][j]){
                ret+=((ll)(max(i,j)+1)*(cnt[i][j]-1));
                rep(ii,0,i){
                    rep(jj,0,j){
                        cnt[ii][jj]-=cnt[i][j];
                    }
                }
            }
        }
    }
    return ret;
}
int main(){
    rep(i,0,50){
        if(!i)    num[i][0]=1;
        else    num[i][0]=2ll*num[i-1][0];
        rep(j,1,25){
            num[i][j]=num[i][j-1]*5ll;
            if(num[i][j]>inf){
                break;
            }
        }
    }
    cin>>T;
    while(T--){
        scanf("%lld%lld",&l,&r);
        assert(l<=r&&l>0&&r>0&&r<=inf);
        printf("%lld\n",(solve(r)-solve(l-1))%mod);
    }
    return 0;
}