Rikkar

思维

1024程序员节(1) C++(3) codeforces(5) dp(3) game(1) git(1) java(4) javaweb(2) math(14) maven(2) mysql(1) VS(2) 二分(5) 区域赛(1) 图(2) 数据结构(2) 新手入门(1) 暴力(3) 未归档(6) 板子(7) 构造(2) 模拟(3) 比赛(1) 笔记(1) 算法(27) 蓝桥杯(20) 规律(1) 贪心(1) 资料(1) 面试题集(1) 项目(1) 题解(44)

/ 注册

全部文章 / 思维（共30篇）

C. Strange Birthday Party（贪心）

题目题意：我有n个朋友，商店有m种商品，这m种商品按序号价格从小到大排列，对于每一个朋友我给出一个序号k，我可以直接给朋友序号k的商品价格的金钱或给朋友买一个序号小于k的商品，且每种商品最多只能买一次，问我需要花费的最少金钱？思路：将朋友的序号从大到小排序，由题意序号大的商品花费的金钱一定大...

2021-12-18

0 425

1475E - Advertising Agency（dfs、dp）

题目思路：对于一个结点有四种情况00 11 10 01，其中00 11我们不需要重新交换。然后因为每个子树都可用其父亲及往上的结点的值交换。故我们从上到下更新每一个结点的交换值，其值为min(自己，父亲)。然后从1开始dfs，先深入到最底下结点,让下面的结点先进行交换（因为越往下的结点花费越少）...

2021-12-18

0 427

1478C Nezzar and Symmetric Array (构造)

题目思路：首先来看一下这个距离是怎么计算的 -4 -3 -2 -1 0 1 2 3 4 不难发现4到3和-3的距离和=2 * 4 到-2 2到-1 1的距离和也都为2 * 4，在此可以发现规律一个较大的数到两个较小的数的距离和等于其自身二倍。观察0 1 2 -1 -2…到4 -4的距离和为都为2...

2021-12-18

0 439

D - AB Graph (构造、图)

题目思路：分为两种情况： 1.当m为奇数时，直接12121212…构造出的一定是回文。 2.当m为偶数时，可以知道n>=3时一定可以构造出。证明如下：当1，2，3三个点中出现来回字母一样，只需两个点不断循环即可。当无上述情况，来回必然是a,b交叉，因此我们一定可以找到如下的图。其实...

2021-12-18

0 387

1368 D. AND, OR and square sum (贪心、位运算)

题目思路：看一个例子对于两个二进制数 1100101 0100100 AND结果：0100100 OR结果：1100101 如果两个二进制位都为1或0，AND OR 中结果不变还是1或0，如果一个是0 一个1，就会把1转到OR结果中AND中的那个位变为0。我将这个过程看作是一个让1往一个数(O...

2021-12-18

0 298

C. Minimum Ties (构造)

题目当n为奇数，构造第一人获胜情况前(n-1)/2项为1，后(n-1)/2项为-1，其余人的获胜情况就是前一人往后滚动一位如：n=5 第一人对第二三四五人的情况 1 1 -1 -1 第二人对第一三四五人的情况 -1 1 1 -1 第三人对第一二四五人的情况 -1 -1 1 1 第四人对第...

2021-12-18

0 398

E. Accidental Victory （思维、二分）

题目思路：首先将数组排个序，容易知道要看一个数能不能成为冠军，其实就是将这个数从小到大不断与比他小于等于的数合并相加如果最终能够合并为一个数则其有成为冠军的机会。在这我们先看看暴力的思路，就是遍历每一个数然后让它与最小的数开始相加直到最终它不能再和后面的数相加（前面所有的总和都比后面的某个数...

2021-12-18

0 365

D. Irreducible Anagrams (思维、前缀和、构造)

题目题意：一个字符串如果只是其中字符顺序被打乱则称其和原字符串相互为字谜。对于两个互为字谜的字符串，两个字符串按相同的位置分割开成为n(n>=2)个小串，然后每个小串都互为字谜，则称这两个字符串是互为可还原的，现在给我们一个字符串，再给出q次问询，每次问询给出一个区间，要我们判断区间内的字...

2021-12-18

0 373

1438C - Engineer Artem （构造）

题目思路：如横纵坐标相加为奇数则将对应位置的数变为奇数+1或不加，如横纵坐标相加为偶则将对应位置数变为偶数。这题我觉得要培养一种感觉，看到一个题目，它给了什么条件要按给的条件那个方向去多思考一下，就像本题说可以加一或不加，那么我们想想加一其实比较容易想到的就是改变奇偶性。而有些题它给了一些数...

2021-12-18

0 316

C. Maximum width (贪心、思维)

题目思路：对于答案我们只需求取每相邻的两个元素的最大相差再从所有的最大相差取最大的即可，那么贪心一下假如要求取的是第一个和第二个元素的最大相差，那么就是第一个元素第一次出现的位置和第二个元素最大的能使得后面能完全匹配第二个数组的位置。简单来说就是—在前面匹配好了的情况，后一个元素取最后面那个刚好...

2021-12-18

0 403