程序蒟蒻

分类

题解(20)

/ 注册

全部文章（共20篇）

【每日一题】8月11日题目精讲—矩阵消除游戏

思路：先枚举行，在确定行的基础上去贪心列。用01字符串去枚举，这个还是头会见，毕竟菜的扣脚。思路不是很难懂。 #include<iostream> #include<string> #include<math.h> #include&l...

贪心

2020-08-25

0 656

【每日一题】8月7日题目精讲—双栈排序

看完题解才发现其实就是二分图匹配，好巧妙。。。。被学弟秀了一脸 #include <bits/stdc++.h> using namespace std; int a[100005]; vector<int> an...

2020-08-23

0 610

【每日一题】8月6日题目精讲—追债之旅

思路：给最短路的dist数组加一维，表示现在是第几天（已经进过了几条边）把最短路松弛操作改为：if (dist[x][k+1] > dist[y][k] + w[x][y]) dist[x][k+1] = dist[y][k] + w[x][y];即可。模板是spfa #...

spfa最短路

2020-08-20

0 550

【每日一题】8月4日题目精讲—购物

思路：首先我们每天肯定都是按照价格从低到高买糖果，所以决策只需要关注当前天买了多少个。 f[i][j]代表前i天已经买了j颗糖果的最小花费，枚举第i天买了多少糖果。 f[i][j] = min(f[i-1][k] + sum[i][i-k] + (j-k)*(j-k)); （k从i-m到i-...

dp

2020-08-19

0 745

【每日一题】8月3日题目精讲—小A的最短路

思路：如果没有缆车的话，就是一个利用LCA求树上任意两点距离的板子题。（有了缆车，其实还是板子题……）有了一个缆车之后，无非就算考虑一下要不要坐缆车以及怎样坐缆车，所以：不坐缆车xy的距离就是原来的距离dist(x,y)，坐缆车的话要考虑是x到u点坐缆车，还是到v点坐缆车，即dist(x,...

lca

2020-08-17

1 640

【每日一题】7月31日题目精讲—兔子的区间密码

https://ac.nowcoder.com/acm/problem/20860 思路：要想让异或之后的结果最大，肯定从高位开始就要尽量大，也就是两个数的高位尽量不同。如果lr的二进制位数不同，首先高位补0补齐，然后看我们能否在r的最高位取1的时候r的最高是不是不一样（如果一样，那...

位运算

2020-08-15

3 703

【每日一题】7月30日题目精讲—Xor Path

https://ac.nowcoder.com/acm/problem/20857?&headNav=acm 思路： #include<iostream> #include<string> #include<math.h...

2020-08-14

1 591

【每日一题】7月29日题目精讲—Max Power

https://ac.nowcoder.com/acm/problem/20663 思路：首先，每一列如果要学应该是学一个从上到下的连续区间，第二，当前这一列最多比右边的那一列多学一个——所以，考虑从右往左一列一列转移： f[i][j][k]表示前i列一共选了k个技能学，第i列选了连续...

dp

2020-08-14

1 594

【每日一题】7月28日题目精讲—涂色PAINT

https://ac.nowcoder.com/acm/problem/19909 思路： f[i][j]表示把i到j的区间涂好的最少次数当i和j颜色一样——可以认为i是涂[i+1,j]的时候顺便涂上的，或者j是涂[i,j-1]的时候顺便涂上的。所以f[i][j]= min(f[i+1][j...

dp

2020-08-11

1 770

【每日一题】8月10日题目精讲—排座椅

题目：https://ac.nowcoder.com/acm/problem/16618 思路：分开行与列分开计算，贪心即可，记得存一下位置并且输出顺序 #include<iostream> #include<string> #include<math.h&g...

贪心

2020-08-11

1 729