2 _XFire

尚未进行身份认证

暂无相关描述

等级
TA的排名 4w+

Codeforces Round #571 (Div. 2)C. Vus the Cossack and Strings

字符串a和字符串b(|a|>=|b|),在a中取与b长度相等的所有子串,比较子串与b串中对应位置字符不同的数量,问有多少子串产生偶数数量。假设b长度为3(a1^b1)(a2^b2)(a3^b3)为不同的字符的数量,(a1^b1)^(a2^b2)^(a3^b3)表示的便是奇偶进行下一步:(a2^b1)^(a3^b2)^(a4^b3)==(a1^b1)^(a2^b2)^(a3^b...

2019-07-03 10:41:56

计蒜客 南昌网络赛 C. Angry FFF Party(java大数快速幂)

好久没写博客了,周六晚上破实验课好无聊,把下午做的题贴一下。思路很简单,预处理到30就足足够了,10以内是有最优选择的,大数的时候因为两个数字之间的差值是特别大的,所以直接贪心一下就可以了。没学过Java,之前就写过一个java大数的A+B;这次网络赛现学现卖,一A真的是刺激!///packageD;importjava.util.Scanner;importjava...

2019-04-20 18:46:52

退役总结

    距离打完退役战西安ec-final已经一个月了,当了一个月的咸鱼,才想到要写一个退役总结。    进集训队打了两个赛季比赛,最后终要退役了。    我从高中开始学的编程,但是只拿了两年省二无奈我是一个失败的oier,或者根本称不上是oier吧!有一点编程基础,到了大学开始寻找打比赛的团队,不想再留遗憾了。印象最深刻的一件事是16年大连区域赛后三位14级学长在睿思楼...

2019-01-16 21:02:13

HDU - 5000 Clone (dp)

题目:克隆人有n个属性,给出每个属性的最大值T[i];属性值可以是0-T[i];如果A的所有属性都不比B低,那么B就不能存活,问最多存活多少人。思路:经过分析可以得到,让他们的属性和达到(T[1]+T[2].....+T[n])/2 也就相当于每个属性都取到平均值,无疑可以有更多人; 那么dp[i][j]就代表前i种属性,和达到j的有多少种。dp[i][j] +=dp[i-1...

2018-09-17 22:16:38

计蒜客 焦作网络赛 String and Times(后缀数组)

题目:给一个字符串问重复出现的次数在[A,B] 区间的子串有多少种。思路:后缀数组,对于一个height[i],求height[i-1]---height[i]区间有多少个h满足存在大于等于h的连续的最长长度>=A并且<=B的一个序列(h的数量比较少可以单个枚举。。),这里用rmq来实现。然后另外算一下A==1的情况,也就是只出现了一次的子串有多少个(比赛时就是这里写错了,唉,我t...

2018-09-15 20:09:34

HDU 5469 Antonidas(搜索剪枝)

题目:n个节点的一颗树,每个节点有个字母,给出目标字符串,问求是否存在点对u,v使得u到v的路径上的字母正好组成这个字符串。思路:dfs搜索,感觉复杂度过不了,但是却过了。到达一个点时候判断还剩下没匹配的长度是不是小于这个点往外连接的最大长度。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;...

2018-09-14 16:11:21

HDU - 5468 Puzzled Elena (dfs序+容斥原理/莫比乌斯反演)

题目:给出一棵树,每个点上有权值.然后求每棵子树中与根节点互质即gcd(a,b)=1的节点个数.思路:该题涉及到一个典型问题.问x与S中有多少个数不互素。解决办法是将S中所有元素依次进行两个步骤:①将元素进行质因数分解。②将质因数可能产生的乘积的出现次数加1。记录一下遍历子树之前的cnt值和遍历子树之后的cnt值,作差就是这棵子树的cnt值。将x进行质因数分解,利用容斥原理求解。#i...

2018-09-14 15:05:54

hihocoder 1388 Periodic Signal (FFT)

题目:两个序列,求一个差值平方和最小min{(a1-b1)²+...+(an-bn)²,(a1-b2)²+...+(an-b1)²,...,(a1-bn)²+...+(an-b1)²}思路:原式变形后就是sigma(a[i]^2)+sigma(b[i]^2)-2*sigma(a[i]*b[(i+k)%n])的最大值,也就是sigma(a[i]*b[(i+k)%n])的最小值。这个可以用F...

2018-09-13 16:30:58

HihoCoder - 1387 求树上相同颜色的直径

题目:给你一棵n个节点的树,每个节点的颜色可能不同,现在要给你两种颜色,问你两种颜色的最大距离。如果有一种颜色不存在那么直接输出-1即可。#include<bits/stdc++.h>usingnamespacestd;constintinf=99999999;constintmaxn=1e5+10;intn,m,a[maxn];structno...

2018-09-13 14:44:08

hdu 6212 Zuma(区间dp)

题目:一共有两种颜色的祖玛游戏,每三个连在一起(或者大于三个)的球球就会被消除掉,问将这个字符串消除干净的最小吐球个数。思路:区间dp,考虑几种情况,*********直接是两个组合,1***1中间挖掉一部分后两边合在一起,1***1***1中间挖掉两部分。#include<bits/stdc++.h>usingnamespacestd;constintinf=...

2018-09-13 12:54:16

计蒜客 2018南京网络赛 I Skr(回文树)

题目:给一串由0..9组成的数字字符串,求所有不同回文串的权值和。比如说“1121”这个串中有“1”,“2”,“11”,“121”三种回文串,他们的权值分别是1,2,11,121。最终输出ans=135。思路:之前写了马拉车的算法,网上看到的这个题是回文树的模板题。。。#include<bits/stdc++.h>usingnamespacestd;typedefl...

2018-09-11 11:25:06

回文树(模板)

引用:PalindromicTree——回文树【处理一类回文串问题的强力工具】回文树练习题集首先,回文树有何功能?假设我们有一个串S,S下标从0开始,则回文树能做到如下几点:1.求串S前缀0~i内本质不同回文串的个数(两个串长度不同或者长度相同且至少有一个字符不同便是本质不同)2.求串S内每一个本质不同回文串出现的次数3.求串S内回文串的个数(其实就是1和2结合起来)4.求以下标i结...

2018-09-09 21:48:35

计蒜客 徐州网络赛 A.Hard to prepare (递推)

题目:n个人坐成一圈,每个人可以选0....2^k-1里面选一个数,问最后相邻的人的数字的xnor大于0的方案数有多少。思路:对于一个确定的k位的数,与它nxor值为0的数字只有一个,就是他的补码。然后对于一条直线来说再加一个满足条件的数的数量就是n-1了。现在这个题目是个圈。加一个数,需要考虑所加数与第1个数是否冲突,与第n-1个数是否冲突。如果第1个数与第n-1个数一样,那么第n-2...

2018-09-09 19:53:24

计蒜客 徐州网络赛J.Maze Designer(最小生成树)

题目:给一个n*m的方格,每个格子中间有个权值表示加上一堵墙的代价,然后需要构成一个图是的任意两点直接有且只有一条路,给出q组询问,每次查询两点之间的最短距离。思路:最大生成树,求lca。很裸的一道题目,唉。但是比赛时没读懂题意,以为每次查询都对应着一个图。。。。#include<bits/stdc++.h>usingnamespacestd;typedeflon...

2018-09-09 19:29:23

POJ-2888 Magic Bracelet (polya定理+dp矩阵快速幂)

题目:用m种颜色给长度为n的项链染色,其中k对颜色不能相邻,旋转相同看作同一种方案,问方案数,结果模9973 。思路:对于一段上的方案数是,dp[i][j]=sigma(dp[i-1][k])(j与k可以相邻);长度非常大的时候这是做不了的,看到这个形式就可以考虑一下矩阵快速幂了。然后应用polya计数。#include<cstdio>#include<cstrin...

2018-09-07 19:12:52

hdu 5009 C -Paint Pearls (dp+模拟链表优化)

题目:有n个珠子需要染上特定的颜色,初始的时候是没有染色的,每次染的代价是染色区间中不同颜色数量的平方。思路:最极端的情况是每次拿一个点染色花费1,最终花费为n,所以这个题目最后dp[n]是不会超过n的,往前找转移的点时候只需要往前找到最多产生sqrt(n)的位置就可以了,因为再往前也是徒劳。维护每个数字出现的最后一次的位置,然后中间有些位置是空的啦,用双向链表维护前面那个不同数字最后出现在哪...

2018-09-07 11:52:05

HDU - 5008 B -Boring String Problem (后缀数组 求排名第k小的子串)

题目:给出一个字符串,求不同的子串中排名第k小的子串,并求出字符串的起止位置,如果有多个重复的子串,求出位置最靠左的子串。思路:子串是后缀的前缀,后缀数组对后缀排序的同时,也对子串进行了排序。对于每一个sa[i],会产生n-sa[i]-height[i]个不同的子串,而且这些子串也是排好序的。维护一个n-sa[i]-height[i]的前缀和,二分找一下就可以,找重复的里面的最...

2018-09-07 11:36:08

HDU 3089 Josephus again(约瑟夫环,加速优化)

题目:有N个人,编号为1~N,按顺时针围成一个圈,每数m个人,就将这个人从圈中消除。(N<=1e12)思路:f(1)=0;f(i)=[f(i-1)+m]%i 这里n非常大。1:当m=1的时候接就是最后的那个人了2: f(i-1)+m<i 满足条件时,算一下可以跳多少次还在满足条件下,即 f(i-1)+m*num<i-1+num求满足条件的最大num如果加上起始...

2018-09-05 17:45:03

poj2154 & 2409 (polya计数)

poj2154:用n种颜色涂环形的n个珠子,重复只考虑旋转,不考虑翻转,问能构成多少种?(n<=1e9)自己写的有点丑就用别人推理的截图了#include<cstdio>#include<cstring>usingnamespacestd;constintMAXN=1000010;intprime[MAXN+5];voidgetP...

2018-09-03 21:31:33

HDU-5527 An Easy Physics Problem(平面上点到圆碰撞反弹)

题目:给一个圆和圆外两点A、B,A以给定的速度出发,若碰到圆则发生完全弹性碰撞,问能否经过B。思路:分类讨论1:A的路径碰到了圆,找出两条射线判断是否经过B点。2:A的路径没有碰到了圆,判断一条射线是否经过B点。精度是真的麻烦。。#include<bits/stdc++.h>usingnamespacestd;typedeflongdoubleldouble...

2018-09-03 20:08:23

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。