5.3训练记录
知识简述
- 双指针：跟题目类似，就是使用两个指针不断地运动递归。不过要注意两个指针不能乱动。
- 双向搜索（折半搜索）：主要目的是降低时间复杂度，因为一般的搜索时间复杂度是呈指数级的，而双向搜索可以让复杂度整体开根号，指数除以 2 。
- 尺取法：如下图所示，不做过多赘述。
4.floyd判环：
主要解决如·下图形状的判环。定义两个快慢指针，快指针一步走两个，慢指针一步走一个，第一次他们相遇时让快指针回到起点，下一次相遇的地点就是环的入口。
题目简介
Meet in the Middle
给定 n 和一个长度为 n 的数组，有多少种方法选择一个该数组的子集使得和为 x 。
就是双向搜索的模版题目
#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int, int> vis;
#define N 50
int n,x,a[N],mid,ans;
void dfs1(int i,int sum)//第一个搜索
{
if(i>mid)
{
vis[sum]++;
return;
}
dfs1(i+1,sum);
dfs1(i+1,sum+a[i]);
}
void dfs2(int i,int sum)//后一半搜索
{
if(vis[x-sum]&&i>n)
{
ans+=vis[x-sum];
return;
}
if(i>n)
return;
dfs2(i+1,sum);
dfs2(i+1,sum+a[i]);
}
signed main()
{
cin>>n>>x;
mid=n>>1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
if(n==1&&x==1&&a[1]==1)//特判
{
cout<<1<<endl;
return 0;
}
dfs1(2,0);
dfs1(2,a[1]);
dfs2(mid+2,a[mid+1]);//从中间断开搜索
dfs2(mid+2,0);
cout<<ans<<endl;
}
异或路径
给你一个 n \ast m 的矩阵 a ，问有多少种从 (1,1) 到 (n,m) 只能往下走或者往右走的路径，使得路径上的权值的异或和为一个给定的数 k 。
这题的难点就是折半搜索折在哪里的问题。敲黑板，因为矩阵要让他两边的搜索尽可能地短，我们就要选对角线 ，也就是 n+m-2 懂了这个这道题也就不难了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=25;
int a[maxm][maxm];
int dir1[2][2]={0,1,1,0};
int dir2[2][2]={0,-1,-1,0};
map<int,int>mark[maxm][maxm];
int n,m,k;
int ans;
void dfs1(int x,int y,int step,int val){//搜索
if(!step){
mark[x][y][val]++;
return ;
}
for(int k=0;k<2;k++){
int xx=x+dir1[k][0];
int yy=y+dir1[k][1];
if(xx<1||xx>n||yy<1||yy>m)continue;
dfs1(xx,yy,step-1,val^a[xx][yy]);
}
}
void dfs2(int x,int y,int step,int val){
if(!step){
if(mark[x][y].count(val^k)){
ans+=mark[x][y][val^k];
}
return ;
}
val^=a[x][y];
for(int k=0;k<2;k++){
int xx=x+dir2[k][0];
int yy=y+dir2[k][1];
if(xx<1||xx>n||yy<1||yy>m)continue;
dfs2(xx,yy,step-1,val);
}
}
signed main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
int step=n-1+m-1;
dfs1(1,1,step/2,a[1][1]);//对角线折半
dfs2(n,m,step-step/2,0);
cout<<ans<<endl;
return 0;
}
mex和med
假设当前的 mex 值是 i 那么区间一定包含 0∼i−1 ，同时区间长度小于等于 i \ast 2 。我们对于每个 mex 值为 i 都仅考虑包含它的长度为 i \ast 2 和长度为 i \ast 2-1 的区间的个数，因为长度为 i \ast 2-2 的区间一定在 mex 值为 i-1 时统计过。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,t;
int a[200005],to[200005];
signed main()
{
cin>>n;
int ans=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
to[a[i]]=i;
}
int l=INT_MAX,r=0;
for(int i=0;i<n;i++)
{
l=min(l,to[i]),r=max(r,to[i]);
int len=i*2+2;
int l1,r1;
if(r-l+1>len)
continue;
l1=max(1ll,r-len+1),r1=min(l,n-len+1);
ans+=max(0ll,(r1-l1+1));
len--;
if(r-l+1>len)
continue;
l1=max(1ll,r-len+1),r1=min(l,n-len+1);
ans+=max(0ll,(r1-l1+1));
}
cout<<ans<<endl;
}
囊中羞涩
这题和 Meet in the Middle 几乎一样，不过多赘述
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[100005];
int ans=0;
int b[1000005],c[1000005];
void dfs(int now,int nn,int res,int *b)
{
if(res>m)
return;
if(now>nn)
{
b[++b[0]]=res;
return;
}
dfs(now+1,nn,res+a[now],b);
dfs(now+1,nn,res,b);
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
sort(a+1,a+n+1);
dfs(1,n/2,0,b);
dfs(n/2+1,n,0,c);
sort(b+1,b+b[0]+1);
for(int i=1;i<=c[0];i++)
{
int l=1,r=b[0],res;
while(l<=r)
{
int mid=(l+r)/2;
if(b[mid]+c[i]<=m)
res=mid,l=mid+1;
else
r=mid-1;
}
ans+=res;
}
printf("%lld",ans);
return 0;
}
特殊价值
这道题的话主要是思路难想，思路就是前缀和记录，再尺取法更新答案。
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
long long n,a[N],x[N];
long long s[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s[i]=s[i-1]+a[i];//前缀和记录异或的值和和
x[i]=x[i-1]^a[i];
}
long long ans=s[n]-x[n];//最大值
int ansl=1,ansr=1e9,l,r=1;//分别是答案的区间两端，和目前的区间两端
for(l=1;l<=n;l++)
{
while(s[r]-s[l-1]-(x[r]^x[l-1])<ans&&r<=n)//尺取法，直到不满足
{
r++;
}
if(r>n)//越界了
break;
if(r-l<ansr-ansl)//更改答案
{
ansl=l;
ansr=r;
}
}
printf("%d %d\n",ansl,ansr);//输出
return 0;
}