涵盖知识点：思维、暴力。
比赛链接：传送门
A - Nastya and Rice
题意： 单个物品的重量区间为(aplusmn b)，问是否存在一种解使得(n)个物品重量区间出现在(cplusmn d)之中。
题解： 极限情况判断大小。
Accept Code：
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;cin>>t;
while(t--){
int n,a,b,c,d;
cin>>n>>a>>b>>c>>d;
if((a+b)*n<c-d||(a-b)*n>c+d)puts("No");
else puts("Yes");
}
return 0;
}
B - Nastya and Door
题意： 要将一个长度为(k)的线段覆盖在([1,n])的某个区间内，要求区间内的极大值点（峰点）尽可能多。
题解： 统计所有极大值点之后扫描一遍。
Accept Code：
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int a[maxn];
bool check[maxn];
int main(){
int t;cin>>t;
while(t--){
int n,k;
cin>>n>>k;
check[1]=check[n]=false;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=2;i<n;i++)check[i]=(a[i]>a[i-1])&&(a[i]>a[i+1]);
int sum=0;
for(int i=1;i<k;i++)sum+=check[i];
int ans=-1,l=0;
for(int i=k;i<=n;i++){
if(check[i-k+1])sum--;
if(ans<sum){
ans=sum,l=i-k+1;
}
sum+=check[i];
}
cout<<ans+1<<" "<<l<<"
";
}
return 0;
}
C - Nastya and Strange Generator
题意： 有一个生成器，会按照以下条件从(1)到(n)从小到大进行赋值构造序列：
- 规定(r_j)为最小的大于等于(j)的且未被赋值的下标。
- 规定(cnt_t)为(jin[1,n])中(t=r_j)的个数。
- 选取任意一个(cnt)值进行赋值。
现在给出一个序列，问是否可以通过这个生成器生成。
题解： 注意到初始状态下所有的(r)都是自己，所以所有的(cnt)都为(1)。但是每确定一个数字后，当前确定的下标的(r)就会增加。所以在一个数字确定后，接下来的数字一定是连续到串结束或者已被赋值的点。根据第一个数字的下标不断进行扫描即可。
Accept Code：
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int p[maxn],idx[maxn];
bool vis[maxn];
int main(){
int t;cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>p[i],idx[p[i]]=i,vis[i]=false;
for(int i=1;i<=n;i++){
if(!vis[i]){
for(int j=idx[i];j<=n;j++){
if(vis[p[j]])break;
if(p[j]-i==j-idx[i])vis[p[j]]=true;
else {puts("No");goto st;}
}
}
}
puts("Yes");
st:;
}
return 0;
}
D - Nastya and Scoreboard
题意： 给定现有的火柴棒排列，问加(k)根火柴棒以后能拼出的最大数字。
题解： 根据每一位的数字依次从大到小借用二进制和位运算dfs暴力搜一遍就能过了。。。好像没什么技术含量的样子（迷惑行为）。另有dp做法？回头研究一下。
Accept Code：
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e3+10,tab[]={119,18,93,91,58,107,111,82,127,123};
int n,k,a[maxn],ans[maxn];
bool vis[maxn][maxn];
string s;
void dfs(int i,int x) {
if(x>k||vis[i][x])return;
vis[i][x]=1;
if(i==n){
if(x==k) {
for(int j=0;j<n;j++)printf("%d",ans[j]);
exit(0);
}
return;
}
for(int j=9;j>=0;j--){
ans[i]=j;
if((tab[j]&a[i])==a[i])dfs(i+1,x+__builtin_popcount(tab[j]^a[i]));
}
}
int main(){
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>s;
for(char j:s)a[i]=(a[i]<<1)+(j-'0');
}
dfs(0,0);
puts("-1");
return 0;
}