文章目录  D Candy Chain  题意 分析：  参考代码     D Candy Chain 题意 Margot 有一个 长度为字符串     a    a   a，给定     n    n   n个子串，每一个子串一个价值      w   i     w_i   wi​，从原串中取出一个子串后，原串的左右结合组合成一个新的串，并且得到改子串的价值      w   i     w_i   wi​。 问能取到的最大价值 分析： claris dp+ trie 树 trie 树：  先将这n个子串加到trie树中，并且将末尾节点的价值设为改子串的价值，并且反转加进去  dp状态  ...

文章目录  hiho1143 && hiho 1151&&1033 骨牌覆盖 V2  骨牌覆盖问题 问题描述 分析：  状态压缩  参考代码    hiho1143 && hiho 1151&&1033 骨牌覆盖 V2 骨牌覆盖问题 问题描述 在     m   ∗   n    m*n   m∗n的一个长方形方格中，用一个1*2的骨牌排满方格。问有多少种不同的排列方法。     (   n   <   =   5   )    (n <= 5)   (n<=5) 题目 2个数M N，中间用空格分...

文章目录  图论建图  初衷 例题    图论建图 初衷  搜集各种各样的建图技巧或者建模想法 例题  1 G Cordon Bleu 题意： n个人，m瓶酒，n个人和m瓶酒各有一个位置，现在要用这n个人将这些酒全部运送到酒店R，不必用上所有的人，每一千米的费用是固定的c，问至少费用是多少？ 分析：建一个超级源点s，向m瓶酒分别连一个容量为1，费用为0的点，然后将这m瓶酒和(n个人，酒店)分别连边，权值 (代表酒->人->酒店） 和(酒->酒店-> 酒) ，然后每个人连一条到汇点容量为1，费用为0的边，酒店则连(n-1) 条这样的边 2 河南省cccp省赛F题

文章目录  ACM-ICPC北京赛区2018  A Jin Yong’s Wukong Ranking List B Heshen's Account Book F Frog and Portal I Palindromes    ACM-ICPC北京赛区2018 A Jin Yong’s Wukong Ranking List #include<bits/stdc++.h> using namespace std; const int maxn = 50; vector<int> G[maxn]; bool yes; bool dfs(int node,int fa)...

文章目录  (SWERC 2017)  A Cakey McCakeFace C Macaron  题意： 分析:  D Candy Chain E Ingredients  题意 分析  F Shattered Cake J Frosting on the Cake     (SWERC 2017) A Cakey McCakeFace O(N^2) 求出所有的差值即可，map 存下 #include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 2000+10; LL a[m...

文章目录  2017-2018 ACM-ICPC Southeastern European Regional Programming Contest (SEERC 2017)  A Concerts J Cunning Friends K - Escape Room G - Robots D - Harry Potter and The Vector Spell F - Binary Transformations    2017-2018 ACM-ICPC Southeastern European Regional Programming Contest (SEERC 2017) A C...

文章目录  D Harry Potter and The Vector Spell  分析： 证明    D Harry Potter and The Vector Spell 分析： 并查集合并，在同一并查集的所有点都可以两两组合形成一个列，所以如果两个点在同一个并查集里，不会产生新的秩，否则秩加1 证明 递推证明 当n= 2的时候，共有三个不同的点，显然成立 假设当k的时候成立， 加入新的（a,b)，其中a并查集中，b不在并查集中 已知：k个点与a 点 的列都可以组合出来 那么a,b 这个列加入并查集，那么也就可以组合出来这k个点和b的列 原命题成立  const int maxn = 1...

文章目录  F. Robots  题意: 分析：    F. Robots 题意:      0   ,   1   ,   .   .   n   −   1    0,1,..n-1   0,1,..n−1 个路口，每一个路口都有一个红绿灯，按下红灯会走向       a   0    ,    a   1    ,    a   2    .   .    a    n   −   1      a_0,a_1,a_2..a_{n-1}   a0​,a1​,a2​..an−1​,按下绿灯会走向       b   0    ,    b   1    ,    b   2    ,   ...

文章目录  2018 ACM-ICPC 南京站  A Adrien and Austin D. Country Meow Problem G. Pyramid Problem I. Magic Potion Problem J. Prime Game Problem K. Kangaroo Puzzle    2018 ACM-ICPC 南京站 A Adrien and Austin 这是https://vjudge.net/contest/255624#status//M/0/ 的简化  if(K == 1) printf("%s\n",(N&1)?"A...

文章目录  Wannafly挑战赛28 msc的宠物  题意: 分析:  状态： 状态转移:  参考代码    Wannafly挑战赛28 msc的宠物 题意: 给定一棵树，树上每个节点有权值，要求删除最多k条边使得所有联通块的最大值和最小的差最大的最小 分析: 最小化最大值，很明显是二分最大的差值D了 转化一下题目其实就是将树上的节点分成k个联通块，使得所有联通块的最大值和最小的差最大的最小。 状态：  f[x] 表示至少删除F[x] 个才能使得x子树差值不超过D g[x][u] 表示至少删除g[x][u] 个才能使得子树最大值为a[u]  状态转移: 设y是x的子节点  如果 a[y] &...

Wannafly挑战赛28 msc的宠物 题意: 给定一棵树，树上每个节点有权值，要求删除最多k条边使得所有联通块的最大值和最小的差最大的最小 分析: 最小化最大值，很明显是二分最大的差值D了转化一下题目其实就是将树上的节点分成k个联通块，使得所有联通块的最大值和最小的差最大的最小。 状态：  f[x] 表示至少删除F[x] 个才能使得x子树差值不超过D g[x][u] 表示至少删除g[x][u] 个才能使得子树最大值为a[u]   状态转移: 设y是x的子节点  如果 a[y] <= a[u] <= a[y]+D,g[x][u] = min(f[y]+1,g[x][u]);（直接...

B msc 和 mcc 题意： 对于一个字符串A，查询里面含有两个不重复子序列序列msc，mcc的子串个数 分析： 经过打表排除发现能够包含以下子序列的字符串都可以满足条件 char ch[10][100] = {"mccmsc","mcmcsc","mcmscc","mmccsc","mmcscc","mmsccc","mscmcc","msmccc"};  所以对于A的每一个位置i,找到最小的j,使得A[i,j] 包含上述子序列中的...

文章目录  Nuts for nuts.. UVA - 10944  题意： 分析： 参考代码    Nuts for nuts… UVA - 10944 题意： n*m的方格中，有一个起点和num个核桃，问把所有的核桃都取了，然后回到原地的最小步数，可以往八个方向移动 分析： 先把起点和核桃都从图中抠出来，然后两两之间的距离是     M   a   p   [   i   ]   [   j   ]   =   m   a   x   (   x   [   i   ]   −   x   [   j   ]   ,   y   [   i   ]   −   y   [   j   ] ...

文章目录  bzoj 树上染色  题意： 分析：    bzoj 树上染色 题意： 给定一棵n个点的树，把其中k个染成黑色，定义价值为黑色节点两两之间的距离和+白色节点两两之间的距离，求最大价值 分析： 树上dp typedef pair<LL,LL> P; LL N,K; const LL maxn = 2000+10; std::vector<P> G[maxn]; LL size[maxn]; LL dp[maxn][maxn]; LL tmp[maxn]; void dfs(LL node,LL fa){ // fill(dp,dp+N+1,) size[nod...