day2上午

清北学堂--刷题班

t1

部分数据
高度相同，按c排序.
c=0，准备没有花费，顺序：高度从小到大，从大到小。
按h排序，枚举第一栋楼从哪里跳，一直往后跳，直到，跳到不行了。

100%
做法1：

考虑一个跳楼的集合，{1245},首先是c的和，其次是跳楼的高度差，所以先排序，高度差 等价于 最高的楼-最低的楼。
枚举两栋楼，最高的hj与最低hi的，确定中间的楼（c），
i+1 ~ j-1 这些楼中拿最小的，按c排序，从小的往大的拿，
n^3logn

做法2：

动态规划
首先按高度排序，
f[i][j]第i栋楼上，跳了j栋楼的最小花费是多少。
i f[k][j+1] = min(f[k][j+1],f[i][j+c[k]+h[k]-h[i]);

难度在noip第 1.5~1.75 题 by zhx

t2

考虑答案是a1,a2...an
给出的是b1,b2....b n(n-1)/2
先排序b，

性质1： a1+a2 = b1
性质2： a1+a3 = b2
a2+a3 = ？（如果知道？，可以解方程）

那么设a2+a3 = x
解出方程，从b中删除这些数
最小的 a1+a4
继续解方程

做法
枚举x是多少(b4,b5...)，看一下是否满足条件。

n^3

判读是否在b中出现过，二分，map，set

t3

数据结构-链表。

p相同，所有数都先modp，链表，

1 5 2 3 4 p=3
1 2 2 0 1

0: 4
1: 1 5
2: 2 3

查询-二分查找。
空间复杂度O(n)。

对p分块。
p<=100 和 p>100
p<=100 预处理。
p>100
mod p = v 的
v,v+p,v+2p...v+kp k<=100
枚举100个数。

解题报告总结：

预计70+30+(>=60)后面可能超时
实际40+30+70

改正：上午t1数据错了，改过来是
实际的分60+30+70

t1

没想出正解，写了<=5搜索，两个特判的数据
h相等和c=0
结果60

考试代码

#include<cstdio>
#include<algorithm>
#include<cstring>


using namespace std;

const int MAXN = 100;
int c[MAXN],h[MAXN];
bool vis[MAXN];
int ans = 1,n,T;


inline int read() {
    int x = 0,f = 1;char ch = getchar();
    for (; ch<'0'||ch>'9'; ch = getchar())
        if (ch=='-') f = -1;
    for (; ch>='0'&&ch<='9'; ch = getchar())
        x = x*10+ch-'0';
    return x*f;
}

void sousuo(int u,int cnt,int sum) { 
    if (sum+c[u] < T) {
        ans = max(ans,cnt);
    }
    else {
        return; 
    }
    for (int i=1; i<=n; ++i) {
        if (i==u || vis[i])continue ;
        vis[i] = true;
        if (sum+abs(h[u]-h[i])+c[u] > T) continue;
        sousuo(i,cnt+1,sum+abs(h[u]-h[i])+c[u]);
        vis[i] = false;
    }

}
void wok1() { // c
    sort(h+1,h+n+1);
    int ret = 0,t1,t2;
    for (int i=1; i<=n; ++i) {
        t1 = 0,t2 = 1;
        for (int j=i+1; j<=n; ++j) {
            if (t1 + (h[j]-h[j-1]) <= T) t1 += (h[j]-h[j-1]),t2++;
            else break;
        }
        ret = max(ret,t2);
    }
    printf("%d",ret);
    return ;    
}
void wok2() { // h
    sort(c+1,c+n+1);
    int ss = 0;
    for (int i=1; i<=n; ++i) {
        if (ss+c[i] <= T) ss += c[i];
        else {
            printf("%d",i-1);
            return ;
        }
    }
    //可以全选上，所以第二组数据这里没有输出。。。，加上下面这句
    printf("%d",n);
}
int main() {

freopen("meet.in","r",stdin);
freopen("meet.out","w",stdout);

bool flag1 = true,flag2 = true;
n = read();
for (int i=1; i<=n; ++i) {
    c[i] = read();
    if (c[i]!=0) flag1 = false;
}
for (int i=1; i<=n; ++i) {
    h[i] = read();
    if (h[i]!=h[1]) flag2 = false;
}
T = read();

if (flag1) {
    wok1();
    return 0;
}
if (flag2) {
    wok2();
    return 0;
}
//  if (n<=5) {
        for (int i=1; i<=n; ++i) {
            vis[i] = true;
            sousuo(i,1,0);
            vis[i] = false;
        }
        printf("%d",ans);
        return 0;
//  }

}
/*
4
3 5 4 11
2 1 3 1
17

5 
1 2 3 4 5
5 4 3 2 1
13

5 
1 4 5 2 1
3 4 2 9 2
10

3


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

10
0 0 0 0 0 0 0 0 0 0
1 4 3 5 3 5 6 7 8 9 
3

5
1 0 3 4 5
3 1 3 2 3
8
*/

正解：

t2

最后半小时写了搜索30，
考试代码：

#include<cstdio>
#include<algorithm>
#include<cstring>


using namespace std;

const int MAXN = 320;
int a[5010],b[MAXN],shu[MAXN],shub[MAXN];
int n,t,mx;
int ans[MAXN][MAXN],p;

inline int read() {
    int x = 0,f = 1;char ch = getchar();
    for (; ch<'0'||ch>'9'; ch = getchar())
        if (ch=='-') f = -1;
    for (; ch>='0'&&ch<='9'; ch = getchar())
        x = x*10+ch-'0';
    return x*f;
}

void pd() {
    memset(shub,0,sizeof(shub));
    for (int i=1; i<=n; ++i) {
        for (int j=i+1; j<=n; ++j) {
            shub[b[i]+b[j]]++;
        }
    }
    for (int i=0; i<=mx; ++i) {
        if (shub[i]!=shu[i]) return ;
    }
    ++p;
    for (int i=1; i<=n; ++i) {
        ans[p][i] = b[i];
    }
}

void dfs(int x,int beg) {
    if (x==n+1) {
        pd();
        return ;
    }
    for (int i=beg; i<mx; ++i) {
        b[x] = i;
        dfs(x+1,i);
    }
}
int main() {

    freopen("city.in","r",stdin);
    freopen("city.out","w",stdout);

    n = read();
    t = n*(n-1)/2;

        for (int i=1; i<=t; ++i) 
            a[i] = read(),mx = max(mx,a[i]),shu[a[i]]++;

    dfs(1,0);



    printf("%d\n",p);
    for (int i=p; i>=1; --i) {
        for (int k=1; k<=n; ++k) {
            printf("%d ",ans[i][k]);
        }
        printf("\n");
    }

    return 0;
} 

/*
4
3 5 4 7 6 5

4
11 17 21 12 20 15
*/

正解：

t3

写完t1现做的这个，先写了30分的暴力，
另外30分是链表，首先全模一遍p，然后用链表把相同的全连起来，顺着链表找。
写完发现剩下的也能做，用链表把所有相同的数连起来，然后对于模p等于v的，顺着链表找v，v+p,v+2p...的个数，加起来。然后就超时了3个点。

考试代码

#include<cstdio>
#include<algorithm>
#include<cstring>


using namespace std;

const int MAXN = 200100;

int a[MAXN],sum[MAXN];
struct Que{
    int l,r,p,v;
}q[MAXN];
int nt[MAXN],head[MAXN],last[MAXN];
int mx;

inline int read() {
    int x = 0,f = 1;char ch = getchar();
    for (; ch<'0'||ch>'9'; ch = getchar())
        if (ch=='-') f = -1;
    for (; ch>='0'&&ch<='9'; ch = getchar())
        x = x*10+ch-'0';
    return x*f;
}
inline void wok(int l,int r,int x) {
    int ans = 0;
    for (int i=head[x]; i!=-1; i=nt[i]) {
        if (i>=l && i<=r) ans++;
        if (i > r) break;
    }
    printf("%d\n",ans);
}
inline void wok2(int l,int r,int v,int p) {
    int ans = 0;

    for (int k=v; k<=mx; k+=p) 
        for (int i=head[k]; i!=-1; i=nt[i]) {
            if (i>=l && i<=r) ans ++;
            if (i > r) break;
        }
    printf("%d\n",ans);
}
int main() {

    freopen("light.in","r",stdin);
    freopen("light.out","w",stdout);


    bool flag = true;
    int n = read(),m = read();
    for (int i=1; i<=n; ++i) {
        a[i] = read();
        mx = max(mx,a[i]);
    }
    for (int i=1; i<=m; ++i) {
        q[i].l = read(),q[i].r = read(),
        q[i].p = read(),q[i].v = read();
        if (q[i].p != q[1].p) flag = false;
    }
    if (n <= 1000 && m <= 1000) {

        for (int i=1; i<=m; ++i) {
            int ans = 0;
            for (int j=q[i].l; j<=q[i].r; ++j) {
                if (a[j]%q[i].p==q[i].v) ans ++; 
            }
            printf("%d\n",ans);
        }
        return 0;

    }


    if (flag) {

        memset(nt,-1,sizeof(nt));
        int p = q[1].p;

        for (int i=1; i<=n; ++i) {
            a[i] = a[i]%p;
            if (last[a[i]]) {
                nt[last[a[i]]] = i;
                last[a[i]] = i;
            }
            else head[a[i]] = i,last[a[i]] = i;
        }
        /*for (int i=0; i<p; ++i) {
            for (int k=head[i]; k!=-1; k=nt[k]) {
                printf("%d ",k);
            }
            printf("\n");
        }*/
        for (int i=1; i<=m; ++i) {
            wok(q[i].l,q[i].r,q[i].v);
        }

        return 0;
    }

        memset(nt,-1,sizeof(nt));

        for (int i=1; i<=n; ++i) {
            if (last[a[i]]) {
                nt[last[a[i]]] = i;
                last[a[i]] = i;
            }
            else head[a[i]] = i,last[a[i]] = i;
        }

        /*for (int i=0; i<=mx; ++i) {
            for (int k=head[i]; k!=-1; k=nt[k]) {
                printf("%d ",k);
            }
            printf("\n");
        }*/

        for (int i=1; i<=m; ++i) {
            wok2(q[i].l,q[i].r,q[i].v,q[i].p);
        }

    return 0;
}
/*

5 2
1 5 2 3 7
1 3 2 1
2 5 3 0


5 3
1 5 2 3 6
1 3 2 1
2 5 2 0
1 6 2 1

6 1
1 2 5 3 5 2 
1 6 3 2
*/