noi.acNOIP2018全国模拟赛第六场

Author Avatar
ZC 10月 21, 2018
  • 在其它设备中阅读本文章

赛后补题,AB题就只写思路了.QwQ

A. queen

在一个n * n的棋盘上,放有m个皇后,其中每一个皇后都可以向上、下、左、右、左上、左下、右上、右下这8个方向移动(就是可以沿对角线和水平竖直方向移动)。其中每一个皇后可以攻击这八个方向上离它最近的皇后。

我们现在考虑每一个皇后会被从几个方向攻击到,设为w。很显然w属于[0,8]。最后要求出来t[0],t[1]……t[8]九个数,表示有多少皇后被攻击到0次,1次……8次。 数据保证m个皇后中任意两个不在同一个位置。

【输入格式】

第一行两个正整数n,m(n,m<=10^5),然后接下来m行,每一行x[i],y[i]分别表示第i个皇后的横坐标和纵坐标。(1<=x[i],y[i]<=n)

【输出格式】

一行9个整数,分别为t[0],t[1]……t[8],两个数中间用空格隔开。

【样例输入1】

8 4
4 3
4 8
6 5
1 6

【样例输出1】

0 3 0 1 0 0 0 0 0

【样例解释1】

皇后1能被皇后2攻击到(同一行),能被皇后3攻击到(同一对角线),能被皇后4攻击到(同一对角线)。
皇后2能被皇后1攻击到(同一行)。
皇后3能被皇后1攻击到(同对角线)。
皇后4能被皇后1攻击到(同对角线)。

【样例输入2】

10 3
1 1
1 2
1 3

【样例输出2】

0 2 1 0 0 0 0 0 0

【数据范围】

对于 30%的数据,n,m<=1000。

对于 60%的数据,n<=100000,m<=1000。

对于 100%的数据,n,m<=100000,1<=x[i],y[i]<=n。

(保证数据有梯度)

solution:

map/set

stl大法好!!!

考虑左右方向的攻击,对每一行开一个set,按列编号插入,看一下是否存在前驱/后继即可。其余方向同理。

B. ladder

【题目描述】

最开始有4个梯子,高度都为n,也就是每个梯子都有n层脚蹬的横木。小明想要对梯子进行改造(撤掉一些脚蹬用的横木),要满足以下两个条件。 1:撤掉一些横木之后,要保证每一层4个梯子中有且仅有1个梯子在这一层是有横木的。 2:梯子上面连向房顶,小明希望存在至少一个梯子能通过它爬到房顶(梯子之间距离较远,不能爬的过程中转换梯子),其中小明每次能至多爬h的高度,也就是从地面上(地面高度为0)可以达到高度为1、2……h的横木上,以及只可以从n-h+1、n-h+2……n高度的横木上爬到房顶(房顶高度为n+1)上去。

也就是说在撤掉一些横木之后,要求存在一个梯子,它的剩下的第一个横木是不超过h的高度,剩下的最后一个横木是大于等于n-h+1的高度,中间的任意两个相邻剩下的横木之间相差高度不超过h。

小明现在想知道满足条件的撤横木的方案数,答案对10^9+9取模。 其中两个方案不同当且仅当:存在某一层在两个方案当中,他们各自保留的那一根横木在不同的梯子上。

【输入格式】

第一行两个整数 n,h。

【输出格式】

一行一个整数,表示合法的方案数对10^9+9取模的结果。

【样例输入1】

5 1

【样例输出1】

4

【样例解释1】

因为这个间隔的上限是1,并且每一层只能留一个横木所以一组合法的方案肯定是只有一个梯子保留了所有的横木,其他的梯子没有保留任何一根横木,其中梯子数是4,所以答案也就是4。

【样例输入2】

4 3

【样例输出2】

256

【样例解释2】

我们会发现对于任意一种摆放方案,都是合法的,所有的摆放方案正是4^3。

【数据范围】

对于 40%的数据,n<=10(数据具有阶梯性)。

对于 70%的数据,n<=300,h<=min(n,15)。

对于 100%的数据,n<=1000,h<=min(n,30)。

solution:

f[i][0/1][dis2][dis3][dis4]表示前i个位置,第1个梯子是否是通的,disj与之前的状态相同。

C. color

【题目描述】

给定一串n个珠子,其中每一个珠子的颜色为a[i],总共有k类颜色珠子标号从1到k。

初始给定一个参数T。询问再给定m个区间l[i]到r[i],每次询问这个区间有多少颜色的珠子出现了恰好T次。

【输入格式】

第一行四个整数n,m,k,T(1<=n,m,k,T<=5*10^5)。

第二行n个整数,第i个整数为a[i],表示对应珠子的颜色(1<=a[i]<=k)。

接下来m行,每行两个整数l[i]和r[i],表示询问的区间(1<=l[i]<=r[i]<=n)。

【输出格式】

输出m行,每行一个整数,第i行表示第i次询问的答案。

【样例输入】

10 5 5 1
1 5 3 4 2 4 1 2 3 5 
1 10
3 6 
2 8
5 7
6 10

【样例输出】

0
2
3
3
5

【数据范围】

对于30%的数据 n,m,k<=2000,T<=n.

对于另外40%的数据 T=1,1<=n,m,k<=5*10^5.

对于所有数据,1<=n,m,k,T<=5*10^5,1<=a[i]<=k,1<=l[i]<=r[i]<=n.

注意:本题输入量较大,请使用较为快速的读入方式。

solution:

莫队.

因为数据较大,所以要用快读.

我直接用fread了.

fread有点长QwQ

#include<bits/stdc++.h>
#pragma GCC optimize(3)
namespace ZDY{
    #define res register
    #define ri res int
    #define ll long long
    #define db double
    #define sht short
    #define il inline
    #define MB template <class T>
    #define Fur(i,x,y) for(ri i=x;i<=y;i++)
    #define fur(i,x,y) for(i=x;i<=y;i++)
    #define Fdr(i,x,y) for(ri i=x;i>=y;i--)
    #define in2(x,y) in(x),in(y)
    #define in3(x,y,z) in2(x,y),in(z)
    #define in4(a,b,c,d) in2(a,b);in2(c,d)
    #define outn(x) out(x),pc('\n')
    #define clr(x,y) memset(x,y,sizeof(x))
    #define cpy(x,y) memcpy(x,y,sizeof(x))
    #define fl(i,x) for(ri i=head[x],to;to=e[i].to,i;i=e[i].nxt)
    #define inf 2147483630
    #define fin(s) freopen(s".in","r",stdin)
    #define fout(s) freopen(s".out","w",stdin)
    #define l2(n) (ceil(log2(n)))
    #define fast ios::sync_with_stdio(false)
    MB il T ABS(T x){return x>0?x:-x;}
    MB il T MAX(T x,T y){return x>y?x:y;}
    MB il T MIN(T x,T y){return x<y?x:y;}
    MB il T GCD(T x,T y){return y?GCD(y,x%y):x;}
    MB il void SWAP(T x,T y){T t=x;y=t;x=y;}
}using namespace ZDY;using namespace std;

class IO{
   #define fok (ch!=EOF)
   #define sep (ch==' '||ch=='\n'||ch=='\t')
   #define dsep !isdigit(ch)
   #define neq(a,b) ((a)-(b)>1e-6)
   char rbuf[1<<20],wbuf[1<<20],b,*p1,*p2;
   int rs,ws,S;
   public:
       IO():p1(rbuf),p2(wbuf),S(1000000),rs(1000000),ws(-1),b(1){}
       ~IO(){fwrite(wbuf,1,ws+1,stdout);}
       il char gc(){return rs==S&&(p1=rbuf,rs=-1,(S=fread(rbuf,1,S+1,stdin)-1)==-1)?(b=0,EOF):(++rs,*p1++);}
       il void pc(int x){ws==1000000&&(p2=wbuf,ws=-1,fwrite(wbuf,1,1000001,stdout)),++ws,*p2++=x;}
       il void puts(const char str[]){fwrite(wbuf,1,ws+1,stdout)?(ws=-1):0,fwrite(str,1,strlen(str),stdout);}
       il void gl(string& s){for(res char ch;(ch=gc())!='\n'&&fok;)s+=ch;}
       il IO& operator>>(int& x){x=0;res char f=0,ch=gc();while(dsep&&fok)f|=(ch=='-'),ch=gc();while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=gc();return x=f?-x:x,*this;}
       il IO& operator>>(ll& x){x=0;res char f=0,ch=gc();while(dsep&&fok)f|=(ch=='-'),ch=gc();while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=gc();return x=f?-x:x,*this;}
       il IO& operator>>(char& ch){ch=gc();while(sep&&fok)ch=gc();return *this;}
       il IO& operator>>(string& s){res char ch=gc();while(sep&&fok)ch=gc();while(!sep&&fok)s+=ch,ch=gc();return *this;}
       il IO& operator>>(double& x){x=0;res char f=0,ch=gc();double d=0.1;while(dsep&&fok)f|=(ch=='-'),ch=gc();while(isdigit(ch))x=x*10+(ch^48),ch=gc();if(ch=='.')while(isdigit(ch=gc()))x+=d*(ch^48),d*=0.1;return x=f?-x:x,*this;}
       il IO& operator<<(int x){res char ch[10],i=-1;!x?(pc('0'),0):0,x<0?(pc('-'),x=-x):0;while(x)ch[++i]=x%10+48,x/=10;while(~i)pc(ch[i]),--i;return *this;}
       il IO& operator<<(ll x){res char ch[20],i=-1;!x?(pc('0'),0):0,x<0?(pc('-'),x=-x):0;while(x)ch[++i]=x%10+48,x/=10;while(~i)pc(ch[i]),--i;return *this;}
       il IO& operator<<(char ch){return pc(ch),*this;}
       il IO& operator<<(char str[]){return puts(str),*this;}
       il IO& operator<<(double x){int y=int(x);*this<<y;x-=y;while(neq(x,int(x)))x*=10;x?*this<<'.'<<int(x):0;return *this;}
       il operator bool(){return b;}
}io;


#define N 500100
int n,m,k,t,a[N],cnt[N],ans=0,sz,b[N];
struct que{
    int l,r,id,p;
}q[N];
il bool cmp(que x,que y){
    if(x.p!=y.p)return x.l<y.l;
    return (x.p&1)?(x.r<y.r):(x.r>y.r);
}
il void add(int x){
    if(cnt[a[x]]++==t)ans--;
    if(cnt[a[x]]==t)ans++;
}
il void dec(int x){
    if(cnt[a[x]]--==t)ans--;
    if(cnt[a[x]]==t)ans++;
}
int main(){
    int l,r;
    io>>n>>m>>k>>t;sz=int(sqrt(n));
    Fur(i,1,n)io>>a[i];
    Fur(i,1,m)io>>l>>r,q[i]=(que){l,r,i,(l-1)/sz+1};
    sort(q+1,q+m+1,cmp);
    l=1,r=0;
    Fur(i,1,m){
        while(r<q[i].r)add(++r);
        while(l>q[i].l)add(--l);
        while(l<q[i].l)dec(l++);
        while(r>q[i].r)dec(r--);
        b[q[i].id]=ans;
    }
    Fur(i,1,m)io<<b[i]<<'\n';
}