题意 经典的 威佐夫博弈（Wythoff Game）： 有两堆石子，数量分别为 $a$ 和 $b$ 每次可以进行两种操作： 从任意一堆取任意多石子 从两堆中取相同数量的石子 最后把石子全部取完的人获胜 要求：判断先手在初始状态下是否能获胜。 解析 威佐夫博弈中，有两种关键状态： P-position（必败点）：如果先手处于此状态，必败 N-position（必胜点）：如果先手处于此状态，必胜 设 $m=\max(a,b)$，$n=\min(a,b)$，则 $(n,m)$ 是 P-position 当且仅当： $\displaystyle n=\lfloor(m-n)\cdot\phi\rfloor$ 其中 $\phi$ 是黄金比例： $\displaystyle\phi=\frac{1+\sqrt{5}}{2}\approx 1.6180339887$ 所有其他状态都是 N-position（先手必胜）。 判定 令 $m=\max(a,b)$，$n=\min(a,b)$； 计算差值 $k=m-n$； 若 $n=\lfloor k\cdot\phi\rfloor$，则输出 0（先手必败）； 否则输出 1（先手必胜）。 证明 已知游戏状态 $(a,b),a\le b$ 定义：$P$ 为必败状态，$N$ 为必胜状态 设 $P$ 集合 $(x_n,y_n),x_n<y_n$，差值 $d_n = y_n-x_n$ $\because$ $P$ 不能互相干扰 $\therefore\forall i\ne j,x_i \ne x_j,y_i \ne y_j,d_i \ne d_j$ $\because$ 若 $\alpha>1$ 无理数，$\beta = \frac{\alpha}{\alpha-1}$(Beatty 定理) $\displaystyle\therefore{\lfloor n\alpha \rfloor}_{n\ge1} \cup {\lfloor n\beta \rfloor}_{n\ge1} = \mathbb{Z}^+,{\lfloor n\alpha \rfloor} \cap {\lfloor n\beta \rfloor} = \emptyset$ 令 $\phi = \frac{1+\sqrt{5}}{2}$ $\because$ 黄金比例满足 Beatty 定理 $\therefore x_n = \lfloor n\phi \rfloor,y_n = x_n+n$，差值 $y_n-x_n = n$ $\because$ $x_n$ 序列和 $n$ 构成 Beatty 序列 $\therefore$ 不可能通过一步到达另一个 $P$ 设 $N(a,b),a<b,k=b-a$ $\because$ 存在唯一 $n$，$x_n \le a < x_{n+1}$ $\therefore$ 存在一步 $(a,b)\to(x_n,y_n)$ 设 $m = \max(a,b),n = \min(a,b),k = m-n$$\therefore(a,b) \in P \iff n = \lfloor k \phi \rfloor$ $\because$ $P$ 构造 $(x_n,y_n)=(\lfloor n\phi \rfloor,\lfloor n\phi \rfloor+n)$ $\because$ 差值 $k=y_n-x_n=n$ $\therefore$ $x_n = \lfloor k \phi \rfloor$ 标程 #include<bits/stdc++.h> #define int long long…

题意 给定正整数 $a,b$，求同余方程 $ax\equiv1\pmod b$ 的最小正整数解 $x$。 解析 由于题目没有保证 $b$ 为质数，所以不能用费马小定理，需要使用拓展欧几里得算法求乘法逆元。 前置芝士 $a$ 在模 $b$ 下存在乘法逆元，当且仅当 $\gcd(a,b)=1$。此时存在整数 $x,y$ 使 $a x + b y = 1$（即裴蜀定理）。等式两边同时对 $b$ 取模可得 $a x \equiv 1 \pmod b$，所以该 $x$ 即为所求逆元。 解法 使用扩展欧几里得算法求出一对 $x,y$ 使得 $ax+by=\gcd(a,b)$。由于题目保证有解，即 $\gcd(a,b)=1$，则此时答案为 $(x\bmod b+b)\bmod b$，从而得到最小非负解。 标程 #include<bits/stdc++.h> #define int long long using namespace std; inline int extended_gcd(int a,int b,int &x,int &y)//用拓展欧几里得算法求逆元 { if(!b) { x=1; y=0; return a; } int gcd; gcd=extended_gcd(b,a%b,y,x); y-=(a/b)*x; return gcd; } inline int inv(int b,int m)//a mod m 意义下的乘法逆元 { int x,y; int gcd=extended_gcd(b,m,x,y); return gcd!=1?-1:(x%m+m)%m; } signed main() { int a,b; cin>>a>>b; int ans=inv(a,b); cout<<ans; return 0; } 时间复杂度 $\mathcal{O}(\log\min(a,b))$。

题意 即维护一棵线段树，支持单点修改+区间查询。 芝士——线段树 线段树（Segment Tree）是一种树状数据结构，主要用来高效处理区间查询（RMQ）与区间修改问题。 下图就是一棵简单的线段树，每一个节点都是其子节点之和，叶子结点用于存储数值，非叶子结点用于维护区间和。 graph TD A["[1,4] sum=10"]-->B["[1,2] sum=3"] A-->C["[3,4] sum=7"] B-->D["[1,1] sum=1"] B-->E["[2,2] sum=2"] C-->F["[3,3] sum=3"] C-->G["[4,4] sum=4"] 我们可以用一个结构体来存储线段树，但由于二叉树的性质，对于编号为 $n$ 的节点，其左右子节点分别为 $2n$ 和 $2n+1$，我们通常可以用一个数组直接存储线段树（不过需要注意，由于线段树需要维护区间和，所以通常要开 $4$ 倍空间，如果你想省空间而不开 $4$ 倍，就等着 RE 吧 doge）。 由于线段树是基于分治思想实现的，所以可以把单次查询或修改的复杂度降到 $\mathcal{O}(\log n)$。 总时间复杂度：$\mathcal{O}(m\log n)$。 标程 #include<bits/stdc++.h> #define int long long using namespace std; int tree[800005],a[200005];//树要开 4 倍 inline void push_up(int id)//上传，注意不要和lazy_tag的下传搞混 { tree[id]=tree[id<<1]+tree[id<<1|1];//更新父节点为子节点之和 } inline void build(int id,int l,int r)//建树 { if(l==r)//到叶子节点了 { tree[id]=a[l];//赋值 return ; } else { int mid=l+r>>1;//分治 build(id<<1,l,mid); build(id<<1|1,mid+1,r); push_up(id); return ; } } inline int query(int id,int l,int r,int L,int R)//区间查询 { if(L<=l&&R>=r)return tree[id];//完全包含 int mid=l+r>>1; int ans=0; if(L<=mid)ans+=query(id<<1,l,mid,L,R);//搜左子树 if(R>mid)ans+=query(id<<1|1,mid+1,r,L,R);//右子树 return ans; } inline void update(int id,int l,int r,int pos,int x)//单点修改 { if(l==r) { tree[id]=x; return; } int mid=l+r>>1; if(pos<=mid)update(id<<1,l,mid,pos,x); else update(id<<1|1,mid+1,r,pos,x); push_up(id); } signed main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; } build(1,1,n);//除非动态开点，否则都要建树 while(m--) { int op,l,r; cin>>op>>l>>r; if(op==1) { update(1,1,n,l,r); } else if(op==2) { cout<<query(1,1,n,l,r)<<endl; } } return 0; }

题目传送门 题目大意 根据经过贡献值和字典序排列后的字符串确定资历深浅，贡献值大的资历浅。 思路 利用 STL 中的 map 容器将姓名作为下标存储贡献值的优先级（STL 容器不熟的点这）。 定义一个二维数组，存储 $n_i$ 与 $n_j$ 的大小关系，优先级高的为 $1$，低的为 $0$​。 具体实现详见代码注释。 代码实现 //改自Yulicezzz的代码 #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define int long long using namespace std; using namespace __gnu_pbds; const int MAXN=1e5+7; map<string,int>name; string s[MAXN]; int mp[1005][1005]; int n,m; signed main() { cin>>m>>n;//按题意输入 for(int i=1;i<=n;i++) { cin>>s[i]; name[s[i]]=i;//map存储优先级 } while(m--) { int l=1;//记录上一个级别的最后一个位置 s[0]='z'+25; for(int i=1;i<=n;i++) { cin>>s[i]; if(s[i]<s[i-1]) { l=i;//更新 } for(int j=1;j<l;j++) { mp[name[s[j]]][name[s[i]]]=-1;//根据优先级存入数组 mp[name[s[i]]][name[s[j]]]=1; } } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i!=j) mp[i][j]==1?cout<<"1":mp[i][j]==-1?cout<<"0":cout<<"?";//输出矩阵 else cout<<"B";//如果 i=j 则输出 B } puts(""); } return 0; } 时间复杂度 约 $O(m ⋅ n^2)$。

方法1：模拟 Alice 筛法（TLE） 根据题意模拟即可（注意：真因数指不包括 $n$ 的所有 $n$​ 的因数）。 代码： #include<bits/stdc++.h> #define int long long using namespace std; inline void solve() { int n; cin>>n; vector<bool>vis(n+1,false);//真因数 int p=n; while(p>1) { for(int i=1;i*i<=p;i++) //标记真因数 { if(p%i==0) { vis[i]=true; if(i!=1&&i!=p/i) vis[p/i]=true; } } int q=-1; for(int i=p-1;i>=2;i--) if(!vis[i]) { q=i;//有被标记的数 break; } if(q==-1)break; p=q;//没有被标记的数 } int count=0;//统计数量 for(int i=2;i<=n;i++) { if(!vis[i]) count++; } cout<<count<<endl; } signed main() { int T; cin>>T; while(T--) solve(); return 0; } 但是提交后发现 TLE 了，说明有一定的规律可循。 方法2：找规律（AC） 题目要求： 创建序列：从 $n$ 到 $2$ 的严格下降序列。 初始化：令 $P=n$。 标记真因数：标记 $P$ 的所有真因数（不包括 $P$ 本身）。 寻找下一个 P：找到从 $P-1$ 到 $2$ 中最大的未被标记的数 $q$，令 $P = q$。 重复：如果 $q$ 存在，重复步骤 $3$ 和 $4$，否则停止。 关键： 标记真因数：每次标记 $P$ 的真因数时 $P$ 本身不会被标记。 寻找下一个 P：每次找到的 $P$ 都是当前未被标记的数中最大的一个。 结果： $n$ 为偶数时：最后一次选 $P$ 时，$P$​ 正好处于 $\frac{n-2}{2}$。 $n$ 为奇数时：最后一次选 $P$ 时，$P$ 正好处于 $\frac{n-2}{2}-1$。 所以： 未被标记的数（即答案）则为 $\lfloor \frac{n+1}{2} \rfloor$。 代码： #include<bits/stdc++.h> #define int long long using namespace std; signed main() { int t; cin>>t; while(t--) { int n; cin>>n; cout<<floor((n+1)/2)<<endl; } return 0; }

这题是典型的排列组合（以下讨论数字个数时都已排除了 $0$） 总的字符串数：字符串长度为 $10000$，且每个位置可以选择的数字有 $9$ 个数字可选，因此，所有可能的字符串总数为：$9^{10000}$。 不包含数字 3：去掉 $3$ 后共有 $8$ 个数字可选，因此不包含 $3$ 的字符串数为：$8^{10000}$。 不包含数字 7：去掉 $7$ 后也共有 $8$ 个数字可选，因此不包含 $7$ 的字符串数也为：$8^{10000}$。 同时不包含数字 3 和 7：则只有 $7$ 个数字可选，因此同时不包含 $3$ 和 $7$ 的字符串数为：$7^{10000}$。 根据容斥原理，同时包含 $3$ 和 $7$，且不包含 $0$ 的字符串数为：$9^{10000}-8^{10000}-8^{10000}+7^{10000}=9^{10000}-2\times8^{10000}+7^{10000}$并将结果对 $10^9+7$​ 取模。 代码实现： MOD=10**9+7 all_=pow(9,10000)#总的字符串数 qu3=pow(8,10000)#不包含数字3(由于不包含数字7的值与3一致，为了节省编译时间，就不再次计算) qu37=pow(7,10000)#同时不包含数字3和7 ans=(all_-2*qu3+qu37)%MOD#代入公式并取模 print(ans) 最终答案为 $157509472$。

双倍经验。 思路 这是一道简单的二维动态规划问题，在每一步向北或向西走时，比较到达该点时，向北走和向西走路上该种矿物的数量总和，并取大的一个。 为了计算更快，可以通过建立 $a$，$b$ 两个前缀和数组来表示该路径上两种矿物的多少。 状态转移 根据思路，不难得出，状态转移方程为： $$ dp[i][j]=\max(a[i][j]+dp[i-1][j],b[i][j]+dp[i][j-1]) $$ 其中 dp[i][j] 代表从 $(1,1)$ 到 $(i,j)$ 的矩阵中最大的采矿量，a[i][j] 和 b[i][j] 分别为 A 矿和 B 矿的二维前缀和，表示采到 $(i,j)$ 所必须经过（即途中必须采集）的矿物数量总和。 结束标志为 $(n,m)$，则答案为 dp[n][m]，输出即可。 代码实现 #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define int long long using namespace std; using namespace __gnu_pbds; int n,m; int A[505][505],B[505][505];//前缀和数组 int dp[505][505]; inline void solve()//dp { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { dp[i][j]=max(A[i][j]+dp[i-1][j],B[i][j]+dp[i][j-1]);//状态转移 } } cout<<dp[n][m]; } inline void pre() { while(cin>>n>>m and n and m)//n=0 且 m=0 时退出不执行 { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>A[i][j]; A[i][j]+=A[i][j-1];//前缀和 } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>B[i][j]; B[i][j]+=B[i-1][j];//前缀和 } } solve(); puts(""); } } signed main() { //freopen(".in","r",stdin); //freopen(".out","w",stdout); pre(); //fclose(stdin); //fclose(stdout); return 0; } 时间复杂度：$O(nm)$。

题目大意 给出两把梯子的高长度 $x$ 和 $y$，以及交叉点 $c$ 的高度，求道路的宽（即两梯子底端之间的距离）。 解题思路 数学 + 二分 可以利用梯子的长度和梯子与地面的夹角来求得道路的宽。 设梯子 $x$ 与 $y$ 与地面的夹角分别为 $\alpha$ 和 $\beta$，道路的宽设为 $w$，梯子 $x$ 的底端与交叉点在地面的水平投影距离为 $h$。 则有 $\sin(\alpha)=\frac{c}{x}$，$\sin(\beta)=\frac{c}{y}$，$\cos(\alpha)=\frac{w+h}{x}$，$\cos(\beta)=\frac{w}{y}$。 解出 $h$ 为：$\displaystyle h=y\times\cos(\beta)=y\times\sqrt{1-\sin^2(\beta)}=y\times\sqrt{1-\frac{c^2}{y^2}}=y\times\frac{\sqrt{y^2-c^2}}{y}=\sqrt{y^2-c^2}$并表示道路宽 $w$ 为：$\displaystyle w=x\times\cos(\alpha)-h=x\times\sqrt{1-\sin^2(\alpha)}-h=x\times\sqrt{1-\frac{c^2}{x^2}}-h=x\times\frac{\sqrt{x^2-c^2}}{x}-h=\sqrt{x^2-c^2}-h$将 $h=\sqrt{y^2-c^2}$ 代入，得：$\displaystyle w=\sqrt{x^2-c^2}-\sqrt{y^2-c^2}$不难看出，该解析式具有单调递减性，又由于数据为实数，则可以使用实数二分，不断逼近所需精度。 代码 #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/hash_policy.hpp> #define int long long #define endl "\n" using namespace __gnu_cxx; using namespace __gnu_pbds; using namespace std; double x,y,c; inline bool check(long double m)//检查函数 { long double h1=sqrt(x*x-m*m); long double h2=sqrt(y*y-m*m); return (h1*h2)<(h1*c+h2*c);//返回精度偏小（true）还是偏大（false）。 } signed main() { while(cin>>x>>y>>c) { long double l=0,r=min(x,y);//左右端点 long double m; while(r-l>=1e-6)//实数二分 { m=(l+r)/2;//注意 double 类型不能用右移运算 if(check(m))r=m; else l=m; } cout<<fixed<<setprecision(3)<<l<<endl; } return 0; }

题目大意 找到满足 $s_1\operatorname{and}s_2=s$ 的字符串对 $(s_1,s_2)$ 的数量，且 $s_1$ 和 $s_2$ 的长度都要与 $s$ 相同，并给出了字符转为数字，进行比较的规则。 解题思路 由于字符串 $s_1$ 和 $s_2$ 的每一位进行与运算的结果都对应着 $s$ 的相应位置，因此我们可以对 $s$ 的每一位进行单独分析。 针对 $s$ 的每一位，只有两种情况： 该位二进制为 $1$，则 $s_1$ 和 $s_2$ 的对应位都为 $1$。 该位二进制为 $0$，则 $s_1$ 和 $s_2$ 的对应位为 $00$，$01$ 或 $10$。 因此，对于 $s$ 的每一位，我们只需要统计该位表示为数字后，二进制表示中 $0$ 的个数总和，记为 $sum$，对于每一个 $0$ 最多有三种情况，根据乘法原理，最终答案为 $3^{sum}$。 代码 #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/hash_policy.hpp> #define int long long #define endl "\n" using namespace __gnu_cxx; using namespace __gnu_pbds; using namespace std; const int MOD=1e9+7;//记得模1e9+7 int ans; inline int check(int n)//检查函数，计算二进制表示下 0 的的个数 { int sum=0; for(int i=1;i<=6;i++)//数最大为 64，则二进制最多有 6 位，只需检查 6 位 { if(n&1)n>>=1;//当前末尾为 1，右移一位 else n>>=1,sum++;//末尾为 0，计数器加 1，右移一位 } return sum; } inline int fastpow(int b,int a)//此题需要用到快速幂 { int res=1; while(b) { if(b&1) res=res*a%MOD; a=a*a%MOD; b>>=1; } return res; } signed main() { string s; cin>>s; for(char c:s) { int n; if(c>='0'&&c<='9')n=c-'0';//按题目要求进行字符与数字间转换 if(c>='A'&&c<='Z')n=c-'A'+10; if(c>='a'&&c<='z')n=c-'a'+36; if(c=='-')n=62; if(c=='_')n=63; ans+=check(n);//累加 0 的个数 } cout<<fastpow(ans,3); return 0; } 时间复杂度 $O(|s|\log |s|)$，其中 $|s|$ 表示字符串 $s$ 的长度。 空间复杂度 $O(|s|)$，所需存储空间取决于字符串 $s$ 的长度，并随着 $s$ 长度的增加而线性增加。

题目大意 给定一个只包含字符 a 和 b 的字符串，通过删除字符（可以不删除）将其转化为满足以下条件的最长字符串： 字符串可以分为三段。 第一段和第三段仅包含 a。 第二段仅包含 b。 每一段都可以为空。 解决思路 可以使用动态规划解决，$dp_{i,j}$ 表示前 $i$ 个字符，第 $j$ 段时，最长美丽字符串的长度，其中 $j\in{0,1,2}$。 可以考虑逐个考虑字符串 $s$ 的每一位： 如果 $s_i$ 是 a，那么： $dp[i][0]=dp[i-1][0]+1$，即第一段延长； $dp[i][1]=dp[i-1][1]$，即第二段不变； $dp[i][2]=\max(dp[i-1][1],dp[i-1][2])+1$，即第三段开始或延长。 如果 $s_i$ 是 b，那么： $dp[i][0]=dp[i-1][0]$，即第一段不变； $dp[i][1]=\max(dp[i-1][0],dp[i-1][1])+1$，即第二段开始或延长； $dp[i][2]=dp[i-1][2]$，即第三段不变。 则最终答案是 $\max(dp[n][0],\max(dp[n][1],dp[n][2]))$，其中，$n$ 为字符串 $s$ 的长度。 代码 #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define int long long #define tem template #define sizet size_t #define il inline #define uni union #define endl "\n" const int INF=0xfffffff; using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; int dp[5005][3]; signed main() { char a; a=getchar(); dp[0][0]=dp[0][2]=(a=='a')?1:0;//初始化 dp[0][1]=1-dp[0][0]; string s; cin>>s; for(int i=0;i<s.size();i++) { if(s[i]=='a')//状态转移 { dp[i+1][0]=dp[i][0]+1; dp[i+1][1]=dp[i][1]; dp[i+1][2]=max(dp[i][1],dp[i][2])+1; } else { dp[i+1][0]=dp[i][0]; dp[i+1][1]=max(dp[i][0],dp[i][1])+1; dp[i+1][2]=dp[i][2]; } } cout<<max(dp[s.size()][0],max(dp[s.size()][1],dp[s.size()][2]))<<endl; return 0; } 时间复杂度 $O(|s|)$，其中 $|s|$ 是字符串 $s$ 的长度。 空间复杂度 $O(|s|)$。