清北考前刷题day2早安-白红宇

清北考前刷题day2早安

阅读量：4570 次

发布时间：2019-06-08

本文共 6243 字，大约阅读时间需要 20 分钟。

/*做法一：按h sort一遍，对于一段区间[i,j]，高度花费就是h[j]-h[i]然后枚举区间，把区间内C排序，一个一个尽量选即可。n^3logn标算：n^3 dp高度排序，保证从前往后调。f[i][j]表示当前在第i栋楼，已经跳了j次楼的最小话费。转移枚举下一次跳那座楼。f[k][j+1]=min(f[i][j],f[i][j]+h[k]-h[i]+c[k]);最后枚举f[i][j]
       
        #include
        
         #include
         
          #include
          
           #define N 510using namespace std;int T,n,ans,cnt;int f[N][N];//当前处于第i座楼房已经跳了j次楼最小花费 struct node{    int h,c;    bool operator < (const node a) const{            return h
           
            '9'||c<'0'){
      if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int main(){    n=read();    for(int i=1;i<=n;i++) L[i].c=read();    for(int i=1;i<=n;i++) L[i].h=read();    T=read();    sort(L+1,L+n+1);        memset(f,127/3,sizeof f);    f[1][0]=f[1][1]=L[1].c;    for(int i=1;i<=n;i++)      for(int j=0;j<=n+1;j++)        for(int k=i+1;k<=n;k++)          f[k][j+1]=min(f[k][j+1],f[i][j]+L[k].h-L[i].h+L[k].c);                    for(int i=1;i<=n;i++)      for(int j=0;j<=n+1;j++)        if(f[i][j]<=T) ans=max(ans,j);    printf("%d\n",ans);    return 0;     }

/*考虑最后要求的数 a1,a2,..an假定从小到大给定了b1,b2......bn 从小到大排序性质一：a1+a2=b1性质二：a1+a3=b2假设a2+a3=x，可以解出a1,a2,a3,并可以在b中b1,b2,x删除。则剩下的最小的一定是a1+a4。由于a1已知，a4可解。这个过程可以反复下去。枚举a2+a3=b里面哪个数就好*/#include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=310;int n,m,res[N],ans[N][N],z[N*N],cnt;bool use[N*N];void check(int p){    memset(use,false,sizeof(use));    if ((z[1]+z[2]+z[p])&1) return;    res[1]=(z[1]+z[2]+z[p])/2-z[p];    res[2]=z[1]-res[1];    res[3]=z[2]-res[1];    use[1]=use[2]=use[p]=true;    for (int a=4,b=3;a<=n;a++)    {        while (b<=m && use[b]) b++;        if (b>m) return;        res[a]=z[b]-res[1];        use[b]=true;        for (int c=2;c
           
            res[a]) return;            int v=res[c]+res[a];            int p=lower_bound(z+1,z+m+1,v)-z;            if (z[p]!=v) return;            int px=p;            while (px && z[px]==z[p]) px--;            px++;            while (px<=m && z[px]==z[p] && use[px]) px++;            if (z[px]!=z[p] || use[px]) return;            p=px;    use[p]=true;        }    }    cnt++;    for (int a=1;a<=n;a++) ans[cnt][a]=res[a];}int main(){    freopen("city.in","r",stdin);    freopen("city.out","w",stdout);    scanf("%d",&n);    m=n*(n-1)/2;    for (int a=1;a<=m;a++) scanf("%d",&z[a]);    sort(z+1,z+m+1);    for (int a=3;a<=m;)    {        check(a);int b=a;        while (b<=m && z[b]==z[a])b++;        a=b;    }    printf("%d\n",cnt);    for (int a=1;a<=cnt;a++)        for (int b=1;b<=n;b++)        {            printf("%d",ans[a][b]);            if (b==n) printf("\n");            else printf(" ");        }    return 0;}

#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define N 100007using namespace std;int n,m,ans,c,p,v;int a[N];vector
             
              sum[N];struct ask{ int l,r,v,p;}A[N];inline int read(){ int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int main(){ freopen("light.in","r",stdin); freopen("light.out","w",stdout); int l,r; n=read();m=read(); for(int i=1;i<=n;i++) a[i]=read(); if(n<=1000) { for(int i=1;i<=m;i++) { ans=0; l=read();r=read();p=read();v=read(); for(int j=l;j<=r;j++) if(a[j]%p==v) ans++; printf("%d\n",ans); } } else { for(int i=1;i<=m;i++) { A[i].l=read();A[i].r=read(); A[i].p=read();A[i].v=read(); } for(int i=1;i<=n;i++) a[i]%=A[1].p; for(int i=1;i<=n;i++) sum[a[i]].push_back(i); for(int i=1;i<=m;i++) { printf ("%d\n",upper_bound(sum[A[i].v].begin (), sum[A[i].v].end (), A[i].r) -lower_bound (sum[A[i].v].begin (), sum[A[i].v].end (), A[i].l)); } } return 0;}

60暴力

链表？！！wt？！

可以对p分块。

p在[1,10^4+1]。如果枚举p预处理每个数mod p扔到vector里。O(np) TLE

可以把p在[1,100]里预处理，vector里二分即可。

p>100时,只有v+p,v+2p...v+kp能对答案造成贡献。一定有v+kp<=10^4,p>100-->k<=100。所以每次询问都最多有100个数对答案造成贡献，可以vector预处理，枚举这100个v+jp，vector里二分。

复杂度n*sqrt(n)*lgn。

#include 
       
        #include 
        
         #include 
         
          using namespace std;const int maxn = 100009;const int maxv = 10000;const int bsz = 100;const int maxb = 103;int n, m;int a[maxn], vb[maxb][maxb], ve[maxb][maxb];int xb[maxn], xe[maxn];int i_buf[maxn * maxb * 2], tib;void pre() {    memset(ve, 0, sizeof(ve));    memset(xe, 0, sizeof(xe));    for (int i = 1; i <= n; ++ i)        ++ xe[a[i]];    for (int i = 0; i <= maxv; ++ i) {        xb[i] = tib;        tib += xe[i];        xe[i] = xb[i];    }    for (int i = 1; i <= n; ++ i)        i_buf[xe[a[i]] ++] = i;    for (int m = 1; m <= bsz; ++ m) {        for (int i = 1; i <= n; ++ i)            ++ ve[m][a[i] % m];        for (int i = 0; i < m; ++ i) {            vb[m][i] = tib;            tib += ve[m][i];            ve[m][i] = vb[m][i];        }        for (int i = 1; i <= n; ++ i)            i_buf[ve[m][a[i] % m] ++] = i;    }}int queryb(int l0, int r0, int p, int k) {    if (vb[p][k] == ve[p][k])        return 0;    int *x1 = lower_bound(i_buf + vb[p][k], i_buf + ve[p][k], l0);    int *x2 = upper_bound(i_buf + vb[p][k], i_buf + ve[p][k], r0);    return x2 - x1;}int querys(int v, int l0, int r0) {    if (xb[v] == xe[v])        return 0;    int *x1 = lower_bound(i_buf + xb[v], i_buf + xe[v], l0);    int *x2 = upper_bound(i_buf + xb[v], i_buf + xe[v], r0);    return x2 - x1;}int querya(int l0, int r0, int p, int k) {    int ans = 0;    for (int i = k; i <= maxv; i += p)        ans += querys(i, l0, r0);    return ans;}int main() {    freopen("light.in", "r", stdin);    freopen("light.out", "w", stdout);    scanf("%d%d", &n, &m);    tib = 0;    for (int i = 1; i <= n; ++ i)        scanf("%d", a + i);    pre();    while (m --) {        int l, r, p, k;        scanf("%d%d%d%d", &l, &r, &p, &k);        if (p <= bsz)            printf("%d\n", queryb(l, r, p, k));        else            printf("%d\n", querya(l, r, p, k));    }}