华东交通大学2019年ACM 双基 个人题解

H、谁在说谎

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
struct node {
    int id,r;
    bool operator<(const node&a)const {
        if(r==a.r) return id<a.id;
        else return r<a.r;
    }
}q[maxn];
int dp[maxn];//1~i内 若干个没有交集的区间的最大价值和
int main() {
    int n=read(),cnt=0;
    for(int i=1,x,y;i<=n;++i) {
        x=read()+1,y=n-read();
        if(x>y) continue;
        q[++cnt]={x,y};
    }
    sort(q+1,q+1+cnt);
    for(int i=1,j=1,flag=0;i<=n;++i) {
        dp[i]=dp[i-1];
        while(q[j].r<i) {
            ++j;
            if(j>cnt) {
                flag=1;
                break;
            }
        }
        int tmp=0;
        while(q[j].r==i) {
            if(q[j].id==q[j-1].id) ++tmp;
            else tmp=1;
            dp[i]=max(dp[i],dp[q[j].id-1]+min(tmp,i-q[j].id+1));
            ++j;
        }
        if(flag) {
            dp[n]=dp[i];
            break;
        }
    }
    printf("%d\n",n-dp[n]);
    return 0;
}

I、不要666

前言：数论的板子题，有题和这个一样但比这个更难的题吉哥系列故事——恨7不成妻
再附上我的题解
建议先看这个，这个题也要求满足条件的数的个数以及他们的和，只是要多求一个满足条件的数的平方和，看不懂怎么求平方和也不要紧，不影响求其它的结果。

MyCode:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+7,mod=1e9+7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll inf[20];
inline void init() {
    inf[1]=1;
    for(int i=2; i<=19; ++i)
        inf[i]=inf[i-1]*10%mod;
}
struct node {
    ll cnt,sum;
    node() {
        cnt=-1;
        sum=0;
    }
} dp[23][10][10];
int digit[23];
node dfs(int len,int p1,int p2,int limit) {//1.当前是几位数 2.数位和%6的值 3.数值%6的值
    node ans,tmp;
    if(!len) {
        ans.cnt=(p1&&p2);
        return ans;
    }
    if(!limit&&dp[len][p1][p2].cnt!=-1) return dp[len][p1][p2];
    int endi=(limit?digit[len]:9);
    ans.cnt=0;
    for(ll i=0; i<=endi; ++i) {
        if(i==6) continue;
        tmp=dfs(len-1,(p1+i)%6,(p2*10+i)%6,limit&&i==endi);
        ll x=i*inf[len]%mod;//当前最高位的值
        ans.cnt=(ans.cnt+tmp.cnt)%mod;
        ans.sum=(ans.sum+x*tmp.cnt%mod+tmp.sum)%mod;
    }
    if(!limit) dp[len][p1][p2]=ans;
    return ans;
}
ll solve(ll x) {
    int len=0;
    while(x) {
        digit[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,0,1).sum;
}
int main() {
    init();
    ll l,r;
    while(~scanf("%lld%lld",&l,&r))
        printf("%lld\n",(solve(r)-solve(l-1)+mod)%mod);
    return 0;
}