[数据结构与算法]2022/3/29 每日思维

代码源每日一题数位计算

我们可以十倍十倍的看，其实是有规律的比如1~9个数分别为:

a[1]=1,2,3...(9-1+1); 10~99:a[2]=1,2,3...(99-10+1); 100~999:a[3]=1,2,3...(999-100+1);

所以我们只要看看n是几位的比如n=238，那么他就等于a[1]+a[2]+(238-100+1)*(238-100+1+1)/2

后面的一项是等差数列求和；a数组也是等差数列，预处理一下就可以；最关键的地方是数大，要多次取模；

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
ll n,a[30];
int main(){
    ll nine=9;
    for(int i=1;i<=18;i++){
        if(i>1){
            ll tmp=nine/2;
            a[i]=(tmp%mod)*((1+nine)%mod)%mod;
        }
        else a[i]=nine*(1+nine)/2;
        nine*=10;
    }
    scanf("%lld",&n);
    ll ma=0,ten=10;
    for(int i=1;i<=18;i++){
        if(n/ten==0){
            ma=i-1;
            ten/=10;
            break;
        }
        ten*=10;
    }
    //cout<<a[ma]<<" "<<ten<<" "<<ma<<endl;
    ll ans=0;
    for(int i=1;i<=ma;i++) ans=(ans+a[i])%mod;
    ll qu=0;
    if((n-ten+1)%2==0){
        qu=(n-ten+1)/2;
        ans=(ans+((qu%mod)*((n-ten+2)%mod))%mod)%mod;
    }
    else{
        qu=(n-ten+2)/2;
        ans=(ans+((qu%mod)*((n-ten+1)%mod))%mod)%mod;
    }
    printf("%lld\n",ans);
	return 0;
}

Woodcutters

对于第i棵树来说，能往左边放就往左边放，不行就放右边；因为第i棵树只会影响到第i+1棵树，第i棵树往左边放了那下一颗树就有更高的几率放下(因为下一颗树会有两个选择放左或放右)，放到右边那么下一颗树就只能去试一试右边能不能放；

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
const ll inf=1e18;
ll n;
struct tree{
    ll x,h;
}a[100005];
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].h);
    a[n+1].x=1e18;a[n+1].h=1e18;
    ll las=a[1].x,ans=1;
    for(int i=2;i<=n;i++){
        if(a[i].x-a[i].h>las) ans++,las=a[i].x;
        else if(a[i].x+a[i].h<a[i+1].x) ans++,las=a[i].x+a[i].h;
        else las=a[i].x;
    }
    printf("%lld\n",ans);
	return 0;
}

A - Powered Addition

找到一个数组a中差值最大的那个数，就是要加的数，因为这个加上这个最大的差值，那么其他的差值也必会满足了；

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
const ll inf=1e18;
ll t,n,a[100005],bit[33];
int main(){
    //freopen("in.txt","r",stdin);
    bit[0]=1;
    for(int i=1;i<=32;i++) bit[i]=bit[i-1]*2;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        ll max1=-inf,maxx=-inf;
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            if(max1<a[i]){max1=a[i];continue;}
            else{
                maxx=max(max1-a[i],maxx);
            }
        }
        ll x=upper_bound(bit,bit+33,maxx)-bit;
        //cout<<bit[x]<<" bit"<<endl;
        printf("%lld\n",x);
    }
	return 0;
}