第一题：数位dp;
但是怎么确定各个数位数字之和？
其实1e18和加起来也就19*9嘛， 枚举数字之和，最后dfs只需判断当前数数字之和是否=我们枚举的模数；
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int digit[20];
ll dp[20][200][2][200];
ll dfs(int dep, int yu, int f, int t, int now, int sum){
if(!dep) return !yu && sum == now;
if(sum > now || sum + dep * 9 < now)return 0;
if(dp[dep][yu][f][sum] != -1)return dp[dep][yu][f][sum];
int i = f ? digit[dep] : 9;
ll tmp = 0;
for(; i >= 0; i--) {
tmp += dfs(dep-1, (yu*10 + i) % now, f&(i == digit[dep]), i, now, sum+i);
}
return dp[dep][yu][f][sum] = tmp;
}
ll get(ll a){
int cnt = 0;
int now = 0;
while(a){
digit[++cnt] = a % 10;
a /= 10;
now += digit[cnt];
}
ll ans = 0;
for(int i = 1; i <= 9*cnt; i++){
memset(dp, -1, sizeof(dp));
ans += dfs(cnt, 0, 1, 0, i, 0);
}
return ans;
}
// 1000000 7000000000000
int main(){
int kk = clock();
ll L, R;
cin>>L>>R;
ll ans1 = get(L-1);
ll ans2 = get(R);
cout<<ans2-ans1<<endl;
int cc = clock();
//cout<<cc-kk;
}
在洛谷发现把顶界压掉跑的快了一倍，但在记忆化搜索时顶界了不能直接返回
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int digit[20];
ll dp[20][210][210];
ll dfs(int dep, int yu, int f, int t, int now, int sum){
if(!dep) return !yu && sum == now;
if(sum > now || sum + dep * 9 < now)return 0;
if(dp[dep][yu][sum] != -1 && !f)return dp[dep][yu][sum];
int i = f ? digit[dep] : 9;
ll tmp = 0;
for(; i >= 0; i--) {
tmp += dfs(dep-1, (yu*10 + i) % now, f&(i == digit[dep]), i, now, sum+i);
}
if(!f)dp[dep][yu][sum] = tmp;
return tmp;
}
ll get(ll a, int opt){
int cnt = 0;
int now = 0;
while(a){
digit[++cnt] = a % 10;
a /= 10;
now += digit[cnt];
}
ll ans = 0;
for(int i = 1; i <= 9*cnt; i++){
memset(dp, -1, sizeof(dp));
ans += dfs(cnt, 0, 1, 0, i, 0);
}
return ans;
}
// 99999 333
int main(){
//int kk=clock();
//freopen("count.in","r",stdin);
//freopen("count.out","w",stdout);
ll L, R;
cin>>L>>R;
ll ans2 = get(R, 2);
ll ans1 = get(L-1, 1);
//cout<<ans2<<" "<<ans1<<"LLLLLLLLL"<<endl;
cout<<ans2-ans1<<endl;
//int cc=clock();
//cout<<cc-kk;
}
// 123456789 123456789123456
第二题：又是期望推式子，真是一遇期望就die；
我们用 ci 表示从翻了i-1个正面到翻了i个正面的期望花费，di表示翻了i个正面的期望天数；
Ci = 2( Di-1 +1 ) - 1 + (1-p) * (2 * (Di-1 + 2) - 1) + (1 - p)^2 * ( 2 * ( Di-1 + 3) - 1 ) + …… + (1-p)^n * (2 * (Di-1 + n + 1) -1 )
上式分别表示翻了一次到i， 翻了2次到i， 注意前面不用×p, 因为我们定的状态最后一定了i；
Di = i/p 我们考虑我们现在在坐标为i的x轴上， 表示我们还要翻i个硬币，如果我们翻了，期望就是p*1, 相当于向左走一步， 如果没翻成功， 就是(1-p) * 0, 因为我们不会向右走；
我们设 x = Di-1
上式Ci = (2x+1)/p + 2(1-p)( 1 - (1-p) ^ n) /p - p*(1-p)^n+1*(2x+2n+1), 当n无限大时；
Ci趋近于 (2x-1)/p + (1-p)/p^2 带入x 的Ci = 2*i/p/p + 1/p;
最后答案就是C1 + C2 + C3 +C4 +…… + Ck
#include<bits/stdc++.h> using namespace std; int main(){ freopen("coin.in","r",stdin); freopen("coin.out","w",stdout); int T; scanf("%d", &T); while(T--){ int k;double p; scanf("%d%lf",&k,&p); double tim = 1/p; double ans = (k+1)*1.0/p*tim - tim; printf("%.3lf %.3lf ", tim, ans); } }
第三题：dp套dp, 求LIS的nlog 的方式f[i]表示长度为i的LIS结尾数是什么， f一定是单增且无重复的；
我们用dp[i][sta][nwsta] 表示我们考虑了前i个数,已经选了sta，nwsta表示f数组中那些数出现过，但是2^15 * 2^15 空间不够；
我们把sta, nwsta压成三进制的，然后再优化一下，后面又不会了，以下是std;
#include <cstdio> const int MAXN = 22, MAXS = 15555555; int a[MAXN], b[MAXN], c[MAXN], d[MAXN], pre[MAXN], pow[MAXN], f[MAXS]; int main() { freopen("sword.in", "r", stdin); freopen("sword.out", "w", stdout); int n, m, ans = 0; scanf("%d%d", &n, &m); pow[0] = 1; for (int i = 0; i < n; ++i) { pow[i + 1] = pow[i] * 3; pre[i] = n; } for (int i = 1; i <= m; ++i) { scanf("%d", &a[i]); b[--a[i]] = i; if (i > 1) pre[a[i]] = a[i - 1]; } a[m + 1] = n; f[0] = c[n] = 1; for (int i = 0; i < pow[n]; ++i) if (f[i]) { int cnt = 0, k = 1, pos = 0; for (int j = d[0] = 0, t = i; j < n; ++j, t /= 3) if (c[j] = t % 3) { ++cnt; if (b[j] > pos) pos = b[j]; if (c[j] == 1) d[++d[0]] = j; } d[d[0] + 1] = n; if (cnt == n) ans += f[i]; for (int j = 0; j < n; ++j) if (!c[j] && c[pre[j]]) { bool t = true; for (; j > d[k]; ++k); for (int l = pos + 1; t && l <= m + 1 && l <= k; ++l) if (a[l] > j) t = false; if (t) f[i + pow[j] + (k > d[0] ? 0 : pow[d[k]])] += f[i]; } } printf("%d ", ans); return 0; }