每日一题5.25

Fengyj

2023 ICPC合肥，J题铜，BC银，I金
https://qoj.ac/contest/1440

XinyuLin

https://qoj.ac/contest/1440

XinyuLin

铜牌题

[C++] 纯文本查看 复制代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll info = 4e18;

struct Edge { int u, v; ll w; };
using State = pair<ll, int>;         

vector<ll> dijstra(int s, const vector<vector<pair<int, ll>>>& g) {
    int n = g.size();
    vector<ll> dist(n, info);
    vector<bool> visd(n + 1);
    priority_queue<State, vector<State>, greater<State>> pq;
    dist[s] = 0;
    pq.emplace(0, s);
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (visd[u]) continue;
        visd[u] = true;
        for (auto [v, w] : g[u]) {
            ll nd = max(d, w);
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.emplace(nd, v);
            }
        }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<Edge> E(m);
    vector<vector<pair<int, ll>>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v; ll w; cin >> u >> v >> w;
        E[i] = { u,v,w };
        g[u].push_back({ v,w });
        g[v].push_back({ u,w });
    }

    auto b1 = dijstra(1, g);       
    auto bn = dijstra(n, g);       

    ll ans = info;
    for (auto& e : E) {
        int u = e.u, v = e.v; ll w = e.w;
        if (b1[u] <= w && bn[v] <= w)
            ans = min(ans, w + max(b1[u], bn[v]));
        if (b1[v] <= w && bn[u] <= w)
            ans = min(ans, w + max(b1[v], bn[u]));
    }
    cout << ans << "\n";
    return 0;
}

Fengyj

B题
#include<bits/stdc++.h>

using namespace std;

const int N = 510, mod = 998244353;
typedef long long LL;
#define int long long
int n, m, w[N];
int fc[N], ifc[N];
int f[N][N], g[N][N];


int inv(int x)
{
    int y = mod - 2, z = 1;
    while (y)
    {
        if (y & 1)
            z = (LL)z * x % mod;
        x = (LL)x * x % mod;
        y >>= 1;
    }
    return z;
}
int binom(int x, int y)
{
    if (x < 0 || y < 0 || x < y)
        return 0;
    return (LL)fc[x] * ifc[y] % mod * ifc[x - y] % mod;
}
inline void add(int &x, int y) { x += y, x >= mod && (x -= mod); }

signed main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]), m += w[i];

    fc[0] = ifc[0] = 1;
    for (int i = 1; i <= m; i++)
    {
        fc[i] = (LL)fc[i - 1] * i % mod;
        ifc[i] = inv(fc[i]);
    }

    f[1][0] = 1;

    for (int i = 1, s = w[1]; i < n;i++,s+=w[i]){
        add(f[i + 1][0], f[i][0]);
        for (int k = 1; k <= s;k++){
            for (int x = 0; x < w[i + 1];x++){//k后面那个位置必须先放一个,x个放前面，剩下w[i+1]-x-1个
                add(f[i + 1][k + x + 1], (LL)f[i][0] * binom(s - k + 1 + w[i + 1] - x - 1 - 1, w[i + 1] - x - 1) % mod);
            }
        }

        for (int j = 1; j <= s;j ++){
            add(f[i + 1][j + w[i + 1]], f[i][j]);
            for (int k = 1; k < j;k++){
                for (int x = 0; x < w[i + 1];x++){
                    add(f[i + 1][k + x + 1], (LL)f[i][j] * binom(j - k  + w[i + 1] - x - 1 - 1, w[i + 1] - x - 1) % mod);
                }
            }
        }
    }
    int res = 0;
    for (int i = 0; i <= m;i++){
        add(res, f[n][i]);
    }
    cout << res << endl;
    return 0;
}

XinyuLin

[C++] 纯文本查看 复制代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
const int MAXM = 500;          

ll q_pow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
ll pi[MAXM + 1], inv[MAXM + 1];
inline int C(int n, int r) {
    if (r < 0 || r > n) return 0;
    return pi[n] * inv[r] % MOD * inv[n - r] % MOD;
}
void init(int m) {                    
    pi[0] = 1;
    for (int i = 1; i <= m; i++) pi[i] = pi[i - 1] * i % MOD;
    inv[m] = q_pow(pi[m], MOD - 2);    
    for (int i = m; i; i--) inv[i - 1] = inv[i] * i % MOD;
}


int a[MAXM + 1];
ll dp[2][MAXM + 1];                  

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    int m = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        m += a[i];
    }
    init(m);
    dp[0][0] = 1;                          
    int len = 0;                           
    int cur = 0, nxt = 1;

    for (int i = 1; i <= n; ++i) {         
        int cnt = a[i];
        if (!cnt) {                        
            for (int j = 0; j <= len; j++) {
                dp[nxt][j] = dp[cur][j];
            }
            swap(cur, nxt);
            continue;
        }
        fill(dp[nxt], dp[nxt] + m + 1, 0);
        for (int j = 0; j <= len; ++j) {
            ll ways = dp[cur][j];
            if (!ways) continue;

            int j1 = (j == 0 ? 0 : j + cnt);
            dp[nxt][j1] = (dp[nxt][j1] + ways) % MOD;

            int lim = (j == 0 ? len + 1 : j);     
            for (int x = 0; x < cnt; ++x) {        
                int rest = cnt - x - 1;            
                for (int k = 1; k <= lim - 1; ++k) {
                    int comb = C((lim - 1 - k) + rest, rest);
                    int j2 = x + k + 1;           
                    dp[nxt][j2] = (dp[nxt][j2] + ways * comb) % MOD;
                }
            }
        }
        len += cnt;                               
        swap(cur, nxt);
    }

    int ans = 0;
    for (int j = 0; j <= len; j++) {
        ans = (ans + dp[cur][j]) % MOD;
    }
    cout << ans << endl;
    return 0;
}

495684945

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;
const int mod=998244353;
int qi_mi(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
void solve(){
	int n,m=0;
	cin>>n;
	vector<int>a(n+10),fact(1010),infact(1010);
	for(int i=1;i<=n;i++)cin>>a[i],m+=a[i];
	fact[0]=infact[0]=1;
	for(int i=1;i<=1000;i++){
		fact[i]=fact[i-1]*i%mod;
		infact[i]=qi_mi(fact[i],mod-2)%mod;
	}
	auto C=[&](int n,int m)->int{
		if(m<0||m>n)return 0;
		return fact[n]*infact[m]%mod*infact[n-m]%mod;
	};	
	vector f(n+10,vector<int>(m+10));
	f[0][0]=1;
	int len=0;
	for(int v=1;v<=n;v++){
		int cnt=a[v];
		if(cnt==0){
			f[v]=f[v-1];
			continue;
		}
		for(int j=0;j<=len;j++){
			int cur=f[v-1][j];
			if(cur==0)continue;
			for(int x=0;x<=cnt;x++){
				if(x==cnt){//全部放在前面
					if(j==0)f[v][0]=(f[v][0]+cur)%mod;
					else f[v][j+cnt]=(f[v][j+cnt]+cur)%mod;
				}else{
					int res=cnt-x-1;//除去放在前面和单独插入的剩下的区间插入
					if(j==0){//之前还没到长度为2的最长上升子序列
						for(int k=1;k<=len;k++){
							int temp_j=x+k+1;//插入到这里
							int cntt=C(len-k+res,res);
							f[v][temp_j]=(f[v][temp_j]+cur*cntt)%mod;
						}
					}else{//已经有了，位置在j
						for(int k=1;k<j;k++){
							int temp_j=x+k+1;//插入到这里
							int cntt=C(j-k-1+res,res);
							f[v][temp_j]=(f[v][temp_j]+cur*cntt)%mod;
						}
					}
				}
			}
		}
		len+=cnt;
	}
	int ans=0;
	for(int i=0;i<=m;i++)ans=(ans+f[n][i])%mod;
	cout<<ans<<endl;
}

signed main(){
	int t=1;ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//	cin>>t;
	while(t--)solve();
	return 0;
}