牛客小白月赛94VP

1.签到：https://ac.nowcoder.com/acm/contest/82957/A

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;
int main()
{for(int i=1;i<=9;i++){int x;cin>>x;mp[i]=x;}string s;cin>>s;s=' '+s;for(int i=1;i<s.size();i++) cout<<mp[s[i]-'0'];
}

2.思维题：https://ac.nowcoder.com/acm/contest/82957/B

可以发现，假如数组是一个非严格递增的答案就是0，否则是n。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[200010];
int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=2;i<=n;i++){if(a[i]<a[i-1]){cout<<n;return 0;}}cout<<0;
}

3.前缀和：https://ac.nowcoder.com/acm/contest/82957/C

显然最终的max与min一定是相邻的（否则中间的数可以归给较大的一边），于是我们枚举分界点，用前缀和维护一下即可。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[200010];
long long sum;
long long kk[200010];
int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];if(n==1){cout<<0;return 0;}for(int i=1;i<=n;i++) sum+=a[i];for(int i=1;i<=n;i++) kk[i]=kk[i-1]+a[i];long long ans=0;for(int i=1;i<=n-1;i++){    ans=max(ans,abs(a[i]-(sum-kk[i])));ans=max(ans,abs(kk[i]-a[i+1]));}cout<<ans;
}

4.暴力+剪枝：https://ac.nowcoder.com/acm/contest/82957/D

首先对于一个gcd a，答案肯定是它的倍数,我们取当前没有被去过的最小倍数即可（因为后面的gcd一定是前面的因子，因此只要是它的倍数，他们的地位就一样，为了方便选第一个。

这样我们就可以直接暴力了，考虑一下优化，当a与前面一个不相等时，答案就是a，因为a肯定比前面一个小，而已选的一定是前面的倍数，所以a自己满足，当相等是，我们从上次答案开始枚举即可。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[200100];
int b[200010],c[200010];
int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int f=0;for(int i=2;i<=n;i++){if(a[i-1]%a[i]==0) continue;f=1;break;}if(f){cout<<-1;return 0;}for(int i=1;i<=n;i++){if(a[i-1]!=a[i]){c[i]=a[i];}else{for(int j=a[i]+c[i-1];j<=n;j+=a[i]){if(b[j]==0){c[i]=j;break;}}}if(c[i]==0){cout<<-1;return 0;}b[c[i]]=1;}for(int i=1;i<=n;i++) cout<<c[i]<<" ";
}

5.E/F枚举：https://ac.nowcoder.com/acm/contest/82957/E

https://ac.nowcoder.com/acm/contest/82957/F

1.直接枚举：

看到数据范围枚举ans，我们从大到小，只要答案符合，就输出。

那么答案要符合，贪心一下就是把所有&ans==ans的全部&，根据&的单调递减，假如它<=k，符合，反之继续。

2.构造二进制枚举：

对于hard版本，我们不可以直接枚举ans,但是我们可以从高位贪心考虑是否要填1，假如按照1方法chack的值<=k，就一定为1，然后继续即可。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,v[200010],w[200010];
int main()
{cin>>n>>k;for(int i=1;i<=n;i++) cin>>v[i]>>w[i];ll ans=0;for(int bt=30;bt>=0;bt--){ll t=ans|(1ll<<bt);ll vs=(1ll<<40)-1ll;for(int i=1;i<=n;i++){if((w[i]&t)==t) vs&=v[i];}if(vs<=k) ans=t;}cout<<ans;
}