samjia2000-CSDN博客

原创 codeforces 906E Reverses

Description给你两个串s和t，其中t是由s中选择若干个不相交的区间翻转得到的，现在要求求出最少的翻转次数以及给出方案。 1≤|s|=|t|≤5000001\le |s|=|t|\le 500000Solution先将s和t串合并成一个新的串a，其中若i为奇数，那么a[i]=s[(i+1)/2]否则a[i]=t[i/2] 然后问题就变成了将a分解成最少的长度为偶数的回文串，跟将字符串分解

2017-12-29 09:12:59 1131

原创清华集训酱油记

Day -INF在YALI训练了十二天，认识了__debug和h10，发现h10是隔膜大师（雾）？！！然后模拟赛打得一般般，不过也算是体验了一把IOI赛制，虽然jzoj上还能看别人的分数？！Day0Day0发生了什么。。。我不记得了好像就是报道完然后中午富榄请我和栋栋在thu桃李园下面的西餐厅吃饭，接着好像就是玩了很久，然后好像day0就过去了Day1怀着忐忑的心情进入了考场，虽然只是假集

2017-12-09 21:53:59 1939

原创 AGC019F YES or NO

题意有n+m个问题，其中n个的答案是YES，m个的答案是NO，你现在从前往后回答问题，按照最优策略猜答案，回答完当前问题后你会知道这个问题的答案，问期望答对的题目的数量 n,m<=500000题解假设当前还剩a个问题答案是YES,b个问题答案是NO，那么显然最优策略是答更大的那个，即答对的概率是max(a,b)/(a+b) 将回答的所有情况画成一个图得到：答案就是从S走到T的路径的权值和

2017-09-23 15:28:04 919

原创洲阁筛

看了Debug的博客之后恍然大悟。定义非完全积性函数F(x) 我们现在要做的事情是求： ∑x=1nF(x)\sum_{x=1}^n F(x) 还要满足的是：F(pc)F(p^c)是与p相关的低阶多项式考虑将每个x的质因数分成小于等于n√\sqrt n和大于n√\sqrt n两部分： ∑x=1nF(x)=∑1≤i≤ni没有大于n√的质因数F(i)⎛⎝⎜⎜⎜1+∑n√<j≤⌊ni⌋j

2017-06-30 11:11:29 1976

原创【NOI2017模拟6.29】呵呵

题目 1≤n≤20001\le n\le2000解法考虑一个特定形态的树的贡献，设点i的度数为d[i]，那么答案就是： ∑(∏wdii⋅di)\sum(\prod w_i^{d_i}\cdot d_i) 考虑prufer序，一个度数为d[i]的点出现的次数是d[i]-1，那么就可以得到一个很显然的DP，f[i][j]表示前i个点的度数为i+j： fi,j=∑d=0jfi−1,j−d⋅(d

2017-06-29 16:42:51 913

原创【NOI2017模拟6.23】回转寿司

题目大意有n个人排成一个圆环，每个人初始有一个数字a[i]，有m轮操作，每轮操作选择一段连续的人并给出一个数字x，按顺时针顺序比较x和a[i]，如果x小于a[i]，就那么交换a[i]和x 1≤n≤4×1051\le n\le 4\times 10^5 1≤m≤2.5∗1041\le m\le 2.5*10^4解法考虑分块，那么对于一个块来说，如果当前某个数x进去了，那么出来的要不是x要不就是这个

2017-06-23 21:30:10 736

原创【NOI2017模拟6.22】没有上司的舞会

题目大意只有加点操作，动态维护树的最大独立集题解考虑LCT，对于一个点x，s[x][0/1]表示x选或不选时不与他在同一条链上的儿子的DP值，f[x][0/1][0/1]表示splay中x维护的这一个区间最左端选或不选以及最右端选或不选的DP值，只要在切掉splay的边或连接时维护s就好了代码#include<iostream>#include<cstring>#include<cstdio>

2017-06-22 22:36:44 753

原创【NOI2017模拟6.22】排列问题

题目大意有n种球，每种球有不同的颜色，第i种球有a[i]个，现在将这些球排成一排，给出q组询问，每组询问给出一个数x，询问满足相邻的球颜色相同的个数为x的排列个数。设m为所有球的个数和，数据满足：1≤n,m≤2×1051\le n,m\le 2\times 10^5题解设g[i]表示所有球总共被分成i段的方案数（注意，g[i]所描述的每一段的颜色一定是一样的，但是相邻的段的颜色是可能一样的）

2017-06-22 22:32:03 531

原创 CSA Beta Round Cycle Tree

题目A cycle tree is a connected undirected graph that respects one of the following: It’s an elementary cycle of length greater than or equal to 3. It’s a graph resulted by attaching an elementary cycl

2017-06-21 15:43:33 467

原创 2016 TCO Algorithm 1B SettingShield

题目大意有h个普通栅栏，一个特殊栅栏和n棵植物第i棵植物位于第i个单位对于第i个普通栅栏有其保护的区间l[i]到r[i]，特殊栅栏的保护区间是1到n 每个栅栏有一个非负整数s[i]，表示它的强度对于代价，普通栅栏需花费s[i]，特殊栅栏需花费t*s[i] 对于第i棵植物有protection[i]，需满足：对于所有保护了植物i的栅栏的强度总和大于等于pretection[i] 求最

2017-06-21 15:41:46 355

原创 SRM713 hard CoinsQuery

题目大意给出n种物品，每种物品有无数个，物品i有其价值v[i]及其体积w[i]，给出q个询问，每个询问给出一个数S，求所有选择物品的方案中总体积恰好为S的方案的最大价值，以及其方案数一种方案可以描述成一个长度为k序列t，满足t[i]表示选择了第t[i]种物品若两方案的k不同，两方案被视为不同若两方案的k相同且存在i使得t1[i]!=t2[i]，两方案被视为不同 1<=n,q,w[i]<

2017-06-21 15:39:02 409

原创 CF228D Fox and Perfect Sets

题目大意定义一个集合是完美的，当且仅当∀a,b∈S,a⊕b∈S\forall a,b\in S,a\oplus b\in S 给出k，求出最大的数不超过k的完美集合个数解法显然一个完美集合可以由一组线性基表示：对于集合S有线性基：α1,α2⋯αk\alpha_1,\alpha_2\cdots\alpha_k 考虑如何唯一表示一个集合（即如何唯一表示一组线性基）首先假定一组线性基，符合：∀

2017-06-21 15:36:05 575

原创【NOI2017模拟6.20】树形图求和

题目解法一首先对于树形图的个数这样算： a[i][i]表示i号点的出度，a[i][j]表示从i到j的边个数的相反数去掉第n行第n列后剩下的矩阵的行列式即为树形图个数考虑枚举每条边并计算这条边的影响。就是说我们枚举一条边(x,y)然后a[x][x]–,a[x][y]++重新计算行列式对于如下矩阵： A=[a1,1......a1,n]A=\begin{bmatrix} a_{1,

2017-06-20 21:00:25 821

Div1 Hard: BearSortsFirst, we must understand what is probability of getting some sequence. It is equal to 0.5k0.5^kwhere kk is number of comparisons made by mergesort to get this sequence. To see why,

2017-06-11 21:45:49 373

原创线性基

对于若干元素a[]维护其线性基对于每个数还要维护它是由什么组成的。添加添加一个数x 从高位向低位枚举，如果对应的位存在线性基，那么就抑或上这个，如果到了一个位使得不能被消掉，那么直接加到这位上。如果最后变成了零向量，那就存起来（也要存储它是由哪些数组成的）。删除要删除一个数a[i] 首先在零向量中找到一个包含这个a[i]的数，然后对于其他所有包含a[i]的数直接将它维护的id抑或上找到的

2017-06-10 22:29:46 512

转载 THUWC2017 bipartite

【问题描述】某人在玩一个非常神奇的游戏。这个游戏中有一个左右各 nn 个点的二分图，图中的边会按照一定的规律随机出现。为了描述这些规律，某人将这些边分到若干个组中。每条边或者不属于任何组（这样的边一定不会出现），或者只属于一个组。有且仅有以下三类边的分组：这类组每组只有一条边，该条边恰好有 50%50\% 的概率出现。这类组每组恰好有两条边，这两条边有 50%50\% 的概率同时出现，有 50

2017-05-26 11:56:36 815

原创 THUPC2017 I题 Sum

前言今年跟着Jason和栋栋去了thupc，做完g题之后我就一直一边吃东西一边看着他们玩2333，最后还莫名有奖金（赚大了; )哈哈哈）题目大意给出长度为n的数组a[] 设fk=∑i=1naikf_k=\sum_{i=1}^n{a_i}^k 求f[1..n] 1≤n≤4×1051\le n\le 4\times 10^5解法这题竟然是生成函数，我竟然没有去写！！（虽然好像很少写多项式求逆来着）

2017-05-19 11:36:02 2067

原创 GDOI2017总结

今年还是客观一点的写总结吧。 Day1 看完题，t4完全没有思路，前三题都会，然后敲的过程也很顺利，对拍也没有出错，然后就以为稳了，最后算算空间，发现t3超了128MB，然后就卡空间，用set存sam的边，最后发现还是过不了，然后就把1000000改成了900000 下午分数出来t1 100 t2 0 t3 30，t3的部分分情况是每个部分分的前面几个点都过掉了然后去重测，t2数据出错，然

2017-05-03 12:33:26 975

原创最后一轮模拟～总结

这几天，疯狂fst啊，今天又fst了两题2333 今天看完题，t1只会做p=2，只能拿60，然后t2感觉做过，直接hash一下就好了，t3是道裸的凸包，感觉可以做，然后t4不知道什么鬼题，然后弃掉。t1做完60，然后找了一会规律，发现好像没有什么规律，然后就去打t2，t2一开始拍出错了，把now的更新打进if里了，接着就没有出错了，然后t3很快打完，由于这个东西很难拍，所以我就打了个小程序来把点都

2017-04-26 21:38:10 464

原创 Atcoder Regular Contest 072 E Alice in Linear Land

题目大意在最开始Alice离终点的距离为D，第i天，Alice会有一个行走距离a[i]，如果当前距离s>abs(s-a[i])，那么s就更新为abs(s-a[i])，s变为0时到达终点。先给出若干询问，每次询问一个位置x，问能否通过改变a[x]的值，来使得Alice经过n天后不能到达终点 1≤q,n≤1051\le q,n\le 10^5题解显然我们可以预处理出pre[i]表示经过前i天之后的

2017-04-25 22:41:45 667

原创【GDOI2017第四轮模拟day2】绝版题

题目大意对于一棵树，q个操作可以新增节点或改变一个点的权值，或询问整棵树的带权重心，强制在线 1≤q≤3×1051\le q\le 3\times 10^5题解考虑如何找带权重心，显然是每次往最大权的子树走，条件是这个子树的权×2大于整棵树的权值和。那么就很明显了，我们要做的是维护以每个点为根的子树的权值和，以及每个点的儿子中的最大权。由于一条链上的信息更改会影响很多点，那么我们可以用LC

2017-04-25 22:17:21 520

原创 GDOI第四轮模拟day2总结

这两天炸的地方不尽相同啊2333 今天看完题就知道前三题都很简单，然后很快打了t4的暴力，t1打到9:30，因为思路不够清晰，拍了发现没有错就没有管了，然后t2，根据我的物理常识，应该是很多规则几何体的中心在同一点，然后就是一个简单的贪心就好了，但是中途全机房电脑蓝屏了，然后t2的代码没了，后来重打了一份，然后t3打到求答案之前一段的时候发现好像要判同构，感觉很麻烦就放弃掉了，然后就一直在看t2代

2017-04-25 21:56:40 360

原创 GDOI第四轮模拟day1总结

终于到最后一轮模拟了，现在的心态跟noip时很不一样，压力大了是一方面，但现在也没有那么过分自信了，相信要谨慎，但也更放得开，没有患得患失之说，希望会不留遗憾吧。今天其实比较麻烦，因为要拍视频，虽然说不要影响训练，但是事情紧迫，中间还是有45分钟离开了的。t1是经典题，很快就扫过了，然后t2也是一个裸的线性基的题，t3是meet in the middle，t4没有想法。然后8:30我就开始打题

2017-04-24 22:21:50 376

原创 GDOI第三轮模拟总结

（之前写的莫名没掉了。。伤心。。。这次没有上一轮炸的那么爽，最近总算找回一些状态 Day1 t1一眼就会了，然后t2有想法，感觉特殊的分块技巧可以过掉，然后t3只会暴力，t4很恶心的计算几何题弃掉了，然后开打，打t1之前感觉不想打平衡树，于是就打线段树，但是发现线段树打起来很恶心，代码长度也比平衡树多很多，又不敢中途推翻重打，于是最后还是调完了，然后t2最后打完后才发现估计错复杂度了，然而已

2017-04-22 21:34:43 290

原创【SDOI2017】硬币游戏

题目大意有n个长度为m的字符集大小为2的串，随机生成字符串，每次以两种字符同样的概率随机多一位放在最后，如果出现了n个串中的一个就结束，对于每个串，输出以当前串为结尾的概率。 1≤n,m≤3001\le n,m\le 300Solution这题列方程真的很精妙啊。直观做法是建出AC自动机，然后根据AC自动机来得到nm个方程。但是这样显然不可以，因为有nm个变量。我们要求的其实只有n个变

2017-04-21 22:21:17 1323

原创 GDOI第二轮模拟总结

第二轮模拟完美爆炸了：100+120+130 省选考成这样就死定了w 这次用了先打暴力的模式，但是这样导致的一个问题是，我没能很认真的想好正解的细节就开始打题了，导致打题时打完调了很久才发现错，然后就没有时间了，很多可以做出来的题也没有切掉，比如day1的t1其实挺套路的，但就是没有认真想清楚就开始打了然后就错了，然后day3的t1用到的prufer序列其实我是会的，但是一直在想生成树计数要用到

2017-04-18 11:13:53 381

原创 GDOI模拟赛round 1(4.11~13)训练总结

虽然每天都有写，但是一轮下来还是要合起来总结一下。贴一下每天的总结： Day1 第一题是sb题，很快就扫过了，然后看完剩下的题后，感觉最后一题不可做，然后t3是裸的点分治，但是感觉时间复杂度过不去，就想了两种分治方法，结合起来用好像很快的样子，t2让我想起了JSOI的某题，莫名有深深的恐惧感，于是就没有去想，打了暴力，t3打了1个钟，因为我的方法很多地方都十分注意常数。对拍t3点分治时问题

2017-04-14 09:22:27 333

原创 GDSOI模拟4.13总结

今天完美爆炸了，50分。。然而原本想打的分数上200 t1很快就想到了暴力的状压，然后很快想到了怎么将4n4^n压成3n3^n然后就可以100分了，接着去看t2，是一个网络流的模型，但是没有想出来怎么建模，t3是裸的虚树，感觉可以敲出来，t4没有认真想，想着50分应该可以打。然后9点开始打题，由于t1很多恶心的细节，然后10:30才对拍完，接着看t2，为了打t3，没有很认真的打了60分暴力，打

2017-04-13 22:44:39 437

原创杜教筛学习小计

今天做模拟赛由于不会杜教筛导致70分。。。于是去学了一下μ\mu求M(n)=∑ni=1μ(i)M(n)=\sum_{i=1}^n\mu(i) μ\mu有性质：∑d|nμ(d)=[n=1]\sum_{d|n}\mu(d)=[n=1] 于是有式子：1=∑i=1n[i=1]=∑i=1n∑d|iμ(d)=∑t=1n∑d=1[nt]μ(d)=∑i=1nM([ni])1=\sum_{i=1}^n[i=1

2017-04-12 21:06:50 1011 1

原创【GDOI2017模拟二试4.12】石子游戏

题目大意给出n个数a[i]，将x改为y的代价为|x-y|，求将a变成xor和为零的最小代价。 1≤n≤15,0≤a[i]≤1091\le n\le 15,0\le a[i]\le 10^9题解考虑动态规划，按二进制从高到低，用3n3^n的状态表示每个数是在k位之前是增加/不变/减少，设f[k][i][S][0/1]表示当前做到第k位，当前考虑第i位，S为每个数的状态，然后转移有： 1、若k位之前

2017-04-12 20:38:47 544

原创 GDOI2017模拟4.12总结

今天看完题，第一题是裸的trie上建sam，然后t2不会做，想了很久meet in the middle之后放弃了，t3的式子很显然，但是我已经忘记杜教筛怎么打了，所以就只打了70分的部分分，t4又是裸的点分治。开始打题的时候是9点，本来想着9:30搞定第一题的，但是打完之后拍的时候发现有错误，调了很久之后发现sam的部分错掉了，漏掉了一句话，然后10:30才搞定，接着直接去打t3，很快就解决掉

2017-04-12 18:31:13 425

原创 GDOI2017模拟4.11总结

昨天CSDN好像炸了，然后就没有写总结。总结还是要每天更新的，毕竟只有两个星期就要GDOI了，要好好从总结里提炼一些短期内有用的东西。第一题是sb题，很快就扫过了，然后看完剩下的题后，感觉最后一题不可做，然后t3是裸的点分治，但是感觉时间复杂度过不去，就想了两种分治方法，结合起来用好像很快的样子，t2让我想起了JSOI的某题，莫名有深深的恐惧感，于是就没有去想，打了暴力，t3打了1个钟，因为

2017-04-12 17:24:35 364

原创 JSOI2017滚粗记

今年去jsoi成功滚粗了啊，本来想在GDOI前练练自己状态的，没想到啊，唉:-(，竟然成功滚粗。 DAY1 看完三题，感觉第一题可做，然后就去做第一题，由于没有发现单调性，然后打了个treap，测了发大数据，好像会被卡常？然后没有管了，接着好像第三题比较可做，然后就去打了个很显然的DP，第二题直接打暴力了。最后成绩出来的时候，发现t1果然被卡常了，然后t3没有分是什么回事？后来晚上的时候dh

2017-04-10 09:54:14 1788

原创 JZOJ3745

给初中的讲题，顺便打下练手题，然而发现我已经是老年选手了，平时口胡太多打题会死的。。。竟然把dep打成dfn，本来是区间修改单点查询的线段树，为了常数改成单点修改区间询问，然而我打了单点询问。题目我们有一个树，大小为n。考虑树上的一条路径，如果一个边的两个点都在这路径上，我们称这个边属于这个路径，如果一个边有且只有一个点在这路径上，我们称这个边与这个路径相邻。现在每个边要么是黑色的要么是白色的，一开

2017-04-02 21:31:48 461

原创 BestCoder Round #93酱油记

今天请假逃了晚修来打BC，真的爽（晚上不用6:50去教室: )）A题目大意就是一个序列，然后每次覆盖掉一个没有相同元素的连续区间，不能覆盖已经覆盖掉的格子。直接dp过去，用个map存一下某个元素上一次出现的位置。B题目大意：给出一个n位合法十进制，然后要求删掉恰好k个位置上的数，使得剩下的数模3等于零。 1<=n<=1051<=n<=10^5 好麻烦的题目先枚举最高位的位置i，那就是说这

2017-04-01 22:34:01 636

原创生成函数学习小记

生成函数是什么一开始没有学的时候，感觉这个东西很高大上，但是后来浅显的了解了一下之后发现，还真的很厉害，反正我这种菜鸡就只能瞎口胡一下。感觉生成函数比较多的应用在计数类问题上，举个简单的例子，有3个栋栋，那么拿走栋栋的方案数的生成函数为f(x)=1+3×x+3×x2+x3f(x)=1+3\times x+3\times x^2+x^3其中xix^i的系数表示取i个栋栋的方案数。一般生成

2017-03-29 14:28:15 1545 1

原创 [codechef MARCH17]SUMDIS

题目大意有一个一行上有n个点的图第i个点向i+1连长度为a[i]的有向边，向i+2连长度为b[i]的有向边，向i+3连长度为c[i]的有向边问两两间最短路长度之和 1≤n≤1051\le n\le10^5水法先来说说我的水法：考虑从后往前枚举起点，那么设当前到i，如果在分别以i+1,i+2,i+3为起点的最短路树中x点的父亲都是一样的，那么在后来枚举的i里面x的父亲是一样的。对于这样的

2017-03-20 22:44:15 545

原创 [Hackerrank Week of Code 30]A Graph Problem

题目大意定义一个无向图的价值为图中无序三元组(x,y,z)满足x,y,z两两之间有边的三元组数给出一个n个点的无向图，求一个非空子图使得子图的价值除以子图的点个数最大。 1≤n≤501\le n\le 50题解失败失败，一开始一直在想01分数规划怎么加上meet in the middle 然后后来发现就是一个最小割模型二分答案，然后根据答案见图，变成类似最大获利的模型，跑网络流之后判获

2017-03-20 16:55:31 642 1

原创 [Hackerrank Week of Code 30]Range Modular Queries

题目大意给出一个序列a[1..n] q个询问形如”l r x y”问a[l..r]中a[i]modx=ya[i]\mod x=y的个数 1≤n,a[i]≤400001\le n,a[i]\le 40000题解对于x≤200x\le200，将a[]分成n√\sqrt n块，预处理s[i][x][y]s[i][x][y]表示前i块中模x等于y的数的个数，然后询问时可以直接用s和暴力查询多出的部分，一

2017-03-17 22:13:01 443

空空如也

空空如也