CF1742G
考虑拆位,先把高位的填成 1 ,后面再考虑填上低位的。
把每一位能填的数存进数组里。
从高位往低位填,每一位填时,尽量把低位也顺便填上。
code
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,logm=32;
int n,a[N],t,res[N],w[logm],vis[N];
struct node {
int id,v;
};
bool cmp(node x,node y) {
return x.v>y.v;
}
vector<node> v[logm];
int main() {
scanf("%d",&t);
for(; t; t--) {
for(int i=logm-1; i>=0; i--) v[i].clear();
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
for(int j=0; j<logm; j++) {
if(a[i]&(1<<j)) {
node f;
f.id=i; f.v=a[i];
v[j].push_back(f);
}
}
}
memset(w,0,sizeof(w));
int tot=0;
for(int i=logm-1; i>=0; i--) {
if(w[i]) continue;
int q=0;
for(int k=0; k<logm; k++) if(!w[k]) q|=1<<k;
for(int j=0; j<v[i].size(); j++)
v[i][j].v&=q;
sort(v[i].begin(),v[i].end(),cmp);
if(v[i].size()) {
res[++tot]=v[i][0].id;
for(int j=0; j<logm; j++) {
if(a[res[tot]]&(1<<j)) w[j]=1;
}
}
}
memset(vis,0,sizeof(vis));
for(int i=1; i<=tot; i++) {
printf("%d ",a[res[i]]);
vis[res[i]]=1;
}
for(int i=1; i<=n; i++) {
if(!vis[i]) printf("%d ",a[i]);
}
puts("");
}
return 0;
}
CF1741E
考虑 DP,设 \(f_i\) 是以 \(i\) 结尾的序列是否合法。
若 \(f_{i-1}\) 合法,则 \(f_{i+a_i}\) 合法。
若 \(f_{i-a_i-1}\) 合法,则 \(f_i\) 合法。
code
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int g,n,a[N];
bool f[N];
int main() {
scanf("%d",&g);
for(; g; g--) {
scanf("%d",&n);
f[0]=1;
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
for(int i=1; i<=n; i++) f[i]=0;
for(int i=1; i<=n; i++) {
int p=i-a[i],q=i+a[i];
if(p>=1) f[i]|=f[p-1];
if(q<=n) f[q]|=f[i-1];
}
puts(f[n]?"yes":"no");
}
return 0;
}