删点
思路:
1.统计$x>0$和$x<0$的点数.并判断各自减去一个点后满足条件.
AC Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llINF=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
bool cal(int a,int b)
{
int res1=max(a-1,0);
int res2=max(b-1,0);
return ((res1==0||b==0)||(res2==0||a==0));
}
void solve()
{
int n;
cin>>n;
int cnt1=0;
int cnt2=0;
int cnt3=0;
int cnt4=0;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
if(x>0)cnt3++;
if(x<0)cnt4++;
}
if(cal(cnt3,cnt4))cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
时间复杂度$O(n)$
两种操作
思路：
1.由于相对关系直接将原操作逆着对$m$逆着爆搜一遍就可以了.
： 为毛逆着也能搜出来.有知道的大佬请告诉我下咋证明。
AC Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llINF=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n,m;
cin>>n>>m;
int ans=0;
while(n!=m)
{
if(m>n&&m%2==0)m/=2;
else m++;
ans++;
}
cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
BFS正解:
以$n$为源点出发按操作建图,搜索$m$到$n$的最短路即可.
重点：
1.BFS的过程要剪枝,一个是$n\geq m$时 只能进行减法操作 直接返回.
2.实际$n\leq m$时,点的最大值一定不会超过$2m$,因为一但通过乘法操作$\geq m$时只能减法.因此超过$m$数的范围就是$[m,2m-1]$
针对以上两种情况,如果不减掉该状态.BFS会因为状态过多超内存。
AC Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llINF=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int dist[N];
int n,m;
void bfs()
{
memset(dist,INF,sizeof dist);
dist[n]=0;
queue<int>q;
q.push(n);
while(!q.empty())
{
auto t=q.front();
q.pop();
int d1=t*2,d2=t-1;//每次能到达的新的位置
if(dist[d1]>dist[t]+1&&d1>0&&d2<=2*m)
{
dist[d1]=dist[t]+1;
q.push(d1);
}
if(dist[d2]>dist[t]+1&&d2>0&&d2<=2*m)
{
dist[d2]=dist[t]+1;
q.push(d2);
}
}
}
void solve()
{
cin>>n>>m;
if(n>=m)
{
cout<<n-m<<endl;
return;
}
bfs();
cout<<dist[m]<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
时间复杂度$O(m)$
截断数列
思路：
1.枚举第一个区间所有可能值,一一判断即可.
具体怎么判断看代码.
2.注意特判下全$0$的情况,该值区间数量是$\geq 2$
可以将暴力判断的过程优化成 在前缀上二分.
$check$函数时间复杂度会从$O(n)$优化成$O(\log n)$
AC Code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llINF=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int n;
char a[N];
bool check(int x)
{
int l=1;
int cnt=0;
while(l<=n)
{
int res=0;
for(int i=l;i<=n;i++)
{
res+=(a[i]-'0');
if(res==x)
{
l=i+1;
cnt++;
break;
}else
{
if(res>x)return false;
}
}
if(res!=x)return false;
while((a[l]-'0')==0&&l<=n)l++;
}
return cnt>=2;
}
void solve()
{
cin>>n;
int sum=0;
bool flag=true;
for(int i=1;i<=n;i++)
{
cin>>a[i],sum+=(a[i]-'0');
if(a[i]!='0')flag=false;
}
if(flag)//全0 必定有答案
{
cout<<"YES"<<endl;
return;
}
for(int i=0;i<=sum;i++)//枚举所有第一个区间的所有可能值
if(check(i))
{
cout<<"YES"<<endl;
return;
}
cout<<"NO"<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
时间复杂度$O(S_a*n)$
