2 青烟绕指柔!

尚未进行身份认证

我要认证

我不怕千万人阻挡,只怕自己投降。

等级
TA的排名 3k+

CCPC - Exam Results

题目链接:CCPC - Exam Results我们先按照最大值从小到大排序,然后枚举作为最大值的值。如果满足后面 最小值的max,这个答案就是合法的。然后对于前面做一个尺取维护答案,对于后面的就是一个线段树区间查询。然后枚举某个的最小值作为最大值,我们可以发现必然是最大值最小值才合法,然后线性遍历即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define

2020-10-24 11:16:03

Codeforces - Zero Remainder Sum

题目链接:Codeforces - Zero Remainder Sum直接dp[i][j][k][l]表示,前 i 行,第 j 列,选出的数字 %k ,并且第 i 行选了 l 个的最大值。然后考虑状态转移即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=

2020-10-21 22:09:16

[TJOI2018]智力竞赛

题目链接:[TJOI2018]智力竞赛首先我们可以想到二分。然后对于需要覆盖的点,看是否被小于等于 n+1 条链全部覆盖,先跑一个传递闭包,然后把小于等于二分的点拿出来建图即可。然后就是一个最小链覆盖了。如果不跑传递闭包,单独对 x+m -> x的边,我们无法处理 3 -> 5 -> 4 ,但是我们二分的答案为4的情况。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc

2020-10-15 14:48:57

Codeforces - Searchlights

题目链接:Codeforces - Searchlights求出枚举每个点右移的距离。然后看向上需要移动多少,复杂度过高。考虑预处理右移之后,每个点最小移动距离。就是枚举每两个点,然后做一个后缀max。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=2e3+

2020-10-14 21:08:02

魔法指纹

题目链接:魔法指纹看似是一个数位dp,但是无法转移状态,也无法确定合法状态。所以我们可以考虑分块打表,我们预处理[1,1e6],[1e6+1,2e6],[2e6+1,3e6]…的前缀和。然后块内暴力即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;int a[20],l,r;

2020-10-13 11:31:46

小Z的笔记

题目链接:小Z的笔记显然可以dp,然后 dp[i] 为前 i 个字符的最小删除数量。然后对于每个合法的 j : dp[i] = min{ dp[j] + i - j -1 }显然每次转移越靠后越优,所以我们预处理每个位置前面的最靠后的某个字符位置即可。当然还有一种做法:把 dp[j] - j -1 看成一个整体,单独维护一个min。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.

2020-10-06 12:01:56

质数取石子

题目链接:质数取石子显然可以枚举素数转移,然后预处理一下素数即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=2e4+10;int n,dp[N],f[N],vis[N];vector<int> p;void init(int n){ f

2020-10-05 22:20:49

前缀单词

题目链接:前缀单词按照Trie建树,我们可以发现儿子和祖先关系是不能同时选取的。然后树形dp即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define int long longusing namespace std;const int N=60,M=N*N;int n,ch[M][26],ed[M],idx,dp[M]; char str[N];vec

2020-10-04 12:36:38

规划

题目链接:规划这个式子显然可以01分数规划,然后问题就变成选n-m个点,并且是一个联通块的最大权值,树形dp即可。dp[i][j] 为以 i 为根节点,选取 j 个点的最大值。然后树上做背包即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=110;int

2020-10-04 11:28:04

Codeforces - Serval and Rooted Tree

题目链接:Codeforces - Serval and Rooted Tree我们一定是控制最少的可以影响根节点的叶子,然后从大到小放数字。每次取max时,也就是子树中需要控制的最小的。取min的时候也就是求和。然后dp即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;con

2020-09-29 13:00:42

Codeforces - Shovels Shop

题目链接:Codeforces - Shovels Shop显然最多买k个物品,然后 k^2 dp即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=2e5+10;int dp[N],mx[N],n,m,a[N],k;signed main(){ cin

2020-09-28 21:20:08

Codeforces - Yet Another Subarray Problem

题目链接:Codeforces - Yet Another Subarray Problem因为m很小,所以枚举最后的的子串 %m 的长度即可。然后做一个倍数为m的前缀max。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define int long longusing namespace std;const int N=3e5+10;int n,a[N],m

2020-09-27 18:10:48

健康监测计划

题目链接:健康监测计划显然从叶子贪心是最优的。于是我们可以想到先取叶子,然后把叶子删掉,然后继续取叶子。一共取 k/2 次叶子,如果k是奇数,最后再任意取一个点即可。所以我们树上拓扑即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=1e6+10;int

2020-09-27 10:52:06

Codeforces - Subsequences

题目链接:Codeforces - Subsequences显然选的越长越优。所以我们对每个长度的子序列求出种类个数即可。求种类个数,直接dp。dp[i][j]为前i个字母,长度为j的方案数。转移的时候如果有前面等于 str[i] 的部分,那么只能从两个相同的字符之间转移。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define int long longus

2020-09-26 22:16:11

Codeforces - Pokémon Army

题目链接:Codeforces - Pokémon Army显然每一段下降的连续子串才会贡献答案。我们把整个序列看成多个连续下降的子串即可。然后用线段树维护答案。#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define int long longusing namespace std;const int N=3e5+10;int n,q,a[N];struct nod

2020-09-25 16:56:12

筐子放球

题目链接:筐子放球可以将问题转化为改变边的定向,使得入度为奇数的点的个数最小。对于任意一个联通块,我们先将非树边任意定向,然后考虑树边,如果当前树边深度大的这个点为奇数,那么我们一定可以让这条边指向深度大的点。如此反复,我们可以发现最后只和联通块边数的奇偶性。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing na

2020-09-25 12:40:58

火车

题目链接:火车可以树剖+fenwick。也可以对每个点做并查集合并暴力跳。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=5e5+10;int n,m,s,pos[N],bl[N],sz[N],son[N],f[N],dep[N],cnt,par[N],vis

2020-09-23 21:02:28

交换茸角

题目链接:交换茸角如果可行。那么对于n个鹿,最多n-1次交换即可。否则,我们一定可以从中选出不相交的子集替换答案。然后枚举子集dp即可。判断是否可行,即sort之后两两是否合法。int i=(s-1)&s;i;i=(i-1)&s 这样即可枚举到s的所有子集,复杂度为 3 ^ nAC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int

2020-09-23 20:12:17

茶颜悦色

题目链接:茶颜悦色对 x 方向做尺取,然后对 y 方向维护长度为 k 的最大值。维护最大值的时候,对每个点为正方形的右端点的最大值,然后线段树上区间修改,区间max即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=1e5+10;int n,k,m,mx[

2020-09-22 16:20:27

道路摧毁

题目链接:道路摧毁dp[0/1]分别代表子树中两种点的最小代价。然后树形dp一下即可。AC代码:#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>#define int long longusing namespace std;const int N=2e5+10,M=N*2;int n,mx,my,a[N],dp[N][2];int head[N],nex[M],to[M]

2020-09-21 22:50:22

查看更多

勋章 我的勋章
  • 签到达人
    签到达人
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024超级勋章
    1024超级勋章
    授予原创文章总数达到1024篇的博主,感谢你对CSDN社区的贡献,CSDN与你一起成长。
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 学习力
    学习力
    《原力计划【第二季】》第一期主题勋章 ,第一期活动已经结束啦,小伙伴们可以去参加第二期打卡挑战活动获取更多勋章哦。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。
  • 原力探索 · S
    原力探索 · S
    在《原力计划【第二季】》打卡挑战活动中,发布 12 篇原创文章参与活动的博主,即可获得此勋章。(本次活动结束后统一统计发放)
  • 1024勋章
    1024勋章
    #1024程序员节#连续参与两年活动升级勋章,当日发布原创博客即可获得