NOIP提高组模拟赛6
A. 简单的区间
这题看着真熟啊，好像把之前的english，入阵曲杂糅了一下。
首先，像入阵曲一样计算出前缀和\(s[]\)式子可以转化为求
\(s[r]-s[l-1]\equiv MAX(mod\;k)\)
像english一样
用单调栈处理出以X为最大值的区间，分区间求解
每次枚举一侧区间，已知MAX，只要知道另一侧有多少与之余数相同的即可
然鹅这题数据范围不允许用前缀和优化某区间余数为特定值的个数，这样english中的启发式合并就没有意义，因为两边都要扫，如果数据相对单调，非常容易卡成\(O(N^2)\)喜提TLE。
所以揉了两道题做不出怎么办？再揉一道
像之前的数颜色那样用vector存余数为i的前缀和的下标，每次查询直接二分，这样复杂度就可以了，记得存一个0进去
#include
#include
#include
#include
using namespace std;
const int MAXN=1000005;
int a[MAXN],l[MAXN],r[MAXN],stc[MAXN],top,n,k;
long long sum[MAXN],ans=0;
vectorv[MAXN];
int ask(int ll,int rr,int y){
int p1=lower_bound(v[y].begin(),v[y].end(),ll)-v[y].begin();
int p2=upper_bound(v[y].begin(),v[y].end(),rr)-v[y].begin();
return p2-p1;
}
void work(int ll,int rr,int xx){
if(rr-xx B. 简单的玄学
首先能够得到，至少有两个变量取值相同的概率，就是1-任意两个变量取值都不同的概率
即\(1-2^n(2^n-1)(2^n-2).....(2^n-m+1)/(2^{nm})\)
如何计算这个式子，并且保留分数形式？
----约分
分母只有2这个因子，上下约分一定只能约2的几次方
如何约分？
有：\(2^n-x\)与\(x\)的2的因子个数一样
性感感性理解下
\(x=2^p*q\)(q不含2这个因子)
\(2^n-x=2^p(2^{n-p}+q)\)
因为q不含2这个因子，所以q是奇数，\((2^{n-p}+q)\)也是奇数，不含2这个因子，所以\(2^n-x\)与\(x\)的2的因子个数一样，即P
所以判断能约几个2，判断分母和\(m!\)有几个2这个因子即可
用\(m!\)除以2，得到其中有几个含2这个因子的，除以4得到有几个含两个2这个因子的....不停除以2的此方，直到大于\(m!\)累计一下个数，得到约分的数，上下乘以逆元即可
#include
#include
#include
using namespace std;
const long long mod=1e6+3,nv=500002;
long long m,n;
long long qp(long long x,long long y){
long long sum=x,ans=1;
while(y){
if(y&1)ans=(ans*sum)%mod;
sum=(sum*sum)%mod;
y>>=1;
}
return ans;
}
int main(){
scanf("%lld%lld",&n,&m);
if(log2(m)>n){printf("1 1\n");return 0;}
long long p=qp(2,n),q=qp(p,m);
long long a=1;
for(int i=0;i C. 简单的填数
想出过卡上下界的做法，但是不知道怎么处理\(a[i]\)有数的情况，还是太菜
定义二元组，（其实就是两个数组）up[i] \((x,c)\) 和down[i] \((x,c)\)，表示上下界，即到第i个数，最小是down->x，出现次数down->c 最大up-x,出现次数up->c
显然一般情况up每两个加一，down每5个加一，如果\(a[i]\)有数，先用上下界判是否合法，然后更新上下界，由于要让up最大，down最小，显然令\(up->x=a[i] \;up->c=2\;down->x=a[i]\;down->c=1\)
这样就能判断是否存在合法方案，并且求出最大值，（注意特判一下
\(up[n]->c==1\)需要减1）
然后考虑如何填数，倒叙填数，定义now和sum，sum表示连续填了几个相同的数，每次填\(min(up[i]->z,now)\);当\(a[i]\)有数，\(now=min(now,a[i])\);sum每到5 now要减一
不是很理解，先口胡一下，不对请大佬指正
这个now大概是个上界，而我们此时需要尽可能小（减的快），就需要用up此时是下界，但是由于正着扫时候\(a[i]\)有数是直接暴力修改，导致中间会断，部分的下界是错误的，需要用上界修正，而now的作用就在这时候体现了，就是说up和now交替合法
#include
#include
using namespace std;
const int maxn=200005;
int min(int x,int y){return x=2) { up[i].z=up[i-1].z+1; up[i].c=1; }
else { up[i].z=up[i-1].z; up[i].c=up[i-1].c+1;}
if(down[i-1].c<5){ down[i].c=down[i-1].c+1; down[i].z=down[i-1].z;}
else{ down[i].c=1; down[i].z=down[i-1].z+1;}
if(a[i]){
if(a[i]up[i].z){flag=1;break;}
if(up[i].z>a[i]){up[i].z=a[i];up[i].c=2;}
if(down[i].z=1;--i){
if(a[i]&&now>a[i])now=a[i],num=0;
if(num==5)--now,num=0;
++num;
as[i]=min(now,up[i].z);
}
printf("%d\n",up[n].z);
for(int i=1;i<=n;++i)printf("%d ",as[i]);
return 0;
}