- 博客(6)
- 收藏
- 关注
RSS订阅原创 2020-2021 ICPC, NERC部分题解
A：给出一个序列，问能否找出一些点，使得相邻两个数的最小值组成的序列非递减。首先考虑最长非递减子序列，每个数之间最多能够插入一个比两侧大的数，超过两个就不合法，可以手推或者脑补一下。因此在选择状态转移的时候如果有多个最大值，要选取下标最小的一个，思考一下，如果dp值相同，下标更小的数一定更大，因为后面有更大的数那么可以从这个数进行转移。所以用线段树维护两个数，第一个为dp值，第二个为该位置的值，用last数组表示上一次这个数出现的位置，如果这段区间内有比两侧的数都大的数，那么答案可以为+2，否则+1。#
2021-01-07 17:43:21
1908
原创 Codeforces Round #694 (Div. 1)
A：有m个价格递增给出的礼物，n个人要分这些礼物，第i个人只要下标≤ki\leq k_i≤ki的礼物，没有符合要求的礼物则要给这个人kik_iki为下标的礼物的钱，问怎么购买礼物可以让支出最少？每个礼物只能买一个。考虑贪心，让需要礼物更贵的人尽可能能给到便宜的礼物，等价于尽可能买更便宜的礼物。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=3e5+5;const ll I
2021-01-07 17:13:42
172
原创 Codeforces Round #693 (Div. 3)
D：题意：两个人取数，A取偶数能加分，B取奇数能加分，问最优情况下分数情况？显然取走别人的虽然不能让自己加分，但是可以让对方减分，因此相对分数是加的，从大到小按顺序取即可。E：题意：给n个有序对，问每个有序对是否存在另一个有序对ai<aja_i<a_jai<aj&&bi<bjb_i<b_jbi<bj or ai<bja_i<b_jai<bj&&bi<ajb_i<a_jbi<aj?
2021-01-05 22:12:07
156
原创 CF1154E. Two Teams(双向链表，模拟)
传送门：CF1154E. Two Teams题意：给出n个人的能力值，且每个值互不相同，有两个序号为1和2的leader要挑人，每次的挑选都是先1后2，每次每个leader都会优先挑选能力值最大的人，以及这个人左右两侧各k个人（若不到k个则全部取完）直到所有人都被挑选完毕。输出每个选手会被分配到的leader序号。解析：这个问题可以转化为一个序列每次取走最大的一个数以及这个数两侧k个数，直到序...
2019-04-17 22:29:49
544
原创 ZOJ4098-I-Defense Plan(折半搜索、数学)
传送门：ZOJ4098题意：给出n个数，有m个互斥关系，可以获得所有的排列组合关系，并且在这些组合中不能同时存在互斥的一对数，每一种可能的组合有一个value=排列中所有数的乘积，题目要求我们输出这些值的方差。拿样例来说，给出三个数1、2、3，一组互斥关系1、2表示第一个和第二个数在一个组合中不能同时存在，因此我们可以获得的所有组合关系有{}、{1}、{2}、{3}、{1 3}、{2 3}，因为...
2019-04-15 08:49:57
493
2
原创 CF #541 (Div. 2)-D. Gourmet choice(拓扑排序，并查集缩点)
@[TOC](CF #541 (Div. 2)-D. Gourmet choice(拓扑排序，并查集缩点))题目链接: D. Gourmet choice.题意：要求给出两个分别包含n和m的序列使得该序列满足给出的大小关系，并且满足其中最大的元素最小，给出n*m的矩阵表示大小关系。明显是一道拓扑排序的题。。比赛的时候没时间做了。。有一点细节的是存在值相等的值，需要通过并查集进行缩点的处理，...
2019-04-05 11:59:09
166
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人