数位DP

AHOI2009 同类分布

先枚举各位数字之和作为模数再DP

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
 
int i,len,mod;
LL a,b;
int z[20];
LL mi[19],f[20][200][200];
 
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
 
IL LL read(){
    LL p=0,f=1; char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}
 
inline LL Mi(LL x,LL y,int MOD){
    LL p=x,t=1,Res=1;
    for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
    return Res;
}
 
IL LL Dfs(int pos,int lead,int limit,LL tot,LL Sum){
    reg LL i=0,up=0,sum=0,res=0;
    if (pos>len){
        if (Sum!=mod) return 0;
        return (!(tot%mod))?1:0;
    }
    res=(tot*(mi[len-pos+1]%mod))%mod;
    if (f[pos][res][Sum]!=-1 && !limit && !lead)    return f[pos][res][Sum];
    up=(limit)?z[len-pos+1]:9;
    for (i=0;i<=up;i++){
        if (!i && lead) sum+=Dfs(pos+1,1,limit&&(i==up),tot,Sum);
        else if (i && lead) sum+=Dfs(pos+1,0,limit&&(i==up),(tot<<3)+(tot<<1)+i,Sum+i);
        else sum+=Dfs(pos+1,0,limit&&(i==up),(tot<<3)+(tot<<1)+i,Sum+i);
    }
    return (!limit && !lead)?f[pos][res][Sum]=sum:sum;
}
 
IL LL Cal(LL x){
    reg LL i=0,ans=0;
    len=0;
    while (x){z[++len]=x%10;    x/=10;}
    for (i=1;i<=9*len;i++){
        memset(f,-1,sizeof(f));
        mod=i;
        ans+=Dfs(1,1,1,0,0);
    }
    return ans;
}
 
int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    a=read();   b=read();
    for (mi[1]=10,i=2;i<=18;i++)    mi[i]=mi[i-1]*10;
    cout<<Cal(b)-Cal(a-1)<<endl;
    return 0;
}

花神的数论题

和上面那个差不多,枚举1的数量

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define MOD 10000007
#define INF 0x3f3f3f3f
using namespace std;
 
LL n,len,l;
LL z[75],f[75][75];
 
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
 
IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}
 
IL LL Mi(LL x,LL y){
    LL p=x,t=1,Res=1;
    for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
    return Res;
}
 
IL LL Dfs(int pos,int pre,int lead,int limit,int s){
    LL sum=0,up=0,i=0;
    if (pos>len)    return (s==l);
    if (!lead && !limit && f[pos][s]!=-1)   return f[pos][s];
    up=(limit)?z[len-pos+1]:1;
    for (i=0;i<=up;i++){
        if (!i && lead) sum+=Dfs(pos+1,0,1,limit&&(i==up),s);
        else if (i && lead) sum+=Dfs(pos+1,i,0,limit&&(i==up),s+1);
        else sum+=Dfs(pos+1,i,0,limit&&(i==up),s+(i==1));
    }
    return (!lead && !limit)?f[pos][s]=sum:sum;
}
 
IL LL Cal(LL x){
    LL Ans=1,sum=0,i=0;
    len=0;
    while (x){
        z[++len]=x%2;   x/=2;
    }
    for (i=1;i<=len;i++){
        memset(f,-1,sizeof(f));
        l=i;
        sum=Dfs(1,0,1,1,0);
        Ans=(Ans*Mi(l,sum))%MOD;
    }
    return Ans;
}
 
int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    scanf("%lld",&n);
    cout<<Cal(n)<<endl;
    return 0;
}

枚举+数位DP式的写法,状态的描述和传统的题目有一点区别

补题的时候顺带写了两道双指针水题…

1. LOJ 2086：双指针

2. LOJ 2086：双指针+线段树

求所有至少k覆盖的区间组中，花费最少的区间组的花费（一组区间的花费定义为，最长区间的长度减去最短区间的长度）。

考虑将区间按长度排序，那么解肯定是连续取的一段。 注意如果 [i:j] 可，那么 [i:j+1]、[i-1:j] 一定都不是最优解。因此只需先枚举 i，然后 j 从 i 枚举到刚好至少 k 覆盖为止。维护一下数轴做区间+1和区间查最大就可以判断了。

复杂度 $O(n^2logn)$ 高了一点，考虑到上面其实有很多重复操作（i 枚举了很长一段，到 i+1 又从头开始了），其实从 i 变成 i+1 的时候应该至少从上次的 j 开始的（不然上次就不是刚好停），因此双指针同时枚举 ij 即可。复杂度 $O(nlogn)$。

代码如下：

#include <cstdio>
#include <climits>
#include <vector>
#include <algorithm>
#define IL inline
using namespace std;
constexpr int MN(1e6+7);
 
template <typename vint, typename sint, typename xint = int>
class STree
{
private:
	static constexpr xint ROOT = 1;
	struct Node
	{
		xint l, r;
		sint max, lza;
	} t[MN << 2];
	xint ll, rr, pos;
	vint vv;
#define li i<<1
#define ri i<<1|1
#define t_mid ((t[i].l+t[i].r) >> 1)
#define add_v(i, v) ({t[i].max += v, t[i].lza += v;})
 
#define pd(i) \
	({ \
		if (t[i].lza) \
		{ \
			add_v(li, t[i].lza); \
			add_v(ri, t[i].lza); \
			t[i].lza = 0; \
		} \
	})
 
	void build(const xint i, const xint l, const xint r)
	{
		t[i].l = l, t[i].r = r, t[i].lza = 0;
		if (l == r)
			t[i].max = 0;
		else
		{
			build(li, l, t_mid),
			build(ri, t_mid+1, r);
			t[i].max = max(t[li].max, t[ri].max);;
		}
	}
	void add(const xint i)
	{
		if (ll <= t[i].l && t[i].r <= rr) add_v(i, vv);
		else
		{
			pd(i);
			if (ll <= t_mid)
				add(li);
			if (rr > t_mid)
				add(ri);
			t[i].max = max(t[li].max, t[ri].max);;
		}
	}
 
public:
	IL void build(const xint l, const xint r)
	{
		build(ROOT, l, r);
	}
	IL void add(const xint l, const xint r, const vint v)
	{
		ll = l, rr = r, vv = v,
		add(ROOT);
	}
	IL sint gmax()
	{
		return t[ROOT].max;
	}
};
 
 
int tr[MN];
STree<int, int> st;
 
struct Node
{
	int l, r, len;
	IL bool operator <(const Node &o) const
	{
		return len < o.len;
	}
} a[MN];
vector<int> vals;
 
#define ID(x) lower_bound(vals.begin(), vals.end(), x)-vals.begin()
 
int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
 
	for (int i=0; i<n; ++i)
	{
		scanf("%d %d", &a[i].l, &a[i].r);
		a[i].len = a[i].r-a[i].l;
		vals.emplace_back(a[i].l);
		vals.emplace_back(a[i].r);
	}
	sort(a, a+n);
 
	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());
	for (int i=0; i<n; ++i)
		a[i].l = ID(a[i].l), a[i].r = ID(a[i].r);
 
	int ans = INT_MAX;
	st.build(0, vals.size()-1);
 
	int l=0, r=0;
	while (r < n)
	{
		st.add(a[r].l, a[r].r, 1);
		while (st.gmax() >= m)
		{
			ans = min(ans, a[r].len - a[l].len);
			st.add(a[l].l, a[l].r, -1);
			++l;
		}
		++r;
	}
	if (ans == INT_MAX)
		puts("-1");
	else
		printf("%d", ans);
 
	return 0;
}

周末填坑