谢天意

题解

/ 注册

全部文章 / 题解（共53篇）

题解 | #数学考试#

题意给定一个长度为n的序列选择两段长度为k的子序列和的最大值有一个类似的题目，是选择两个点，思路是遍历，记录下过程中的最大值，答案便是最大值加上当前的数的最大值这题也类似，遍历过程中记录长度为k的最大值，答案是最大值加上当前区间取最大值重点是两段不能相交 #include<iostream...

尺取法前缀和

2021-04-09

0 518

题解 | #字符串#

题意给定一个字符串，问最短子序列能包含a到z字母思路尺取法，也叫双指针j往后找满足有26个字母的时候，i往前 #include<iostream> using namespace std; int a[30]; int check() { for(int i=1;i<...

双指针尺取法

2021-04-09

0 550

题解 | #毒瘤xor#

给定一个长度为n的序列，有m次操作，每次有一个l到r的区间，找出x使得l到r区间内的数异或x的和最大思路这种位运算的题基本都是考虑二进制来做，对区间操作，可以想到对点操作，也就是前缀和考虑对于每一位，是选1好还是选0好 #include<iostream> using namespac...

前缀和二进制枚举

2021-04-09

0 712

题解 | #拼数#

贪心题对于序列中的两个数，交换顺序不改变其他数的值，所以要选择两种顺序较大的那一个。直接a+b>b+a就行了写题解之前一时间没想出来这种解法，想的是比较最高位的数来排序，这其实也可以，但当位数不同时要考虑的情况其实也是上面的情况。 #include<iostream> #inclu...

贪心

2021-04-09

0 491

题解 | #纪念品分组#

题意有n件物品，每个背包最多可以装两件，求最少数量可以装下排序后在两端双指针即可，从最大的开始选，考虑能不能装下最小的，不能则它单独装一个，以此枚举。有一个问题，对于一个质量为m，有没有必要尽量选择和另一个能装满。其实没必要，举个例子，一组数据 1 3 5 7 9 一组最多为12，对于9 可以和...

排序贪心枚举

2021-04-08

0 481

题解 | #铺地毯#

题意有n次操作，每次操作选择一个区域，铺上一个毯子，给一个点，求最上面一个毯子的编号思路从最后一个往前枚举，枚举到的一定是最后一个铺上的 #include<iostream> using namespace std; struct node { int x1,x2,y1,y2...

枚举贪心暴力

2021-04-08

0 487

题解 | #[HNOI2003]激光炸弹#

题意很明确，一个图中有些点有权值，求矩阵覆盖权值最大很明显是二维前缀和，但是调了半天，细节还是要多考虑 #include<iostream> using namespace std; int a[6010][6010],sum[6610][6010]; int main() { ...

前缀和

2021-04-08

0 599

题解 | #明明的随机数#

题目要排序加去重 set完美满足这个要求 #include<iostream> #include<set> using namespace std; int main() { int n; cin>>n; set<int>a; ...

排序

2021-04-08

0 447

题解 | #校门外的树#

经典老题了，之前一直用线段树，直到知道了差分。。。题目是0到n都种了一个树，可以考虑偏移一位，1到n+1种了一个树l到r区间-1即可直接利用差分数组，求一遍前缀和即可得到原数组，等于1的代表没有被砍掉 #include<iostream> using namespace std; int...

差分

2021-04-08

0 498

题解 | #Protecting the Flowers#

题意有n头牛，每头牛有两个属性a,b 消灭这头牛要2a分钟，没被消灭的牛每分钟破环b个草草，求怎么排序会使得被破坏的草最少思路听了雨巨的课前只考虑两头牛的先后顺序，当时是从直觉判断贪心的正确，听了雨巨的课才知道，因为在整个序列中，交换两头牛对其他的牛没有影响，所以可以考虑根据两头牛的情况判断假设...

贪心

2021-04-08

0 504