4 HbFS-

尚未进行身份认证

di4CoveRy

等级
TA的排名 3w+

AtCoder Grand Contest 002 做题记录

A - Range Product题意:给定两个整数aaa、bbb(a≤ba≤ba\leq b),判断∏bi=ai∏i=abi\prod _{i=a}^b i的正负形。 −109≤a≤b≤109−109≤a≤b≤109-10^9 \leq a\leq b\leq 10^9 解答:分类讨论即可。#include <bits/stdc++.h>using namespac...

2018-08-20 17:30:50

AtCoder Grand Contest 001 做题记录

寒假!A - BBQ Easy题意:有2N2N2N根烤肉扦,第iii个烤肉扦长度为LiLiL_i,每一块肉需要横跨两根烤肉扦,长度为111。可以随意分配烤肉扦的顺序,询问最多同时可以烤多少块肉。 N≤100,Li≤100,LiN≤100,Li≤100,LiN\leq100,L_i\leq100,L_i是整数解答:将烤肉扦从小到大排序,下标为奇数的位置之和即为答案。#inc...

2018-08-05 23:07:12

Codeforces 840D:Destiny

大意: 有一个长度为NN的序列,有MM次询问,每次询问区间[L,R][L,R]中出现次数大于区间长度除以kk的元素中,最小的那个数是多少。若不存在这样的元素输出-1。 N,M≤3∗105,K≤5N,M\leq3*10^5,K\leq5 解答: 序列从前往后建主席树,查询的时候若子树大小太小就返回,那么至多只会访问k个叶节点。时间复杂度:O(KNlogN)O(KNlogN)。#include

2017-09-03 08:48:46

Codeforces 840B:Leha and another game about graph

大意: 给出一个NN个点MM条边的无向联通图,每个点有一个点权AiA_i,你需要为每一条边选择0或者1的边权,使得所有权值不为-1的点所连接的所有边的异或和等于AiA_i。 N≤3∗105N\leq 3*10^5,N−1≤M≤3∗105N-1\leq M\leq 3*10^5,−1≤Ai≤1-1\leq A_i \leq 1 解答: 若存在一个点的点权为-1,则选择一棵以该点为根的任意一棵生

2017-09-02 20:30:57

AtCoder Grand Contest 018 做题记录

退役后的第一次补题 果然做题的时间拉长了好多 但是挺多题自己想出来了 也是蛮爽的UPD:8.11 明早还要上课,能写多少写多少吧。A - Getting Difference有点翻车,A想了好久才弄出来 题意: 有NN个球,第ii个球上写着AiA_i。进行如下操作:拿出两个球上面分别写着xx,yy,放回去三个球上面分别写着xx,yy,|x−y||x-y|询问是否能在若干次操作后使得序列

2017-08-11 22:09:56

2017百度之星资格赛-1005 寻找母串

题意: 对于一个串S,当它同时满足如下条件时,它就是一个01偏串: 1、只由0和1两种符组成; 2、在S的每一个前缀中,0的个数不超过1的个数; 3、S中0的个数和1的个数相等。 现在给定01偏串S,请计算一下S在所有长度为n的01偏串中作为子串出现的次数的总和。 由于结果比较大,结果对1e9+7取余后输出。 n≤109,|S|≤105n\leq 10^9,|S|\leq10^5 解法:长

2017-08-07 20:29:57

Codeforces 835E:The penguin's game

题意: 现在有NN个数,下标从11-NN。这NN个数中有N−2N-2个数是xx,有22个数是yy。 你可以每次向交互库提问,询问一个下标集合的数的异或和。 你需要在1919次询问之内回答这两个数的下标是多少。 解答: 考虑这两个下标的二进制,由于N≤1000N\leq 1000,二进制串的长度至多为1010 可以用1010次询问得到这两个数的异或值:       ~~~~~~每次按照二

2017-08-01 22:49:28

AtCoder Grand Contest 017做题记录

诶最后三道题+第三题的部分分收场了 感觉这场比赛没怎么动脑子 不过也是NOI前最后一场AGC了吧,估计AtCoder的rating以后没机会变了A - Biscuits题意: 有NN袋饼干,第ii袋饼干大小为AiA_i,询问有多少种方案使得选出来的饼干总数模2为p N≤50,Ai≤100N\leq 50,A_i\leq100 解答: Fi,jF_{i,j}表示前ii袋饼干,选出来总和模2

2017-07-10 11:05:23

Codeforces 241E:Flights

【大意】 有一个n 个结点且每条边权值均为1 的有向图,要你把一些边权改成2 使得任意一条从1到n 的路径长度都相等。 【解答】 相当于给定了一个有向图,现在让你给每条边确定一个权值。 权值的值域为11或者22,每条1到n的路径都是最短路。 令disxdis_x为xx到nn的最短路,对于每一条边E(u,v)E(u,v) 都有 disv+1≤disu≤disv+2dis_v+1\leq

2017-06-25 15:09:30

Codeforces 238E:Meeting Her

【大意】 有一个n 个结点的有向图,边权均为1。Urapl 想从a 出发去b。有p 个公交车公司。在每 一秒的开始,第i 个公司的公交车随机选择一条从si 到ti 的最短路径然后走这条路径。如果 一个公交车经过Urpal 所在的交叉点,则Urpal 可以上这辆公交车,他可以在中途任意一个结 点下车。 在任何时刻Urpal 只知道他自己的位置和约会地点。当他上了公交车时他只知道这辆公交 车

2017-06-25 14:58:05

Codeforces 249E:Endless Matrix

ii,jj的二维前缀和 若x≥yx\geq y y(4x+3x2+2x3−y−3xy+y3)6\frac{y(4x+3x^2+2x^3-y-3xy+y^3)}{6} 否则 (−x+x3+4y+3xy−3y2+2y3)x6\frac{(-x+x^3+4y+3xy-3y^2+2y^3)x}{6}

2017-06-17 20:29:12

Codeforces 241D : Numbers

【大意】 给定一个1到n的排列a和一个素数p,构造一个子序列,使得元素异或和为0且首尾相接形成的大整数是p的倍数。n,p≤\leq50000。 【解答】 做法是把原数列中小于32的数拿出来构造这个序列,无视掉序列中大于等于32的数小于等于 32的数中,异或和为0的组合有(312)4(\frac{31}{2})^4种 当p不为2或者5时,首尾相接拼起来模p为0可以看做是一个随机函数,答案出现的

2017-06-16 21:20:54

Codeforces 240F : TorCoder

对于每一种字符分开来维护 26棵线段树,线段树节点维护区间字符出现的次数,分别维护他们的位置判断一次操作是否合法: 对于每一个字符, 查询区间内该元素的个数,若出现两个字符出现的次数同为奇数,或者区间长度为偶数并且有字符出现的次数为奇数,则该操作不合法。进行一次操作: 对于单个字符,由于操作结束之后位置一定是在两侧连续的(不考虑出现次数为奇数时中间的那一个字符),用线段树区间赋值标记即可。

2017-06-15 21:56:09

[UOJ#185][ZJOI2016] 小星星

将树镶嵌在图里面,等价于用树去覆盖这个图,每个点都被覆盖一次。 每个点都被覆盖一次,等价于,每个点至少被覆盖一次方案数=所有点都可以覆盖-至少有1个点未被覆盖+至少有2个点未被覆盖-至少有3个点未被覆盖……(这里的图上的点可以被树上的点重复覆盖) 求某些点不能被覆盖的方案数,可以用树上dp完成,Fi,jF_{i,j}表示树上第ii个点对应图上第jj个点,该子树的方案数 爆枚图上有哪些点一定不能

2017-06-15 19:52:57

[HAOI2017]供给侧改革

先将询问离线,把询问按照r分类,从小到大回答每一个询问。 由随机的性质得知两个串的lcp不会特别长,我们令其最长为40 对于区间[1,R],[2,R],[3,R]…[R-1,R],求其中最长的LCP一定是单调不增的 从左到右将后缀的前40位插入字典树,字典树路径上存下最后一次访问该点的时间,第二次访问这个深度为dep节点的时候就能得到一对时间x,y表示以x开头的后缀和以y开头的后缀的LCP长度

2017-06-11 21:48:53

[HAOI2017]新型城市化

orz栋爷教我的这题 http://blog.csdn.net/werkeytom_ftd/article/details/72992793#include <bits/stdc++.h>#define N 20050#define M 1000050#define INF (1<<29)using namespace std;typedef pair<int,int> pii;int

2017-06-11 21:42:37

Codeforces 235C : Cyclical Quest

【大意】 给一个长度为n 的字符串s,q个询问,每次询问一个串t,问s 有多少个子串与t循环同构。(起始位置不同的子串算作多个子串) 所有的字符均为小写字母,n≤106n\leq 10^6,q≤105q\leq 10^5,∑|t|≤106\sum|t| \leq 10^6 【解答】 对s构建后缀自动机,并且利用后缀链接(parent)数组进行树上动态规划,算出每个节点的right集合大小。

2017-06-10 22:11:22

[BZOJ4874]筐子放球

做法很简单,把筐子看成点,球看成连接两条点的无向边,含有奇数条边的连通块即为答案。 思路是转化成图之后,相当于对于每一条边选择一个点使它的点权+1。对于每一个边数为偶数的连通块,存在一种方案使得所有的点权都是偶数;对于每一个边数为奇数的连通块,存在一种方案使得有点数-1的#include <bits/stdc++.h>#define N 1000500using namespace std;

2017-06-02 13:39:56

[BZOJ4816][Sdoi2017]数字表格 数学

考虑每个fif_i对答案的贡献,就能得到式子 ∑k=1nf∑d|kμ(d)⌊nkd⌋⌊mkd⌋k\sum_{k=1}^nf_k^{\sum_{d|k}\mu (d)\lfloor \frac{n}{kd}\rfloor \lfloor \frac{m}{kd}\rfloor} 转化成枚举kdkd,令T=kdT=kd ∏T=1n(∏d|Tfμ(Td)d)⌊nT⌋⌊mT⌋\prod_{T=1}^n

2017-05-31 16:51:08

[BZOJ4870][Shoi2017]组合数问题 矩阵快速幂

诶感觉这题很套路啊 听说赛场上写出来的人不多 可能比赛的时候比较紧张这题放最后一题没那么好像吧 解法到不是特别难相当于求一个模意义下的杨辉三角嘛 塞到矩阵里面转移就好了#include <bits/stdc++.h>#define N 55using namespace std;typedef long long LL;inline int rd() { int x=0,f=

2017-05-29 22:32:56

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!