19-大数据一班-杨文冠

题解

学习(23) 未归档(1) 练习(1)

/ 注册

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

Gift

题意：2021年，n个人过生日，做蛋糕需要天，生日那天给第i个人有个好感度，也可以选择送礼物，需要花元，获得个好感度，每个礼物最多买一次。在生日当天做蛋糕，如果只要一天也能赶上。思路：2021年不会出现2月29假设给i个人做蛋糕，j个人发礼物是最优的我们可以爆搜求出表示给j个人发礼物能得到的最大好...

背包第45届ICPC昆明爆搜 dp

2021-04-07

3 623

M.Stone Games

题意：每次询问给出L,R，问[L,R]中选择一个子集求和，无法凑出的最小正整数是多少；思路：首先，如果没有1，那么;假设现在能组成，且内有，那么就能凑出，即凑出,然后继续凑;反之若内不存在，则无法凑出的最小正整数就是x的增长速度是指数级的，因此最多次就出来了。询问两个区间总和之差，需要用区间权值...

第45届ICPC昆明可持久化线段树

2021-04-06

9 804

Xortest Path

题意：求任意两点的异或最短路思路：假设点x到点y必须经过一条边，那么它可以通过走环来减少路径的异或和(如果和环的异或值异或后更小)如图，特别的即我们可以先以1为根，建一颗树，跑出1到所有点的异或值，此时往树中加边一定会形成一个环，所以在建树时没有跑过的边对应一个环，这个环的异或值为。按二进...

异或最短路贪心 XOR

2021-04-06

3 713

Educational Codeforces Round 106 (Rated for Div. 2) 来自专栏

A - Domino on Windowsill 思路：贪心只要还有位置，多米诺骨牌就能摆上去。 MyCode: #include <bits/stdc++.h> using namespace std; const int maxn=2e5+7,maxm=1e6+7,mod=1e9...

贪心思维

2021-04-03

1 702

Codeforces Round #710 (Div. 3) 来自专栏

D、Epic Transformation 题意：选择数组中不同的两个数消去，求消去后数组最少有多少个数。思路：出现次数最多的数，如果出现次数小于等于n，最优策略是先排出现次数少的数，然后按出现次数降序插入，最后不可能有两个及以上的数没有配对成功，那么顶多有个数找不到配对；如果出现次数大于n，那么...

单调栈模拟规律贪心暴力双端队列

2021-04-03

1 779

CodeCraft-21 and Codeforces Round #711 (Div. 2) 来自专栏

A. GCD Sum 思路：虽然，当个位是偶数，然后总体只有奇数个奇数时，一定是大于1的 MyCode： #include <bits/stdc++.h> using namespace std; const int maxn=1e5+10,maxm=2e5+10,mod=1e9+7...

模拟记忆化搜索贪心暴力二进制交互 dp 结论题

2021-03-30

2 618

Codeforces Round #705 (Div. 2) 来自专栏

A、Anti-knapsack 题意：给我们一个n，一个k(n,k<=1000)，需要我们得到一个集合，集合的元素全部小于n，并且任意子集相加不等于k，而且这个集合元素相加尽可能大。思路：大于的数全取，小于的的数只能取一半，所以取大的一半。 MyCode: #include <bits...

构造模拟字符串桶排序贪心枚举素数分解线性筛 GCD XOR

2021-03-09

3 743

Traveling in the Grid World

题意：从(0,0)走到(n,m)，选择一个中转点(x1,y1)，然后从(x0,y0)沿直线走到中转点且中间不经过任何一个点称为一次散步，输出所有散步的最小总长度。思路：要记的结论：一对不互质的数(n,m)一定可以被分解为两对互质的数(i,j)和(n-i,m-j)之和( (i,j)与就在(0,0)和...

第45届ICPC上海

2021-03-02

2 604

Fibonacci

题意：找斐波那契序列里有多少对数相乘为偶数思路：其实就是奇数x偶数+偶数乘以奇数个数考虑到奇奇偶的性质，可以求出奇数和偶数的个数。 MyCode: #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; ...

第45届ICPC上海

2021-03-02

5 732

古代猪文

题意：给定整数，计算思路：若，则上式为0。否则互质，可以用欧拉降幂: 较大，可以考虑用定理定理要求模数是质数，尝试分解质因数，发现。 MyCode： ```#include <bits/stdc++.h> using namespace std; const int maxn=2e...

lucas 中国剩余定理

2021-03-02

2 607