CF
Problem - 1413C - Codeforces
优先队列好题，和最小函数值解法类似
先找每个b的品位最大值，然后用小根堆找其中的最小值，更新答案，并且把当前这个b的品味增大，（即把最小值变大），此时一定能把差值（max-min）变小。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
#define pii pair<int, int>
const LL mod = 998244353;
const int N = 1e5+10;
priority_queue<pii, vector<pii>, greater<pii>> q;
int cnt[N], b[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);vector<int> a(6);for (int i = 0; i < 6;i++){cin >> a[i];}sort(a.begin(), a.end(), greater<int>());int n, mx = 0, ans = 1e9;cin >> n;for (int i = 1; i <= n;i++){cin >> b[i];q.push({b[i] - a[0], i});mx = max(mx, b[i] - a[0]);}while(!q.empty()){auto now = q.top();q.pop();ans = min(ans, mx - now.first);int t = now.second;cnt[t]++;if(cnt[t]>=6){cout << ans << endl;return 0;}q.push({b[t] - a[cnt[t]], t});mx = max(mx, b[t] - a[cnt[t]]);}
}
Problem - 1647D - Codeforces
漂亮数其实就是“能被 d 整除，但不能被 d² 整除”的数。
一道有坑的分类讨论
注意：
d=s*s时，要满足 \(k>3\)
还有，当判断 \(s\) 是合数时还要特判 \(s\) 不是 1
#include <bits/stdc++.h>
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
const LL mod = 998244353;
const int N = 2e5+10;bool isprime(int x){if(x<2)return false;for (int i = 2; i * i <= x;i++){if(x%i==0)return false;}return true;
}void solve()
{int x, d;cin >> x >> d;int k = 0, s = x;while(s%d==0)s /= d, k++;if(k<=1){cout << "NO\n";return;}if(isprime(s)==false&&s!=1){//注意，这里特判 1cout << "YES\n";return;}if(isprime(d)){cout << "NO\n";return;}else{if(d==s*s){if(k>=4){cout << "YES\n";}else{cout << "NO\n";}}else{if(k>=3){cout << "YES\n";}else{cout << "NO\n";}}}}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
牛客周赛
F-小苯的DFS_牛客周赛 Round 142
树形dp+DFS
#include <bits/stdc++.h>
using namespace std;
#define LL long long
//#define double long double
#define endl '\n'
#define ULL unsigned long long
const LL mod = 998244353;
const int N = 2e5+10;
vector<int> e[N];
LL a[N];
LL f[N], inv[N], dp[N], mx[N], mn[N];void init(int n){f[0] = f[1] = inv[0] = inv[1] = 1;for (int i = 2; i <= n; i++){f[i] = f[i - 1] * i % mod;inv[i] = mod - (mod / i) * inv[mod % i] % mod;}for (int i = 1; i <= n; i++){inv[i] = inv[i - 1] * inv[i] % mod;}
}void dfs(int u,int fa){dp[u] = 1;mx[u] = a[u];mn[u] = 1e9;vector<pair<LL, LL>> ch;for(auto v:e[u]){if(v==fa)continue;dfs(v, u);if(dp[v]==0){dp[u] = 0;return;}mx[u] = max(mx[u], mx[v]);mn[u] = min(mn[u], a[v]);dp[u] = dp[u] * dp[v] % mod;ch.push_back({a[v], mx[v]});}if(a[u]>mn[u]){dp[u] = 0;return;}int c = ch.size();sort(ch.begin(), ch.end());for (int i = 0; i+1 < c;i++){if(ch[i].second>ch[i+1].first){dp[u] = 0;return;}}LL cnt = 1;for (int i = 0,j; i < c;i=j){j = i;while(j<ch.size()&&ch[j].first==ch[i].first)j++;cnt = cnt * f[j - i] % mod;}dp[u] = dp[u] * cnt % mod * inv[c] % mod;
}void solve()
{int n;cin >> n;for (int i = 1; i <= n;i++){cin >> a[i];e[i].clear();mx[i] = 0;dp[i] = 0;}for (int i = 1; i < n;i++){int u, v;cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}dfs(1, 0);cout << dp[1] << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);init(200000);int T;cin >> T;while (T--){solve();}
}