目录前言树状数组  lowbit函数  直观表述    代码   运行结果树状数组构建代码树状数组的应用  单点修改和（单点）区间查询  结合差分数组区间修改,单点查询        差分数组Colortheballhdu1556  问题描述  问题分析

给定字符串\(S\)。求有多少长\(M\timesL\)的子串，使得将其划分成\(M\)个长度为\(L\)的字符串\(S_1,S_2,\dotsS_M\)互不相同。\(1\leM\timesL\le|S|\le10^5\)。从\(0\)起下标。显然这些字符串的起始位置在模\(L\)意义下相同。不妨枚举这个值\(r\in[

看到\(\oplus\)，肯定想到trie。当我们一位可以是\(1\)但是变成\(0\)时，一个子树内的都合法。特殊的，最后走到的叶子也合法。想法负一：我会莫队！时间复杂度\(\mathcal{O}(n\sqrt{n}\logn)\)，待更新。想法零：我会树套树！待更新。想法一：我会HH的项链！我们按照\(r\)离线，每一次查

目录前言并查集  并查集的初始化  并查集的合并  并查集合并的优化，路径压缩Howmanytables(hdu1213)  问题描述  输入  输出问题分析代码带权并查集Howmanyanswersarewrong(hdu3038)  问题描述  输入  输出问题分析代码

本质上是一个Anti-NimGame。考虑如何计算SG函数。如果当前有堆\(x\)个石子，我取出任意个后，一定会把当前堆分为左右两堆，我们可以枚举左右两堆的大小\(l,r\),保证\(0\lel+r<x\)，则有\[SG(x)=\mathrm{mex}(SG(l)\oplusSG(r))\]#include<bits/stdc++.h>usingnames

操作1，的关键是找到第一只和最后一只空花瓶，完全可以利用二分法查找，找第一只花瓶可以在[X,N]内查找，第一个位置pos1，最后一只花瓶则在[POS1,N]中找，然后更新[POS1,POS2]，全部置1即可代码：#include<iostream>usingnamespacestd;constintN=5e4+5;structnode{ intlazy; in

问题描述：给定一个数列，数列中所有元素都初始化为0，对其执行多种区间操作操作1：add修改：对区间[L,R]内的所有数加c操作2：multi修改：对区间[L,R]内所有数乘以c操作3：change操作：把区间[L,R]内所有数改为c操作4：sum操作：对区间中的每个数的p次方求和。1<=p<=3输入：有不超过10个测试用例。

https://ac.nowcoder.com/acm/contest/34655/C有\(n\)个箱子，第\(i\)个箱子最多放\(s_i\)个石子，当前箱子里的石子数为\(c_i\)。两个人轮流往箱子里放石子，而且每一次放的数量都有限制：不能超过当前箱子内石子数的平方。例如箱子里有\(3\)颗石子，那么下一个人就可以放\(1-9\)

题目链接：hdu7548SunBian(2024“钉耙编程”中国大学生算法设计超级联赛（10）)思路：一道比较签到的题。先说结论：1.当n=k时A必胜2.当k=1时，n为奇数A胜，否则B胜3.其余情况全都为B胜证明：1.显然n=k时A可以一回合全部取完2.k=1时双方只能轮流来，显然奇数A胜偶数B胜3.此时A是

T1001超维攻坚(HDU7469)三维凸包，不会。T1002黑白边游戏(HDU7470)显然这道题没有一个固定的最优策略，所以只能\(\text{dp}\)决策。可以倒着做，设\(f_{i,S}\)表示从后往前进行了第\(i\simm\)轮，第\(i\)轮结束后（在原始意义下是开始前）黑边集合为\(S\)，双方使用最优策

题目链接：HDU3590【PPandQQ】思路    树上删边问题，套个反尼姆博弈。    反尼姆博弈是取走最后一个石子的人输掉游戏，所以需要特判一些特殊情况。    1.有堆的石子个数都是1，所以堆数为奇数时，先手必败，否则先手必胜    2.所有堆中存在石子数为

题目链接：HDU2873【BombGame】思路    数据范围较小，直接暴力求所有状态的SG值，然后将棋盘上所有炸弹的对应位置的SG值异或起来就可以得到当前局面的结果。对于相同位置的上有两个炸弹会自动爆炸，本来他们的SG值的异或和就为0，所以可以不用管。代码intn,m,vis[N*N

题目链接：HDU3980【PaintChain】思路    第一次操作，无论从哪个珠子开始染色，都会得到相同的长度为n-m的链，然后就是在这条链中取一段长度为m的珠子染色，当这一段珠子在链条中间的时候，就会把链条分成两段，就是一个简单的两段连续珠子的长度的sg值异或一下，求出sg[n-m]的

题目链接：HDU2999【StoneGame,Whyareyoualwaysthere?】思路    由于只能取连续的一段石子，当取出的石子是这段石子的中间一部分时就相当于将一段石子分成两段石子，简单异或一下求SG值就行了代码intsg[N],vis[N],a[N];intn,m,k;voidgetsg(){memset

T1004游戏(HDU7460)注意到对于两个人，他们\(t\)轮后能力值相同的概率只与他们初始时的能力差有关，所以我们先\(\text{FFT}\)求出\(|a_i-a_j|=k\)的\((i,j)\)对数。构造多项式\(F(x)=(p_1x^2+p_2+p_3x)\)，其中\(p_1,p_2,p_3\)，分别表示在一轮中两个人相对

题目传送门思路数位dp数位dp数位dp模版题。依次考虑每一位，满足题目给出的限制，统计数量，是一些较简单的数位dp题目的过程。数位dp运用了差分的思想，即求\(ans(l-r)\)的答案用\(ans(1-r)-ans(1-(l-1))\)来表示.对于本题，我们需要满足的性质很简单：使数不超

T1004a*bproblem(HDU7448)不会。T1005小塔的养成游戏之梦(HDU7449)不会。T1009强攻计策(HDU7453)容易发现初始速度是多少对答案没有影响，所以我们默认初始速度为\(0\)。题意相当于在平面直角坐标系上（横轴为时间，纵轴为速度），有一个目标高度，维护一条尽量接近目标的直线，但

A-鸡爪肯定是希望\(1,2,3\)的度数尽可能多。考虑答案一定是\(\lfloor\dfrac{n}{3}\rfloor\)，所以把前面\(1\sim\lfloor\dfrac{n}{3}\rfloor\)都作为鸡爪的中心，并且向\(1,2,3\)连边。剩下一些再连到\(1,2\)上面去。B-梦中的地牢战斗建分层图跑最长路，由于没有正环，所

T1009数位的关系(HDU7441)考虑\(l=r\)的情况，此时只要计算一个数字，我们将其展开为一个字符串\(S\)。设\(f_{i,j,k}\)表示考虑了\(S\)的前\(i\)位，选出了\(j\)个数字加入子序列，最后一个加入子序列的数字是\(k\)的方案数，转移平凡。拓展到\(l\neqr\)，经典地将答

Problem-7498(hdu.edu.cn)直接dfs显然不行，达到了2^500，那么我们可以考虑枚举所有红绿灯的状态，总共有三种状态，k的范围小于等于10，因此所有状态数为3^10不会超，所以通过三进制状压dp即可完成，（这道题目比较卡时间，#defineintlonglong去掉）dp开二维，第一维记录前一种状态，第二维记

题目链接：HDU4334【Trouble】思路    哈希+贪心，直接将五个数组分成两个或者三个数组，此时数组相加的时间复杂度为O(n2)或者O(n3)，然后双重循环数组e和s1并遍历找出s2中是否有满足题意的元素，这个步骤可以使用二分代替还能降低时间复杂度。代码#include<iostream>#inc

题目链接：HDU1020【Encoding】思路    简单模拟，计算相同字母的连续子串个数。代码#include<iostream>#include<algorithm>#include<queue>usingnamespacestd;#definelllonglongconstintN=500+10;voidsolve(){strings;cin>>s;int

团队队员常用：Codeforceshttp://codeforces.com/problemset牛客网https://www.nowcoder.com/ta/acm-training/刷题链接:http://poj.org/pojhttp://www.spoj.com/http://acm.hdu.edu.cn/hduhttps://cn.vjudge.net/vj(包含大部分网站的题库)http://www.51nod.com51N

T1把\(A\)的所有循环位移哈希一下扔set里，拿\(B\)的所有长为\(|A|\)的子串查一遍即可。代码#include<iostream>#include<set>usingnamespacestd;set<unsignedlonglong>st;constintB=2333;unsignedlonglongpw[2000005];intmain(){inttc;

题目链接：HDU1213HowManyTables思路    经典并查集，将互相认识的人全部放在一个集合内，然后计算有几个集合就有几个桌子。代码#include<iostream>usingnamespacestd;#definelllonglongconstintN=1e3+10;intfa[N];voidinit(intn){for(i