题解 | #优美的数#
优美的数
https://ac.nowcoder.com/acm/contest/20038/A
2021牛客OI赛前集训营-普及组（第一场）部分题解
传送门：https://ac.nowcoder.com/acm/contest/20038#question
A题：按题意，直接枚举即可，时间复杂度 O(n)。
#include<cstdio>
#include<iostream>
using namespace std;
const int N=3010;
int T,a[N],ans[N],m,cnt,num;
bool check(int n){
if(n%7==0) return 1;
else{
while(n!=0){
if(n%10==7) return 1;
n/=10;
}
return 0;
}
}
int main(){
scanf("%d",&T);
for(int i=1;i<=T;++i){
scanf("%d",&a[i]);
m=max(m,a[i]);
}
while(cnt<=m){
++num;
if(check(num)) ans[++cnt]=num;
}
for(int i=1;i<=T;++i) printf("%d\n",ans[a[i]]);
return 0;
}
B题：注意到异或的逆运算还是异或，即 a^b=X, 则 b=X^a, 即对于每一个 a[i]，查找 X^a[i] 的个数，使用二分查找即可，时间复杂度 O(nlogn)。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=1e6+10;
int n,x,a[N],cnt;
signed main(){
scanf("%lld%lld",&n,&x);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;++i){
int t=x^a[i],j1,j;
if(a[i]==t) ++cnt;
j1=lower_bound(a+i+1,a+n+1,t)-a,j=j1;
if(j1>=1&&j1<=n) while(a[j]==t&&j!=i) ++cnt,++j;
j1=lower_bound(a+1,a+i,t)-a,j=j1;
if(j1>=1&&j1<=n) while(a[j]==t&j!=i) ++cnt,++j;
}
printf("%lld",cnt);
return 0;
}
C题：
- 60分做法：ST表+暴力枚举，时间复杂度 O(n2)，不能通过。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e7+3,LOG=29,MAX=0x3f3f3f3f;
int n,m,k,ans=MAX,a[N],b[N],f1[N][LOG],Log2[N],q[N],f2[N][LOG];
void init_log2(){
Log2[1]=0,Log2[2]=1;
for(int i=3;i<=n;++i) Log2[i]=Log2[i/2]+1;
}
void dp_len1(){
for(int i=1;i<=n;++i) f1[i][0]=a[i];
for(int j=1;j<=Log2[n];++j){
int len=1<<j;
for(int i=1;i<=n-len+1;++i) f1[i][j]=min(f1[i][j-1],f1[i+(1<<(j-1))][j-1]);
}
}
void dp_len2(){
for(int i=1;i<=n;++i) f2[i][0]=b[i];
for(int j=1;j<=Log2[n];++j){
int len=1<<j;
for(int i=1;i<=n-len+1;++i) f2[i][j]=max(f2[i][j-1],f2[i+(1<<(j-1))][j-1]);
}
}
int st_min1(int l,int r){
int len=r-l+1;
return min(f1[l][Log2[len]],f1[r-(1<<Log2[len])+1][Log2[len]]);
}
int st_max2(int l,int r){
int len=r-l+1;
return max(f2[l][Log2[len]],f2[r-(1<<Log2[len])+1][Log2[len]]);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) scanf("%d",&b[i]);
init_log2();
dp_len1();
dp_len2();
for(int l=1;l<=n;++l){
for(int r=l;r<=n;++r){
int t1=st_max2(l,r),t2=st_min1(l,r),len=r-l+1;
if(t1-t2>=k) ans=min(ans,len);
// printf("%d %d:%d %d\n",l,r,t1,t2);
}
}
if(ans==MAX) printf("So Sad!");
else printf("%d",ans);
return 0;
}
2.80分做法：在60分的基础上加上"二分答案"优化，时间复杂度 O(nlogn)。
3.正解：单调队列+双指针。每次移动一下移动右端点，然后移动左端点直到不符合题意，取个最小值；用单调队列维护区间最大 / 最小值。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e7+3,MAX=0x3f3f3f3f;
int n,m,k,ans=MAX,a[N],b[N],q1[N],q2[N],f1=1,r1,f2=1,r2;
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) scanf("%d",&b[i]);
q1[0]=1,q2[0]=1;
for(int i=1,j=1;i<=j&&j<=n;){
while(f1<=r1&&a[j]<=a[q1[r1]]) --r1;
q1[++r1]=j;
while(f2<=r2&&b[j]>=b[q2[r2]]) --r2;
q2[++r2]=j;
while(i<=j&&b[q2[f2]]-a[q1[f1]]>=k){
ans=min(ans,j-i+1);
++i;
while(f1<=r1&&q1[f1]<i) ++f1;
while(f2<=r2&&q2[f2]<i) ++f2;
}
++j;
}
if(ans==MAX) printf("So Sad!");
else printf("%d",ans);
return 0;
}
D题：树形DP，为二次扫描与换根法的经典题，即为洛谷P1364“医院设置” （ https://www.luogu.com.cn/problem/P1364 ） 加强版。根据求和的性质以及乘法分配律，缩一个距离，做功就减少 Sum(i) 个；同样地，加一个距离，做功就增加 Sum(i) 个 [ Sum 为子树权值之和（包括自身）] ，所以动规方程即为 F(i) = F( Father(i) ) - Sum(i) + Sum( root ) - Sum(i) ，F 为做功，Father 为父节点，Root为根。存图要存双向，任选一个为根，一遍 DFS 扫描求 Sum 和 F( root )，再一遍 DFS 扫描求 F ，统计最大值即可。 注意：N是2e5，极大值MAX要开到 0x7f7f7f7f7f7f7f7f 。（亲身经历：100 pts -> 10 pts）
#include<cstdio>
#include<iostream>
using namespace std;
#define int long long
const int N=3e5+10,MAX=0x7f7f7f7f7f7f7f7f;
int n,w[N],cnt,sum[N],f[N],head[N<<1],ans=MAX,dep[N];
struct Node {
int to,next;
} e[N<<1];
void Add(int u, int v) {
++cnt;
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int u,int fa) {
sum[u]=w[u];
for(int i=head[u]; i; i=e[i].next) {
int s=e[i].to;
if(s==fa) continue;
dep[s]=dep[u]+1;
dfs(s,u);
sum[u]+=sum[s];
}
f[1] += w[u] * dep[u];
}
void dp(int u,int fa) {
ans=min(ans,f[u]);
for(int i=head[u]; i; i=e[i].next) {
int s=e[i].to;
if(s==fa) continue;
f[s]=f[u]-sum[s]+sum[1]-sum[s];
dp(s,u);
}
}
signed main() {
cin>>n;
for(int i=1; i<=n; ++i) cin>>w[i];
for(int i=1; i<=n-1; ++i) {
int u, v;
cin>>u>>v;
Add(u,v);
Add(v,u);
}
dfs(1,0);
dp(1,0);
cout<<ans<<endl;
return 0;
}
