4 WorldWide_D

尚未进行身份认证

暂无相关描述

等级
TA的排名 1w+

GDOI2018 记

day0达成成就:在中山住酒店晚上去远洋喝东西,顺便看同行的两个人玩沙雕游戏将近1h回去开个会就差不多睡了day1我上去抄个密码,回头有个兄弟做我位上帮我把密码输了。。拿到题目,t1似乎是个签到题,t2有点眼熟但是不太会,t3是个一眼题,t4又是有点眼熟。。先把t1写了,发现自己是约数个数*n的做法。1e6之内似乎约数个数最大是200多,但是我感觉由于ai≤10,应该跑不满,就没有管

2018-05-03 22:46:54

[codeforces955F] Heaps

题目大意我们称一个有根树的节点u是k-aryheapofdepthm的,当且仅当其满足以下条件之一:1.m=12.m>1,u有至少k个儿子是至少k-aryheapofdepthm-1的(即儿子可以是k-aryheapofdepthn的,n≥m)给定一个n个节点的有根树(1是树根)。设dp[k][u]表示一个最大的m,满足u为根的子树中存在节点是k-a

2018-03-26 21:47:52

[codeforces 917D]Stranger Trees

题目大意给定一棵n个节点的树。对于k=0到n-1,输出有多少棵n个节点的带标号无根树恰好与给定的树有k条公共边。答案模109+710^9+7n≤100分析我们从prufer序的角度考虑这道题。选择了若干条原树的边后,我们得到一些联通块。把这些联通块都缩在一起,假设剩下m个点,接下来我们要去连接这些联通块,得到一棵树,然后考虑这棵树的prufer序是怎样的。由于当前叶子的父亲所表示的联通块

2018-03-01 20:32:05

[codeforces 938G]Shortest Path Queries

题目大意给定一个n个点m条边的无向联通简单图,边有边权。接下来有q次操作,操作有三种:1.添加一条边,保证添加后仍是简单图2.删除一条边,保证删除后仍是联通图3.给定x,y,求所有x到y的路径中所有边权异或和最小值(一条边经过多次算多次)n,m,q≤200000边权<230<2^{30}分析首先我们联想到CF另一道题845G,这题没有前两个操作,只询问1到n的答案。那道

2018-03-01 15:27:56

[arc061F] Card Game for Three

题目大意A,B,C三个人玩游戏,最初每个人分别有n,m,k张牌,每张牌上有字母a,b,c之一,但是不知道每张牌具体是什么。由A先操作,每轮操作者翻出自己牌堆顶的一张牌并弃置,下一轮的操作者是该牌上字母对应的人。不能操作的人赢。问有多少种初始牌的情况能使A胜利。答案模1,000,000,0071≤n,m,K≤300,000分析考虑枚举翻牌序列有x个b,有y个c,那么序列长度应该是n+x+y。由于最后一

2018-02-27 15:53:31

[agc013E]Placing Squares

题目大意给定一个n和m个数(升序给定,满足1≤s1<s2<…<sm<n)你有无限个边长为正整数的正方形。你在数轴正半轴用正方形放在上面覆盖它。需满足:正方形恰好把0到n的区域覆盖完;不能翻转或叠置,且相邻两个正方形之间的缝隙坐标不能是m个数中任意一个。一个方案的贡献为所有正方形面积乘积。求贡献和模109+710^9+7n≤10910^9m≤10510^5分析这题的思路在之前打

2018-02-22 18:30:56

[agc016F] Games on DAG

题目大意给定一个n个点m条边DAG,每条有向边(x,y)满足x<y。现在有一个博弈:有两个棋子分别在节点1、2,两人轮流做以下操作:选择一个棋子,由其所在节点的出边移动到另一个节点。不能操作算输。假设两人绝顶,现在问有多少种边的子集满足:保留这些边之后先手必胜。方案数模109+710^9+7n≤15,没有重边分析可以考虑按照sg给图分层。同时容易发现,两个棋子是两个独立的游戏,为了方便,只需

2018-02-15 12:00:48

GDKOI游记

day0又到了写游记的时候了~这次koi摆到了冬令营之前,还设置了一个讲课日,很悠闲啊。然而之前一个月都在做5h3题的模拟赛,可能会对4h4题不适应day1早上出门,感到凉凉。集体迟到了15min…结果试机的时间也没有了。只得匆匆应战。看完所有题,第一题马上有了思路,但是发现自己写出来是两个log的。计算一下感觉有点虚。但是评测时开O2,我就大胆写了。结果样例调了挺久,一对拍又是错。。很

2018-01-28 22:00:28

[codeforces896E] Welcome home, Chtholly

题目大意给定一个n个数的序列。m次操作:1.给区间[l,r]中所有大于x的数减x2.询问区间[l,r]中数值为x的数个数。n,m≤1000001≤a[i],x≤100000分析这题?循环展开然后optimize一下就过了这是由乃题,我们应该考虑分块。值域范围比较小,我们可以直接记录cnt[i][j]表示块i中数值为j的数个数。然后再用并查集把同一块中数值相同的元素缩在一起。对于

2018-01-19 20:31:10

[bzoj5011][Jx2017]颜色

题目大意给定n个数的序列,你需要选出一个数字集(可以为空集),使得原序列中所有未被选的数字恰好是一个非空的区间。n≤300000,1≤ai≤n分析题目等价于被选的数字恰好是一个非空的区间。对于所有可行的极小区间,它们之间的关系只有两种:包含和没有交集。那么可以考虑扫一遍这个序列,用单调栈按第一次出现时间维护当前未被扫完的数值。如果栈顶的数值被扫完了,那么一直退栈直到栈空或栈顶元素未被扫完。这

2018-01-19 10:43:27

[Codeforces860E]Arkady and a Nobody-men

题目大意给定一个n个节点的有根树。设r(a,b)r(a,b),其中b是a的祖先,这表示b的后代中除a以外深度不大于a的节点个数。设z(a)=∑r(a,b)z(a)=\sumr(a,b)。求每个z(a)z(a)n≤500000分析答案等于:∑dep(b)≤dep(a)dep(lca(a,b))−dep(a)\sum_{dep(b)≤dep(a)}dep(lca(a,b))-dep(a)这等价于z

2018-01-16 20:22:03

[codeforces856C]Eleventh Birthday

题目大意给定n个正整数,你需要把它们按任意顺序拼接,得到一个大数。问有多少种方案使得最终得到11的倍数。如果两个数相同,它们交换位置也算不同方案。答案对998244353取模n≤2000数字≤10910^9分析找突破口。我们发现,一个数的奇数位每加1,对模11的余数的贡献是1,偶数为每加1,贡献是-1。证明?10≡−1(mod11)10≡-1(mod11)我们跟着这个思路走下去。对

2018-01-12 22:22:26

[codeforces 891E]Lust

题目大意给定大小为n的数组,还有一个变量res(初始为0)。进行k次操作,每次随机选择一个数ai,然后给res加上∏j≠iaj\prod_{j≠i}aj,然后ai-1问最终res的期望值模1e9+71e9+7的值。n≤5000,0≤ai,k≤10910^9分析首先转化题意:每一次加的数可以看成操作前所有数的乘积减操作后所有数的乘积。那么只需求最终序列累乘的期望值,然后用初始的值减去它即可。接

2018-01-11 17:41:14

[codeforces 886F]Symmetric Projections

题目大意给定二维平面上n个点。问有多少条直线满足:所有点在它上面投影得到的点集是对称的。有无限条输出-1n≤2000分析首先:对称中心一定是原点集的重心在其上面的投影。接下来:如果两个点关于重心对称,那么它们在任意直线上的投影点都关于重心在其上的投影点对称。可以将这对点删去。接下来枚举两个点,令它们对称,容易发现对应的直线是唯一的。那么我们可以得到n2n^2条直线,一条直线出现过不小于n次才

2018-01-11 10:56:23

[codeforces827F] Dirty Arkady's Kitchen

题目大意给定n个点m条无向边,边权为1.每条边还有一个出现时间区间。从1出发,每个时刻必须沿着一条边走到另一个点。问你最早什么时候到达n。无解输出-1n,m≤500000分析我们不妨把每个点拆成两个点,表示时刻为奇数和偶数。边也按照奇偶拆开,再拆成两条有向边。然后用小根堆以加入时间为关键字维护每条边。设Late[u][p]表示当前奇偶性为p的点u,最晚可以逗留到什么时候。加入一条边时,如

2018-01-10 16:56:36

[codeforces848D] Shake It!

题目大意给定n,m,最开始一个无向图中只有两个点s,t和连接它们的一条边。你需要进行n次操作,每次选择图中一条边(u,v),加入一个点i,并且添加两条边(u,i),(i,v)。问最终有多少种不同构的图,满足其s-t最小割为m。模10^9+7输出n,m≤50分析设f[i][j]表示i次操作,s-t最小割为j的方案数。接下来你需要枚举五个数a,b,c,d,x(其中四元组(a,b

2018-01-09 22:21:04

[codeforces 718E]Matvey's Birthday

题目大意给定一个长度为n的字符串,字符集大小为8。两个点i,j之间有权值为1的边当且仅当满足以下条件之一1.|i-j|=12.si=sj求图的直径和多少个有序点对之间的最短路长度等于直径2≤n≤100000分析好题设dist(i,j)dist(i,j)表示点i到点j的最短距离,Dist(i,c)Dist(i,c)表示点i到字符c的最短距离。易得dist(i,j)=min(|i−j

2018-01-03 17:29:08

[codeforces884F]Anti-Palindromize

题目大意定义“反回文串”为一个字符串S[1..|S|],对于任意1≤i≤|S|都满足S[i]≠S[|S|-i+1]。很显然长度为奇数的字符串不可能是反回文串。现给定字符串S,保证其长度为偶数。你需要把S的字符顺序打乱得到字符串T,满足它是反回文串,并且最大化其价值。价值定义为:所有满足S[i]=T[i]的位置i的b[i]之和(b数组给定)|S|≤100字符集为小写字母分析这种问题一般考虑网络

2017-12-29 21:39:06

[codeforces840E] In a Trap

题目大意有一个n个节点的有根树,边权为1,点权给定,第i个点的点权是ai。q次询问,每次给定u,v,并保证u是v的祖先。问对于u到v路径上的所有i(包括u,v),最大的aixordist(i,v)。其中dist(i,v)是i到v的距离n≤500000≤ai≤nq≤150000分析这题的做法很有趣。我们把v到u的路径每256个节点分成一段(最后一段可能不够256个,可以单独枚举

2017-12-27 15:13:23

[bzoj5101] [POI2018]Powód

题目大意有一个n*m的网格图,给定相邻的格子之间墙的高度,并且默认边界的墙的高度是无穷大的。再给定水位上限H,问有多少种可能的水位。n*m≤500000H≤1,000,000,000分析可以把每个格子看成一个点,相邻的点之间有边权为墙高度的边,然后求一次最小生成树。在克鲁斯卡尔算法过程中,当两个点在一个联通块时,水位一定是一样的。那么再设Ans[x]表示联通块x当前的答案。新加入一条

2017-12-24 16:01:02

查看更多

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