个人建站软件,可以做婚礼鲜花布置的网站,建立网站建站程序,做酱菜网站整体概述
难度#xff1a;1600 →\rightarrow→ 2200 →\rightarrow→ 2600 P6005 [USACO20JAN] Time is Mooney G 标签#xff1a;DP 前置知识#xff1a;链式前向星 难度#xff1a;绿 1600
题目描述#xff1a; 输入格式#xff1a; 输出格式#xff1a; 样例输…整体概述
难度1600 →\rightarrow→ 2200 →\rightarrow→ 2600 P6005 [USACO20JAN] Time is Mooney G 标签DP 前置知识链式前向星 难度绿 1600
题目描述 输入格式 输出格式 样例输入
3 3 1
0 10 20
1 2
2 3
3 1样例输出
24解题思路 发现数据范围很小考虑可否 DPDPDP。 定义 dpi,jdp_{i,j}dpi,j 表示第 iii 天到达 jjj 城市的最大收益则单次更新可以暴力枚举每个节点更新其相邻的节点复杂度只为 O(M)O(M)O(M)。 并且发现数据给定 mi≤1000m_i\le 1000mi≤1000则 TTT 不可能超过 100010001000 否则 c∗T∗Tc*T*Tc∗T∗T 一定大于总收益。所以总复杂度为 O(1000⋅M)O(1000·M)O(1000⋅M)。
完整代码
#includebits/stdc.h
#define Size(x) ((int)(x).size())
#define int long long
using namespace std;
const int N 1e35,M 2e35,INF 0x3f3f3f3f;
int n,m,c,val[N],ha[N],idx;
struct Edge{int from,to,ne;}edge[M];
inline void ins(int u,int v){edge[idx] {u,v,ha[u]}, ha[u] idx;
}
int dp[N][N];
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin n m c;for(int i1;in;i) cin val[i];for(int i1,u,v;im;i){cin u v;ins(u,v);}for(int i0;iN;i) for(int j0;jN;j) dp[i][j] -INF;dp[0][1] 0;int ans 0;for(int t0;t1000;t){for(int u1;un;u){if(dp[t][u]-INF) continue;for(int iha[u];i;iedge[i].ne){int v edge[i].to;dp[t1][v] max(dp[t1][v],dp[t][u]val[v]);}}ans max(ans,dp[t][1] - c*t*t);}cout ans;return 0;
}P10391 [蓝桥杯 2024 省 A] 零食采购 标签重链剖分 前置知识线段树、状态压缩 难度蓝 2200
题目描述 输入格式 输出格式 样例输入
4 2
1 2 3 1
1 2
1 3
2 4
4 3
1 4样例输出
3
2解题思路 题目很简单给出一棵树每个节点有一个权值 1≤c≤201\le c\le 201≤c≤20大量查询每次询问两个节点 uuuvvv 在树上简单路径上经过的所有店的权值类型个数。 我们发现 ccc 很小可以压缩到 intintint 的每一个位上那么原问题转化为询问树上简单路径上的权值的 或和那么就是裸的重链剖分的板子题了线段树只需要支持单点修改区间查 或和 即可。
完整代码
#includebits/stdc.h
#define Size(x) ((int)(x).size())
#define int long long
using namespace std;
const int N 1e55;
int n,q,ha[N],idx,a[N];
struct Edge{int to,ne;}edge[N1];
inline void ins(int u,int v){edge[idx]{v,ha[u]}, ha[u] idx;
}
int fa[N],siz[N],son[N],dep[N];
inline void dfs1(int u,int par){fa[u] par, dep[u] dep[par]1;siz[u] 1;for(int iha[u];i;iedge[i].ne){int v edge[i].to;if(v par) continue;dfs1(v,u), siz[u] siz[v];if(siz[son[u]] siz[v]) son[u] v;}
}
int dfn[N],back[N],Time,top[N];
inline void dfs2(int u,int Top){top[u] Top;dfn[u] Time, back[Time] u;if(!son[u]) return;dfs2(son[u],Top);for(int iha[u];i;iedge[i].ne){int v edge[i].to;if(v ! fa[u] v ! son[u]) dfs2(v,v);}
}
#define ls ((u)1)
#define rs ((u)1|1)
#define mid (((l)(r))1)
int tr[N2];
inline void up(int u){tr[u] tr[ls] | tr[rs];
}
inline void build(int l,int r,int u){if(l r){tr[u] 1a[back[l]];return ;}build(l,mid,ls), build(mid1,r,rs);up(u);
}
inline int queryOR(int x,int y,int l1,int rn,int u1){if(x l r y) return tr[u];int ans 0;if(x mid) ans | queryOR(x,y,l,mid,ls);if(y mid) ans | queryOR(x,y,mid1,r,rs);return ans;
}
inline int query(int u,int v){int ans 0;while(top[u] ! top[v]){if(dep[top[u]] dep[top[v]]) swap(u,v);ans | queryOR(dfn[top[u]],dfn[u]);u fa[top[u]];}if(dep[u] dep[v]) swap(u,v);ans | queryOR(dfn[v],dfn[u]);return ans;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin n q;for(int i1;in;i) cin a[i];for(int i1,u,v;in;i){cin u v;ins(u,v), ins(v,u);}dfs1(1,0);dfs2(1,1);build(1,n,1);while(q--){ int u,v; cin u v;int res query(u,v), cnt 0;while(res) res res-1, cnt 1;cout cnt \n;} return 0;
}P7519 [省选联考 2021 A/B 卷] 滚榜 标签状压DP 前置知识差分数组 难度紫 2600
题目描述 输入格式 输出格式 样例输入
3 6
1 2 16 50
4 7 9 3 0 311 300
6 8 8 12 0 11 6 1 0 15 5样例输出
59630140983
解题思路 发现题目的数据范围很小求总排名方案书肯定为状压 DPDPDP。 状压 DPDPDP 肯定有一维 O(2n)O(2^n)O(2n) 表示已经公布了哪几个人本题的 bib_ibi 要求单调不降肯定需要一维 O(n)O(n)O(n) 记录上公布的人需要一维 O(m)O(m)O(m) 记录已经用了多少道题。 接着考虑如何转移对于每个状态 sss枚举最后一个人是 iii暴力枚举下一个人是 jjj假设 iii 要变成第一所需的过题数为 ddd那么由于 bib_ibi 需要单调不降后续所有的人都需要过 ddd 到题所以转移需要消耗 cnt∗dcnt*dcnt∗d 道题其中 cntcntcnt 为还没有被公布的人数。 最后暴力统计所有答案即可总复杂度 $O(2n·n2·m)。 我们可以预处理一个数组 sis_{i}si 表示 iii 超过所有人所需的最小的 bib_ibi再预处理一个数组 cnticnt_icnti 表示状态为 iii 时还没有公布的人数为 cnticnt_icnti那么便可以很方便地转移了。
完整代码
#includebits/stdc.h
using namespace std;
const int N 13, M 505;
int n,m,up,dp[1N][N][M],a[N],d[N][N],s[N],cnt[1N];
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin n m; up 1n;for(int i0;in;i) cin a[i];for(int i0;in;i) for(int j0;jn;j){if(j i) d[i][j] max(0,a[j]-a[i]1);else d[i][j] max(0,a[j]-a[i]);}for(int i0;in;i) for(int j0;jn;j) s[i] max(s[i],d[i][j]);cnt[0] n;for(int i1;iup;i) cnt[i] cnt[i1] - (i1);for(int i0;in;i) if(n*s[i] m) dp[1i][i][n*s[i]] 1;for(int s0;sup;s){for(int i0;in;i) if((si)1){for(int j0;jn;j) if(!((sj)1)){for(int td[j][i]*cnt[s];tm;t){dp[s|(1j)][j][t] dp[s][i][t-d[j][i]*cnt[s]];}}}}long long ans 0;for(int i0;in;i) for(int j1;jm;j) ans dp[up-1][i][j];cout ans;return 0;
}
