做题笔记Ⅰ
做题笔记Ⅰ
动态规划
P3572
题面翻译
有 \(n\) 棵树排成一排，第 \(i\) 棵树的高度是 \(d_i\)。
有 \(q\) 只鸟要从第 \(1\) 棵树到第 \(n\) 棵树。
当第 \(i\) 只鸟在第 \(j\) 棵树时，它可以飞到第 \(j+1, j+2, \cdots, j+k_i\) 棵树。
如果一只鸟飞到一颗高度大于等于当前树的树，那么它的劳累值会增加 \(1\)，否则不会。
由于这些鸟已经体力不支，所以它们想要最小化劳累值。
题解
考虑一种复杂度为 \(O(n^2q)\) 的朴素做法，显然不可过。
观察题目，发现转移的区间是近似于滑动窗口的。考虑单调队列优化。
对于单调队列有一句经典的话： 如果一个选手比你小，还比你强，你就可以退役了 。我们通常有一个误区，那就是队列内的点都是会产生贡献的转移点，但其实不是。单调队列内的点是有优劣之分的，我们之所以保存其他点，是因为最优的点会退役，而其他点会在之后成为最优点。从某种程度上来说，这与但单调栈是类似的，这也是保证复杂度的关键。
回到本题，我们在队列中留下 \(dp\) 与 \(a\) 相对优的值，线性 \(dp\) 即可。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
int n,a[N],q,k,dp[N];
list<int>z;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cin>>q;
while(q--)
{
cin>>k;
z.clear();
z.push_back(1);
for(int i=2;i<=n;i++)
{
if(z.size()!=0&&i-z.front()>k)
z.pop_front();
dp[i]=dp[z.front()]+(a[z.front()]<=a[i]);
while(z.size()!=0&&(dp[z.back()]>dp[i]||(dp[z.back()]==dp[i]&&a[z.back()]<a[i])))
z.pop_back();
z.push_back(i);
}
cout<<dp[n]<<endl;
}
return 0;
}
P2034
题目描述
给定一行 \(n\) 个非负整数 \(a_1 \cdots a_n\)。现在你可以选择其中若干个数，但不能有超过 \(k\) 个连续的数字被选择。你的任务是使得选出的数字的和最大。
题解
正难则反，考虑将原问题转化为从 \(a\) 中选若干数使得，任意两数差不大于 \(k\),求答案最小。
观察到问题类似于滑动窗口，考虑单调队列优化dp。
我们考虑那句经典的话：如果一个选手比你小，还比你强，你就可以退役了。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+100;
int n,k,a[N],dp[N],ans=LLONG_MAX,sum;
list<int>q;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i],sum+=a[i];
memset(dp,63,sizeof(dp));
dp[0]=0;
q.push_back(0);
for(int i=1;i<=n;i++)
{
if(q.front()<i-k-1)
q.pop_front();
dp[i]=min(dp[i],dp[q.front()]+a[i]);
while(dp[i]<=dp[q.back()])
q.pop_back();
q.push_back(i);
}
for(int i=n;i>=n-k;i--)
{
ans=min(ans,dp[i]);
}
cout<<sum-ans;
return 0;
}
P6584
题目描述
小 Z 和 \(m\) 个 Youyou 在一棵树上相遇了！
这棵树上，每条边的长度都是 \(1\)。
初始时，小 Z 在 \(x\) 号节点上，并且有一把射程为 \(k\) 的枪。
因为小 Z 技术精湛，所以 Youyou 一打就死，而小 Z 永远不会死掉。
小 Z 和 Youyou 都按回合行动，在每一回合中，按照下面的顺序行动：
-
回合计数器 \(+1\)（初始为 \(0\)）。
-
小 Z 可以用枪射死与小 Z 树上距离小于等于 \(k\) 的所有 Youyou。
-
如果所有 Youyou 都被消灭了，游戏结束，这时回合计数器的值就是小 Z 用的回合数。
-
小 Z 可以选择沿着一条边，移动到任意相邻节点，也可以选择不动。
-
所有 Youyou 都会沿着他和小 Z 的简单路径向小 Z 移动一条边的距离。如果此时他们在同一个节点，则不动。
小 Z 需要求出消灭所有敌人需要的最小回合数。
题解
我们考虑小 Z 延边移动的操作。我们发现，动不一定优，简单来说，当小 Z 朝一个 Youyou 走时，其他子树的 Youyou 与小 Z 相对不变，这样，当小 Z 打完那个 Youyou 时，还要调头打其余的 Youyou 。
于是，我们有了一个思路：
1.打击其他子树的 Youyou。
2.向最深的 Youyou前进。
我们预处理出 \(dp[i]\) 表示在以 \(i\) 为根节点得到子树中，最远 \(Youyou\) 与 \(i\) 的距离。模拟上述两个操作即可，值得注意的是，题中操作顺序繁琐，细节颇多。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+100;
int k,n,m,root,dp[N];
bool f[N];
vector<int>edge[N];
void dfs1(int x,int fa)
{
if(f[x]==1)
dp[x]=0;
for(int i=0;i<edge[x].size();i++)
{
int to=edge[x][i];
if(to==fa)
continue;
dfs1(to,x);
dp[x]=max(dp[x],dp[to]+1);
}
return;
}
void dfs2(int x,int fa,int nw)
{
int mx=-1,mn=-1,mxd,mnd;
for(int i=0;i<edge[x].size();i++)
{
int to=edge[x][i];
if(to==fa)
continue;
if(dp[to]>mx)
{
mn=mx;
mnd=mxd;
mx=dp[to];
mxd=to;
}
else if(dp[to]>mn)
{
mn=dp[to];
mnd=to;
}
}
mx++,mn++;
int us=max(mn-nw-k,0);
if(mx-us-nw<=k)
{
cout<<nw+us+1;
exit(0);
}
dfs2(mxd,x,nw+us+1);
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
edge[u].push_back(v);
edge[v].push_back(u);
}
cin>>m;
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
f[x]=1;
}
cin>>k>>root;
memset(dp,-63,sizeof(dp));
dfs1(root,0);
dfs2(root,0,0);
return 0;
}
CF1324F
题目描述
- 给定一棵 \(n\) 个节点无根树，每个节点 \(u\) 有一个颜色 \(a_u\)，若 \(a_u\) 为 \(0\) 则 \(u\) 是黑点，若 \(a_u\) 为 \(1\) 则 \(u\) 是白点。
- 对于每个节点 \(u\)，选出一个包含 \(u\) 的连通子图，设子图中白点个数为 \(cnt_1\)，黑点个数为 \(cnt_2\)，请最大化 \(cnt_1 - cnt_2\)。并输出这个值。
- \(1 \leq n \leq 2 \times 10^5\)，\(0 \leq a_u \leq 1\)。
题解
本题为换根dp的基础题。为什么需要换根dp呢？原因是普通的dp只能维护节点子树类的信息。
对于此题，我们考虑一种朴素的求解方式，对于每个节点，枚举其作为根结点。令 \(dp[x]\) 为在节点 \(x\) 的子树内，包含 \(x\) 的连通子图的答案最大值，转移只需枚举产生正贡献的儿子即可。但是显然，这样的复杂度是爆炸的。
我们考虑换根dp。按照dfs序遍历每个节点为根节点的情况，我们不难发现，每次换根，只会改变交换的两节点的 \(dp\) 值，暴力修改即可。复杂度线性。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int n,a[N],dp[N],ans[N];
vector<int>edge[N];
void dfs1(int x,int fa)
{
if(a[x]==1)
dp[x]++;
else
dp[x]--;
for(int i=0;i<edge[x].size();i++)
{
int to=edge[x][i];
if(to==fa)
continue;
dfs1(to,x);
if(dp[to]>0)
dp[x]+=dp[to];
}
return;
}
void dfs2(int x,int fa)
{
for(int i=0;i<edge[x].size();i++)
{
int to=edge[x][i];
if(to==fa)
continue;
int xx=dp[to],xxx=dp[x];
if(dp[to]>0)
dp[x]-=dp[to];
if(dp[x]>0)
dp[to]+=dp[x];
ans[to]=dp[to];
dfs2(to,x);
dp[to]=xx;
dp[x]=xxx;
}
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs1(1,0);
ans[1]=dp[1];
dfs2(1,0);
for(int i=1;i<=n;i++)
{
cout<<ans[i]<<" ";
}
return 0;
}
P3478
题目描述
给定一个 \(n\) 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。
一个结点的深度之定义为该节点到根的简单路径上边的数量。
题解
本题为换根dp的简单题。
我们令 \(dp[x]\) 为以 \(x\) 为根节点的子树内的节点深度之和。令 \(s[x]\) 为以 \(x\) 为根节点的子树大小。注意：这里的深度是从节点到根的路径长，为方便求解可以考虑给0号节点设上-1。
初始时我们令根为1，换根时，注意一下更新顺序，分别更新 \(dp\) 和 \(x\) 即可。最后严谨起见，防止如下hack：
in:
1
ans:
1
我们给初始值附上1。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+100;
int n,u,v,ans,mx,dp[N],s[N],d[N];
vector<int>edge[N];
void dfs1(int x,int fa)
{
d[x]=d[fa]+1;
dp[x]=d[x];
s[x]=1;
for(int i=0;i<edge[x].size();i++)
{
int to=edge[x][i];
if(to==fa)
continue;
dfs1(to,x);
s[x]+=s[to];
dp[x]+=dp[to];
}
return;
}
void dfs2(int x,int fa)
{
for(int i=0;i<edge[x].size();i++)
{
int to=edge[x][i];
if(to==fa)
continue;
int x1=dp[x],x2=dp[to],x3=s[x],x4=s[to];
s[x]-=s[to];
dp[x]-=dp[to]-s[x];
dp[to]+=dp[x]-s[to];
s[to]+=s[x];
if(dp[to]>mx)
{
mx=dp[to];
ans=to;
}
dfs2(to,x);
dp[x]=x1,dp[to]=x2,s[x]=x3,s[to]=x4;
}
return;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<n;i++)
{
cin>>u>>v;
edge[u].push_back(v);
edge[v].push_back(u);
}
d[0]=-1;
dfs1(1,0);
mx=dp[1];
ans=1;
dfs2(1,0);
cout<<ans;
return 0;
}
图论
P5952
题目描述
在地面上有一个水箱，它的俯视图被划分成了 \(n\) 行 \(m\) 列个方格，相邻两个方格之间有一堵厚度可以忽略不计的墙，水箱与外界之间有一堵高度无穷大的墙，因此水不可能漏到外面。已知水箱内每个格子的高度只能是 \([0,H]\) 之间的整数，请统计有多少可能的水位情况。
因为答案可能很大，请对 \(10^9+7\) 取模输出。
我们说两种情况是不同的当且仅当存在至少一个方格的水位在两个情况中不同。
题解
这是一道网格图转最小生成树的巧妙题，本质是木桶效应。
根据样例，不难发现连通块的算法。但是怎样确定计算的顺序呢？
我们考虑从小加边，跑最小生成树，对合并的连通块算贡献，因为其他的墙均高于当前，因此不会产生新的连通块，这样顺序就确定了。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int N=5e5+100;
int n,m,H,fa[N],h[N],ans[N];
struct node{
int u,v,val;
bool operator < (const node &x) const
{
return val<x.val;
}
};
vector<node>p;
int id(int x,int y)
{
return (x-1)*m+y;
}
int find(int x)
{
if(fa[x]!=x)
{
fa[x]=find(fa[x]);
}
return fa[x];
}
void merge(int x,int y,int v)
{
x=find(x),y=find(y);
ans[x]=(((ans[x]+v-h[x])%mod)*((ans[y]+v-h[y])%mod))%mod;
h[x]=v;
fa[y]=x;
return;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m>>H;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
fa[id(i,j)]=id(i,j);
ans[id(i,j)]=1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<m;j++)
{
int x;
cin>>x;
p.push_back(node{id(i,j),id(i,j+1),x});
}
}
for(int i=1;i<n;i++)
{
for(int j=1;j<=m;j++)
{
int x;
cin>>x;
p.push_back(node{id(i,j),id(i+1,j),x});
}
}
sort(p.begin(),p.end());
for(int i=0;i<p.size();i++)
{
if(find(p[i].u)==find(p[i].v))
continue;
merge(p[i].u,p[i].v,p[i].val);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(find(id(i,j))==id(i,j))
{
cout<<(ans[id(i,j)]-h[id(i,j)]+H)%mod;
return 0;
}
}
}
return 0;
}
数据结构
P3594题解
题目描述
给定一个长度为 \(n\) 的序列，你有一次机会选中一段连续的长度不超过 \(d\) 的区间，将里面所有数字全部修改为 \(0\)。请找到最长的一段连续区间，使得该区间内所有数字之和不超过 \(p\)。
题解
根据贪心的思想，因为数字之和不超过 \(p\)，且希望选择的长度尽量长，显然选择的数因为尽量小。又因为数值为正数，因此将一个数变为\(0\)，显然是优的，因此可以将不超过 \(d\) 转化为 \(d\)。我们不难发现，答案区间一定是包含 \(d\) 的。
我们用单调队列维护答案区间，统计时减去区间类长度为 \(d\) 的权值最大区间，这个可以用单调队列线性维护，用st表会MLE，线段树会TLE。
以下给出线段树O2的实现：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+100;
int n,p,d,a[N],qz[N],tree[N*4],sum,L=1,ans=INT_MIN,w[N];
int lson(int l,int r)
{
return (l+r)/2;
}
int rson(int l,int r)
{
return (l+r)/2+1;
}
void update(int x)
{
tree[x]=max(tree[x*2],tree[x*2+1]);
return;
}
void build(int l,int r,int x)
{
if(l==r)
{
tree[x]=w[l];
return;
}
build(l,lson(l,r),x*2);
build(rson(l,r),r,x*2+1);
update(x);
return;
}
int get(int l,int r,int x,int l1,int r1)
{
if(l>=l1&&r<=r1)
{
return tree[x];
}
int sum=0;
if(lson(l,r)>=l1)
sum=max(sum,get(l,lson(l,r),x*2,l1,r1));
if(rson(l,r)<=r1)
sum=max(sum,get(rson(l,r),r,x*2+1,l1,r1));
return sum;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>p>>d;
for(int i=1;i<=n;i++)
{
cin>>a[i];
qz[i]=qz[i-1]+a[i];
}
for(int i=d;i<=n;i++)
{
w[i]=qz[i]-qz[i-d];
}
build(1,n,1);
for(int i=1;i<d;i++)
{
sum+=a[i];
}
for(int i=d;i<=n;i++)
{
sum+=a[i];
int rs=sum-get(1,n,1,L+d-1,i);
while(rs>p)
{
sum-=a[L++];
rs=sum-get(1,n,1,L+d-1,i);
}
ans=max(ans,i-L+1);
}
cout<<ans;
return 0;
}
数学
CF1545B题解
题目描述
你有一个长为 \(n\) 的棋盘,这个棋盘上有一些棋子,你可以进行如下操作:
如果第 \(i + 2\) 个位置是空的,且第 \(i + 1\) 个位置非空,则可以将第 \(i\) 个位置的棋子挪到第 \(i + 2\) 个位置 (\(i + 2 \leq n\)).
如果第 \(i - 2\) 个位置是空的,且第 \(i - 1\) 个位置非空,则可以将第 \(i\) 个位置的棋子挪到第 \(i - 2\) 个位置 (\(i - 2 \geq 1\)).
现在将给出一个棋盘的初始状态,求可以通过上述操作可以到达的状态数,你可以进行任意次操作,答案对 \(998244353\) 取模.
题解
模拟样例，很容易发现棋子是两两一组进行移动的。我们考虑在没有落单的棋子时我们怎么做这道题，显然我们可以用组合数学插板法解决。
接着，我们来考虑落单的棋子，我们观察发现，落单棋子，要么不动，要么被推着走，所以，成对棋子的移动，完全决定了落单棋子的移动，我们直接删除他们即可。
我们设空格的数量为 \(num1\)，成对棋子的对数为 \(num2\)。答案即为 \(C_{num1+num2}^{num2}\)。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int N=2e5+100;
int t,n,inv[N],qinv[N],qz[N];
string s;
int qpow(int a,int b)
{
int s=1,base=a;
while(b!=0)
{
if(b&1==1)
{
s*=base;
s%=mod;
}
base*=base;
base%=mod;
b>>=1;
}
return s;
}
void pre()
{
for(int i=1;i<=N-100;i++)
{
inv[i]=qpow(i,mod-2);
}
qinv[0]=1;
for(int i=1;i<=N-100;i++)
{
qinv[i]=qinv[i-1]*inv[i];
qinv[i]%=mod;
}
qz[0]=1;
for(int i=1;i<=N-100;i++)
{
qz[i]=qz[i-1]*i;
qz[i]%=mod;
}
return;
}
void C(int a,int b)
{
cout<<((qz[a]*qinv[a-b])%mod*qinv[b])%mod<<endl;
return;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
pre();
cin>>t;
while(t--)
{
cin>>n>>s;
s=" "+s;
int num1=0,num2=0;
bool f=1;
for(int i=1;i<=n;i++)
{
if(s[i]=='0')
{
f=1;
num1++;
}
else
{
f^=1;
num2+=f;
}
}
C(num1+num2,num2);
}
return 0;
}
P2158
题目描述
作为体育委员，C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 \(N \times N\) 的方阵，为了保证队伍在行进中整齐划一，C 君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐（如下图）。
现在，C 君希望你告诉他队伍整齐时能看到的学生人数。
题解
首先考虑从C君引出的一条直线上只会有一个点产生贡献，由此想到一次函数。
考虑以C君为原点建系，显然只有横纵坐标互质的点会产生贡献，又因为横纵坐标对称，所以只需要算出1n-1的欧拉函数之和乘2即可，特判(1,1)(注意这里是1n-1的和，部分题解给出的解释是因为算的行列是1~n-1，但其实只是碰巧相等而已，实质是多出的，和少的部分相等)。
最后注意一下欧拉函数和埃氏筛的求法。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=4e4+100;
int n,p[N],ans;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
p[i]=i;
for(int i=2;i<=n;i++)
if(p[i]==i)
for(int j=i;j<=n;j+=i)
p[j]-=p[j]/i;
for(int i=1;i<=n-1;i++)
ans+=p[i];
ans*=2;
if(n!=1)
ans+=1;
cout<<ans;
return 0;
}
P2152
题目描述
Sheng bill 有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的最大公约数！因此他经常和别人比赛计算最大公约数。有一天Sheng bill很嚣张地找到了你，并要求和你比赛，但是输给 Sheng bill 岂不是很丢脸！所以你决定写一个程序来教训他。
题解
题解的方法很乱，但我的方法就只是高精度模拟辗转相除，考虑到高精模实在是有些许困难，所以我们用相减更损法取而代之，显然他的复杂度是非常爆炸的。
考虑优化，当两个数非常接近的时候，我们发现，相减的复杂度跟取模的效果是一模一样的。但是当两数数位相差较大时怎么办呢？很简单，我们可以补位。最后注意一下常数带来的影响就可以极限过了！
代码：
#include<bits/stdc++.h>
#define rint register int
using namespace std;
const int N=1e4+100;
string s1,s2;
int l,op;
struct node{
int l,a[N];
inline bool operator < (const node &x)const
{
if(l!=x.l)
return l<x.l;
for(rint i=l;i>=1;i--)
{
if(a[i]!=x.a[i])
return a[i]<x.a[i];
}
return false;
}
inline bool operator == (const node &x)const
{
if(l!=x.l)
return false;
for(rint i=l;i>=1;i--)
{
if(a[i]!=x.a[i])
return false;
}
return true;
}
}a1,a2,z;
inline void gcd()
{
if(a1==a2)
return;
if(a1<a2)
{
if(a2.l>a1.l)
{
op=0,l=a2.l-a1.l;
for(rint i=a2.l;i>=a2.l-a1.l+1;i--)
{
if(a2.a[i]>a1.a[i-l])
{
op=1;
break;
}
else if(a2.a[i]<a1.a[i-l])
{
op=-1;
break;
}
}
if(op==0)
{
for(rint i=a2.l-a1.l;i>=1;i--)
{
if(a2.a[i]!=0)
{
op=1;
break;
}
}
}
if(op==0)
{
a2=a1;
return;
}
if(op==1)
{
for(rint i=a2.l;i>=a2.l-a1.l+1;i--)
z.a[i]=a1.a[i-l];
for(rint i=a2.l-a1.l;i>=1;i--)
z.a[i]=0;
z.l=a2.l;
}
if(op==-1)
{
for(rint i=a2.l-1;i>=a2.l-a1.l;i--)
z.a[i]=a1.a[i-l+1];
for(rint i=a2.l-a1.l-1;i>=1;i--)
z.a[i]=0;
z.l=a2.l-1;
}
}
else
{
z=a1;
}
while(z<a2)
{
for(rint i=1;i<=z.l;i++)
{
a2.a[i]-=z.a[i];
if(a2.a[i]<0)
a2.a[i]+=10,a2.a[i+1]-=1;
}
for(rint i=a2.l;i>=1;i--)
{
if(a2.a[i]==0)
a2.l=i-1;
else
break;
}
}
gcd();
}
else
{
if(a1.l>a2.l)
{
op=0,l=a1.l-a2.l;
for(rint i=a1.l;i>=a1.l-a2.l+1;i--)
{
if(a1.a[i]>a2.a[i-l])
{
op=1;
break;
}
else if(a1.a[i]<a2.a[i-l])
{
op=-1;
break;
}
}
if(op==0)
{
for(rint i=a1.l-a2.l;i>=1;i--)
{
if(a1.a[i]!=0)
{
op=1;
break;
}
}
}
if(op==0)
{
a1=a2;
return;
}
if(op==1)
{
for(rint i=a1.l;i>=a1.l-a2.l+1;i--)
z.a[i]=a2.a[i-l];
for(rint i=a1.l-a2.l;i>=1;i--)
z.a[i]=0;
z.l=a1.l;
}
if(op==-1)
{
for(rint i=a1.l-1;i>=a1.l-a2.l;i--)
z.a[i]=a2.a[i-l+1];
for(rint i=a1.l-a2.l-1;i>=1;i--)
z.a[i]=0;
z.l=a1.l-1;
}
}
else
{
z=a2;
}
while(z<a1)
{
for(rint i=1;i<=z.l;i++)
{
a1.a[i]-=z.a[i];
if(a1.a[i]<0)
a1.a[i]+=10,a1.a[i+1]-=1;
}
for(rint i=a1.l;i>=1;i--)
{
if(a1.a[i]==0)
a1.l=i-1;
else
break;
}
}
gcd();
}
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>s1>>s2;
a1.l=s1.size();
a2.l=s2.size();
for(rint i=0;i<a1.l;i++)
a1.a[a1.l-i]=s1[i]-'0';
for(rint i=0;i<a2.l;i++)
a2.a[a2.l-i]=s2[i]-'0';
gcd();
for(rint i=a1.l;i>=1;i--)
cout<<a1.a[i];
return 0;
}
其它技巧
P5968
题目描述
给定一个数列 \(a\)：
- 当 \(n\le 2\) 时，\(a_n=n\)。
- 当 \(n>2\)，且 \(n\) 是奇数时， \(a_n=2\times a_{n-1}\)。
- 当 \(n>2\)，且 \(n\) 是偶数时，\(a_n=a_{n-1}+r_{n-1}\)。
其中 \(r_{n-1}= \operatorname{mex}(|a_i-a_j|)(1\le i\le j\le n-1)\)， \(\operatorname{mex} \left\{ S\right\}\) 表示最小的不在 \(S\) 集合里面的非负整数。
数列 \(a\) 的前若干项依次为：
\(1,2,4,8,16,21,42,51,102,112,224,235,470,486,972,990,1980\)。
可以证明，对于任意正整数 \(x\)，只存在唯一一对整数 \((p,q)\) 满足 \(x=a_p-a_q\)，定义为 \(\operatorname{repr}(x)\)。
比如 \(\operatorname{repr}(17)=(6,3)\)，\(\operatorname{repr}(18)=(16,15)\)。
现有 \(n\) 个询问，每次给定一个正整数 \(x\)，请求出 \(\operatorname{repr}(x)\)。
题解
对于此类在较小项复杂且无规律的题目，通常考虑其超过值域之后的情况。
对于此题，因为存在倍增的操作，因而当 \(a\) 超过 \(10^9\) 之后就只能通过操作一得到答案。
我们考虑打出 \(a\) 在 \(10^9\) 之类的表并记录答案。对于有答案的，输出答案。反之，O(1)计算即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int a[]={0,1,2,4,8,16,21,42,51,102,112,224,235,470,486,972,990,1980,2002,4004,4027,8054,8078,16156,16181,32362,32389,64778,64806,129612,129641,259282,259313,518626,518658,1037316,1037349,2074698,2074734,4149468,4149505,8299010,8299049,16598098,16598140,33196280,33196324,66392648,66392693,132785386,132785432,265570864,265570912,531141824,531141876,1062283752,1062283805};
int n,x;
struct node{
int val,u,v;
bool operator < (const node &x)const
{
return val<x.val;
}
};
vector<node>p;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
for(int i=1;i<=56;i++)
{
for(int j=1;j<i;j++)
{
p.push_back(node{a[i]-a[j],j,i});
}
}
sort(p.begin(),p.end());
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
int xx=lower_bound(p.begin(),p.end(),node{x,0,0})-p.begin();
if(p[xx].val==x)
{
cout<<p[xx].v<<" "<<p[xx].u<<'\n';
continue;
}
int num=x-xx;
cout<<num*2+56<<" "<<num*2+55<<'\n';
}
return 0;
}
P5539
题目描述
小 X 得到了一个正整数 \(n\) 和一个正整数集合 \(S\)，他想知道有多少个正整数 \(x\) 满足以下所有条件：
- \(3 \le x \le n\)
- 存在 \(a \in S, x \equiv 0 \pmod a\)
- 存在 \(b \in S,x-1 \equiv 0 \pmod b\)
- 存在 \(c \in S,x-2 \equiv 0 \pmod c\)
请你帮小 X 求出来。
题解
首先，看一眼感觉是中国剩余定理。但是复杂度是有问题的。
考虑到 \(abc\) 很大时可以暴力求解，想到套路性的bitset优化暴力。
我们用unsigned long long手写bitset来维护 \(n\) 个数。对于一个数 \(x\in S\)。当 \(x>64\) 时。显然可以直接暴力求解。反之我们用类似于分块的思想，先处理出1~64个 \(x\) 的结果，因为每 \(x\) 为一循环,一个ull又维护64位。因此就构成了一个完整的循环结，再暴力求解即可。
观察到答案只与数有关，统计连续的 \(1\) 即可。
代码：
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull bs[15625009],cs[70];
int n,m;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
if(x>64)
{
for(int j=0;j<=n;j+=x)
bs[j/64]|=(1ull<<(j%64));
}
else
{
for(int j=0;j<=x;j++)
cs[j]=0;
for(int j=0;j<=64;j++)
cs[j*x/64]|=(1ull<<(j*x%64));
for(int j=0;j<=n/64;j++)
bs[j]|=cs[j%x];
}
}
for(int i=n+1;i/64==n/64;i++)
bs[i/64]=((bs[i/64]|(1ull<<(i%64)))^(1ull<<(i%64)));
bs[0]=((bs[0]|1)^1);
int ans=0;
for(int i=0;i<=n/64;i++)
{
ull f=bs[i];
f=f&(f>>1)&(f>>2);
while(f)ans+=(f&1),f>>=1;
}
for(int i=1;i<=n/64;i++)
{
if((bs[i]&1)&&(bs[i-1]&(1ull<<63))&&(bs[i-1]&(1ull<<62)))
ans++;
if((bs[i]&1)&&(bs[i]&2)&&(bs[i-1]&(1ull<<63)))
ans++;
}
cout<<ans;
return 0;
}