Decision`s blog

题目大意：在$x$轴的非负区域，有长度为$n$的路，需要在这条路上铺设管道；如果在某个位置是十字路口的话，需要将这个位置的管道高度铺设在$y = 2$的位置上面，而在非十字路口的位置，可以铺设在$y = 1$的位置，也可以铺设在$y = 1$的位置，而不同高度的情况下需要对应高度的管道架；设一单位的管道需要的费用是$a$，一单位管道架需要的费用是$b$，求铺设到终点所需的最小费用 被B题卡了快一个小时才看C题。。满足最优子结构和无后效性就是DP了这次又是写出了C的时候没写出B呢。。。设$f_{i,j}$为铺设到$i$位置的时候高度为j的最小花费那么可以得到转移方程在$s_i$为1的时候：$$\begin{cases}f[i][0] = INF\f[i][1] = min(f[i-1][0] + 2a,f[i-1][1] + a) + 2b\\end{cases}$$在$s_i$为0的时候：$$\begin{cases}f[i][0] = min(f[i-1][1] + 2a,f[i-1][0] + a) + b\f[i][1] = min(f[i-1][0] + 2a,f[i-1...

题目大意：给出两个$n \cdot m$的矩阵$A$和$B$,一开始矩阵$B$全为0，每次可以选定一个坐标$(x,y)(1 \le x < n、1 \le y < m)$，将$(x,y)、(x,y + 1)、(x + 1,y)、(x + 1,y + 1)$都变成1，求将矩阵$B$变为$A$的最小步数，并输出所有的操作的坐标。 这个思维题又把我卡死了，C题都写得出来但是我写不出这个B，结束前3分钟才给A掉然后没时间写别的了。。要操作的次数最少，也就是说每次操作要保证改变的0的数量最多把一个0的位置变成1，假设这个坐标是$(x,y)$，那么可以通过修改$(x - 1,y - 1)、(x - 1,y)、(x,y - 1)、(x,y)$这四个位置来达到那么每次直接扫描一下$B$中是0但$A$中是1的位置，如果操作的区域中在$A$中没有0，就可以求出一个能使得这次操作最大化的操作位置来进行操作显然时间复杂度是$O(nm)$的，然后我这里还带了一些常数，但是影响不大 这一场从$\Delta$-80+在最后3分钟拉回来。。最后涨了一分。。。（我还真是个弟弟。。思维题必杀我 1234...

A - Choose Two Numbers给出两个数组，长度分别为$ n、m(1 \le n \le 100、1 \le m \le 100)$，找出两个分别属于两个数组的数，使得它们的和不在两个数组里 暴力 裸暴力，手滑了两发白给。。 123456789101112131415161718192021int n,m;int a[300],b[300];bool mp[1000];int main() { mst(mp,0); ios::sync_with_stdio(0); cin>>n; for(int i = 1;i <= n;i++) cin>>a[i],mp[a[i]] = 1; cin>>m; for(int i = 1;i <= m;i++) cin>>b[i],mp[b[i]] = 1; for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { ...

div3都能给我打掉分，我真的是个菜狗了。。 A - Nearest Interesting Number 给出一个数$ n $问大于等于它的哪个数的每个位相加起来和是4的倍数 枚举 123456789101112131415161718int a;int main(){ cin >> a; for(int i = a;i <= 2000;i++){ int tmp = i; int x = 0; while(tmp){ x += tmp % 10; tmp /= 10; } if(x % 4 == 0){ cout<<i<<endl; break; } } return 0;} B - Equalize Prices 给出一个数列$a_i$,问能不能找到一个尽量...

A - qh与复读机I A、每次按顺序给出$ n $个字符串，求出每个字符串是前面多少个字符串的前缀和后缀 tire树因为题面给定数据范围$\sum |S_i| < 1e6$，也就是说如果建一棵树的话结点数是不会超过这么多的，而且遍历的时候也是，那么考虑正序和逆序建树，每次建树的同时到达最后一个结点返回当前结点已经记录的单词数量，也就分别对应了前缀和后缀时间复杂度$O(n)$ 123456789101112131415161718192021222324252627282930313233343536373839404142#define maxn 1000007struct Node{ int child[26]; int sum; void init(){ for(int i = 0;i < 26;i++) child[i] = 0; sum = 0; }}Tree[2][maxn];int cnt1 = 0,cnt2 = 0;int insert(bool statu,const string& s)...

A - 迷宫 给出一个带权有向图，翻转一条边的代价是其权重，求出翻转边后图中无环的最小代价 二分 拓扑判环一开始只能想到要让图中没有环，但是想不清楚怎么操作，于是等到题解emmmm考虑对于要改变的边，相当于删去之后反向加回来，那么代价就是边里面权值最大的二分权值，权值越大的可以改变的边越多，二分最少的代价使得不存在环即可 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253int n,m;int u,v;ll w;int top[maxn],in[maxn];vector<Edge> G1;vector<int> edges[maxn];bool check(ll now){ int cnt = 0; for(int i = 1;i <= n;i++) edges[i].clear(); mst(in,0); mst(top,0); for(int i = 0;i < m;i++){...

A - oy环游世界 A、给定n个点，求出从起点开始遍历到最后一个点的最短曼哈顿距离 状态压缩n最多有17个点，可以考虑将17个点压缩到一个int里面，这个时候可以考虑一个状态$f _ {S,i}$，表示遍历了集合S后以i为终点的路径的最短的距离，状态转移方程为:$$f_{S,j} = min(f_{S,j},f_{S_j,j + dist(j,k)})$$$S_j$表示集合$S$除去点$j$后的集合 12345678910111213141516171819202122232425262728293031323334struct Point{ ll x,y; ll operator - (const Point& a) const{ return abs(x - a.x) + abs(y - a.y); }}all[20];ll n,s;ll f[1<<20][20];int main(){ cin>>n>>s; mst(f,0x3f3f3f); for(ll i = 0;i &...

A、对一个有n个数的区间进行四种操作，该区间内每个数的初始值为$ a_i $，在输入的第二行进行输入 op = 1时，输入三个数$ L、R、k $,表示对区间$ [L,R] $的数全部加上$ k $op = 2时，输入三个数$ L、R、k $,表示对区间$ [L,R] $的数全部乘上$ k $op = 3时，输入三个数$ L、R、k $,表示对区间$ [L,R] $的数全部变成$ k $op = 4时，输入两个数$ L、R $,要求输出区间方差乘上样本数的平方后的结果 线段树 lazy标记 答案最后要求输出的是$ n^2S^2 $ 那么把方差的公式展开：$$\begin{align}n^2S^2&= n \sum ^ {n} _ {i = 1}(X_i - \bar X)^2 \&=n\sum ^ {n} _ {i = 1} (X_i ^ 2 - 2 X_i \bar X + \bar X^2) \&=n\sum ^ {n} _ {i = 1} X _ i ^2 - 2n\bar X \sum ^ {n} _ {i = 1}X_i + n\sum...

相关概念 对于字符串$ S $,其前缀为$ pre(s,r) = s[0…r] $,后缀为$ suf(s,r) = s[|s| - r - 1 …..|s|] $，其中$ 0 < r < |s| $如果对于字符串有$ pre(s,r) = suf(s,r) $，则称$ pre(s,r) $是该字符串的$ border $,此时可以得到字符串的一个周期为$ |s| - r $ 相关算法及数据结构KMP算法 对于模式串和匹配串在一个字符串中匹配另外一个字符串的时候，如果一位一位的匹配，在发现某个字符不一样的时候将匹配串进行右移进行匹配，算法的效率是十分低下的，这个时候可以考虑在匹配失败的时候直接移动到匹配失败的位置那么就需要求一个$ next $数组，即字符串在该位置已匹配的字符数量‘$ next $数组是当前位置之前的字符串字串前缀与后缀的最大长度 求一个字符串的next数组，需要将其本身作为匹配串，从第2位开始匹配，这里令$ nest[0] = 0 $，然后依次匹配求出该数组 123456789101112131415char s[len];int next[le...

A. Sea Battle给出四个整数w1,h1,w2,h2 计算在方格上围出w1h1与w2h2的方形所需要的方块的数量 数学显然ans = (max(w1,w2)+h1+h2+2) * 2，凹入的部分可以换到方形凸出的地方，使得两个方形被围住 12345678int w1,h1,w2,h2,ans;int main(){ cin>>w1>>h1>>w2>>h2; ans = (max(w1,w2)+h1+h2+2) * 2; cout<<ans<<endl; return 0;} B. Draw!给出n个数对，对应某个时刻的比分，输出最大的平局的次数6 对于数对(a,b)和数对(c,d)，要平局次数最大，则中间可能出现(x,x)是最好的，而x小于c,d中最小的，大于a,b中最大的，所以取平均值，如果a，b不相等，则可能出现x = min(a,b)的情况，有1的贡献，所以每次输入的时候，ans = ans + max(0,min(c,d) - max(a,b) + (a!=b))...