SMU Winter 2024 div2 ptlks的周报Week 2（1.29-2.4）

这周学习到的知识点有 斯特林数（ F 鸡数题！）

F 鸡数题！

思路

第二类斯特林数

代码

#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;

int n,m,f[100005],fi[100005];

int qpow(int a, int n){
	int ans = 1;
	while(n){
		if(n&1){
			ans *= a;
			ans %=MOD;
		}
		a *= a;
		a %=MOD;
		n >>= 1;
	}
	return ans%MOD;
}
void fa(){
	f[0]=fi[0]=1;
	for(int i=1;i<100005;i++){
		f[i]=i*f[i-1]%MOD;
		fi[i]=qpow(i,MOD-2)*fi[i-1]%MOD;
	}
}


int32_t main() {
	int T=1;
	//cin>>T;
	while (T--) {
		cin>>n>>m;
		if(n<m){
			cout<<0<<endl;
		}else{
		fa();
		int s=0;
		for(int i=0;i<=m;i++){
			int t=qpow(i,n);
			t*=fi[i]*fi[m-i]%MOD;
			t%=MOD;
			if((m-i)%2)s-=t;
			else s+=t;
		}
		s=(s%MOD+MOD)%MOD;
		cout<<s;
		}
	}
	return 0;
}

P8802 [蓝桥杯 2022 国 B] 出差

思路

最短路

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,a[1005];
vector<pair<int,int>> g[10005];
vector<int> vis(1005, 0),mn(1005,INT64_MAX);


void f(int x,int s) {
	if(s<mn[x])mn[x]=s;
	vis[x]=0;
	for(int i=0;i<g[x].size();i++){
		if(!vis[x]){
			if(g[x][i].second+s+a[g[x][i].first]<mn[g[x][i].first]){
				f(g[x][i].first,g[x][i].second+s+a[g[x][i].first]);
				vis[g[x][i].first]=0;
			}
		}
	}
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	//cin>>T;
	T = 1;
	while (T--) {
		int m;
		cin >> n>>m;
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		for(int i=0;i<m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			u--,v--;
			g[u].emplace_back(v,w);
			g[v].emplace_back(u,w);
		}
		f(0,0);
		cout<<mn[n-1]-a[n-1];
	}

	return 0;
}

P8806 [蓝桥杯 2022 国 B] 搬砖

思路

由题意不难得出排序条件为价值与重量之和，之后背包dp即可

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, w[1005], v[1005], f[40005];
vector<pair<int, int>> a;


int cmp(pair<int, int> x, pair<int, int> y) {
	return x.second + x.first <= y.second + y.first;
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	//cin>>T;
	T = 1;
	while (T--) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> w[i] >> v[i];
			a.emplace_back(make_pair(w[i], v[i]));
		}
		sort(a.begin(), a.end(), cmp);
		int mx=0;
		for (int i = 0; i < n; i++) {
			for (int j = a[i].first+a[i].second; j >= a[i].first; j--) {
				f[j] = max(f[j], f[j - a[i].first] + a[i].second);
				mx = max(mx, f[j]);
			}
		}
		cout << mx;
	}

	return 0;
}

P8612 [蓝桥杯 2014 省 AB] 地宫取宝

思路

一开始想复杂了，实际可以用四维数组dp

代码

#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;

int n, m,k,ans=0;
int a[55][55];
int dp[55][55][55][55];

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	//cin>>T;
	T = 1;
	while (T--) {
		cin >> n>>m>>k;
		for (int i = 1; i <=n; i++) {
			for (int j = 1; j <=m; j++) {
				cin>>a[i][j];
				a[i][j]++;
			}
		}
		for (int j = 1; j <=13; j++) {
			dp[n][m][k][j]=1;
			if(a[n][m]>j)dp[n][m][k-1][j]=1;
		}
		for (int i = n; i >0; i--) {
			for (int j = m; j >0; j--) {
				for (int u = k; u >=0; u--) {
					for (int v = 13; v >=0; v--) {
						if(i==n&&j==m&&(u==k||u==k-1)){
							continue;
						}else{
							if(a[i][j]>v)dp[i][j][u][v]=(dp[i][j+1][u+1][a[i][j]]+dp[i+1][j][u+1][a[i][j]]+dp[i][j+1][u][v]+dp[i+1][j][u][v])%MOD;
							else dp[i][j][u][v]=(dp[i][j+1][u][v]+dp[i+1][j][u][v])%MOD;
						}
					}
				}
			}
		}
		cout<<dp[1][1][0][0];
	}
	
	return 0;
}