2 BIT_jzx

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 11w+

20201022考试总结

考的非常崩。。挺水的一套题,自己却犯了很严重的错误,在临考前暴露的很多不足点题目T1:祖先算法:倍增考场思路:一眼题,但是自己一直过不了样例,然后就开始自闭。因为运算是32位以内,所以当超32位是就可以直接取模即可,这是之前自己没有想到的,要划重点#include <bits/stdc++.h>using namespace std;#define ll unsigned long longconst int MAXN = 1e5 + 3;int..

2020-10-22 20:55:08

小W吃零食

题目思路&题解我的思路:显然这道题是状压dp,但是这个限制条件怎么搞?我dp怎么这么菜啊正解首先还是考虑状压,因为注意到n很小,且B也很小,可以设dp[i][S]表示第i天为止,S是一个七进制的状压,第j位表示第j个零食还有多少天可以吃。然后就变成sb状压dp了(其实就是我太菜了),但是这道题需要卡空间,且还要写高精度,直接用滚动数组与__int128即可代码#include<cstdio>#include <iostream>#incl

2020-10-20 13:47:48

VanUSee

题目题解&思路为什么我觉得这道题很难。。这是一道博弈结论题:不难发现总共两人只会移动|S|-|T|次,且最好最后一次剩的串在原序列中间,因此考虑最后剩下的字串是否可以为T,那么对于|S|-|T|为奇数,那么最后一次即为先手,所以对于位置k(k = |S|-|T| / 2下取整)如果从k开始可以匹配T,且从k+1开始也可以匹配T,则最后一定可以剩下T串。如果是偶数,那么如果从k开始可以匹配,那么最后可以剩下T,因为左右要删去的个数是相等的,否则还要讨论一种情况,如果从k-1开.

2020-10-16 14:01:20

贪玩(van)蓝月

题目最窄的题目描述。。。思路&题解自己的思路这是不可能有的正解首先需要发现一个性质,如果现在已经求出k的答案,那么k+2的答案序列就一定是在k的答案序列中插入两个(可以是末尾与开头)数所得到,至于为什么,其实我也不知道,那么考虑k+2的转换,考虑CDQ假设对于k,在区间l-mid选了k1个点,mid+1-r选了k2个点那么对于k+2,就有一下情况:1.在区间l-mid选k1+1个点,mid+1-r选k2+1个点2.在区间l-mid选k1个点,mid+1..

2020-10-15 17:34:31

异或(GYM102331B)

题目给定一个长度为 n 的非负整数列 a1, a2, . . . , an 和非负整数 x, 求有多少个非空子序列 1 ≤ b1 < b2 < · · · < bk ≤ n,满足对任意的 (i, j) (1 ≤ i < j ≤ k) 都有 abi ⊕ abj ≥ x。其中 ⊕ 表示按位异或。 由于这个数可能非常大,你只需要回答这个数除以 998 244 353 的余数即可。 Input 第一行两个整数 n, x (1 ≤ n ≤ 3

2020-10-12 13:59:25

矩形Rectangle

题目我怎么这么菜啊思路&题解自己的思路以为可以用扫描线扫,但是发现这些点不连续,没有多想,就去看题解了正解首先扫描线扫坐标,先确定右端线,然后在从右往左确定左端的线,边扫边加点,那么矩形左右已经确定了,现在考虑左端线:左端线上的一个点,它的贡献就为左端点上面的点 与左端点下面的点构成的矩形,但是对于上界在l点以内的点与下界在r以内的点的矩形并不是最小矩形,要减去,其中点l是在右端线上第一个比i大于或等于的,r是右端线上最后一个比i小的,由于是区间,就可以用..

2020-10-11 13:10:36

黑暗之魂(JZOJ)

题目题解思路:自环重边可以特判然后就变成了找树上的直径最大,答案加1即可否则这就是一棵基环树,找到这个环,然后求出以环上的每个节点为根的最大直径,然后考虑在环上做贡献。对于环上的每个点,先求出环的总长summ,显然对于i,与它贡献的点j一定满足,sum[i]表示从起点到i的环上路径长,其中起点可以随便给然后破环成链,因为求的是最大,直接用单调队列维护即可。至于怎样找环,可以使用拓扑排序,也可以直接DFS注意拓扑排序不要写错,先判断这个点是否在环上,然后第二次连边时不要脸.

2020-10-09 15:28:05

三角陷阱

题目思路&题解最开始想的是O(NQ)的差分数组,以为5e8能跑过去,然而。。。。这道题可以O(Q)做,即用二维差分数组,其实似乎跟二维树状数组差不多,主要这道题是三角形。我们可以选择对角线差分,即·差分后可将其分为两个操作,若现在修改成为了这样的:差分数组中就可以在最左列加上s,最后一行减去s,而这样的操作是可以进行差分的,于是用前缀数组差分即可代码#include<bits/stdc++.h>using namespace std;#defi.

2020-10-05 17:56:51

[SDOI2012]基站建设

题目题目描述Up主家终于买电脑了,但是接下来有各种问题要处理。首要解决的问题就是网络问题。他要从移动公司开始,通过一些基站来传递网络到他家。为了简化问题,我们假设移动公司,所有的基站,up主家位于同一条直线上,他们都位于这一条直线上的某一点x,这些点不会重合。每个基站发射和接收的范围都是一个切于地面的圆,发射的半径r1是固定的,接收半径r2是可调的的。如下图:一个点i如果能从另一个点j接收到信号(当且仅当x[j] < x[i]),必须满足i的接收范围与j的发射范围相切,并且需要付s

2020-09-26 11:14:01

【Usaco2010 Open Gold-1】奶牛的跳格子游戏

题目Description奶牛们正在回味童年,玩一个类似跳格子的游戏,在这个游戏里,奶牛们在草地上画了一行N个格子,(3 <=N <= 250,000),编号为1..N。就像任何一个好游戏一样,这样的跳格子游戏也有奖励!第i个格子标有一个数字V_i(-2,000,000,000 <=V_i <= 2,000,000,000)表示这个格子的钱。奶牛们想看看最后谁能得到最多的钱。规则很简单: * 每个奶牛从0号格子出发。(0号格子在1号之前,那里没钱) * 她向N号格子进行一系列

2020-09-21 17:59:23

莫队(总结)

前置知识分块。普通莫队首先来看一道例题:HH的项链问题描述 HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运,所以每次散步 完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH不断地收集新的贝壳,因此, 他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同 的贝壳?这个问题很难回答。。。因为项链实在是太长了。于是,他只好求助睿智的你,来解 决这个问题。输入格式第一行:一个整数N,表示项链的长度。第二行:N个整数,...

2020-09-17 19:53:27

[CSP-S 2019 Day1]树上的数

题目问题描述给定一个大小为的树,它共有个结点与条边,结点从编号。初始时每个结点上都有一个的数字,且每个的数字都只在恰好一个结点上出现。接下来你需要进行恰好次删边操作,每次操作你需要选一条未被删去的边,此时这条边所连接的两个结点上的数字将会交换,然后这条边将被删去。次操作过后,所有的边都将被删去。此时,按数字从小到大的顺序,将数字所在的结点编号依次排列,就得到一个结点编号的排列。现在请你求出,在最优操作方案下能得到的字典序最小的。如左图,蓝圈中的数字一开始分别在结点②、①、③、⑤、④。按照

2020-09-17 18:36:03

树上石子

题目题解&思路首先不难发现只有|1与&0是对答案有贡献的,如果这道题把每一位拆开来做就会变得很简单,直接线段树维护一下即可,可是如果要求合并起来做就需要其它思路。自己的思路开始是想用一个lazy标记,虽然这样lazy确实可以合并,也可以进行pushdown,但是算异或值的时候就很麻烦,不知道这一位的0或1是强制覆盖还是按原来的。正解用两个lazy标记,lazy0表示如果这一位上有1,则这一位区间强制覆盖为1,lazy0表示如果这一位上有0,则这一位区间强制覆盖为0,那么m

2020-09-13 15:54:56

【USACO 2009 JAN GOLD】安全路径

题目问题描述Gremlins最近在农场上泛滥,它们经常会阻止牛们从农庄(牛棚_1)走到别的牛棚(牛_i的目的地是牛棚_i)。每一个gremlin只认识牛_i并且知道牛_i一般走到牛棚_i的最短路经。所以它们在牛_i到牛棚_i之前的最后一条牛路上等牛_i,当然,牛不愿意遇到Gremlins,所以准备找一条稍微不同的路经从牛棚_1走到牛棚_i,所以,请你为每一头牛_i找出避免gremlin_i的最短路经的长度。和以往一样,农场上的M (2 <= M <= 200,000)条双向牛路编号为1

2020-09-10 12:56:03

CF1404C - Fixed Point Removal

题目Leta1,…,ana1,…,anbe an array ofnnpositive integers. In one operation, you can choose an indexiisuch thatai=iai=i, and removeaiaifrom the array (after the removal, the remaining parts are concatenated).The weight ofaais defined as the maxim...

2020-09-07 21:40:54

【SDOI2011 第1轮 DAY1】染色

题目问题描述给定一棵有个节点的无根树和m个操作,操作有2类:1、将节点a到节点b路径上所有点都染成颜色c;2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”、“222”和“1”。请你写一个程序依次完成这m个操作。输入格式第一行包含2个整数n和m,分别表示节点数和操作数;第二行包含n个正整数表示n个节点的初始颜色下面n-1行每行包含两个整数x和y,表示x和y之间有一条无向边。下面m行每行描述一个操作:“C a b c”表

2020-09-07 21:22:31

【APIO2015】雅加达的摩天楼

题目题目描述雅加达(印尼首都)有座摩天楼排成一列,依次编号为到。有只神秘生物 doge 住在雅加达,分别编号为到。号 doge 最初居住于号摩天楼。doge 能够在摩天楼间跳跃,号 doge 的弹跳力为。每次跳跃,位于号摩天楼、弹跳力为的 doge只能跳跃到号(若)或号(若)摩天楼。号 doge 有一条紧急的消息要尽快传送给号 doge。任何一个收到消息的 doge 可以跳跃到其他摩天楼上,也可以将消息传递给它当前所在的摩天楼上的其他...

2020-09-07 21:17:44

高斯消元(新)

之前的博客好像有点水做法高斯消元上面已经讲过,另一种写法是先消成倒三角状,在从下往上一个个解出未知数。对于无解的情况:有n个未知数,大于n个方程发现后面的方程未知数元已经被消掉可是增广矩阵的右边还有值,则判无解。另外,消元时发现某一行所有元被消掉可是增广矩阵的右边还有值,则判无解。对于有无穷解的情况:从下往上解方程时发现可能有无穷解,那么先把可以求出解的方程算出来,再对那些还不能求出解的方程求解,如果发现系数为0,则就有无穷解例题Description有一个有趣.

2020-09-06 15:10:03

求解梅克司

题目这个梅克司竟然是音译...思路&题解:这道题有些难度,首先枚举左端点从1到n。当l=1时,对于所有的rmex的值总共可以O(N)求,现在考虑将左端点右移时对后面mex的值的变化。显然,mex的值是单调不下降的,对于右端点r如果mex(i,r)的值是大于ai的,那么当l移到l+1时,新的mex(l,r)的值可能会变为ai,于是找到最小的r,满足mex(i,r)刚好大于ai,于是就可以在线段树上二分即可。但是不是所有的都会变,在考虑一个性质,找到下一个j使得aj==ai且j>i

2020-08-24 23:37:11

CPU监控

题目题目背景Bob 家的机子很烂……真的很烂……以至于看视频或者跑邪恶的暴力程序的时候,由于 CPU 使用率持续过高而宕机。题目描述Bob 需要一个程序来监视 CPU 使用率。这是一个很繁琐的过程,为了让问题更加简单,Bob 会慢慢列出今天会在用计算机时做什么事。Bob 会干很多事,除了跑暴力程序看视频之外,还会做出去玩玩和用鼠标乱点之类的事,甚至会一脚踢掉电源……这些事有的会让做这件事的这段时间内 CPU 使用率增加或减少一个值;有的事还会直接让 CPU 使用率变为一个值。当然

2020-08-23 23:35:43

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 阅读者勋章Lv1
    阅读者勋章Lv1
    授予在CSDN APP累计阅读博文达到3天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。