UESTC暑假前集训-动态规划-解题报告

A - oy环游世界

A、给定n个点，求出从起点开始遍历到最后一个点的最短曼哈顿距离

状态压缩
n最多有17个点，可以考虑将17个点压缩到一个int里面，这个时候可以考虑一个状态$f _ {S,i}$，表示遍历了集合S后以i为终点的路径的最短的距离，状态转移方程为:
$$
f_{S,j} = min(f_{S,j},f_{S_j,j + dist(j,k)})
$$
$S_j$表示集合$S$除去点$j$后的集合

struct Point{
	ll x,y;

	ll operator - (const Point& a) const{
		return abs(x - a.x) + abs(y - a.y);
	}
}all[20];

ll n,s;
ll f[1<<20][20];

int main(){
	cin>>n>>s;
	mst(f,0x3f3f3f);
	for(ll i = 0;i < n;i++) cin>>all[i].x>>all[i].y;
	if(s - 1 != 0) swap(all[0],all[s - 1]);
    f[1][0] = 0;
    for(ll i = 1;i <= n;i++) f[1 << i | 1][i] = all[0] - all[i];
    for(ll i = 1;i < (1 << n);i++){
        for(ll j = 1;j < n;j++){
            if(i & (1 << j)){
                for(ll k = 1;k < n;k++){
                    if(i & (1 << k)){
                        f[i][j] = min(f[i][j],f[i ^ (1 << j)][k] + (all[j] - all[k]));
                    }
                }
            }
        }
    }
    ll ans = INF;
    for(int i = 1;i<n;i++) ans = min(ans,f[(1 << n) - 1][i]);
    cout<<ans<<endl;
    return 0;
}

B - 挖矿攻略

B、给定zh的nm的一片矿地，对应位置上有不同数量的黑矿和红矿，现在我作为一个*搬砖工**要帮zh修传送带让zhdg的收益最多，zhdg在北边和西边建了矿场，传送带要求直接通向矿场

二维动态规划
因为每块地的传送带只能直接通向矿场，那么如果当前的传送带向上的话那么它上面一个也是向上的，而左的话它左边一个也是向左的，那么考虑用每行每列的前缀和进行转移，时间复杂度$O(nm)$
$$
f_{i,j} = max(f_{i -1,j} + sum1[i][j],f_{i,j - 1} + sum2[i][j])
$$

int n,m;
int a[501][501],b[501][501],f[501][501];

int main(){
    cin>>n>>m;
    mst(a,0);
    mst(b,0);
    mst(f,0);
    for(int i = 1;i <= n;i++){
         for(int j = 1;j <= m;j++){
             cin>>a[i][j];
             a[i][j] += a[i][j - 1];
         }
    }
    for(int i = 1;i <= n;i++){
         for(int j = 1;j <= m;j++){
             cin>>b[i][j];
             b[i][j] += b[i - 1][j];
         }
     }
    for(int i = 1;i <= n;i++){
         for(int j = 1;j <= m;j++){
             f[i][j] = max(f[i - 1][j] + a[i][j],f[i][j - 1] + b[i][j]);
         }
   }
   cout<<f[n][m]<<endl;
   return 0;
}

C - 手办

C、给出一个长度为$ n $的序列，每个元素$a_i \in [114514,114521]$，要求从里面取出k个然后放回去使得连通块的数量最少

玄学动规
问题可以转化为拿走k个手办再放回去的混乱度
用一个状态$f[i][j][k][l]$表示当前到第$ i $个，前面拿走了$ j $个，当前所有的手办的种类集合$k$，最后一个手办种类为$ l $的时候的混乱度
拿走某个手办的时候，如果当前这个手办和最后一个一样，那么
$$
f[i][j + 1][k][l] = f[i - 1][j][k][l]
$$
否则直接拿走就是
$$
f[i][j + 1][k][l] = f[i - 1][j][k][l] + 1
$$
不拿走的话，转移就是：
$$
f[i][j][k | h[i]][h[i]] = f[i - 1][j][k][l] + 1
$$
时间复杂度$O(7*2^7nk)$

int n,kk,h[300],cnt = 0;
int f[101][101][1 << 10][10],vis[10];
int siz = 0;

void init(){
	siz = 0;
	mst(vis,0);
	for(int i = 0;i<=n;i++){
		for(int j = 0;j<=kk;j++){
			for(int k = 0;k<(1 << 10);k++){
				for(int l = 0;l < 10;l++){
					f[i][j][k][l] = INF;
				}
			}
		}
	}
}

int main(){
	while(cin>>n>>kk){
		cnt++;
		int ans = INF;
		init();
		int num = 0;
		if(n == 0 && kk == 0) break;
		for(int i = 1;i<= n;i++){
			cin>>h[i];
			h[i] -= 114513;
			vis[h[i]] = 1;
		}
		for(int i = 0;i < 10;i++){
			if(vis[i]){
				num ++;
				for(int j = 1;j <= n;j++){
					if(h[j] == i) h[j] = num;
				}
			}
		}
		f[0][0][0][0] = 0;
		siz = (1 << num) - 1;
		for(int i = 0;i < n;i++){
			for(int j = 0;j <= kk;j++){
				for(int k = 0;k <= siz;k++){
					for(int l = 0;l <= num;l++){
						if(f[i][j][k][l] != INF){
							f[i + 1][j + 1][k][l] = min(f[i + 1][j + 1][k][l],f[i][j][k][l]);
							f[i + 1][j][k|(1 << (h[i + 1] - 1))][h[i + 1]] = min(f[i + 1][j][k|(1 << h[i + 1] - 1)][h[i + 1]],f[i][j][k][l] + (h[i + 1] == l ? 0 : 1));
						}
					}
				}
			}
		}
		for(int i = 0;i <= kk;i++){
			for(int j = 0;j <= siz;j++){
				for(int k = 0;k <= num;k++){
					int numm = 0;
					for(int l = 0;l < num;l++){
						if((j & (1 << l)) == 0) numm ++;
					}
					ans = min(ans,f[n][i][j][k] + numm);
				}
			}
		}
		cout<<"Case "<<cnt<<": "<<ans<<endl<<endl;
	}
	return 0;
}

#####D - 序列

D、给出一个序列，要求输出序列中一个对称的先严格递增然后严格递减的最长的序列的长度

LIS

两次LIS，然后依次以某个元素为中点的最长的序列长度比较得出答案
时间复杂度$ O(2nlogn + n) $

int n,ans = -1,top1 = 1,top2 = 1;
int A[1000007];
int a[1000007],b[1000007];
int f1[1000007],f2[1000007];
int s1[1000007],s2[1000007];

int main(){
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>A[i];
        a[i] = A[i];
    }
    sort(A + 1,A + n + 1);
    for(int i = 1;i<=n;i++) a[i] = b[n - i + 1] = lower_bound(A + 1,A + n + 1,a[i]) - A;
    f1[1]= 1;
    s1[top1++] = a[1];
    for(int i = 2;i<=n;i++){
        if(a[i] > s1[top1 - 1]){
            f1[i] = top1;
            s1[top1++] = a[i];
        }
        else{
            int pos = lower_bound(s1 + 1,s1 + top1,a[i]) - s1;
            s1[pos] = a[i];
            f1[i] = pos;
        }
    }
    f2[1]= 1;
    s2[top2++] = b[1];
    for(int i = 2;i<=n;i++){
        if(b[i] > s2[top2 - 1]){
            f2[i] = top2;
            s2[top2++] = b[i];
        }
        else{
            int pos = lower_bound(s2 + 1,s2 + top2,b[i]) - s2;
            s2[pos] = b[i];
            f2[i] = pos;
        }
    }
    for(int i = 1;i<=n;i++){
        ans = max(ans,min(f1[i],f2[n - i + 1]));
    }
    cout<<2 * ans - 1<<endl;
    return 0;
}

E - 神

E、给定一个字符串$s$，要求将其分为长度为$k$的，$|s| / k$块后，对每块进行排序，然后输出最小的连通块的数量

分块动规？
一开始以为和C题差不多，后来想了一下其实不一样。。
先预处理一下，将每块左边连$ i $,右边连$ j $的时候的最小的块数求出来，然后用$f_{i,j,k}$表示到第$ i $块，以字母$ j $开头，字母$ k $结尾的最小连通块数，那么可以得到转移方程
$$
f_{i,j,k} = min\{f_{i - 1,j,m} + cnt_{i - 1,m,k} - 1\}
$$
这里$i,j,k,m$对应字母在字母表中的顺序
时间复杂度$O(26^3len + 26^2len/k)$

int T,k;
int len;
char s[1007];
int f[1007][26][26],cnt[1007][26][26];
bool vis[1007][26];

void init(){
	mst(f,0);
	mst(cnt,0);
	mst(vis,0);
	len = strlen(s) / k;
	for(int i = 0;i<len;i++){
		int l = i * k,r = (i + 1) * k;
		mst(vis,0);
		int ccnt = 0;
		for(int j = l;j < r;j++){
			if(!vis[i + 1][s[j] - 'a']){
				ccnt++;
				vis[i + 1][s[j] - 'a'] = 1;
			}
		}
		for(int j = 0;j < 26;j++){
			for(int l = 0;l < 26;l++){
				if(j == l && ccnt == 1 && vis[i + 1][j]) cnt[i + 1][j][l] = 1;
				else if(vis[i + 1][j] && vis[i + 1][l] && j != l) cnt[i + 1][j][l] = ccnt;
				else if(!vis[i + 1][j] && !vis[i + 1][l]) cnt[i + 1][j][l] = ccnt + 2;
				else cnt[i + 1][j][l] = ccnt + 1;
			}
		}
	}
}

int main(){
	cin>>T;
	for(int cas = 1;cas <= T;cas++){
		cin>>k;
		cin>>s;
		init();
		for(int i = 0;i < 26;i++){
			for(int j = 0;j < 26;j++){
				f[1][i][j] = cnt[1][i][j];
			}
		}
		for(int i = 2;i <= len;i++){
			for(int j = 0;j < 26;j++){
				for(int l = 0;l < 26;l++){
					f[i][j][l] = INF;
					for(int m = 0;m < 26;m++){
						if(f[i - 1][j][m] + cnt[i][m][l] - 1< f[i][j][l]){
							f[i][j][l] = f[i - 1][j][m] + cnt[i][m][l] - 1;
						}
					}
				}
			}
		}
		int ans = INF;
		for(int i = 0;i < 26;i++){
			for(int j = 0;j < 26;j++){
				ans = min(f[len][i][j],ans);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

#####F - 苇名欧一郎

F、给出T组数据，每组数据给出一个数$n$，以及$n - 1$个01串，第一个01串表示在没有任何武器的情况下可以击杀的敌人，后面的$n$个01串表示击杀某个敌人后得到武器后可以击杀的敌人

状态压缩
考虑将击杀了的人表示在一个集合里面，那么当前可以击杀的人就是将对应的01串用或运算放进来，查询后面某个没有击杀的敌人能不能被击杀，之后再向后面进行转移
异或运算的地方可以用$O(2^n - 1)$的时间进行预处理，放到集合里面会炸时间复杂度
用$f_S$表示击杀了$S$中的敌人的方案数，转移方程：
$$
f_S = \{f_S + f_{S_j},j\in S_1\}
$$
$S_1$表示当前可以击杀的敌人的集合
时间复杂度$O( 2^n(n + 1))$

ll T,n;
ll f[1 << 17],could[1 << 17];
ll pre = 0;
ll a[30];
char ss[30];

ll ctoint(char *s){
	ll res = 0;
	ll len = strlen(s);
	for(ll i = len - 1;i >= 0;i--){
		if(s[i] == '1') res = res * 2 + 1;
		else res *= 2;
	}
	return res;
}

void inttoch(ll num){
	for(int i = 16;i >= 0;i--) cout<<((num & (1 << i)) == 0 ? 0 : 1);
	cout<<endl;
}

ll get(ll num){
	ll res = pre;
	for(ll i = 0;i < n;i++){
		if(num & (1 << i)){
			res |= a[i];
		}
	}
	return res;
}

int main(){
	cin>>T;
	for(ll cas = 1;cas <= T;cas ++){
		cin >> n;
		cin >> ss;
		pre = ctoint(ss);
		for(ll i = 0;i < n;i++){
			cin>>ss;
			a[i] = ctoint(ss);
		}
		mst(f,0);
		mst(could,0);
		for(ll i = 0;i <= (1 << n) - 1;i++) could[i] = get(i);
		for(ll i = 0;i < n;i++){
			if(pre & (1 << i)) f[1 << i] = 1;
		}
		for(ll i = 0;i <= (1 << n) - 1;i++){
			for(ll j = 0;j < n;j++){
				if(i & (1 << j)){
					ll co = could[i ^ (1 << j)];
					if(co & (1 << j)) f[i] += f[i ^ (1 << j)];
				}
			}
		}
		cout<<"Case "<<cas<<": "<<f[(1 << n) - 1]<<endl;
	}
	return 0;
}

G - 子串

G、给出长度为nn的数字串，请求出其中能被$k$整除的子串个数

字符串动态规划
考虑用$f_{i,j}$表示前面i个数字所表示的数$mod \ k = j$的个数，转移方程：
$$
f_{i + 1,10j + a[i + 1] mod \ k} = f_{i + 1,10j + a[i + 1] mod \ k} + f_{i,j}
$$
注意到第$i + 1$次的状态只需要第$i$次的状态进行转移，那么用一个二维的滚动数组就可以降低空间复杂度到$O(2k + n)$
时间复杂度$O(nk)$

int a[maxn],n,k;
char s[maxn];
ll ans = 0;

int main(){
    cin>>n>>k;
    cin>>s;
    ll f[3][k + 1];
    mst(f,0);
    for(int i = 0;i < n;i++)  a[i + 1] = s[i] - '0';
    f[1][a[1] % k]++;
    ans += f[1][0];
    for(int i = 1;i < n;i++){
        f[2][a[i+1]%k]++;
        for(int j = 0;j < k;j++){
            f[2][(j*10 + a[i + 1])%k] += f[1][j];
        }
        ans += f[2][0];
        for(int j = 0;j <k;j++) f[1][j] = f[2][j],f[2][j]=0;
    }
    cout<<ans<<endl;
    return 0;
}

#####H - van游戏

H、给出一棵有向树，树的每个结点有一定的权值，两个人依次取权值，当前的人只能取上一个人取的结点的儿子的权值，eom希望游戏结束时自己权值大的情况下moe的权值小，moe则希望eom权值小的前提下自己权值大，两人都按照最优策略取，输出出游戏结束时两人所得权值是多少

暴力 dfs 树上dp
用两个dfs进行求解，到每个人求解的时候先获取子树上的信息再进行决策，最后统计答案即可
辣鸡数据耗我罚时
时间复杂度$O(y),y = n$

int n,m,root,cnt[1000007];
ll f[1000007][2],w[1000007];
vector<Edge> G;
vector<int> edges[1000006];
string name;

void dfs1(int now);
void dfs2(int now);

void addedge(int u,int v){
    G.push_back(Edge(u,v));
    edges[u].push_back(G.size() - 1);
}

void dfs1(int now){
    int nxt = 0;
    ll maxx = 0;
    ll minn = INF;
    int len = edges[now].size();
    for(int i = 0;i < len;i++){
        int v = G[edges[now][i]].to;
        dfs2(v);
        if(f[v][0] > maxx || (f[v][0] == maxx && f[v][1] < minn)) nxt = v,maxx = f[v][0],minn = f[v][1];
    }
    f[now][0] = f[nxt][0];
    f[now][1] = f[nxt][1] + w[now];
}

void dfs2(int now){
    int nxt = 0;
    ll minn = INF;
    ll maxx = 0;
    int len = edges[now].size();
    for(int i = 0;i < len;i++){
        int v = G[edges[now][i]].to;
        dfs1(v);
        if(f[v][0] < minn || (f[v][0] == minn && f[v][1] > maxx)) nxt = v,minn = f[v][0],maxx = f[v][1];
    }
    f[now][0] = f[nxt][0] + w[now];
    f[now][1] = f[nxt][1];
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    mst(f,0);
    mst(cnt,0);
    cin>>name;
    cin>>n;
    for(int i = 1;i <= n;i++){
        cin>>w[i];
    }
    int u,v,x;
    for(int i = 1;i < n;i++){
        cin>>u>>v;
        addedge(u,v);
        cnt[v] ++;
    }
    for(int i = 1;i <= n;i++){
        if(cnt[i] == 0) root = i;
    }
    if(name == "eom") dfs2(root);
    else dfs1(root);
    cout<<f[root][0]<<" "<<f[root][1]<<endl;
    return 0;
}

I - 攻略妹纸

I、给出oydy想攻略的$n$个妹子，oydy对每个妹子有一定的好感度$a_i$并且有自己的魅力值$k$，而每个妹子也对oydy有一定的初始好感度$ b_i $，要攻略一个妹子要求妹子对oydy的好感度到达一定的值$ c_i $并且oydy的魅力值达到$d_i$，现在oydy手里有$ m $单位的钱，求最大的能获得的愉悦值

01背包
看了题解之后才写的。。对题目抽象后等价于有$ n $个物体，体积为$ w = (c - b)y $，价值为$ a_i $，选取前提是$ k >= h = (d - k)x $，那么排序瞎搞一下。。
时间复杂度$ O(nw + nlogn) $

ll n,m,k,x,y;
ll a,b,c,d;

struct oy {
	ll val,w,h;

	bool operator < (const oy& a) const{
		if(h == a.h) {
            if(w == a.w) return val < a.val;
            return w < a.w;
        }
		return h < a.h;
	}
}all[maxn];

ll f[maxn][maxn],ans = 0;


int main(){
	mst(f,0);
	cin>>n>>m>>k>>x>>y;
	for(ll i = 1;i <= n;i++){
		cin>>a>>b>>c>>d;
		all[i].val = a;
		all[i].w = (c - b) * y;
		all[i].h = (d - k) * x;
	    if(all[i].w < 0) all[i].w = 0;
	    if(all[i].h < 0) all[i].h = 0;
	}
	sort(all + 1,all + n + 1);
	for(ll i = 1;i <= n;i++){
		ll tm = m - all[i].h;
		for(ll j = 0;j <= tm;j++){
			if(j < all[i].w)  f[i][j] = f[i - 1][j];
			else f[i][j] = max(f[i - 1][j],f[i - 1][j - all[i].w] + all[i].val); 
			ans = max(ans,f[i][j]);
		}
	}
	cout<<ans<<endl;
	return 0;
}

J - 扫广场

J、给出一个01矩阵，要求使用最少的将1变成0的操作使得所有的0连通

连通性dp
（写不来，待填坑）
放一个写得跟屎一样的代码

int n,m;
int up,low,len,las;
vector<int> statu;
char zh[250][250];
int f[100][1000],oy[250];
int dirx[] = {1,-1,0,0};
int diry[] = {0,0,1,-1};

int quickpow(int a,int b){
	int res = 1,t = a;
	while(b){
		if(b & 1) res *= t;
		t *= t;
		b >>= 1;
	}
	return res;
}

bool check1(int x){
	int s[10],vis[10],tmp = 0;
	mst(s,0);
	mst(vis,0);
	int l = 0;
	int count = 0;
	for(int i = 0;x;i++){
		s[i] = x % 5;
		x /= 5;
		l = i;
	}
	for(int i = l;i >= 0;i--){
		if(s[i] == 0) continue;
		if(!vis[s[i]]){
			for(int j = s[i] + 1;j < 5;j++){
				if(vis[j]) return false;
			}
		}
		vis[s[i]] = 1;
		if(s[i - 1] > 0  && i - 1 >= 0 && s[i] != s[i - 1]) return false;
		tmp = max(tmp,s[i]);
	}
	for(int i = 1;i <= tmp;i++) if(!vis[i]) return false;
	return true;
}


void print_test(int x,int k){
	int s[10];
	for(int i = 0;i < low;i++) s[i] = x % k,x /= k;
	for(int i = low -1 ;i >= 0;i--) cout<<s[i];
}

int NextStatu(int u,int v){
	int res = 0,count = 0,tmp = 0,t1 = v,t2 = u;
	int s1[8],s2[8],link[8],vis[8],link2[8];
	bool flag = 0;
	mst(s1,0);
	mst(s2,0);
	mst(vis,0);
	mst(link,0);
	mst(link2,0);
	for(int i = 0;i < low;i++){
		s1[i] = u % 5;
		s2[i] = v % 2;
		u /= 5;
		v /= 2;
		tmp = max(tmp,s1[i]);
	}
	for(int i = low - 1;i >= 0;i--){
		if(s2[i] == 0){
			if(!flag) flag = 1,count++,s2[i] = count;
			else s2[i] = count;
		}
		else{
			if(flag) flag = 0;
			s2[i] = 0;
		}
	}
	for(int i = low - 1;i >= 0;i--){
		if(s1[i] == 0) continue ;
		if(link[s1[i]] == 0) link[s1[i]] = s2[i];
	}
	for(int i = 1;i <= tmp;i++){
		if(link[i] != 0) continue;
		else return -1;
	}
	if(tmp >= 1){
		count = 1;
		for(int i = low - 1;i >= 0;i--){
		    if(s2[i] == 0) link2[s2[i]] = 0;
		    else if(link2[s2[i]] == 0 || (link2[s2[i]] > s1[i] && s1[i] != 0)) link2[s2[i]] = s1[i];
	    }
	    for(int i = low - 1;i >= 0;i--){
	    	if(s2[i] == 0 || vis[i]) continue;
	    	if(link2[s2[i]] == 0){
	    		for(int j = low - 1;j >= 0;j--) if(!vis[j] && link2[s2[j]] == 0 && s2[j] == s2[i]) s2[j] = count,vis[j] = 1;
	    		count ++;
	    	}
	    	else if(link2[s2[i]] != 0){
	    		for(int j = low - 1;j >= 0;j--) if(!vis[j] && link2[s2[j]] == link2[s2[i]]) s2[j] = count,vis[j] = 1;
	    		count ++;
	    	}
	    }
	}
	for(int i = low - 1;i >= 0;i--) res = res*5 + s2[i];
	return res;
}

void init(){
	cin>>n>>m;
	up = max(m,n),low = min(m,n);
	mst(f,0x3f3f);
	int pownum = quickpow(5,low);
	for(int i = 0;i < pownum;i++){
		if(check1(i)) statu.push_back(i);
	}
	for(int i = 1;i <= n;i++){
		cin>>zh[i];
	}
	mst(oy,0);
	if(n >= m){
		for(int i = 1;i <= n;i++){
			for(int j = 0;j < m;j++){
				oy[i] = oy[i] * 2 + zh[i][j] - '0';
				if(zh[i][j] == '0' && i > las) las = i;
			}
		}
	}
	else{
		for(int j = 0;j < m;j++){
			for(int i = n;i >= 1;i--){
				oy[j + 1] = oy[j + 1] * 2 + zh[i][j] - '0';
				if(zh[i][j] == '0' && j + 1 > las) las = j + 1;
			}
		}
	}
}

int get(int u,int v){
	int tmp1,tmp2,res = 0;
	for(int i = 0;i < 8;i++){
		tmp1 = u % 2;
		tmp2 = v % 2;
		u /= 2;
		v /= 2;
		if(tmp1 == tmp2) continue;
		else if(tmp1 == 1 && tmp2 == 0) res++;
		else if(tmp1 == 0 && tmp2 == 1) return -1;
	}
	return res;
}

bool check_dfs(){
	for(int i = 1;i <= n;i++){
		for(int j = 0;j < m;j++){
			if(zh[i][j] == '0') return false;
		}
	}
	return true;
}

void dfs_flood(int x,int y){
	zh[x][y] = '2';
	int nx,ny;
	for(int i = 0;i < 4;i++){
		nx = x + dirx[i];
		ny = y + diry[i];
		if(nx > n || nx < 1 || ny >= m || ny < 0) continue;
		if(zh[nx][ny] == '0') dfs_flood(nx,ny);
	}
}

int main(){
	//freopen("std.out","w",stdout);
	init();
	len = statu.size();
	for(int i = 0;i < (1 << low);i++){
		int nxt = get(oy[1],i),now = NextStatu(0,i);
		if(nxt == -1) continue;
		int pos = lower_bound(statu.begin(), statu.end(),now) - statu.begin();
        if(statu[pos] != now) continue;
	    f[1][pos] = nxt;
	}
	for(int i = 2;i <= las;i++){
		for(int j = 0;j < len;j++){
			for(int k = 0;k < (1 << low);k++){
				int now = NextStatu(statu[j],k);
				if(now != -1){
					int nxt = get(oy[i],k);
					if(nxt == -1) continue;
					int pos = lower_bound(statu.begin(), statu.end(),now) - statu.begin();
					if(statu[pos] != now) continue;
					f[i][pos] = min(f[i][pos],f[i - 1][j] + nxt);
				}
			}
		}
	}
	int ans = INF;
	for(int i = 0;i < len;i++){
		bool flag = 0;
		int tmp = statu[i];
		for(int j = 0;j < low;j++){
			if(tmp % 5 > 1) flag = 1;
			tmp /= 5;
		}
		if(flag) continue; 
		ans = min(ans,f[las][i]);
	}
	bool flag = 0;
	for(int i = 1;i <= n;i++){
		for(int j = 0;j < m;j++){
			if(zh[i][j] == '0'){
				flag = 1;
				dfs_flood(i,j);
				break;
			}
		}
		if(flag) break;
	}
	if(check_dfs()) ans = 0;
	cout<<ans<<endl;
	return 0;
}

K - 抽卡

K、给出n、m，以及直接抽中的概率x，和抽中一个特定碎片的概率y，抽取n次，输出在n次内可以抽中或者集齐碎片的概率

矩阵快速幂

题面害人
好吧是我没认真读题，对于每次抽奖，直接抽中的概率是$ x $，而抽中某一个特定碎片的概率是$ y $，那么抽不中碎片也不能一发入魂的概率就是$z = 1 - x - m * y$
那么分两种情况考虑

• 不管碎片，直接抽中的概率
• 通过碎片抽齐的概率

首先看直接抽中的概率，因为用碎片凑齐的情况下一次抽中都算抽中，那么这个可以直接计算
假设到第$ i - 1$次一次抽中的概率为$ p $，那么显然第$ i $次一次抽中的概率就是$(1 - p) * x$,假设第$ i $次直接抽中的概率是$ f_ i$，那么有下面的关系
$$
f_i = x(1 - f_{i - 1}) \
f_{i - 1} = x(1 - f_{i - 2})
$$
整理一下可以得到
$$
\left[\begin{matrix}f_n \\ f_{n - 1}\end{matrix}\right] = \left[\begin{matrix}2 - x & x - 1 \\ 1 & 0\end{matrix}\right] ^ {n -1}\left[\begin{matrix}f_{1} \\ f_{2}\end{matrix}\right]
$$
然后是考虑通过凑齐碎片得到的概率，考虑前面$ i $次获得了$ j $块碎片，也就是令$f_{i,j}$表示前面$ i $次获得了$ j $块碎片，那么这个状态由前面$ i - 1 $次获得了$ j - 1 $块碎片和前面$ i - 1 $次获得了$ j $块碎片转移过来，对于前一次只获得$j$块不同碎片的情况下乘$ z + j * y$，表示这一次一块都没抽到以及抽到的是已经有的，而对于前一次获得了$ j - 1 $块不同的碎片的情况下，要从剩下的里面选一块出来，那么就是要乘$ (m - j + 1) * y$，所以得到下面的关系
$$
f_{i,j} = f_{i - 1,j - 1} * (m - j + 1) * y + f_{i - 1,j} * (z + j * y)
$$
于是可以得到转移矩阵
$$
\left[\begin{matrix}f_{n,0} \\ f_{n,1} \\ f_{n,2} \\ … \\ f_{n,m} \end{matrix}\right] =
\left[\begin{matrix}
z &0 & 0 & 0 & 0 & … & 0 \\
0 & my & y + z & 0 & 0 & … & 0 \
0 & 0 & (m - 1)y & 2y+z & 0 & … & 0\
…& …\ & … & … & … & … & …\
0 & 0& 0 & 0 & 0 & … & my + z\
\end{matrix}\right] ^ n
\left[\begin{matrix}f_{0,0} \\ f_{0,1} \\ f_{0,2} \\ … \\ f_{0,m}\end{matrix}\right]
$$
然后使用写一个矩阵的struct再套上快速幂的板子，取$f_{n,m} + f_n$相加就是答案
时间复杂度$ O (m^3logn)$
需要特判一下n = 0的情况，不然会TLE毒瘤出题人出来挨打

struct matrix{
	ll num[102][102];
	int w,h;

	matrix operator * (const matrix& a) const{
		matrix res;
		mst(res.num,0);
		res.h = h;
		res.w = a.w;
		for(int i = 1;i <= h;i++){
			for(int j = 1;j <= a.w;j++){
				for(int k = 1;k <= w;k++){
					res.num[i][j] = (res.num[i][j] + num[i][k] * a.num[k][j] + mod) % mod;
				}
			}
		}
		return res;
	}

	void init(int hh,int ww){
		h = hh;
		w = ww;
		mst(num,0);
		for(int i = 1;i <= h;i++) num[i][i] = 1;
	}
};

matrix MatrixQuickMod(matrix a,int b){
	matrix t = a,res;
	res.init(a.h,a.w);
	if(b <= 0) return res;
	while(b){
		if(b & 1) res = res * t;
		t = t * t;
		b >>= 1;
	}
	return res;
}

ll n,m;
double tmpx,tmpy;
ll x,y,z,Ans;
matrix ans,res,dp,f;

void init(){
	x = 1000 * (tmpx + 1e-6);
	y = 1000 * (tmpy + 1e-6);
	z = 1000 - x - m * y;
	ans.init(2,1);
	res.init(2,2);
	dp.init(m + 1,m + 1);
	f.init(m + 1,1);
	ans.num[1][1] = (ll)(1000.00 * tmpx);
	ans.num[2][1] = 0;
	res.num[1][1] = (ll)(1000.00 * (2.00 - tmpx + 1e-6));
	res.num[1][2] = (ll)(-1000.00 * (1.00 - tmpx+ 1e-6));
	res.num[2][1] = 1000;
	res.num[2][2] = 0;
	res = MatrixQuickMod(res,n - 1);
	dp.num[1][1] = z;
	for(int i = 2;i <= m + 1;i++){
		dp.num[i][i - 1] = (m - i + 2) * y;
		dp.num[i][i] = ((i - 1) * y + z);
	}
	dp = MatrixQuickMod(dp,n);
	f.num[1][1] = 1;
	f = dp * f;
	ans = res * ans; 
	Ans = (ans.num[1][1] + f.num[m + 1][1]) % mod;
}

int main(){
	//freopen("std.in","r",stdin);
	cin>>n>>m>>tmpx>>tmpy;
	if(n == 0){
		cout<<0<<endl;
		return 0;
	}
	else if(n == 1 && m == 0){
		cout<<(ll)(tmpx * 1000)<<endl;
		return 0;
	}
	init();
	cout<<Ans<<endl;
	//std::cout<<(double)clock() / CLOCKS_PER_SEC <<"s"<<std::endl;
	return 0;
}

L - zh的奖杯

L、给出zhh的$n$个🏆，但是zhh大爷太忙了，让我帮他把🏆用一堆箱子装起来，每两个🏆之间要放入单位体积的棉花，而且家里有矿的zhh大爷要箱子花费的代价最小，每个箱子的代价为$(x - l)^2$，$l$是一个常数，$x$是装入某个箱子的🏆总体积

斜率优化
一开始我以为是个贪心
首先得到状态转移方程为:
$$
f_i = min\{ f_j +( \sum_{k = j + 1} ^ i v_k + i - j - 1 - l) ^ 2 \}
$$
表示的是装前面 i 件的最小花费 ，这里可以令：
$$
g(x) = sum(x) + x \
f_i = min\{f_j + (g(i) - g(j) - 1 - l)^2\}
$$
假设$ 1 <= j_1 < j_2 < i $，并且$ j 2$ 的决策更优，就得到:
$$
f{j_1} + (g(i) - g(j_1) - 1 - l)^2 >= f_{j_2} + (g(i) - g(j_2) - 1 - l)^2
$$
化简有：
$$
2g(i) >= \frac {f_{j_2} + (g(j_2) + l + 1) ^2 - (f_{j_1} + (g(j_1) + l + 1) ^2) }{g(j_2) - g(j_1)}\
令h(x) = (g(j_1) + l + 1) ^2 \
得2g(i) >= \frac {f_{j_2} + h(j_2) - (f_{j_1} + h(j1)) }{g(j_2) - g(j_1)}
$$
那么对于两个决策$j_1、j_2$，满足上面的式子的时候$j_2$是最优的，而$g(i)$是单调递增的，要保证斜率也是单调递增的
使用单调队列进行维护，时间复杂度$O(n)$

ll n,L;
ull f[500007];
ll x[500007],y[500007],q[500007],sum[500007],v[500007];
ll l = 1,r = 0;

ll x2(ll x){
    return x * x;
}

double slope(int i,int j){
    return 1.0 * ((f[i] + x2(y[i])) - (f[j] + x2(y[j]))) / (y[i] - y[j]);
}

int main(){
    cin>>n>>L;
    x[0] = 0,y[0] = L + 1;
    for(int i = 1;i <= n;i++){
        cin>>v[i];
        sum[i] = sum[i - 1] + v[i];
        x[i] = sum[i] + i;
        y[i] = sum[i] + i + L + 1;
    }
    f[0] = q[++r] = 0;
    for(int i = 1;i <= n;i++){
        while(l < r && slope(q[l],q[l + 1]) <= 2 * x[i]) l++;

        f[i] = f[q[l]] + x2(x[i] - y[q[l]]);
        cout<<f[q[l]]<<" "<<x2(x[i] - y[q[l]])<<" "<<f[i]<<endl;
        while(l < r && slope(q[r - 1],q[r]) >= slope(q[r],i)) r--;
        q[++r] = i;
    }
    cout<<f[n]<<endl;
    return 0;
}

M - 崭新龙狙，制霸全区

M、求给出的两个数$L、R$之间的数中出现的连续4750的个数之和

数位dp
看到数据范围一眼数位dp，但是我想出来状态QAQ
后面写的时候函数里直接把string传了进去导致lutece爆空间，我是辣鸡
我写了，一发mle了，有什么好说的
连xyy都看不下去了

string num1,num2;
char tmp[maxn];
int pp[] = {0,4,7,5,0};
int len1,len2;
int f[maxn][6],pre[maxn],PRE[maxn];
int ans1,ans2,ans;

int quickmod(int a,int b){
	int res = 1,t = a;
	while(b){
		if(b & 1) res = (res * t) % zh;
		t = (t * t) % zh;
		b >>= 1;
	}
	return res;
}

void init(){
	cin>>num1>>num2;
	int len = num1.length();
	reverse(num1.begin(),num1.end());
	num1[0] -= 1;
	if(len == 1 && num1[0] == '0' - 1) num1[0] += 1;
	else{
		for(int i = 0;i < len ;i++){
		    if(num1[i] - '0' < 0){
			    num1[i] += 10;
			    num1[i + 1] -= 1;
		    }
	     }
	     reverse(num1.begin(),num1.end());
	}
	len1 = num1.length();
	len2 = num2.length();
}

void charinit(const string& s){
	int len = s.length();
	pre[len] = 1;
	PRE[len - 1] = s[len - 1] - '0';
	for(int i = len - 1;i >= 1;i--){
		pre[i] = (pre[i + 1] * 10) % zh;
		PRE[i - 1] = (PRE[i] + (s[i - 1] - '0') * quickmod(10,len - i)) % zh;
	}
	for(int i = 1;i <= len;i++) PRE[i]++,PRE[i] %= zh;
}

int dfs(int u,int v,int lim,int l,const string& s){
	if(u >= l)  return v == 4;
	if(!lim && f[u][v] != -1) return f[u][v];
	int res = v == 4;
	int V = v;
	v = v == 4 ? 0 : v;
	if(!lim) res = (res * pre[u]) % zh;
	else res = (res * PRE[u]) % zh;
	int upp = lim ? s[u] - '0' : 9;
	for(int i = 0;i <= upp;i++){
		tmp[u] = '0' + i;
		if(pp[v + 1] == i){
			res = (res + dfs(u + 1,v + 1,i == upp && lim,l,s)) % zh;
		}else{
			if(i == 4) res = (res + dfs(u + 1,1,i == upp && lim,l,s)) % zh;
			else res = (res + dfs(u + 1,0,i == upp && lim,l,s)) % zh;
		}
	}
	if(!lim) f[u][V] = res;
	return res;
}

int main(){
	init();
	charinit(num1);
	mst(f,-1);
	ans1 = dfs(0,0,1,len1,num1);
	charinit(num2);
	mst(f,-1);
	ans2 = dfs(0,0,1,len2,num2);
	ans = (ans2 - ans1 + zh) % zh;
	cout<<ans<<endl;
	return 0;
}