CF
Problem - 54C - Codeforces
概率dp好题
转移公式：$$dp[i][j]=dp[i−1]j+dp[i−1][j−1]p_i$$
#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 = 1010;
double p[N];
double dp[N];LL calc(LL n){LL ans = 0, tmp = n, lst = 0;int cnt = 0;while(tmp){lst = tmp % 10;tmp /= 10;cnt++;}cnt--;LL x = 1;for (int i = 1; i <= cnt;i++){ans += x;x *= 10;}if(lst>1){ans += x;}else if(lst==1){ans += n - x + 1;}return ans;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;LL l, r;for (int i = 1; i <= n;i++){cin >> l >> r;LL c1 = calc(r) - calc(l - 1);p[i] = 1.0 * c1 / (r - l + 1);}int k;cin >> k;dp[0] = 1.0;for (int i = 1; i <= n;i++){for (int j = n; j >= 0;j--){//注意，0的时候也要考虑dp[j] = dp[j] * (1 - p[i]);if(j>0)dp[j] += dp[j - 1] * p[i];}}double ans = 0.0;for (int i = 0; i <= n;i++){if(i*100>=n*k)ans += dp[i];}cout << fixed << setprecision(10) << ans << endl;
}
Problem - 743D - Codeforces
树形dp好题
dp[u]：求 \(u\) 的所有子树（包括含有 u）的最大值
然后找 \(u\) 孩子的最大值和次大值，求答案即可
#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;
LL a[N], sum[N], dp[N];
int p[N];
vector<int> e[N];void dfs(int u,int fa){sum[u] = a[u];p[u] = fa;dp[u] = -1e18;for(auto v:e[u]){if(v==fa)continue;dfs(v, u);sum[u] += sum[v];dp[u] = max(dp[u], dp[v]);}dp[u] = max(sum[u], dp[u]);
}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];}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);LL ans = -1e18;for (int i = 1; i <= n;i++){LL mx1 = -1e18, mx2 = -1e18;for(auto v:e[i]){if(v==p[i])continue;if(dp[v]>mx1){mx2 = mx1;mx1 = dp[v];}else if(dp[v]>mx2){mx2 = dp[v];}}if(mx2!=-1e18){ans = max(ans, mx1 + mx2);}}if(ans==-1e18){cout << "Impossible\n";}elsecout << ans << endl;
}
Problem - 283B - Codeforces
记忆化搜索
这里要注意， \(x=1,x+i=i+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;
LL a[N], f[N][2];
int n;
bool vis[N][2];LL dfs(LL x,int i){if(x<=0||x>n)return 0;if(f[x][i]!=-1)return f[x][i];if(vis[x][i])return 1e18;vis[x][i] = 1;LL tmp;if(i==0){tmp = dfs(x + a[x], 1);}else{tmp = dfs(x - a[x], 0);}if(tmp!=1e18){f[x][i] = a[x] + tmp;}else{f[x][i] = 1e18;}return f[x][i];
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;for (int i = 2; i <= n;i++){cin >> a[i];}memset(f, -1, sizeof f);for (int i = 1; i <= n;i++){if(f[i][0]==-1)f[i][0] = dfs(i, 0);if(f[i][1]==-1)f[i][1] = dfs(i, 1);}for (int i = 1; i <= n-1;i++){if(f[i+1][1]==1e18){cout << -1 << endl;}else{cout << i + f[i + 1][1] << endl;}}
}
算法学习 01BFS
核心思想
-
适用场景：
- 图的边权只有两种情况：0 或 1。
- 经典例子：
- 迷宫中走到同类格子不花费，走到不同格子花费 1。
- 路径切换开关时花费 0 或 1。
-
使用双端队列
deque：- 当走到下一节点 不增加距离（权值为 0） 时，把它放到队列前面（
push_front）。 - 当走到下一节点 增加距离 1（权值为 1） 时，把它放到队列后面（
push_back）。 - 队头总是当前最短距离的节点出队 → 类似 Dijkstra 但不需要堆。
- 当走到下一节点 不增加距离（权值为 0） 时，把它放到队列前面（
-
时间复杂度：
- 每条边最多进出队一次 → O(V + E)。
- 比 Dijkstra 的 O((V+E)logV) 更快（当边权只有 0/1 时）。
在边权为0和1时，算是dijkstra的优化，时间复杂度从 \(O(n\log n)\) 变成 \(O(n)\)
双端队列_01bfs——附详解典例-CSDN博客
1、边权为0，放到队首。（从边权为0的边走，不增加消耗，得多走这样的边）
2、边权为其他，放到队尾。（增加消耗，少用）
（这样，队列前面的元素值一定比后面的元素值小，每次求队首元素来更新相连的点的距离，完美的替代了优先队列的功能！）
P4554 小明的游戏 - 洛谷
01BFS简单题
#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 = 510;
int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int a[N][N], n, m;
int dist[N][N], stx, sty, edx, edy;
bool vis[N][N];
char ch;void bfs(){memset(dist, 0x3f, sizeof dist);memset(vis, 0, sizeof vis);dist[stx][sty] = 0;deque<PII>q;q.push_front({stx, sty});while(!q.empty()){auto t = q.front();q.pop_front();int x = t.first, y = t.second;if(vis[x][y])//出队时要记得判断！！！continue;vis[x][y] = 1;//出队时标记！！！for (int i = 0; i < 4;i++){int xx = x + dx[i], yy = y + dy[i];int flag = 0;if(xx<0||xx>=n||yy<0||yy>=m||vis[xx][yy]){continue;}if(a[x][y]!=a[xx][yy])flag = 1;if(dist[xx][yy]>dist[x][y]+flag){dist[xx][yy] = dist[x][y] + flag;if(flag){q.push_back({xx, yy});}else{q.push_front({xx, yy});}}}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);while(cin>>n>>m&&n!=0&&m!=0){for (int i = 0; i < n;i++){for (int j = 0; j < m;j++){cin >> ch;if(ch=='@')a[i][j] = 1;elsea[i][j] = 0;}}cin >> stx >> sty >> edx >> edy;bfs();cout << dist[edx][edy] << endl;}
}
CF1063B Labyrinth - 洛谷
这居然是之前做过的题，01BFS理解之后做起来更轻松了
#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 = 2010;
char a[N][N];
bool vis[N][N];
struct node{int x, y, l, r;
};
int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int n, m, r, c, L, R, ans;void bfs(){deque<node> q;q.push_front({r, c, L, R});while(!q.empty()){node now = q.front();q.pop_front();int x = now.x, y = now.y;if(vis[x][y]||now.l<0||now.r<0){continue;}vis[x][y] = 1;ans++;for (int i = 0; i < 4;i++){int xx = x + dx[i], yy = y + dy[i];if(xx<=0||xx>n||yy<=0||yy>m||vis[xx][yy]||a[xx][yy]=='*')//注意，看清楚continue;if(i==0||i==1){//上下q.push_front({xx, yy, now.l, now.r});//优先处理//这样使得该点出队时，往左和往右数目是最多的时候}else if(i==2){//左q.push_back({xx, yy, now.l - 1, now.r});}else if(i==3){q.push_back({xx, yy, now.l, now.r - 1});}}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> m >> r >> c >> L >> R;for (int i = 1; i <= n;i++){for (int j = 1; j <= m;j++){cin >> a[i][j];}}bfs();cout << ans << endl;
}
第三题P4667 [BalticOI 2011] Switch the Lamp On (Day1) - 洛谷