赛前冲刺套题day3

明天考试,很慌……

CSP-S2021加油!

[题目1]绿洲

这题真·卡常数到极致......

其实这题也没有那么难,就是做K遍最短路

因为边权为1,所以最短路算法应选择bfs()(没想到吧)

另几个最短路算法(dijkstra(未知),dijkstra堆优化(80分),spfa(90分)……)均不能满分(开O3+快读卡常数除外)

所以我选择了卡常数……


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
int n,m,k;
int city[100005],final_dist[100005];
int h[100005],e[200005],ne[200005],idx;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra(int S)//本人之前写的是dij堆优化,懒得把函数名改成spfa了
{
    int dist[100005],st[100005]={0};
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
    queue<int> q;
    q.push(S);
    st[S] = true;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + 1)
            {
                dist[j] = dist[t] + 1;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)final_dist[i]=max(final_dist[i],dist[i]);
}
int main()
{
    freopen("oasis.in","r",stdin);
    freopen("oasis.out","w",stdout);
    memset(h,-1,sizeof h);
    n=read();
    m=read();
    k=read();
    for(int i=1;i<=k;i++)city[i]=read();
    while(m--)
    {
        int a=read();
        int b=read();
        add(a,b);
        add(b,a);
    }
    for(int i=1;i<=k;i++)dijkstra(city[i]);
    for(int i=1;i<=n;i++)printf("%d ",final_dist[i]);
    return 0;
}

[题目2]数列

vector NB!!!
而且题解说要用并查集维护其实也是不用的


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int n;
vector<int>A;
vector<int>pos[10005];
int main()
{
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        A.emplace_back(x);
    }
    A.emplace_back(0);
    int cnt=0,flag=1;
    for(int i=0;i<A.size();i++)
    {
        if(A[i])
        {
            pos[A[i]].emplace_back(i);
            flag=0;
        }
        else
        {
            if(!flag)cnt++;
            flag=1;
        }
    }
    int res=cnt;
    for(int i=0;i<=10000;i++)
    {
        for(auto item:pos[i])
        {
            if(A[item-1]&&A[item+1])cnt++;
            else if(!A[item-1]&&!A[item+1])cnt--;
            A[item]=0;
        }
        res=max(res,cnt);
    }
    printf("%d",res);
    return 0;
}

[题目3]遛狗

前置知识:P5490 【模板】扫描线


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+10;
typedef long long LL;
int n,cnt=0;
LL x1,x2,y1,y2,X[N<<1];
struct scan
{
    LL l,r,h;
    int mark;
    bool operator < (const scan &P)const
    {
        return h<P.h;
    }
}line[N<<1];
struct tree
{
    int l,r,sum;
    LL len;
}tr[N<<2];
void build(int k,int l,int r)
{
    tr[k]={l,r,0,0};
    if(l==r)return;
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
}
void pushup(int x)
{
    int l=tr[x].l;
    int r=tr[x].r;
    if(tr[x].sum)tr[x].len=X[r+1]-X[l];
    else tr[x].len=tr[x<<1].len+tr[x<<1|1].len;

}
void modify(int x,LL L,LL R,int c)
{
    int l=tr[x].l;
    int r=tr[x].r;
    if(X[r+1]<=L||R<=X[l])return;
    if(L<=X[l]&&X[r+1]<=R)
    {
        tr[x].sum+=c;
        pushup(x);
        return;
    }
    modify(x<<1,L,R,c);
    modify(x<<1|1,L,R,c);
    pushup(x);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
        X[2*i-1]=x1;
        X[2*i]=x2;
        line[2*i-1]={x1,x2,y1,1};
        line[2*i]={x1,x2,y2,-1};
    }
    n<<=1;
    sort(line+1,line+n+1);
    sort(X+1,X+n+1);
    int tot=unique(X+1,X+n+1)-X-1;
    build(1,1,tot-1);
    LL ans=0;
    for(int i=1;i<n;i++)
    {
        modify(1,line[i].l,line[i].r,line[i].mark);
        ans+=tr[1].len*(line[i+1].h-line[i].h);
    }
    printf("%lld",ans);
    return 0;
}

然后就没有然后了……

[题目4]食材运输

说是都是暴力,但我要二分[doge]


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=110,M=15,INF=1<<29;
typedef long long LL;
typedef pair<int,int>PII;
int n,m,k,idx,h[N],d[N][M],g[N][M];
struct Edge
{
    int e,ne,w;
}edge[N*2];
void add(int u,int v,int w)
{
    edge[++idx]={v,h[u],w};
    h[u]=idx;
}
PII dfs(int u,int father,int op)
{
    PII res={0,-1};
    if(g[u][op])res.second=0;
    for(int i=h[u];i;i=edge[i].ne)
    {
        int to=edge[i].e;
        int w=edge[i].w;
        if(to==father)continue;
        auto t=dfs(to,u,op);
        if(t.second!=-1)
        {
            res.first+=t.first+(w*2);
            res.second=max(res.second,t.second+w);
        }
    }
    return res;
}
int state[N],f[1<<M];
bool check(int mid)
{
    memset(state,0,sizeof state);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<k;j++)
        {
            if(d[i][j]<=mid)state[i]|=(1<<j);
        }
    }
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<(1<<k);j++)f[j|state[i]]=min(f[j|state[i]],f[j]+1);
    }
    return f[(1<<k)-1]<=m;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<k;j++)scanf("%d",&g[i][j]);
    }
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<k;j++)
        {
            auto t=dfs(i,-1,j);
            if(t.second!=-1)d[i][j]=t.first-t.second;
        }
    }
    int l=0,r=INF;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%d",r);
    return 0;
}

最后

CSP-S 2021 加油!

CSP-S 2021 加油!

CSP-S 2021 加油!

发表评论

邮箱地址不会被公开。 必填项已用*标注