1004 Tokitsukaze and Multiple 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6794   题意：含有n个数的序列，相邻的数可以相加成为一个新的数，问最后最多能有多少个数是p的倍数   思路：用set就特别简单，我们现在set里插入0，再用个变量t来表示每个数ai mod p,如果这个t已经存在set里，则说明已经有一个数是p的倍数ans++（因为一个数加上p的倍数再mod p 肯定还是这个数，或者这个数本来就是p的倍数），并将set清空且重新插入0,否则将t插入，直至遍历完。  #include <b...

1011 Kindergarten Physics 题目链接http://acm.hdu.edu.cn/showproblem.php?pid=6812   题意：输出t时间后两质点的距离   思路：物理菜鸡推了好久的公式才a下，看了题解说质点移动的距离远小于 10e-6（所容许的误差值）， 所以对于任意数据范围内的输入，都直接输出 d 即可。  #include #include #include #include #include #include #include #include #include #include #include #include #include #include...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6777   题意：第一个人在0时刻已经涂上荧光粉，如果某个人在同一时间、同一地点与涂上荧光粉的人相遇，那他也会沾上荧光粉，结果按照从小到大输出身上有荧光粉的人的编号。   思路：排个序模拟下就好，排序优先次序为时间、时间相同优先地点、两者都相同优先编号。这题代码也许更适合那些不会或者说不是很会用map、vector、pair这些，因为我也不是很会用，太菜了，后面学习一下尝试用新方法写出来。      #include <bits/stdc++.h> #include ...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6776   题意：有n个小朋友，已知每个小朋友离小沃沃的距离为a[i],求每个小朋友之间最短距离之和。   思路：当每个小朋友在同一直线上最短，排个序。      #include <bits/stdc++.h> #include <iostream> #include <cstdio> #include <queue> #include <cstring> #include &l...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6768 题意：多个测试样例，接下来三行，每行首先输出n，代表斐波那契数列长度，1代表取这一位的值，0不取。以样例来说 A=f[1]+f[3],B=f[4],C=f[2]+f[6]。原本有A*B=C ，但现在改变了C斐波那契数列中的一位，使其由原本的1变为0。我们的目的就是找到这一位。 思路：这道题就是签到题。。。读不懂英文题面，半天没看懂，读懂了超简单。其实就是A*B=C+f[i] ,i就是被改变的那一位。由于 a * b溢出，所以要同余。我没取模，自然溢出也a了，题解说 取MOD = 2^64，我...

太菜了。。。感谢大佬抬我   题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6772   题意：n个装备，每个装备有k种，一个人最多只能选一种装备的一个，每个装备有四个属性a,b,c,d,DMG=(100+∑i∈Sai)(100+∑i∈Sbi)(100+∑i∈Sci)(100+∑i∈Sdi),化简为DMG=100^4+100^3(a+b+c+d)+100^2(ab+ac+ad+bc+bd+cd)+100(abc+abd+acd+bcd)+abcd,求穿上每种装备后的DMG最大值。   思路：就dfs搜一下      #include &...

牛客多校的账号是组里一同学单独买的，看他在群里说别***当天就只看了看题。这道题一开始没把式子看懂，后来自己举了几个例子发现其实就是最多有几个c相乘输出其值。以样例来说 f(10)=5 * f(gcd(5,10))=5 * f(5)=5* 5* f(1)=25.也就是说，这个函数退出的条件就是f(gcd(i,x))=1,也就是说跟gcd有关，就不难想到只要分解x的质因数数量并且把每一个都用上就可以得到最多个c相乘，即递归次数最多。 再举个例子：8用质因数相乘表示即为->8=2* 2* 2 所以f(8)= c* f(gcd(2,8))=c* f(4)=c* c* f(gcd(2* 2))=...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6754   其实就是一个签到题，读懂题想到了就很简单，但我反正是看了半天没看懂，最后还多亏组员成功拿下   题意就是给你一个长度为n的字符串，字符串的子串为回文串的数量最少有多少。   思路：当n=1时，很明显答案为26（a~z） 当n=2时，字符串无非两种情况，aa,ab(其它任意两个字符都行，这里只是举个例子)，两种情况都增加一个回文子串，前者为a,aa。后者为a,b。所以当n=2时答案为2626 当n=3时，我们增加一个字符无非就是四种情况aaa,abb,aba,abc,都增加了一个回文子串，...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6745   写这道题的时候一直tle，结果发现是因为用的是cin却在a完上一题把cin.tie(0)和ios::sync_with_stdio(0)不小心删了。。。直到结束后才发现   思路：举个例子 求（a，b）逐步减一到两者均为一时一共有多少次互质可以看作 ans(a,b)=max((a-1,b),(a,b-1))+1。（加一的前提是（a，b）互质）。  #include <bits/stdc++.h> #include <cassert> #define INF 0x3...

题意：我们需要按照一定的顺序输出a的所有因数，同时要保证，从第二个数开始每个数都必须由其前一个数乘以某个质数或除以某个质数得出的。 思路：各质数 的 幂次方 组合，每次 每个幂方 之和 大小 改变为1。 以题目中样例来说 a=(2^3)*(3^2)=72。易得a所有因数为:   #include <bits/stdc++.h> #define ll long long using namespace std; vector<ll> ans; ll p[25],k[25]; int ...

我们来讲讲AC自动机，单看这个名字我们恐怕还不知道这是用来干嘛得，但我们之前已经学了KMP以及trie树，我们知道KMP 大多是用来解决单串单串匹配的问题的，而AC自动机=KMP+trie树，AC自动机是一种多模匹配算法，AC自动机的关键是构建字典图实现自动跳转，构建 失配指针 实现多模式匹配。首先AC自动机的建立需要一个Trie树 然后转化成Trie图 Trie图就是在每个tire树上的每个节点的所有分支(不论存不存在)连上一条接向树上其他节点的边接向的位置 要连到该前缀上一次匹配的点 找最优所谓AC自动机就是在KMP的基础上 用来解决一大串里面的许多小串出现次数 出现位置 出现个数等问题的...

之前简单的总结了下扩欧，这次来说说扩欧具体有哪些用法总的来说扩展欧几里德算法的应用主要有以下两个方面：（1）求解不定方程；（2）求解模线性方程（线性同余方程）与逆元； （1）求解不定方程所谓不定方程就是形如：ax+by=c 我们通过扩欧可以知道若 c mod Gcd(a, b)=0,则该方程存在整数解，否则不存在整数解。由上面的推导,我们知道,我们可以使用 ExGcd： ax + by = Gcd( a, b ) 求出一组解 ( x0 , y0 ) 使其满足 a * x0 + b * y0 = Gcd( a, b )，令d=Gcd(a,b)令 A = a/d , B = b/d, C = c/...

讲扩欧前先来回顾以下gcd，直接上代码int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b);}扩展欧几里得算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。第一种情况：当b==0时，很明显gcd(a,b)=a,x=1,y=0;第二种情况：设ax1+by1=gcd(a,b),bx2+(a mod b)y2=gcd(b,a%b)因为gcd(a,b)=gcd(b,a%b) 所以有ax1+by1=bx2+(a mod b)y2；又因为a m...

这篇讲讲trie树什么是trie树，trie树是一种树形结构，是一种哈希树的变种。典型应用是用于统计、排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。优点：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓地字符串比较，查询效率比哈希树搞。看了这个解释，可能会让你更无法理解什么是trie树，没关系，继续看下面。首先我们简单看下trie树的样子，不难看出，这棵trie树是由五个单词（at，bee，ben，bt，q）组成的Trie树，也很容易看出每个字母的父亲节点就是他的前一个字母 我们总结出trie树的三个性质，1.根节点不包含字符，除根节点外每一个节点都...