1 w_uxidixi

学生身份

我要认证

一年小白

等级
TA的排名 6w+

CodeForces - 1418D. Trash Problem 线段树+离散化/set维护

CodeForces - 1418D. Trash Problem 线段树+离散化/set维护不难想到,最后的ans=max{a[i]}−min{a[i]}−max{a[i]−a[i−1]}ans=max\{a[i]\}-min\{a[i]\}-max\{a[i]-a[i-1]\}ans=max{a[i]}−min{a[i]}−max{a[i]−a[i−1]}一、线段树做法维护区间的最大值,最小值,和区间最大的相邻差值需要用到离线,将所有的点都放入数组才能离散化,然后构造线段树的过程中,记录下哪些点

2020-09-24 11:41:22

传纸条 Page270 线性dp

传纸条 Page270 线性dp1.如果把来去分开做的话,还得判断是否有重复经过2.从顶点开始假设有两个人在同步走,如果走到同一个点A,想了好久为什么算经过一次,而不是算经过0次。因为能走到那个地方,就必然存在另一种走法,使得一个玩家经过该点A,而另一个玩家走到B点(AB距离出发点的距离相等),假设最坏情况是玩家走到B点的路上权值都是0,这时候恰巧算一次,但是并不是意味着无法到达这个点,所以取0次是不对的。代码:const int maxn=50+7;const int INF=1e9;cons

2020-09-22 20:04:20

Mobile Service Page269 线性dp

Mobile Service Page269 线性dp1.如果直接做的话是dp[i][pos1][pos2][pos3]dp[i][pos1][pos2][pos3]dp[i][pos1][pos2][pos3],显然超时,将冗余信息除掉后,降了个维度就可以做了。(根本想不到)2.要注意,同一个点不能两个人同时到达,所以要加个判断语句。代码:int dp[1007][maxn][maxn],cost[maxn][maxn],n,m,x[1007];int main(){ scanf("%

2020-09-22 17:40:25

Making the Grade Page267 线性dp

Making the Grade Page267 线性dpdp[i]dp[i]dp[i]表示处理完前i个的构造,且bi=aib_i=a_ibi​=ai​(对于非递减的B序列)dp[i]=min{dp[j]+cost(i,j)∣1≤j≤i,a[j]≤a[i]}dp[i]=min\{dp[j]+cost(i,j)|1\leq j\leq i,a[j]\leq a[i]\}dp[i]=min{dp[j]+cost(i,j)∣1≤j≤i,a[j]≤a[i]}其中,cost(i,j)cost(i,j)cost

2020-09-22 17:36:53

LCIS Page266 线性dp

LCIS Page266 线性dpLIS复习int dp[maxn],n,a[maxn],ans=0;int main(){ scanf("%d",&n); rep(i,1,n)scanf("%d",&a[i]),dp[i]=1; rep(i,1,n)rep(j,1,i-1)if (a[i]>a[j])dp[i]=max(dp[i],dp[j]+1); rep(i,1,n)ans=max(ans,dp[i]); W(ans); r

2020-09-22 17:18:47

Mr. Young‘s Picture Permutations Page265 线性dp

Mr. Young’s Picture Permutations Page265 线性dp1.一开始直接建了一个30^5的dp数组,爆空间了,然后用map+哈希处理一下,题解用的是dp[maxn][maxn/2][maxn/3][maxn/4][maxn/5],因为队伍的人数限制a1>=a2>=a3>=a4>=a5a_1>=a_2>=a_3>=a_4>=a_5a1​>=a2​>=a3​>=a4​>=a5​,且a1+a2+a3+a4+a

2020-09-22 17:02:22

CodeForces - 1409F. Subsequences of Length Two dp

CodeForces - 1409F. Subsequences of Length Two dp题意:给出一个s串和t串,可以修改s串中的字母最多k次,问最后s中最多存在子序列t多少个dp状态:dp[i][j][k]dp[i][j][k]dp[i][j][k]表示在位置[1,i][1,i][1,i]上,修改了j次,共出现t[1]字符k次如果t[1]=t[2],就需要特判,直接把所有能替换的全部替换为t[1],如果用上述dp的话会少情况。代码:int n,x,dp[maxn][maxn][maxn

2020-09-22 16:57:17

CodeForces - 1409

CodeForces - 1409A - Yet Another Two Integers Problem一直取10,剩余的一次完成ll t,a,b;int main(){ scanf("%lld",&t); while(t--) { scanf("%lld%lld",&a,&b); printf("%lld\n",(max(a,b)-min(a,b))%10==0?(max(a,b)-min(a,b))/10:(m

2020-09-18 15:41:57

CodeForces - 1391D - 505 dp

CodeForces - 1391D - 505 dp题意:给一个矩形,其偶数的子正方形中1的个数必须为奇数思路:由于长为2的正方形中1的个数为奇数,所以4个长为2拼起来的长度为4的正方形中1的个数一定为偶数,所以当n>=4时,情况必然不存在;当n=1时,输出0;问题转化为求n=2和n=3时的两种情况做法:当n=2时,枚举第一列的状态,如果第一列中有1个1,那么第二列要么全0要么全1;如果第一列中全1或全0,则第二列一定是1个1。就两种状态,暴力比大小当n=3时,第i+1列的一种状态对应第

2020-09-17 12:17:10

CodeForces - 1395D - Boboniu Chats with Du 贪心

CodeForces - 1395D - Boboniu Chats with Du 贪心题意:如果ai>ma_i>mai​>m,并且当天可以说话,则接下来ddd天不能说话。其余所有情况都能说话,计算能说话的∑ai\sum a_i∑ai​的最大值思路:大于mmm的如果取,则肯定取当前最大的,并且是从最后一个位置nnn开始取,每隔ddd个取一个如何去利用前缀和:暴力枚举取xxx个大于mmm的,那么会消耗(x−1)(d+1)+1(x-1)(d+1)+1(x−1)(d+1)+1天,剩余的天

2020-08-14 12:17:01

CodeForces - 1393

CodeForces - 1393A - Rainbow Dash, Fluttershy and Chess Coloring手动算几个int t,n;int main(){ scanf("%d",&t); while(t--) { scanf("%d",&n); W(n/2+1); }}B - Applejack and Storages统计当前边长的个数,由于情况很少,全部枚举出来int n,

2020-08-12 22:08:58

CodeForces - 1384

CodeForces - 1384A - Common Prefixes GNU前缀取相同,后面的不同的字母向后移一位char ans[maxn][60];int t,n,a[maxn];int main(){ scanf("%d",&t); while(t--) { scanf("%d",&n); rep(i,1,n)scanf("%d",&a[i]); rep(i,1,50)ans[1][i]=

2020-08-12 21:51:07

CodeForces - 1382D - Unmerge 背包

CodeForces - 1382D - Unmerge 背包题意:给出一个[1,2n][1,2n][1,2n]的排列ppp,问是否存在两个长度为nnn的数组aaa,bbb,满足merge(a,b)=pmerge(a,b)={ba=emptyab=emptya1+merge([a2,a3,..an],b)a1<b1b1+merge(a,[b2,b3,..bn])a1>b1merge(a,b)=\begin{cases}b& a = empty\\a& b = empty

2020-08-07 01:41:18

CodeForces - 1379C - Choosing flowers 二分

CodeForces - 1379C - Choosing flowers 二分题意:给出mmm种商品,购买xxx次该商品iii获得的利润是:val(x)={0x=0ai+(x−1)∗bix!=0val(x)=\begin{cases}0& \text{x=0}\\a_i+(x-1)*b_i& \text{x!=0}\end{cases}val(x)={0ai​+(x−1)∗bi​​x=0x!=0​思路:只可能会取到一个bib_ibi​,换句话说,最多只有一种商品会被购买多次

2020-08-05 21:28:09

CodeForces - 1380

CodeForces - 1380A - Three IndicesO(n^2)暴力int t,n,a[maxn];bool ok[maxn];int main(){ scanf("%d",&t); while(t--) { bool mark=false; scanf("%d",&n); rep(i,1,n)scanf("%d",&a[i]); rep(i,2,n-1)

2020-08-02 17:17:51

CodeForces - 1372D - Omkar and Circle 前缀和(dp)

CodeForces - 1372D - Omkar and Circle 前缀和(dp)题意:给一个奇数长度的数组,操作是选择一个位置,删除其相邻的数,并将该位置的数赋值为相邻数的和,求最终剩下的一个数字最大为多少注意:位置1和位置n算相邻思路及问题转化:选择某位置,表面上看删除的是相邻的两个数,但是其实总和SSS减少的是这个位置的数,于是这个问题可以转化为:删除n/2n/2n/2个不相邻的数,剩下的数字和最大如何去利用前缀和:在一个奇数长度的数组中删去n/2n/2n/2个数,剩余数字n/2+1

2020-07-12 11:02:15

数组实现邻接表的原理和细节

数组实现邻接表的原理细节学的不太到位,几个月没写就立刻忘记了,系统的整理一下首先简单说一下自己对邻接表的理解:邻接表其实就是所有顶点的链表例如下图所示:以111为起点的边:111->222以222为起点的边:222->555,222->333以333为起点的边:333->555以555为起点的边:555->111,555->444数据结构:int tol=1,head[maxn];struct node{ int to,next;}edg

2020-07-06 00:36:42

树状数组应用总结

前言做个总结,忘记之后再翻翻首先明确一下树状数组的结构性质:1.每个内部节点c[x]c[x]c[x]保存以它为根的子树中所有叶节点的和2.每个内部节点c[x]c[x]c[x]的子节点个数等于lowbit(x)lowbit(x)lowbit(x)的位数,即位为1的数量例如:x=9=23+21x=9=2^3+2^1x=9=23+21,分为[1,8],[9,9][1,8],[9,9][1,8],[9,9]两个区间,区间和分别为c[8],c[9]c[8],c[9]c[8],c[9]x=13=23+22

2020-07-03 23:31:56

楼兰图腾 Page205 树状数组求逆序对

楼兰图腾 Page205 树状数组求逆序对1.树状数组写起来感觉比归并好理解多了2.求^和v的形状,求出任意一个后,可以采用将数组“倒过来”的方法,即将数组的大小关系重置一下3.不仅是逆序对,正序对也很好求,改变遍历方向即可代码:/** * Author1: low-equipped w_udixixi * Author2: Sher丶lock * Date :2020-07-03**Zz:overint or overarrayXx:overwatch to 5e8Ss:un

2020-07-03 17:20:47

CodeForces - 1373

CodeForces - 1373A - Donut Shops买1个的时候,店2最亏,店1最有可能比店2便宜买b个的时候,店2最赚,店2最有可能比店1便宜比较这两种情况即可ll a,b,c;int ans1,ans2,t;int main(){ scanf("%d",&t); while(t--) { scanf("%lld%lld%lld",&a,&b,&c); if (a*b>c)ans2=

2020-07-03 14:33:32

查看更多

勋章 我的勋章
  • GitHub
    GitHub
    绑定GitHub第三方账户获取
  • 签到达人
    签到达人
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 分享学徒
    分享学徒
    成功上传1个资源即可获取