A. Nastya and Rice
题意
有n粒米，每粒米的重量在((a-b,a+b))之间，有一个袋子，承重在((c-d,c+d))之间，判断是否有可能装下。
思路
求出米的重量区间(((a-b)n,(a+b)n))，判断((c-d,c+d))区间是否有交集。
代码
#include<iostream>
#include<string.h>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
#include<set>
#include<map>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
int main(){
int T;
cin>>T;
while(T--){
LL n,a,b,c,d;
cin>>n>>a>>b>>c>>d;
LL l1=(a-b)*n,r1=(a+b)*n;
LL l2=c-d,r2=c+d;
if(max(l1,l2)<=min(r1,r2)){
cout<<"Yes"<<endl;
}
else cout<<"No"<<endl;
}
return 0;
}
B. Nastya and Door
题意
求出在长度为k的区间的左端点l，区间内的peek最多，如果有多个区间peak一样多，输出左端点最小的l，如果(a_i)是peak则(a_i>a_{i-1},a_i>a_{i-1})，区间的边界不可以算peak（题目背景弄那么长，和题意连接牵强...
思路
直接求前缀和，枚举每一个区间的左端点l。(注意最坏情况没有peak时，输出最短点时1！
代码
#include<iostream>
#include<string.h>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
#include<set>
#include<map>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
int a[200010],f[200010],sum[200010];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,k;
memset(f,0,sizeof f);
memset(sum,0,sizeof sum);
scanf("%d%d",&n,&k);
a[0]=a[n+1]=1e9+10;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i){
if(a[i]>a[i-1]&&a[i]>a[i+1]){
f[i]=1;
}
else f[i]=0;
}
for(int i=1;i<=n;++i)
sum[i]=sum[i-1]+f[i];
int t=0,l=1;
for(int i=1;i<=n;++i){
if(sum[i+k-1]-sum[i-1]-f[i]-f[i+k-1]>t){
t=sum[i+k-1]-sum[i-1]-f[i]-f[i+k-1];
l=i;
}
}
cout<<t+1<<" "<<l<<endl;
}
return 0;
}
C. Nastya and Strange Generator
题意
一开始有一个空序列，要求变成一个目标序列，n次操作的步骤如下：
r数组，(r_j)表示从j到n，a数组中第一个没有填数的下标；
cnt数组，(cnt_t)表示r数组有t的个数；
第i次操作选择cnt数组中最大元素的下标t(有多个最大值可以选择任意一个)，将i填入(a_t)。
判断n次操作后最终是否可以变成目标序列。
思路
每当r中一个数被选择，它就等于它右边的数，右边的数在cnt中出现的次数就++。考虑初始r={1,2,...,n}，所以每次被选则的数要么右边没数了，要么右边的数比它大1。
代码
#include<iostream>
#include<string.h>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
#include<set>
#include<map>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
int a[100010],n,f[100010];
bool solve(){
int tn=n,s=0;
for(int i=1;i<=n;++i){
if(f[i]==tn) tn-=s+1,s=0;
else if(f[i]+1==f[i+1]) s++;
else return false;
}
return true;
}
int main(){
int T;
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i],f[a[i]]=i;
if(solve()){
puts("Yes");
}
else puts("No");
}
return 0;
}
D. Nastya and Scoreboard
题意
有n个数字晶体管，初始时每个晶体管中的某些部分在亮着，求K次点亮操作，使得每个晶体管都是一个数，且组成的十进制数最大。((1≤n≤2000,1≤k≤2000))
思路
很显然的01背包。但是由于n很大，最终的答案一定是一个高精度数，那么常数就变得很大。(被Tle过了
转化一下思路：先找到数字合法方案，再贪心选数字。
(f[i][j]=1)表示从n到i点亮j次可以使得n到i成为合法的数字，否则(f[i][j]=0).这个过程很容易就不细说了。
当预处理完成后，判断(f[1][k])是否等于1，如果不等于1，说明误解。
然后从1到n依次枚举高位，从最大的数开始选，选前判断当前位选这个数下一位到n是否存在合法方案。
代码
#include<bits/stdc++.h>
using namespace std;
int st[10],a[200010],ones[1<<7],n,m;
void init(){
for(int i=0;i<(1<<7);++i){
for(int j=0;j<7;++j){
if(i&(1<<j)) ones[i]++;
}
}
char s[10][10]={"1110111","0010010","1011101","1011011","0111010",
"1101011","1101111","1010010","1111111","1111011"};
for(int i=0;i<10;++i){ //
for(int j=0;j<7;++j){
if(s[i][j]=='1') st[i]|=(1<<j);
}
}
char str[10];
for(int i=1;i<=n;++i){
cin>>str;
for(int j=0;j<7;++j){
if(str[j]=='1') a[i]|=(1<<j);
}
}
}
string ans;
bool f[2010][2010];
void solve(){
f[n+1][0]=1;
for(int i=n;i>=1;--i){
for(int j=0;j<10;++j){
if((st[j]&a[i])==a[i]){
int t=ones[(st[j]^a[i])];
for(int k=t;k<=m;++k){
if(f[i+1][k-t]){
f[i][k]=1;
}
}
}
}
}
if(f[1][m]==0){
puts("-1");
return ;
}
for(int i=1;i<=n;++i){
for(int j=9;i>=0;--j){
if((st[j]&a[i])==a[i]){
int t=ones[(st[j]^a[i])];
if(f[i+1][m-t]){
ans+=char('0'+j);
m-=t;
break;
}
}
}
}
cout<<ans<<endl;
}
int main(){
cin>>n>>m;
init();
solve();
return 0;
}