写在前面
以下代码，目前均可通过民间OJ数据（dotcpp & New Online Judge），
两个OJ题目互补，能构成全集，可以到对应链接下搜题提交（感谢OJ对题目的支持）
如果发现任何问题，包含但不限于算法思路出错、OJ数据弱算法实际超时、存在没考虑到的边界情况等，请及时联系作者
题解
A.幸运数（模拟）
题面
题解
由于是填空题，按题意本地暴力，几秒就跑出来结果了，直接交结果
代码
#include
using namespace std;
int ans;
int main(){
/*
for(int i=1;i B.有奖问答（搜索/dp）
题面
题解
1. 搜索：2的30次方种可能，每次要么+10要么清零，遇到100分时，直接return，几秒跑出来结果后，直接交结果
2. dp：dp[i][j]表示前i轮过后分数为j的方案数，注意中间可以随时停止
代码（dp）
#include
using namespace std;
typedef long long ll;
ll dp[31][101],ans;
int main(){
dp[0][0]=1;
for(int i=0;i C.平方差（构造/规律）
题面
题解
打表或构造发现，形如4k+2的数无法被表示，
统计[l,r]的答案，前缀和作差，转化为[1,r]的答案减去[1,l-1]的答案
而[1,x]中，形如4k+2的数的个数为(x+2)/4
证明的话，x=(y+z)(y-z)，注意到y+z和y-z同奇偶，
1. y+z为奇数时，x为奇数；y+z为偶数时，x为4的倍数，这表明4k+2无法被取到
2. 
，
，这表明奇数和4的倍数均能被取到
代码
#include
using namespace std;
typedef long long ll;
const int N=500;
bool vis[N];
int l,r;
int cal(int x){
return x-(x+2)/4;
}
int main(){
/*
for(int i=0;i=0 && v D.更小的数（区间dp）
题面
题解
未反转的段仍相同不用关注，只需关注反转的段，
记反转前的串为old（即num串），之后的串为new
运用递归/记忆化搜索的思想，有以下几种情况
1. 当i=j时，new[i,j]不小于old[i,j]
2. 当i+1=j时，new[i,j]小于old[i,j]，当且仅当new[i] 3. 否则， ①若num[j] ②若num[j]=num[i]，则可以去掉这两个字母，只需比较new[i+1,j-1]和old[i+1,j-1] ③若num[j]>num[i]，new[i,j]一定大于old[i,j] 从短串递推到长串，就是区间dp了，当然直接写记忆化搜索也行 代码中，dp[i][j]=1表示反转后更小，=0表示反转后大于等于原来 1. 树上莫队： 树上莫队=莫队+dfs序 建树后求dfs序，每个子树对应的dfs区间就是一个询问区间，将询问区间排序后套用莫队， 维护当前颜色i出现的次数now[i]、出现次数为i的颜色种类数freq[i] 任取区间内出现的一种颜色x，若now[x]*freq[now[x]]=区间长度则合法，否则不合法 复杂度O(nsqrt(n)) 2. 启发式合并： 可以维护相同的东西，只是套了个启发式合并的壳 重儿子直接继承当前维护的信息，把轻儿子维护的信息往重儿子上合并， 由于每个点至多出现在log个轻儿子所在的子树里，复杂度O(nlogn) 每个西瓜三种选择：不选，选但不劈，选且劈两半 直接三进制枚举的话，3的30次方，复杂度爆炸 考虑拆成两半枚举（折半枚举，也叫meet-in-middle） 分别维护3的15次方大小的集合a、b， 答案只可能完全来自a、或者完全来自b、或者ab各一部分 ab各一部分的话，在枚举b集合内的元素对应的和为x时，到a集合内查元素和m-x是否存在 复杂度O(3^15*log(3^15))，大概3e8多，时间1s(题面pdf)，比较极限，难以通过(New Online Judge2s dotcpp3s)，试了试unordered_map去卡2s也TLE了，而瓶颈主要在集合查的这个log， 所以手写哈希（开散列），将log这个常数再压一压，就可以通过2s的题了 256M空间其实也比较极限，哈希模数那个数组不要开太大 kruskal重构树裸题， 重构树听上去高端，实则就是在kruskal建最大生成树的过程中额外建点、赋权 比如，u和v当前不在一个集合里，通过w这条边合并时， 新开一个点x，令x是u和v的父亲，而x的权值为w， 查询时，查u和v的lca的权值即可，即为最大连通路径上的最小连通权值 因为按权值从大到小遍历，已经通过权值大的边，使得点之间尽可能连通了 按每个二进制位i考虑，从而转化为0、1序列的问题 一个子段[l,r]在第i位有贡献，当且仅当[l,r]内第i位出现的次数为奇数次， 前缀和做差[l,r]=[1,r]减[1,l-1]，所以维护当前有多少个前缀是奇数，有多少个前缀是偶数 [l,r]为奇数，若[1,r]为偶数则要求[1,l-1]为奇数，反之同理， 枚举每个右端点，统计与其对应的有贡献的左端点，计算答案 最担心被卡掉的一个题，由于唯一解的数据似乎不太好造，导致也不太好在本地测时间 写状压的话感觉总难免需要关注三行的有效状态，复杂度好像更没有办法保证，所以写了搜索剪枝 总体思路还是枚举每一位填0还是填1，加入了校验机制，以及搜到解之后直接return代码
#includeE.更小的数（树上莫队/启发式合并）
题面
题解
代码（树上莫队）
#includeq[i].l;l--)add(c[id[l-1]],1);
int col=c[id[l]],cnt=now[col],f=freq[cnt];
if(f*cnt==r-l+1)ans++;
}
printf("%dn",ans);
return 0;
}
/*
6
2 0
2 1
1 2
3 3
3 4
1 4
*/
F.买瓜（折半枚举+三进制枚举/枚举子集的子集）
题面
题解
（调小了TLE调大了MLE）代码
#includeG.网络稳定性（kruskal重构树）
题目
题解
代码
#includeH. 异或和之和（按位计算贡献）
题目
题解
代码
#includeI. 像素放置（搜索）
题面
题解
a[i][j]：原图转化过来的数字，下划线转成了INF
b[i][j]：当前填的答案数组
cur[i][j]：(i,j)本身及(i,j)周围一圈合法位置中，当前填了几个1
填一个数时，考虑它本身及周围一圈的合法位置（最多9个）
校验机制是：
1. 如果当前填了这个数，导致超过上限，即cur[i][j]>a[i][j]，则不合法
2. 如果当前填的格子，是格子(i,j)管辖的最后一个格子，填完这个数后，a[i][j]和cur[i][j]不等，则也不合法
代码
#include
using namespace std;
const int S=15,INF=0x3f3f3f3f;
int n,m,a[S][S],b[S][S],cur[S][S];
char s[S][S];
bool ok;
bool in(int x,int y){
return 0a[nx][ny])return 0;
}
}
if(in(x-1,y-1) && cur[x-1][y-1]+v J.翻转硬币（整除分块+杜教筛）
题面
题解
1. 5e6，可以考虑埃筛枚举因数，x需要翻当且仅当x的真因数翻了奇数次
2. 1e9，观察5e6时的式子，其实就是莫比乌斯函数
模2意义下的值，
即只有0和1两种情况，此时可以认为是
或
，然后直接套杜教筛
3. 1e18，观察1e9时的式子或思考莫比乌斯函数的定义，
只有包含完全平方因子的数的
值才为0，
所以，考虑对平方因子容斥，
即为所求，
即：
当然，化到这个式子的情况下，直接暴力也是可以通过1e9的数据的
然而，对于1e18，直接整除分块（数论分块）的话是
的，不能接受
于是，类似杜教筛预处理
前缀和的操作，
这里实际预处理
部分的答案（询问是单组的，现算这部分效果是一样的）
用杜教筛预处理的前缀和，后面[1e6,1e9]的部分用整除分块配合的区间和解决
【SSL 2402】最简根式（杜教筛）（整除分块）_SSL_TJH的博客-CSDN博客，与这个题类似
复杂度感觉是
的，但据uoj群友说是
的，就不太懂了…
实际预处理到1e6交New Online Judge也是会TLE的，改到1e7才过
代码
#include
using namespace std;
typedef long long ll;
const int N=1e7+10;
bool ok[N];
int pr[N],mu[N],cnt,up;
mapsmu;
ll n,ans[N];
void sieve(ll n){
mu[1]=1;
for(ll i=2;i=N)break;
ok[k]=1;
if(i%pr[j]==0){
mu[k]=0;
break;
}
mu[k]=-mu[i];
}
}
for(int i=1;i
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
