牛客IOI周赛18-普及组

数字计数

https://ac.nowcoder.com/acm/contest/7226/A

$\text{A 数字计数}$

分析

数据范围很小，可以考虑快排，再通过去重函数一下直接求解。时间复杂度为 $O(n\log n)$ 。也可以开四个变量 $O(n)$ 扫一次得出答案。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 10010;
LL a[N],n,m;
int main() {
    scanf("%lld",&m);
    for(int i  =1;i <= m;i++ )scanf("%lld",&a[i]);
    sort(a+1,a+1+m);
    n = unique(a+1,a+1+m)-a-1;
    cout << a[n]-a[n-1]<<" "<<a[n]-a[2]<<" "<<a[n-1]-a[2]<<" "<<a[n-1]-a[1]<<endl;
    return 0;
}

$\text{B 数颜色}$

分析

考虑一个节点的贡献是多少。那么它可以贡献的区域为 $last_{col_i} \text{到} i$ 。把所有区间储存下来，把所有询问按右端点排序，这样前面的询问才不会影响后面的计算，树状数组维护一下就好了。复杂度为 $O(n^2\log n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 100;
int read(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f ? -x : x;
}
int a[N],t[N],last[N],m,n,ans;
struct Q{int l,r,id;}q[N];
bool cmp(Q x,Q y) {
    return x.r < y.r;
}
void add(int x,int d){
    for(int i = x;i <= n;i+=i&-i) t[i] += d;
}
int ask(int x){
    int tot = 0;
    for(int i = x;i;i -= i&-i) tot += t[i];
    return tot;
}
int main()
{
    n = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    m = 0;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            q[++m].l = i;q[m].r = j;q[m].id = m; 
        }
    }
    sort(q+1,q+1+m,cmp);
    for(int i = 1,r = 0;i <= m;i++)
    {
        while(r < q[i].r)
        {
            r++;
            if(!last[a[r]]) last[a[r]] = r;
            else {
                add(last[a[r]],-1);
                last[a[r]] = r;
            } 
            add(r,1);
        }
        ans += ask(q[i].r) - ask(q[i].l-1);
    }
    cout << ans << endl;
    return 0;
}

$\text{C 智斗恶龙}$

分析

先 $bfs$ 一次，处理可以到达的所有节点。因为要最大值减去最小值最小，所以我们的答案一定是个连续的区间。考虑把可以到达的节点的值排个序，去重。记录一下最小的差就可以了。总的复杂度为 $O(\sum n\times m \log(\sum n\times m))$ 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1100;
#define LL long long
LL read() {
    LL x = 0,f = 0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f ? -x : x;
}
LL vis[N][N],pd[N][N],T,n,m,sx,sy,d,X;
LL st[N*N],top;
struct Node{LL x,y,d;};
queue<Node> q;
LL dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
int main() {
    T = read();
    while(T--) {
        n = read();m = read();sx = read();
        sy = read();d = read();X = read();
        while(q.size()) q.pop();
        q.push((Node){sx,sy,d});
        memset(st,0,sizeof(st));top = 0;
        memset(vis,0,sizeof(vis));
        memset(pd,0,sizeof(pd));
        for(LL i = 1;i <= n;i++) {
            for(LL j = 1;j <= m;j++) pd[i][j] = read();
        }
        vis[sx][sy] = 1;
        while(q.size()) {
            Node a = q.front();q.pop();
            if(pd[a.x][a.y] == -1) continue;
            if(pd[a.x][a.y] > 0) st[++top] = pd[a.x][a.y];
            if(!a.d) continue;
            for(LL i = 0;i < 4;i++) {
                Node b;
                b.x = a.x + dx[i]; b.y = a.y + dy[i];
                b.d = a.d - 1;
                if(b.x<1||b.x>n||b.y<1||b.y>m||vis[b.x][b.y]||pd[b.x][b.y] == -1) continue;
                vis[b.x][b.y] = 1;q.push(b);
            }
        }
        sort(st+1,st+top+1);
        LL tot = unique(st+1,st+top+1)-st-1;
        LL ans = 0x3f3f3f3f3f3f3f3f;
        for(int i = 1;i <= tot;i++) {
            if(i + X - 1 > tot) continue;
            LL d = st[i+X-1]-st[i];
            ans = min(ans,d); 
        }
        if(ans == 0x3f3f3f3f3f3f3f3f) printf("no\n");
        else printf("%lld\n",ans);
    }
    return 0;
}

$\text{D 能量水晶}$

分析

考虑如果存在一个值 $X$ 没有取，而且这是个合法方案，那么所有比 $X$ 大的值是可以不取的，这就是个类似 $01$ 背包的技术问题了，为了不重不漏的考虑所有方案，我们钦定一个值 $X$ 没有取，且 $\forall X_i < X$ 的值全部取了。那么排序，计算前缀和，最后对于后面 $\forall X_i>X$ 的值进行 $dp$ 转移就好了。时间复杂度为 $O(n^2m)$ 。但是 $n\le 3000$ 这就很迷惑了，要么是我时间复杂度算错了，要不就是数据太水，导致这个思路的代码可以通过。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 31000;
#define LL long long
LL read() {
    LL x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f ? -x : x;
}

LL n,T,a[N],f[N],s[N];
//bool cmp(int x,int y) {return x > y;}
LL ans = 0;
int main() {
//    memset(f,-1,sizeof(f));
    n = read();T = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    sort(a+1,a+1+n);
    for(LL i = 1;i <= n;i++) s[i] = s[i-1] + a[i];
    for(LL i = 1;i <= n;i++) // 下一个法术
    {
        LL sum = s[i-1];
        if(T-sum < 0) continue;
        memset(f,0,sizeof(f));
        f[0] = 1;T -= sum;
        for(int j = i+1;j <= n;j++) {
            for(int t = T;t >= a[j];t--){
                f[t] = f[t] + f[t-a[j]];
            }
        } 
        for(LL j = max(T - a[i] + 1,0LL);j <= T;j++) ans += f[j];
        T += sum;
    } 
    cout << ans << endl;
    return 0;
}