本文主要是介绍2018.12.15【NOIP提高组】模拟B组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
解题报告
- JZOJ 100046 收集卡片
- 题目
- 分析
- 代码
- JZOJ 100047 基因变异
- 题目
- 分析
- 代码
- JZOJ 100044 abcd
- 题目
- 分析
- 代码
JZOJ 100046 收集卡片
题目
询问一段字母种类最多的最短区间
分析
扫描每一个结尾,找到最适合的开头,统计最短长度
代码
#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
char s[500001];
int n,cnt[151],sum=1,ans=2147473647,ans1=1,head=1;
signed main(){scanf("%d",&n);rr char c=getchar();while (!isalpha(c)) c=getchar(); cnt[s[1]=c]=1;for (rr int i=2;i<=n;++i){if (++cnt[s[i]=getchar()]==1) ++sum;while (head<i&&cnt[s[head]]>1){if (!(--cnt[s[head]])) --sum;++head;}if (ans1<sum) ans1=sum,ans=i-head+1;else if (ans1==sum) ans=ans>(i-head+1)?(i-head+1):ans;}printf("%d",ans);return 0;
}
JZOJ 100047 基因变异
题目
给定一个数字 x x x和 n n n个指定的数,可以在某一个二进制位取反(也就是异或 2 t 2^t 2t),可以异或指定的数,问最少需要多少次操作才能变成 y y y,( T ≤ 100000 , n ≤ 20 T\leq 100000,n\leq 20 T≤100000,n≤20)
分析
一看询问的数量就知道必须快速查询,然后想了半天都没想好,后来发现可以从0开始广搜找对于每个数最少的次数,预处理后 O ( 1 ) O(1) O(1)查询。查询的时候可以这样想,若异或的数是 a n s ans ans,那么 x x x xor a n s ans ans xor y y y= x x x xor y y y xor a n s ans ans,所以说 x x x xor y y y即为需要查询的数
时间复杂度 O ( 2 20 + T ) O(2^{20}+T) O(220+T)
代码
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <queue>
#define rr register
using namespace std;
int a[21],cnt[1050001],n,t;
inline signed iut(){rr int ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;
}
inline void print(int ans){if (ans>9) print(ans/10);putchar(ans%10+48);
}
signed main(){n=iut(); t=iut(); rr queue<int>q; q.push(0);for (rr int i=1;i<=n;++i) a[i]=iut();sort(a+1,a+1+n); n=unique(a+1,a+1+n)-a-1;//剪枝while (q.size()){int x=q.front(); q.pop();for (rr int i=1;i<=n;++i)if (!cnt[x^a[i]]&&x!=a[i])cnt[x^a[i]]=cnt[x]+1,q.push(x^a[i]);//指定的数for (rr int i=0;i<20;++i)if (!cnt[x^(1<<i)]&&x!=(1<<i))cnt[x^(1<<i)]=cnt[x]+1,q.push(x^(1<<i));//取反某一二进制位}while (t--){rr int x=iut(),y=iut();print(cnt[x^y]); putchar(10);}return 0;
}
JZOJ 100044 abcd
题目
有4个长度为 n n n的数组 a , b , c , d a,b,c,d a,b,c,d,现在需要选择 n n n个数构成数组 e e e,使 a i ≤ e i ≤ b i a_i\leq e_i\leq b_i ai≤ei≤bi,且 ∑ i = 1 n e [ i ] × c [ i ] = 0 \sum_{i=1}^ne[i]\times c[i]=0 i=1∑ne[i]×c[i]=0,最后使 ∑ i = 1 n e [ i ] × d [ i ] \sum_{i=1}^ne[i]\times d[i] i=1∑ne[i]×d[i]最大
分析
这道题目可以转换为选择 a i a_i ai到 b i b_i bi个物品,单个费用为 c i c_i ci,价值为 d i d_i di,并使价值最大,说到这里其实就是一个多重背包,不过可以直接取 a i a_i ai个,然后把 b i − a i b_i-a_i bi−ai进行多重背包,但是单纯的多重背包依然会超时,单调队列又太麻烦,所以说可以用二进制优化,把它转换成01背包
代码
#include <cstdio>
#include <cctype>
#include <cstring>
#define rr register
#define max(a,b) ((a)>(b))?(a):(b)
using namespace std;
int w[4001],v[4001],f[50001],n,m,ans;
inline signed iut(){rr int ans=0,f=1; rr char c=getchar();while (!isdigit(c)&&c!='-') c=getchar();if (c=='-') f=-f,c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans*f;
}
signed main(){memset(f,0xcf,sizeof(f)); f[0]=0;for (rr int t=iut();t;--t){rr int a=iut(),b=iut(),c=iut(),d=iut();ans+=a*d,m-=a*c,b-=a;//容量在多重背包的时候用费用补回去for (rr int i=1;i<=b;i<<=1)w[++n]=i*c,v[n]=i*d,b-=i;//二进制拆分if (b) w[++n]=b*c,v[n]=b*d; }for (rr int i=1;i<=n;++i)//01背包for (rr int j=m;j>=w[i];--j)f[j]=max(f[j],f[j-w[i]]+v[i]);printf("%d",f[m]+ans);return 0;
}
这篇关于2018.12.15【NOIP提高组】模拟B组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!