CF
Problem - 1692H - Codeforces
一道很好的dp思维题
#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;
int a[N], lst[N];
int dp[N], l[N];void solve()
{int n;cin >> n;map<int, int> mp;for (int i = 1; i <= n;i++){cin >> a[i];lst[i] = mp[a[i]];mp[a[i]] = i;}int ans = 0, pos = 0;for (int i = 1; i <= n;i++){if(dp[lst[i]]-(i-lst[i]-1)>0){dp[i] = dp[lst[i]] - (i - lst[i] - 1) + 1;l[i] = l[lst[i]];}else{dp[i] = 1;l[i] = i;}if(dp[i]>ans){ans = dp[i];pos = i;}}cout << a[pos] << " " << l[pos] << " " << pos << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - 1843F1 - Codeforces
简单树形dp
或者说树上的前缀 DPmx1,mn1 + 最大子段和 DPmx,mn
注意：
mx1,mx数组初始化
#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;
int mx1[N], mn1[N];//以i结尾
int mx[N], mn[N];//根到i中的最大和最小void solve()
{int n;cin >> n;for (int i = 1; i <= n;i++){mx1[i] = mn1[i] = mx[i] = mn[i] = 0;}mx[1] = mx1[1] = 1;//注意int idx = 1;//编号int fa, x;for (int i = 1; i <= n;i++){char ch;cin >> ch;if(ch=='+'){cin >> fa >> x;mx1[++idx] = max(mx1[fa] + x, x);mn1[idx] = min(mn1[fa] + x, x);mx[idx] = max(mx[fa], mx1[idx]);mn[idx] = min(mn[fa], mn1[idx]);}else{int u, v, k;cin >> u >> v >> k;if(mn[v]<=k&&k<=mx[v]){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();}
}
Problem - 626D - Codeforces
概率dp好题
#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 = 2010;
int a[N];
double dp[5][5010];int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 1; i <= n;i++){cin >> a[i];}sort(a + 1, a + 1 + n);int tot = 0;for (int i = 1; i <= n;i++){for (int j = i + 1; j <= n;j++){if(a[j]>a[i]){//保证严格大于dp[1][a[j] - a[i]]++;tot++;}}}for (int i = 1; i <= 5000;i++){dp[1][i] /= tot;//计算概率}for (int i = 1; i <= 5000;i++){for (int j = 1; j <= 5000;j++){dp[2][i + j] += dp[1][i] * dp[1][j];//重要一步}}double ans = 0.0;for (int i = 1; i <= 5000;i++){for (int j = i + 1; j <= 5000;j++){ans += dp[2][i] * dp[1][j];//二轮概率*第三轮大于前两轮之和的概率}}cout << fixed << setprecision(10) << ans << endl;
}
天梯赛补题
L2-047 锦标赛 - 团体程序设计天梯赛-练习集
#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;
int win[20][1 << 18];//记录赢家编号
int ans[1 << 18];
int lost[20][1 << 18];//记录输家能力值int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int k;cin >> k;for (int i = 1; i <= k;i++){for (int j = 0; j < (1 << (k - i));j++){//每一轮输家cin >> lost[i][j];if(i==1){//对第一轮特殊处理，假设左边输ans[j << 1] = lost[i][j];win[i][j] = j << 1 | 1;}else{if(lost[i][j]<lost[i-1][j<<1]&&lost[i][j]<lost[i-1][j<<1|1]){cout << "No Solution\n";return 0;}else if(lost[i][j]>=lost[i-1][j<<1]){//左边输满足，就让左边输//对于这一轮 j 场比赛//比赛选手编号分别为win[i-1][j<<1](左),win[i-1][j<<1|1](右)ans[win[i - 1][j << 1]] = lost[i][j];win[i][j] = win[i - 1][j << 1 | 1];}else{ans[win[i - 1][j << 1 | 1]] = lost[i][j];win[i][j] = win[i - 1][j << 1];}lost[i][j] = max(lost[i][j], max(lost[i - 1][j << 1], lost[i - 1][j << 1 | 1]));//更新子树能力最大值}}}int w;cin >> w;if(lost[k][0]>w){cout << "No Solution\n";return 0;}ans[win[k][0]] = w;for (int i = 0; i < (1 << k);i++){if(i!=0)cout << " ";cout << ans[i];}
}