[考试记录] 2024.8.10 csp-s 模拟赛18

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 1e5 + 5;
int n, m, cir, ans1, ans2, f[N], x[N];
vector<int> G[N];
inline int find(int k){
	if(!f[k]) return k;
	return f[k] = find(f[k]); 
}
signed main(){
//	freopen("t1.in", "r", stdin);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>m;
	for(int i=1, y; i<=m; ++i){
		cin>>x[i]>>y;
		int fa = find(x[i]), fb = find(y); 
		if(fa != fb) f[fb] = fa;
		if(x[i] == y){ ++cir; continue; }
		G[x[i]].push_back(y), G[y].push_back(x[i]);
	} int bg = find(x[1]);
	for(int i=2; i<=m; ++i) if(find(x[i]) != bg) return cout<<0, 0;
	if(cir) ans2 = cir * (cir-1) / 2 + cir * (m - cir);
	for(int i=1; i<=n; ++i) for(int v : G[i]) ans1 += G[v].size() - 1;
	ans1 >>= 1;	return cout<<ans1 + ans2, 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, k, a[101], ans;
vector<int> vec;
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>k;
	for(int i=1; i<=n; ++i){
		cin>>a[i]; k += a[i];
		for(int j=1; j*j<=a[i]; ++j){
			vec.push_back(j);
			vec.push_back((a[i] + j - 1) / j);
		}
	}
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	for(int it : vec){
		int sum = 0, d;
		for(int i=1; i<=n; ++i){
			sum += (a[i] + it - 1) / it;
		} d = k / sum;
		if(d >= it) ans = max(ans, d);
	} return cout<<ans, 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, a, b, res[51], dp[51][51][51], ans = LONG_MAX;
struct SquareTable{
	int mx[51][10], mn[51][10];
	inline void init(){
		for(int i=1; i<=n; ++i) mx[i][0] = mn[i][0] = res[i];
		for(int j=1; j<=__lg(n); ++j) for(int i=1; i+(1<<j)-1<=n; ++i){
			mx[i][j] = max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
			mn[i][j] = min(mn[i][j-1], mn[i+(1<<(j-1))][j-1]);
		}
	}
	inline int QueryMx(int l, int r){
		if(l > r) return -1;
		int k = __lg(++r - l);
		return max(mx[l][k], mx[r-(1<<k)][k]);
	}
	inline int QueryMn(int l, int r){
		if(l > r) return INT_MAX;
		int k = __lg(++r - l);
		return min(mn[l][k], mn[r-(1<<k)][k]);
	}
} st;
signed main(){
	ios::sync_with_stdio(0), cin.tie(0) ,cout.tie(0);
	cin>>n>>a>>b; for(int i=1; i<=n; ++i) cin>>res[i]; st.init();
	if(b == 0) return cout<<a, 0;
	memset(dp, 0x7f, sizeof(dp));
	for(int len=1; len<=n; ++len) for(int l=1, r=len; r<=n; ++l, ++r)
		dp[l][r][1] = a + b * (st.QueryMx(l, r) - st.QueryMn(l, r)) * (st.QueryMx(l, r) - st.QueryMn(l, r));
	for(int len=2; len<=n; ++len){
		for(int l=1, r=len; r<=n; ++r, ++l){
			for(int k=2; k<=len; ++k){
				for(int lenn=1; lenn<len; ++lenn){
					for(int ln=l, rn=l+lenn-1; rn<=r; ++ln, ++rn){
//						printf("l = %lld r = %lld ln = %lld rn = %lld ", l, r, ln, rn);
						int lmx = st.QueryMx(l, ln-1), lmn = st.QueryMn(l, ln-1);
						int rmx = st.QueryMx(rn+1, r), rmn = st.QueryMn(rn+1, r);
						int mx, mn;
						if(l == ln) mx = rmx, mn = rmn;
						else if(r == rn) mx = lmx, mn = lmn;
						else mx = max(lmx, rmx), mn = min(lmn, rmn);
//						printf("mx = %lld mn = %lld\n", mx, mn);
						dp[l][r][k] = min(dp[l][r][k], dp[ln][rn][k-1] + a + b * (mx - mn) * (mx - mn));
					}
				}
			}
		}
	}
	for(int i=1; i<=n; ++i) ans = min(ans, dp[1][n][i]);
	return cout<<ans, 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, a, b, res[51], pos[51], g[51][51][51][51], f[51][51];
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>a>>b; for(int i=1; i<=n; ++i) cin>>res[i], pos[i] = res[i];
	sort(pos+1, pos+1+n); int cnt = unique(pos+1, pos+1+n) - pos - 1;
	for(int i=1; i<=n; ++i) res[i] = lower_bound(pos+1, pos+1+cnt, res[i]) - pos;
	memset(f, 0x3f, sizeof(f)), memset(g, 0x3f, sizeof(g));
	for(int i=1; i<=n; ++i) f[i][i] = a, g[i][i][res[i]][res[i]] = 0;
	for(int len=2; len<=n; ++len) for(int l=1, r=len; r<=n; ++l, ++r){
		for(int mx=1; mx<=cnt; ++mx) for(int mn=1; mn<=mx; ++mn)
			g[l][r][max(mx, res[r])][min(mn, res[r])] = min(g[l][r][max(mx, res[r])][min(mn, res[r])], g[l][r-1][mx][mn]);
		for(int mx=1; mx<=cnt; ++mx) for(int mn=1; mn<=mx; ++mn){
			for(int k=l; k<r; ++k) g[l][r][mx][mn] = min(g[l][r][mx][mn], g[l][k][mx][mn] + f[k+1][r]);
			f[l][r] = min(f[l][r], g[l][r][mx][mn] + a + b * (pos[mx]-pos[mn]) * (pos[mx]-pos[mn]));
		}
	} return cout<<f[1][n], 0;
}