best_jayce-CSDN博客

原创 arc 116 D - I Wanna Win The Game

传送门题意：n(5e3)个数a1...an(>=0), a1^a2^...^an = 0, a1 + a2 +... + an = m(5e3),求数组ａ的个数dp[i][j]代表前i位和为j的方案数#include<bits/stdc++.h>using namespace std;using ll = long long;const int mod = 998244353;const int maxn = 5e3 + 5;ll dp[20][maxn];ll

2021-04-14 17:55:59 172

原创 arc 116C - Multiple Sequences

传送门题意：给定n(2e5),m(2e5)，求长度为ｎ序列A的个数，其中是的整数倍，且不超过ｍdp[n][m]表示最后一个元素为n，长度为ｍ，元素互不相同,每个元素是前一个元素的整数倍(至少２倍)的序列个数,易知序列长度不会超过19元素可以重复的情况等价于在上一种情况把n个小球分到j个盒子且盒子非空,在上面序列乘上即可最终答案为#include<bits/stdc++.h>using namespace std;using ll = long long;const i

2021-04-09 15:44:58 207

原创 LRU cahe

struct Node { Node(int val, int key) : val(val), key(key){} int val{-1}; int key{-1}; list<Node*>::iterator it{};};class LRUCache {private: unordered_map<int, Node*> m; list<Node*> cache; int capacity{1};p.

2021-02-25 10:29:06 104

原创 codeforces 1477B. Nezzar and Binary String

传送门题意：两个01字符串s和f，q个区间询问，每次询问需要保证区间全为0或1，每次询问后可修改小于区间长度一半的字符，问是否能将s经过q次转换到达f倒序遍历询问，可以先修改再保证区间全0或全1，用线段树区间修改区间查询即可#include <bits/stdc++.h>using namespace std;#define ll long longconst int maxn = 2e5 + 5;using pii = pair<int, int>;stri

2021-02-07 11:27:12 233

原创 codeforces 1466F. Euclid‘s nightmare

传送门n个含两位1的向量，每个向量为1的维度互相连边，在不构成环的情况下，有2^n种可能(2^(n+1)个维度),在这个基础上只要加一条含一位1且该维度已出现过1，则可使|T|最大达到2^(n+1)；因此连边后每个连通块最多可包含一个只有一个1的向量并使答案翻倍，所以可以把含一个1的向量看作连向m+1的边，然后用并查集找出所有边的条数即为答案#include <bits/stdc++.h>using namespace std;typedef long long int

2020-12-31 20:21:10 468

原创 codeforces1469E. A Bit Similar

题意：给定一个字符串s(1e6)，要求找出一个长为k(1e6)的字典序最小串s1使s1与s的每一个长为k的子串至少有一个位置相同；枚举s的所有k长子串的反码，这n-k个字符串是不能取的;当2^k大于n-k时，可将前k-log(n)个反码全设为0，枚举后log(n)个位置，最后取s子串反码没出现过的字典序最小串#include<bits/stdc++.h>using namespace std;const int N = (int)1e6 + 77;int n, k;bool

2020-12-29 23:32:57 475 3

原创三维偏序

#include <bits/stdc++.h>using namespace std;#define ll long longconst int maxn = 2e5 + 5;struct node{ int x, y, z, ans, cnt; bool operator == (const node& rhs) { return x==rhs.x && y == rhs.y && z == rhs.z; .

2020-12-02 16:34:23 155

原创 codeforces1426E. Rock, Paper, Scissors

题意:a b两人石头剪刀布共出n次,分别给出每个人的三种可能次数,求a赢的最小次数和最大次数最大次数即取a三种状态和b对应状态的最小值相加最小次数,对于a的每种状态,计算这种状态平局和失败的最大次数,即中的最大值,若等于,此时其他两种状态一种为平局一种为失败,剩余即为最小答案#include <bits/stdc++.h>using namespace std;int main() { ios_base::sync_with_stdio(false), cin.tie

2020-12-01 10:19:09 176

原创 Codeforces 1433F. Zero Remainder Sum

题意:nxm的矩阵, 每一行最多可以选m/2个, 求选出所有值的和能被k整除的最大值;分别算每一行余数的最大值,然后枚举计算前n行最大值#include<bits/stdc++.h>using namespace std;#define ll long long#define INF 0x3f3f3f3fint n, m, k;int main(){ while(cin >> n >> m >> k) {

2020-11-25 15:56:46 126

原创 codeforces 1442B. Identify the Operations

传送门题意:数组a(所有数不同 )中选中ai删除,然后将或插入到数组b末尾,问一种有多少种可能分别计算两边的数能删除的个数设为,而每次删除一个数不会改变之后的数的大小,所以直接相乘就是结果#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll mod = 998244353;ll t;ll n, k;ll a[200007];ll b[200007];ll pos[200.

2020-11-17 16:16:25 150

原创 codeforces 600E. Lomsat gelral (dsu on tree)

#include <bits/stdc++.h>#define LL long longusing namespace std;const int MAXN = 1e5 + 10;inline int read() { char c = getchar(); int x = 0, f = 1; while (c < '0' || c > '9') { if (c == '-') f = -1; .

2020-11-10 13:59:28 74

原创 codeforces1422D. Returning Home

传送门题意:在n x n(1e9)的坐标系内,开始位于起点(x0, y0), 要去(x1, y1), 有m(1e5)个跳转点当x或y坐标相同时可以直接到达,问最少步数;到达终点可以从起点直接走到或跳转点走到将m个点离散化,每个点的x坐标和y坐标与点连边,每个跳转点再与终点连边,计算最短路即可#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int, int>p.

2020-11-06 10:46:31 86

原创 codeforces1407D. Discrete Centrifugal Jumps

题意:n个房子高度为hi,i满足以下任一条件可以跳到j????+1=????i+1=j max(ℎ????+1,…,ℎ????−1)<min(ℎ????,ℎ????)max(hi+1,…,hj−1)<min(hi,hj) max(ℎ????,ℎ????)<min(ℎ????+1,…,ℎ????−1)max(hi,hj)<min(hi+1,…,hj−1).用一个递增和一个递减的单调栈分别记录第三种转移和第二种转移#include <bits/stdc++.h&gt

2020-10-14 13:45:27 161

原创 codeforces1404C. Fixed Point Removal

#include <stdio.h>#include <algorithm>using namespace std;struct node { int l; int r; int wz; bool operator<(node b) const { return r < b.r; }};node nn[524288];int n, q;int a[524288];int c[524288];voi.

2020-10-12 14:33:53 126

原创 codeforces1398E.Two Types of Spells

题意:两种类型的魔法,一种火魔法造成x点伤害,另一种电魔法造成x点伤害并使后一次魔法造成伤害翻倍,n(2e5)次操作,每次获得或失去一种魔法,求每次能造成的最大伤害.用small和big两个set记录较小和较大两部分和,其中big大小等于elec大小,每次插入或删除一个数更新big和small两个set,复杂度为logn;k个电魔法可使k或k-1个魔法伤害翻倍,令sum = sumsmall + sumbig + sumbig,即使较大的k个魔法伤害翻倍的结果;当电魔法存在且火魔法为空时,电魔法只能加倍

2020-08-18 17:43:32 158

原创 codeforces1389F. Bicolored Segments

题意:n(2e5)个线段[li,ri](1e9),每个线段有颜色1或2,求最大线段集合使没有线段两两颜色不同且相交二分图最大独立集 = 点数 - 最大匹配先对线段坐标离散化,然后按r排序,对于每个线段,选取与它相交且r最小的不同颜色线段与之匹配,则可得到最大匹配数#include <bits/stdc++.h>using namespace std;typedef long double ld;typedef long long ll;const int maxN = 4

2020-08-11 16:36:34 204

原创 codeforces 1382E. Mastermind

题意:n个数的数组a,b,每个数∈[1,n+1],已知数组b,构造数组a使a,b刚好有x个数在相同位置匹配,刚好有y个数相同(不考虑位置)按照使最多的数的个数最少的原则用priority_queue分配前x个数,剩下n-x个数中有n-y个数与b中相等但位置不同,最后剩余的数用没出现过的数填充. 主要问题即n-x数中选出y-x数个不匹配,若n-x中出现最多的数的数量f不超过n-x的一半,显然可以将每个数右移[n-x/2]的单位达到,若超过一半,则此时最多不匹配数为2*(f-n+x),若y-x大于这个值,则

2020-07-28 14:09:57 252

原创 lougu2017 [USACO09DEC]Dizzy Cows G

题意:n个点,c1条有向边,c2条无向边,给定的c1条有向边不存在环,分配c2的方向使图不存在环根据有向边统计入度,拓扑排序,碰到端点有入度为0的点的无相边,则方向为入度为0的边指向另一点#include<bits/stdc++.h>using namespace std;const int maxn = 3e5+7;int head[maxn], nxt[maxn], v[maxn], to[maxn], in[maxn], from[maxn];int cnt,n,c1,c

2020-07-20 15:32:55 96

原创 codeforces1373F. Network Coverage

可以二分b[1]给a[1]的值，看了standing学了种O(n)的办法，每次求a[i]-b[i-1]，若大于0，则累加到下一次(a[i]只能有b[i]和b[i+1])组成，然后判断这个值和b[i]的大小#include <bits/stdc++.h>using namespace std;typedef long long ll;int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t;

2020-07-04 16:14:57 343

原创 codeforces1369E. DeadLee

题意:n(1e5)种食物,每种食物有w[i](1e6)个,m(2e5)个朋友,每个朋友有两种喜欢的食物并且每次各吃一盘,安排一种顺序使每个朋友至少能吃到一种喜欢的食物.贪心,记sum[i]为某种食物的需求总量,若w[i]>=sum[i],则喜欢该食物的朋友至少能吃到一种,将这些朋友的另一种食物需求量各减1,然后就是拓扑模拟这个过程把结果逆序输出#include<bits/stdc++.h>using namespace std;const int maxn = 2e5+7;

2020-06-29 11:18:39 184

原创 codeforces1370E. Binary Subsequence Rotation

题意:长度为n的01字符串s,t,一种操作可以选择s的子序列将该序列循环右移一位,求最少操作次数可以使s=t每次贪心选取尽可能多的s,t不相等的位置组成序列进行旋转,这些序列必须是在s中相邻两点不相同的,所以操作次数等于s中与t不同的最大的连续单个数序列#include <bits/stdc++.h>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n;

2020-06-28 19:07:20 3217

原创 codeforces1373E. Sum of Digits

题意：定义f(x)为x的所有数位和，给定n(0=<n<=150)和k(0<=k<=9)，求满足f(x)+f(x+1)+...+f(x+k)=n的x最小值k<=9,可得最多一次进位，根据贪心容易知道满足题意的x必定为xx999x的形式，即从十位开始有若干个9，可以枚举个位数c和中间9的个数得到结果#include <bits/stdc++.h>int main() { std::ios::sync_with_stdio(false); std::cin

2020-06-28 01:03:06 269

原创 codeforces 1364D Ehabs Last Corollary

题意:n个点的联通图,一定能找到小于k的环或(k+1)/2个互不相邻点#include<bits/stdc++.h>using namespace std;int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m, k; std::cin >> n >> m >> k; vector<vector<in.

2020-06-22 11:53:00 155

原创 luogu2939分层图最短路

#include<bits/stdc++.h>using namespace std;;const int maxn = 100100;const int maxm = 500500;int nextt[maxm * 42], w[maxm * 42], to[maxm * 42], head[maxn * 42], cnt = 0;void add(int u, int v, int cost){ cnt++; nextt[cnt] = head[u]; head[u].

2020-06-18 16:45:21 116

原创 codeforces 1366E. Two Arrays

传送门题意:n个数的数组a,m个数的数组b(递增),将数组a分为m段,使得每段最小值min{a[i]} = b[i],求分割方法数因为数组b递增,所以预处理出数组a的后缀最小值suf[i],然后对于数组a的每个数a[i],设suf[i]刚好等于b[m](若suf[i]在数组b中找不到,则该点不能作为一个新的段的起始点),则对于第m段a的起点范围是:第一个suf[i]==b[m]和最后一个suf[j]==b[m]之间的数[i,j],终点是后缀suf[i],统计每段的方案数数然后相乘即为结果. 最后需要

2020-06-12 17:28:51 282

空空如也

空空如也