目录

1001-深度自同构

1003-游走

1007-单峰数列

1008-比特跳跃

1011-抓拍

1012-死亡之组

---

1001-深度自同构

每个数的答案其实与它的各个因数有关，正向递推一下

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
const int mod=998244353;
int a[N],d[N],f[N];
void solve(){int n;cin>>n;cout<<1<<' ';a[1]=1;for(int i=2;i<=n;i++){f[i]+=1;}for(int i=2;i<=n;i++){d[i]=a[i-1];a[i]=(d[i]+f[i])%mod;for(int j=i*2;j<=n;j+=i)f[j]=(f[j]+d[i])%mod;cout<<a[i]<<' ';}
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;
//    cin >> t;while (t--) solve();return 0;
}

1003-游走

主要是几个点要注意

1：每次插入的数前后路程距离不能大于时间差距，奇偶性要相同，

2：如果开头是一段连续的1，那最小和最大需要特殊考虑

3：最小的答案一定是不减的

#include "bits/stdc++.h"using namespace std;
#define int long longbool check(int q1, int p1, int q2, int p2, int &mint, int &maxt) {int dp = abs((p1 - p2));if (p2 != 1) {maxt = min(maxt, q2 - dp);}if (p1 == 1 && (q2 - q1) % 2 != dp % 2 && q2 - q1 >= dp) {mint = max(mint, q1 + 1);return true;}return dp % 2 == (q2 - q1) % 2 && dp <= q2 - q1;}void solve() {int n, m;cin >> n >> m;map<int, int> f;f[0] = 1;bool bad = false;int mint = 0;int maxt = numeric_limits<int>::max();while (m--) {int op;cin >> op;if (op == 0) {int p, q;cin >> p >> q;if (bad) {continue;}if (f.count(q)) {if (f[q] != p) {bad = true;}continue;}auto it = f.emplace(q, p).first;auto itl = prev(it);auto [q1, p1] = *itl;auto [q2, p2] = *it;if (!check(q1, p1, q2, p2, mint, maxt)) {bad = true;continue;}auto itr = next(it);auto [q3, p3] = *itr;if (itr != f.end() && !check(q2, p2, q3, p3, mint, maxt)) {bad = true;}if (mint > maxt) {bad = true;}} else if (op == 1) {if (bad) {cout << "bad" << '\n';} else {cout << mint << '\n';}} else {if (bad) {cout << "bad" << '\n';} else if (maxt == numeric_limits<int>::max()) {cout << "inf" << '\n';} else {cout << maxt << '\n';}}}
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while (T--)solve();return 0;
}

1007-单峰数列

线段树维护

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+50;
int treez[maxn<<2],treef[maxn<<2],treegd[maxn<<2];
int a[maxn],c[maxn];
void pushup(int p) {                 //更新节点的值treez[p]=treez[p<<1]+treez[p<<1|1];treef[p]=treef[p<<1]+treef[p<<1|1];treegd[p]=treegd[p<<1]+treegd[p<<1|1];
}
void build(int p,int l,int r) {     //建树 树节点为p （左儿子p*2 右儿子p*2+1） l为区间左端点 r为右端点if(l==r) {if(c[l]>0) treez[p]++;else if(c[l]<0) treef[p]++;return;}int mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);pushup(p);if(c[mid]>0&&c[mid+1]<0) treegd[p]++;else if(c[mid]<0&&c[mid+1]>0) treegd[p]+=10;
}void update(int p,int l,int r,int x,int y,int w) { //更新区间 （x,y） 的值 改变量为wif(l==r) {if(c[l]>0) treez[p]--;else if(c[l]<0) treef[p]--;c[l]=c[l]+w;if(c[l]>0) treez[p]++;else if(c[l]<0) treef[p]++;return;}int mid=(l+r)>>1;if(x<=mid)update(p<<1,l,mid,x,y,w);if(mid<y)update(p<<1|1,mid+1,r,x,y,w);pushup(p);if(c[mid]>0&&c[mid+1]<0) treegd[p]++;else if(c[mid]<0&&c[mid+1]>0) treegd[p]+=10;
}int queryz(int p,int l,int r,int x,int y) {int ans=0,mid=(l+r)>>1;if(x<=l&&r<=y) {return treez[p];}if(x<=mid) ans+=queryz(p<<1,l,mid,x,y);if(mid<y) ans+=queryz(p<<1|1,mid+1,r,x,y);return ans;
}
int queryf(int p,int l,int r,int x,int y) {int ans=0,mid=(l+r)>>1;if(x<=l&&r<=y) {return treef[p];}if(x<=mid) ans+=queryf(p<<1,l,mid,x,y);if(mid<y) ans+=queryf(p<<1|1,mid+1,r,x,y);return ans;
}
int querygd(int p,int l,int r,int x,int y) {int ans=0,mid=(l+r)>>1;if(x<=l&&r<=y) {return treegd[p];}if(x<=mid) ans+=querygd(p<<1,l,mid,x,y);if(mid<y) ans+=querygd(p<<1|1,mid+1,r,x,y);if(x<=mid&&mid<y) {if(c[mid]>0&&c[mid+1]<0) ans++;else if(c[mid]<0&&c[mid+1]>0) ans+=10;}return ans;
}
void solve() {int n,q,x,y,w,numz,numf,numgd;int op;cin>>n;for(int i=1; i<=n; i++)cin>>a[i];for(int i=0; i<=n; i++)c[i]=a[i+1]-a[i];
//	for(int i=0;i<=n;i++) cout<<i<<' '<<c[i]<<'\n';build(1,1,n);cin>>q;for(int i=1; i<=q; i++) {cin>>op;if(op==1) {cin>>x>>y>>w;if(x>0) update(1,1,n,x-1,x-1,w);update(1,1,n,y,y,-1*w);} else if(op==2) {cin>>x>>y;if(x==y) {cout<<1<<'\n';continue;}numz=queryz(1,1,n,x,y-1);numf=queryf(1,1,n,x,y-1);if(!numz&&!numf) cout<<1<<'\n';else cout<<0<<'\n';} else if(op==3) {cin>>x>>y;if(x==y) {cout<<1<<'\n';continue;}numz=queryz(1,1,n,x,y-1);if(numz==y-x) cout<<1<<'\n';else cout<<0<<'\n';} else if(op==4) {cin>>x>>y;if(x==y) {cout<<1<<'\n';continue;}numf=queryf(1,1,n,x,y-1);if(numf==y-x) cout<<1<<'\n';else cout<<0<<'\n';} else {cin>>x>>y;if(x==y) {cout<<0<<'\n';continue;}numgd=querygd(1,1,n,x,y-1);numz=queryz(1,1,n,x,y-1);numf=queryf(1,1,n,x,y-1);if(numgd==1&&numz+numf==y-x) cout<<1<<'\n';else cout<<0<<'\n';}}
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;
//    cin >> t;while (t--) solve();return 0;
}

1008-比特跳跃

首先，如果不考虑已经有的道路，只进行跳跃的话，跳两次一定比跳一次更优。所以首先可以从1出发，连到每个点，先连一条边，权值为比特跳跃的花费。

其次考虑二进制位，如1100可以由1000和100这样的只有一位01不同的转移过来，因为上一个前提，最多就连续跳一次，所以可以对于每个数，遍历每个二进制位，把一个0的位置变成1，把前后两个数进行连边。复杂度是18*n

最后跑一边迪杰斯特拉即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
const int mod=998244353;
int n,m,k;
vector<pair<int,int>>to[N];
int dis[N];
int vis[N];
void dij(){dis[1] = 0 ;priority_queue<pair<int,int>>q;q.push({0,1});while(!q.empty()){int  u =q.top().second;q.pop();vis[u] = 1;for(int i=0;i<to[u].size();i++){int v =to[u][i].first;int w =to[u][i].second;if(vis[v])continue;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;q.push({-dis[v],v});}}}}void bfs(){queue<int>q;for(int i=0;i<=18;i++){int k=1<<i;if(k<=n){q.push(k);vis[k]=1;}}while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<=17;i++){if(((x>>i)&1)==0){int y=x|(1<<i);if(y>n)continue;to[x].push_back({y,(x|y)*k});to[y].push_back({x,(x|y)*k});dis[y]=min(dis[y],dis[x]+(x|y)*k);if(vis[y]==1)continue;q.push(y);vis[y]=1;}}}
}
void solve(){cin >>n>>m>>k;for(int i=1;i<=n;i++){dis[i] = 1e15;to[i].clear();}for(int i=2;i<=n;i++){to[1].push_back({i,k*(1|i)});}for(int i=1,u,v,w;i<=m;i++){cin>>u>>v>>w;w=min(w,(u|v)*k);to[u].push_back({v,w});to[v].push_back({u,w});}for(int i=1;i<=n;i++)vis[i]=0;bfs();for(int i=1;i<=n;i++)vis[i]=0;dij();for(int i=2;i<=n;i++)cout<<dis[i]<<" ";cout<<'\n';}
signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
}
/*** 1
6 4 3
1 3 2
1 5 20
2 4 1
4 6 10** */

1011-抓拍

处理出边界，进行三分

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
const int mod=998244353;
int lx[4],rx[4],ly[4],ry[4];
int jxx1,jxx2,jxy1,jxy2;
int n;
int cf1d0[4],c0dz1[4];
int tim[10],js=0;
string s;
struct node{int x,y;
};
vector<node>v[4];
double check(double t){double maxx=-1*1e12,minx=1e12,maxy=-1*1e12,miny=1e12;if(!v[0].empty()){maxx=max((double)rx[0],maxx);minx=min((double)lx[0],minx);maxy=max((double)ry[0]+t,maxy);miny=min((double)ly[0]+t,miny);}if(!v[1].empty()){maxx=max((double)rx[1],maxx);minx=min((double)lx[1],minx);maxy=max((double)ry[1]-t,maxy);miny=min((double)ly[1]-t,miny);}if(!v[2].empty()){maxx=max((double)rx[2]+t,maxx);minx=min((double)lx[2]+t,minx);maxy=max((double)ry[2],maxy);miny=min((double)ly[2],miny);}if(!v[3].empty()){maxx=max((double)rx[3]-t,maxx);minx=min((double)lx[3]-t,minx);maxy=max((double)ry[3],maxy);miny=min((double)ly[3],miny);}return (maxx-minx)*2+(maxy-miny)*2;
}
void solve(){node t;for(int i=0;i<4;i++){lx[i]=1e12;rx[i]=-1*1e12;ly[i]=1e12;ry[i]=-1*1e12;}cin>>n;for(int i=1;i<=n;i++){cin>>t.x>>t.y>>s;if(s[0]=='N') v[0].push_back(t);if(s[0]=='S') v[1].push_back(t);if(s[0]=='E') v[2].push_back(t);if(s[0]=='W') v[3].push_back(t);}for(int i=0;i<4;i++){for(int j=0;j<v[i].size();j++){t=v[i][j];lx[i]=min(t.x,lx[i]);rx[i]=max(t.x,rx[i]);ly[i]=min(t.y,ly[i]);ry[i]=max(t.y,ry[i]);}}double l=0,r=2e9;double mid1,mid2;while(fabs(r-l)>=1e-6){mid1=l+(r-l)/3.0;mid2=l+(r-l)*2/3.0;if(check(mid1)<check(mid2)) r=mid2;else l=mid1;}int aa=(int)l;int ans;ans=min(min(check(max(0ll,aa-1)),check(aa)),check(aa+1));cout<<ans<<'\n';
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;
//    cin >> t;while (t--) solve();return 0;
}

1012-死亡之组

考虑小于的个数，以及自身是否小于l即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N = 2e5 + 100;
const int mod=998244353;int a[N];
void solve(){int n,l,d;cin>>n>>l>>d;for(int i=1;i<=n;i++){cin>>a[i];}int k=a[1];sort(a+1,a+n+1);int cnt=0;for(int i=1;i<=n;i++){if(a[i]<l)cnt++;}if(cnt>=3){if(k>=l){if(k-a[1]>d){cout<<"Yes"<<'\n';}else{cout<<"No"<<'\n';}}else{if(a[n]-a[1]>d){cout<<"Yes"<<'\n';}else{cout<<"No"<<'\n';}}}else{cout<<"No"<<'\n';}
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin>>T;while (T--)solve();return 0;
}