题意  q次询问，每次给一个x，问1到x的因数个数的和  思路  考虑每一个因子的贡献，对于因子p，有x/p对：p(1,2,3,……,n/p)。其中前p-1个是已经被枚举过的，p*p这对被计算了两次，所以每个因子的贡献是(x/p-p)*2+1枚举加和即可  代码 #include<bits/stdc++.h> using namespace std; int main(){ int q; cin >> q; for(int i=1;i<=q;i++){ int x; cin >> x ; long long ans=0; for(int j=1;j*j...

贴一个大佬的题解 题意    求解x的个数，如果不存在输出0  思路  唯一分解定理+质因数分解 质因数分解：对于任何一个数n，对它质因数分解只需要枚举到  不断试除，如果最后剩余的不是1，那剩余的就是唯一的大于根号n的因子 对于一个质因子p，和公约数相关的会限制次数的下界，和公倍数相关的会限制次数的上界  如果a0和a1相同下界就是这个值，如果a0和a1不同次数就只能是a1 如果b0和b1相同上界是这个值，如果b0和b1不同次数就只能是b1   题目保证：cnta1<=cnta0，cntb0<=cntb1 最后判断即可  代码 #include<bits/stdc++.h&...

题意  m个操作，起始只有结点0，有如下三种操作  1 i——在结点i下开一个新点，序号为最大编号 2 i a——给结点i的子树全部加上a 3 i——查询结点i的值    思路  先把操作记录下来，建出树 对整颗子树的操作其实就是对dfn的一段区间操作，所以，所有的操作都可以在按dfn顺序的线段树上完成 遍历树得到dfn序以及每个结点的开始区间和结束区间 维护线段树即可 线段树本身记录的就是laz，每次开新点给对应的点清零就行  代码 #include<bits/stdc++.h> #define endl '\n' using namespace std; struct ty{ ...

二进制按位拆贡献看太久，最后一题爆搜没敢写  A 题意  给定k，输出两个非负整数使得异或和为k  思路  签到，0和k  代码 int main(){ int k; cin >> k; cout << 0 << ' ' << k << endl; return 0; }  B 题意  给定长为n的序列a，求相邻两个元素的异或和，获得长为n-1的序列b，求序列b的gcd  思路  直接模拟  代码 int a[30]; int b[30]; int main(){ int n; cin >> n; for(int i=0;...

好复杂的一个题  题意  n个结点，形成一棵根为1的树 k个帮派，每个帮派会控制一些结点 帮派可能结盟，单个帮派也可自己结盟，结盟后任意两个被控制的结点之间的路径都被联盟控制 Q次询问，每次询问给出首都V和结盟的帮派，只需要考虑结盟的帮派 每次询问回答首都V到最近的被控制的城市的距离  思路  对于结盟：任何两个点u,v结盟后所控制的点是lca(u,v)到u和v的路径上的所有点，多个点结盟就是lca(all_node)到每一个点的路径上的所有点 对于每次询问：共有分为三种情况，记LCA为询问中所有的控制点的lca  V不在LCA子树中，则V一定不被控制，此时dis就是V和LCA在树上的距离： ...

题意  给定一棵树，n个节点，你有k种颜色，对于任意相同颜色的点对，两个点之间的路径必须都和这两个点颜色相同，统计合法的染色方案个数  思路  由于树是连通的，所以如果要满足条件，一个节点的颜色要不然是一个全新的无人使用的颜色，要不然和自己的父亲相同 计数，考虑dp，  表示前i个节点使用了j种颜色，转移方程   代码 #include<bits/stdc++.h> using namespace std; using ll = long long ; ll dp[400][400]; vector<int> G[500]; const int p=1e9+7; int...

题意  长为x的跑道上有A，B两个打卡点，必须先在A打卡再在B打卡 请问完成两次打卡后跑步距离超过k的概率  思路  用图形算概率，横轴为A纵轴为B，占比就是概率 如果k<x，那么只要B<=A||(B>A&&B>k)就可以 如果k>x，那么B>=k-x&&B<=A 如果k>2x，寄 如果k=x，当且仅当B<=A  代码 #include<bits/stdc++.h> using namespace std; void solve(){ int k,x; scanf("%d%d",&k,&a...

题意  n堆石子，可以做两种操作  对一个奇数堆石子拆分成两堆 合并两个偶数堆石子   无法操作的人判负，给定n和每堆石子个数，判断胜负  思路  如果没有偶数且奇数不全是1，A分解，B分解，A合并，B分解——A必胜 如果有偶数，所有奇数没有贡献，能合并cnt_even-1次  代码 #include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; int cnt=0; int flg=0; for(int i=0;i<n;i++){ int tmp; cin >> tm...

题意  对于一个数n，两个人每次可以把它拆分成两个因数，没得拆的人输，给定n，判断胜负情况  思路  对任何一个数，最终一定会被拆成它的质因数分解形式，然后无法继续拆解 而中途的拆法并不影响结果 每次拆会使得总数+1，总共能拆因子个数-1次 如果质因数分解有奇数个因子，先手必败 反之后手必败  代码 #include<bits/stdc++.h> using namespace std; int prime[100000]; int vis[100000]; int cnt=0; void sieve(int lim){ for(int i=2;i<=lim;i++){ if...

题意  n*m棋盘，交替染色，不能染的输  思路  奇数先手赢，偶数后手赢  #include<bits/stdc++.h> using namespace std; int main(){ int n,m; cin >> n >> m; if(n*m%2){ cout << "akai" << endl; }else{ cout << "yukari" << endl; } return 0; }

题意  n*n棋盘，白皇后在(1,1)黑皇后在(1,n)，其余位置是中立棋 皇后可以水平，垂直，斜向吃子，无法吃子的一方输 白先黑后 如果白方能赢，给出第一步往哪走  思路  如果奇数，无论白棋怎么走，黑棋都对称的走，最后一定会两方之间只剩下1列中立棋，此时该白方走，然后黑方可以直接吃 如果偶数，白方向右走一步就变成黑方先手的奇数情况，白方必胜  #include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n ; if(n%2){ cout << "black" <&lt...

300多AK，输TT 背景：不动点  一个序列中的元素，当且仅当  认为是一个不动点 一个矩阵中的元素，当且仅当  认为是一个不动点    A 题意  长为4的序列，输出其中的不动点个数  思路  签到，直接模拟  代码 int main(){ int cnt=0; for(int i=1;i<=4;i++){ int tmp; cin >> tmp; if(tmp==i)cnt++; } cout << cnt ; return 0; }  B 题意  构造一个长为n有k个不动点的排列  思路  观察发现k=n-1就寄了 正解：先把前k个按顺序放，后面的错一位放...

题意  对于一个序列，如果某个数字出现两次及以上就可以全部拿取 否则就不能拿取，给出长为n的序列，有m次查询 每次查询会给出一个区间，回答最多拿取多少种数字  思路  附一个别的大佬的blog，推导很详细 对于一个数字，可不可以拿取，取决于到当前位置该数字有没有出现超过两次，也就是一个数出现意味着左端点落在上一次和上上次之间可得的数量增加1 离线查询，按照查询右端点排序 维护一个树，记录处理到当前位置，每个点可得的最大值 这个树设计两个操作，对于某个点值的查询，对于某个区间的整体加一 可以维护这个树的差分数组，单点的查询变为前缀和，区间的增加变为两个单点的修改，这样就不用开线段树可以用树状数组...

题意  对于长为n的全0序列，完成m次如下两种操作  输入x y，将所有1-base下标为x的倍数的元素加上y 输入x y，输出x到y区间和    思路  对于操作1，如果暴力做，每次的复杂度会是  分析x  如果x很大，那么x的倍数就不会很多，暴力的复杂度是可以接受的 如果x很小，通过数学可以快速得到需要增加的元素的个数，开一个桶，记录每个x被加的y的总和，最后统一计算贡献(这个方法在x大的时候设计开不下数组的问题)   x的分界定多大  采用上面的方法后，修改的复杂度变为  ，查询的复杂度变为  ，由均值不等式得分界定在  即可    代码 #include<bits/stdc++....