10.2模拟赛
目录\(\to \rm link\leftarrow\)
二分图排列
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,inf=1e9;
int n;
int a[N],f[N][2];
vector <int> p;
inline void solve(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=0;i<=n;++i) f[i][0]=f[i][1]=-inf;
f[n][0]=f[n][1]=inf;
for(int i=n-1;i;--i){
int t0[4]={-a[i+1],a[i+1],f[i+1][0],f[i+1][1]};
int t1[4]={f[i+1][0],f[i+1][1],-a[i+1],a[i+1]};
for(int j=0;j<2;++j){
int t=(!j)?-a[i]:a[i];
for(int k=0;k<4;++k)
if(t<t0[k])
f[i][j]=max(f[i][j],t1[k]);
}
if(f[i][0]==-inf&&f[i][1]==-inf){
puts("NO");
return;
}
}
puts("YES");
int t1=f[0][0],t2=f[0][0];
for(int i=1;i<=n;++i){
if(-a[i]>t1)
t1=a[i]=-a[i];
else if(-a[i]>t2&&-a[i]<f[i][0])
t2=a[i]=-a[i];
else t1=a[i];
if(t1<t2) swap(t1,t2);
printf("%d ",a[i]);
}
puts("");
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
/*
4
3
1 2 3
6
1 3 2 6 5 4
4
4 1 3 2
8
3 2 1 6 7 8 5 4
*/
搬题能不能搬简单点啊！
最短路问题 V3
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define emp emplace_back
#define int long long
const ll inf=1e15;
const int N=2e5+100;
struct E{
int x,w;
E(int a,int b){x=a,w=b;}
};
int n,m;
ll d[85][N];
int f[N][20],dep[N],ds[N];
vector <E> G[N];
vector <int> p;
bool vis[N];
inline void spfa(int s){
queue <int> q;
for(int i=1;i<=n;++i) d[s][i]=inf;
d[s][p[s]]=0;
q.push(p[s]);
memset(vis,0,sizeof(vis));
vis[p[s]]=1;
while(!q.empty()){
int x=q.front();
q.pop();
vis[x]=0;
for(auto y:G[x]){
if(d[s][y.x]>d[s][x]+y.w){
d[s][y.x]=d[s][x]+y.w;
if(!vis[y.x]) vis[y.x]=1,q.push(y.x);
}
}
}
}
inline void dfs(int x,int fa){
f[x][0]=fa;
for(int i=1;i<=19;++i)
f[x][i]=f[f[x][i-1]][i-1];
for(auto y:G[x]){
if(y.x==fa) continue;
if(f[y.x][0]==0){
dep[y.x]=dep[x]+1;
ds[y.x]=ds[x]+y.w;
dfs(y.x,x);
}
else if(dep[x]<dep[y.x]){
p.emp(x);
spfa(p.size()-1);
p.emp(y.x);
spfa(p.size()-1);
}
}
}
inline int lca(int x,int y){
if(dep[x]<dep[y])
swap(x,y);
for(int i=19;i>=0;--i)
if(dep[f[x][i]]>=dep[y])
x=f[x][i];
if(x==y) return x;
for(int i=19;i>=0;--i)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("2.out","w",stdout);
#endif
int q;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;++i){
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
//cout<<x<<" "<<y<<" "<<z<<endl;
G[x].emp(y,z);G[y].emp(x,z);
}
dfs(1,1);
scanf("%lld",&q);
for(int i=1;i<=q;++i){
int x,y;
scanf("%lld%lld",&x,&y);
bool fl=0;
int z=ds[x]+ds[y]-2*ds[lca(x,y)];
for(int i=0;i<(int)p.size();++i)
z=min(z,d[i][x]+d[i][y]);
printf("%lld\n",z);
}
return 0;
}
捡石子游戏
我写的记搜，复杂度 \(\rm O(n)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;
#define emp emplace_back
int n;
int f[N],a[N];
vector <int> p,G[N];
inline int dfs(int x){
if(f[x]!=-1) return f[x];
f[x]=0;
for(int y:G[x])
if(a[y]<a[x])
f[x]|=(dfs(y)^1);
return f[x];
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("2.out","w",stdout);
#endif
scanf("%d",&n);
memset(f,-1,sizeof(f));
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(int i=1,x,y;i<n;++i){
scanf("%d%d",&x,&y);
G[x].emp(y),G[y].emp(x);
}
for(int i=1;i<=n;++i)
if(dfs(i)) p.emp(i);
if(!p.size()) puts("-1");
else for(int x:p) printf("%d ",x);
return 0;
}
凹函数
