2020-2021:teams:legal_string:jxm2001:动态规划_1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:动态规划_1 [2020/09/25 12:14] jxm2001 [算法练习] |
2020-2021:teams:legal_string:jxm2001:动态规划_1 [2021/01/28 20:37] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 295: | 行 295: | ||
| === 习题六 === | === 习题六 === | ||
| + | |||
| + | [[https://cometoj.com/contest/71/problem/D?problem_id=4019|Comet OJ-Contest #12 D题]] | ||
| == 题意 == | == 题意 == | ||
| 行 307: | 行 309: | ||
| $|x-y|\le m$ 等价于增量 $n-m\le d\le n+m$，考虑计算出 $d\le n+m$ 的值减去 $d\le n-m-1$ 的值即可。 | $|x-y|\le m$ 等价于增量 $n-m\le d\le n+m$，考虑计算出 $d\le n+m$ 的值减去 $d\le n-m-1$ 的值即可。 | ||
| + | |||
| + | 另外注意 $n-m\le 0$ 的情况需要特判防止 $\text{dp}$ 出错，由于 $|x-y|\le n$ 必成立，所以结果为 $0$。 | ||
| 搜索函数为 $f(pos,eq1,eq2,eq3)$。其中 $eq1$ 表示 $x$ 前缀是否与 $A$ 前缀相等，$eq2$ 表示 $y$ 前缀是否与 $B$ 前缀相等。 | 搜索函数为 $f(pos,eq1,eq2,eq3)$。其中 $eq1$ 表示 $x$ 前缀是否与 $A$ 前缀相等，$eq2$ 表示 $y$ 前缀是否与 $B$ 前缀相等。 | ||
| - | $eq3$ 表示 $d$ 前缀是否与上界相等，然后枚举每一位可能，使其满足约束 $x\opluse y=n$，直接转移即可。 | + | $eq3$ 表示 $d$ 前缀是否与上界相等，然后枚举每一位可能，使其满足约束 $x\oplus y=n$，直接转移即可。 |
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXL=64; | ||
| + | int A[MAXL],B[MAXL],N[MAXL],M[MAXL]; | ||
| + | LL dp[MAXL][2][2][2]; | ||
| + | void cal(LL x,int *X){ | ||
| + | _for(i,1,MAXL) | ||
| + | X[i]=0; | ||
| + | int pos=0; | ||
| + | while(x){ | ||
| + | X[++pos]=x&1; | ||
| + | x>>=1; | ||
| + | } | ||
| + | } | ||
| + | LL dfs(int pos,bool eq1,bool eq2,bool eq3){ | ||
| + | if(!pos)return 1; | ||
| + | if(~dp[pos][eq1][eq2][eq3])return dp[pos][eq1][eq2][eq3]; | ||
| + | LL ans=0; | ||
| + | _for(i,0,2){ | ||
| + | int x=i,y=i^N[pos]; | ||
| + | if((eq1&&x>A[pos])||(eq2&&y>B[pos])||(eq3&&((x>y)>M[pos+1]))) | ||
| + | continue; | ||
| + | ans+=dfs(pos-1,eq1&&x==A[pos],eq2&&y==B[pos],eq3&&(x>y)==M[pos+1]); | ||
| + | } | ||
| + | return dp[pos][eq1][eq2][eq3]=ans; | ||
| + | } | ||
| + | LL solve(LL m){ | ||
| + | mem(dp,-1); | ||
| + | cal(m,M); | ||
| + | return dfs(62,true,true,true); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int T=read_int(); | ||
| + | while(T--){ | ||
| + | LL a=read_LL(),b=read_LL(),n=read_LL(),m=read_LL(); | ||
| + | cal(a,A); | ||
| + | cal(b,B); | ||
| + | cal(n,N); | ||
| + | enter(solve(n+m)-((n-m>0)?solve(n-m-1):0)); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | === 习题七 === | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/CF908G|CF908G]] | ||
| + | |||
| + | == 题意 == | ||
| + | |||
| + | 定义 $S(x)$ 表示将 $x$ 的每个位从小到大重排后的值，例如 $S(3190)=0139,S(4312)=1234$。 | ||
| + | |||
| + | 给定 $1\le X\le 10^{700}$，求 | ||
| + | |||
| + | $$ | ||
| + | \sum_{i=1}^X S(i) | ||
| + | $$ | ||
| + | |||
| + | == 题解 == | ||
| + | |||
| + | 考虑按贡献计算，设 $f(i,j)$ 表示 $1\sim X$ 中满足 $S(x)$ 的第 $j$ 位等于 $i$ 的 $x$ 的个数，$n=\text{len}(X)$，于是 | ||
| + | |||
| + | $$ | ||
| + | ans=\sum_{i=1}^9i\sum_{j=1}^n f(i,j)10^{j-1}=\sum_{i=1}^{9}i\sum_{j=1}^n (g(i,j)-g(i+1,j))10^{j-1} | ||
| + | $$ | ||
| + | |||
| + | 其中 $g(i,j)=\sum_{k=i}^9f(i,k)$ 表示 $1\sim X$ 中满足 $S(x)$ 的第 $j$ 位大于等于 $i$ 的 $x$ 的个数。 | ||
| + | |||
| + | 不难发现 $g(i,j)$ 也等于 $1\sim X$ 中满足 $x$ 中至少有 $j$ 位大于等于 $i$ 的 $x$ 的个数，于是 | ||
| + | |||
| + | $$ | ||
| + | g(i,j)=\sum_{k=j}^n \text{dp}(i,k) | ||
| + | $$ | ||
| + | |||
| + | 其中 $\text{dp}(i,j)$ 表示 $1\sim X$ 中满足 $x$ 中有 $j$ 位大于等于 $i$ 的 $x$ 的个数，显然该值通过数位 $\text{DP}$ 即可计算。 | ||
| + | |||
| + | 时间复杂度 $O(100n^2)$。 | ||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXL=705,Mod=1e9+7; | ||
| + | char s[MAXL]; | ||
| + | int a[MAXL],dp[10][MAXL][MAXL][2],suf[11][MAXL]; | ||
| + | int dfs(int v,int pos,int cnt,bool eq){ | ||
| + | if(!pos||cnt<0)return cnt==0; | ||
| + | if(~dp[v][pos][cnt][eq])return dp[v][pos][cnt][eq]; | ||
| + | int ans=0,mv=eq?a[pos]:9; | ||
| + | _rep(i,0,mv) | ||
| + | ans=(ans+dfs(v,pos-1,cnt-(i>=v),eq&&(a[pos]==i)))%Mod; | ||
| + | return dp[v][pos][cnt][eq]=ans; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | mem(dp,-1); | ||
| + | scanf("%s",s+1); | ||
| + | int len=strlen(s+1); | ||
| + | for(int i=1,j=len;i<=len;i++,j--)a[i]=s[j]-'0'; | ||
| + | int ans=0; | ||
| + | _for(i,1,10)for(int j=len;j>=1;j--) | ||
| + | suf[i][j]=(suf[i][j+1]+dfs(i,len,j,true))%Mod; | ||
| + | _for(i,1,10){ | ||
| + | int p=1; | ||
| + | _rep(j,1,len){ | ||
| + | ans=(ans+1LL*i*p%Mod*(suf[i][j]-suf[i+1][j]+Mod)%Mod)%Mod; | ||
| + | p=10LL*p%Mod; | ||
| + | } | ||
| + | } | ||
| + | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/动态规划_1.1601007286.txt.gz · 最后更改: 2020/09/25 12:14 由 jxm2001
