Eternity

Until The End

NOIP2022.02.12模拟赛

发表于 更新于 分类于
本文字数： 9.1k 阅读时长 ≈ 8 分钟

还彳亍

题目I——城墙（wall）

题目描述

给出一个长度为 $n$ 的序列和一个数 $S$ ，求出最短的区间使得区间和大于等于 $S$ 。

思路

因为 $n \leq 1500000$ ，所以复杂度最大为 $O(n \log n)$ ，统计前缀和，二分统计长度是否能达到，每次暴力区间和。复杂度合适。

Task One AC Code

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
const int MAXN=1500001;
template<class T>
inline void underRead(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
int n,S,num[MAXN];
ll sum[MAXN];
inline bool underCheck(int k)
{
    for(int i=k;i<=n;++i) if(sum[i]-sum[i-k]>=S) return 1;
    return 0;
}
int main()
{
    freopen("wall.in","r",stdin);
    freopen("wall.out","w",stdout);
    underRead(n),underRead(S);
    for(int i=1;i<=n;++i)
    {
        underRead(num[i]);
        sum[i]=sum[i-1]+num[i];
    }
    int l=1,r=n;
    if(sum[n]<S)
    {
        printf("0");
        return 0;
    }
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(underCheck(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d",l);
    return 0;
}
/*
10 15
5 1 3 5 10 7 4 9 2 8
*/

题目II——岗哨（sentry）

题目含义

给出一个长度为 $n(n \leq 10^6)$ 的序列：

第一个答案求的是一段最长的，严格递增的，右端点最小的子区间，输出该子区间的右端点。

第二行答案求的是去掉一个区间后，一段最长的，严格递增的，右端点最小的子区间，输出该子区间的右端点和长度。

其他事项

洛谷有一道类似题目——UVA1471防线

根据机房老大哥的教导，这道题的方法多样：树状数组，线段树，$Dp$，离散化等。

思路

注：本人的线段树写挂了，所以以下方法来自同机房巨佬_Live_的题解

对于第一个答案，用 $num_i$ 结构体统计每一个连续上升子区间的信息，得出最大的子区间长度，输出右端点即可。

对于第二个答案，用 $f_i$ 统计以 $i$ 为起点的最长上升子序列的大小， $g_i$ 来统计以 $i$ 结尾的最长上升子序列的大小。枚举 $a_i , i \in ( 1 , n )$ ，找到每一个 $k$ 使 $a_k < a_i$ 时的 $g_k + f_i$ 最大。

这样子看来，这个模拟的过程类似于求 $LIS$ （最长上升子序列）的过程。以 $b_i$ 数组存储能够使 $g_i$ 的值为 $i$ 的最小的 $a_i$ 的值。最后我们求到的 $dp$ 位置是第二个区间的左端点，所以最后输出的应该是 $dp+f_{dp}-1$ 的位置。

Task Two AC Code

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
const int INF=1e9;
template<class T>
inline void underRead(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
int T,n,v[MAXN<<2],a[MAXN],g[MAXN],f[MAXN],b[MAXN];
inline void underBuild(int p,int l,int r)
{
    v[p]=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    underBuild(p<<1,l,mid),underBuild(p<<1|1,mid+1,r);
}
inline void underModify(int p,int l,int r,int x,int d)
{
    v[p]=underMax(v[p],d);
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(x<=mid) underModify(p<<1,l,mid,x,d);
    if(mid<x) underModify(p<<1|1,mid+1,r,x,d);
}
inline int underQuery(int p,int l,int r,int x,int y)
{
    if(x<=l&&r<=y) return v[p];
    int mid=(l+r)>>1,ans=0;
    if(x<=mid&&y>=l) ans=underQuery(p<<1,l,mid,x,y);
    if(y>mid&&x<=r) ans=underMax(ans,underQuery(p<<1|1,mid+1,r,x,y));
    return ans;
}
int h[MAXN],tot,Max,Dp,t[MAXN];
struct Node
{
    int l,r;
}num[MAXN];
inline void underWork()
{
    // underRead(n);
    memset(b,0x7f7f7f7f,sizeof(b));
    a[0]=a[n+1]=0;
    for(int i=1;i<=n;++i) 
    {
        // underRead(a[i]);
        a[i]=h[i];
        g[i]=1;
        if(a[i]>a[i-1]) g[i]=g[i-1]+1;
    }
    int ans=0,dp=0;
    for(int i=n;i;--i)
    {
        f[i]=1;
        if(a[i]<a[i+1]) f[i]=f[i+1]+1;
    }
    for(int i=1;i<=n;++i)
        if(ans<underMax(f[i],g[i]))
        {
            ans=underMax(f[i],g[i]);
            dp=i;
        }
    /*sort(b+1,b+1+n);
    int cnt=unique(b+1,b+1+n)-b-1;
    underBuild(1,1,cnt+1);*/
    b[1]=a[1];
    for(int i=1;i<=n;++i)
    {
        int k=lower_bound(b+1,b+1+n,a[i])-b-1;
        if(f[i]+k>ans)
        {
            ans=f[i]+k;
            dp=i;
        }
        b[g[i]]=underMin(b[g[i]],a[i]);
    }
    /*for(int i=1;i<=n;++i)
    {
        int x=lower_bound(b+1,b+1+n,a[i])-b;
        ans=underMax(ans,f[i]+underQuery(1,1,cnt+1,1,x));
        underModify(1,1,cnt+1,x+1,g[i]);
    }*/
    printf("%d %d",dp+f[dp]-1,ans);
}
/*inline int underDisc(int x)
{
    int l=1,r=tot;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(num[mid].l<=x&&x<=num[mid].r) return mid;
        else if(num[mid].l>x) r=mid;
        else if(num[mid].r<x) l=mid+1;
    }
    return l;
}
inline void underCheck()
{
    for(int l=1;l<n;++l)
    {
        if(Max>=n-l) return ;
        for(int i=2;i<=n-l;++i)
        {
            //i ~ i+l-1
            int u1=i-1,u2=i+l;
            if(t[u1]==t[u2])
            {
                i=num[t[u2]].r-l;
                continue;
            }
            //i+l=num[t[u2]].r
            if(h[u1]<h[u2])
            {
                int len=(u1-num[t[u1]].l+1)+(num[t[u2]].r-u2+1);
                if(len>Max) Max=len,Dp=num[t[u2]].r;
            }
        }
    }
}*/
int main()
{
    freopen("sentry.in","r",stdin);
    freopen("sentry.out","w",stdout);
    underRead(n);
    num[++tot].l=1;
    for(int i=1;i<=n;++i)
    {
        underRead(h[i]);
        if(h[i-1]>=h[i])
        {
            num[tot].r=i-1;
            num[++tot].l=i;
        }
        t[i]=tot;
    }
    num[tot].r=n;
    if(tot==1)
    {
        printf("%d\n%d %d",n,n,n);
        return 0;
    }
    if(tot==n)
    {
        printf("1\n1 1");
        return 0;
    }
    int maxn=0,dp=1;
    for(int i=1;i<=tot;++i) 
    {
        int k=num[i].r-num[i].l+1;
        if(k>maxn)
        {
            maxn=k;
            dp=num[i].r;
        }
    }
    // Max=maxn,Dp=dp;
    printf("%d\n",dp);
    underWork();
    return 0;
}
/*
8
1 2 3 7 6 4 5 2
*/

题目III——黑客（Hack）

题目含义

给定一个有向图，从任意一点出发遍历所有点，删除所有经过的边；再从任意一点出发遍历所有点，如果能达到，求出两次所需的最小权值和。

思路

说实话，当看到 $n \leq 10 , m \leq 25$ 时我真的以为正解是爆搜。然而测试数据有 $1000$ 套。

跑一遍最小生成树（建议 $Kruskal$ ），求出这棵树上的必要边（删掉会使原图最小生成树的总权值变大的边）。这些边必在第二棵最小生成树里。枚举必要边在 $A$ 和 $B$ 生成树里的情况，则 $ans = \min ( a + b )$ 。

可惜蒟蒻到最后也没打出来qwq

Task Three AC Code

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
const int MAXN=101;
const int MAXM=206;
const int INF=1e9;
template<class T>
inline void underRead(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
struct Node
{
    int u,v,w;
}Edge[MAXM<<2];
int id[MAXN],b[MAXN],c[MAXN];
int f[MAXN],coun,cnt,num,n,m;
bool vis[MAXM];
inline bool underCmp(Node a,Node b)
{
    return a.w<b.w;
}
inline int underFind(int x)
{
    if(id[x]==x) return x;
    return id[x]=underFind(id[x]);
}
inline void underInit()
{
    cnt=num=0;
    memset(vis,0,sizeof(vis));
}
inline void underInPut()
{
    underRead(m);
    for(int i=1;i<=m;++i) scanf("%d%d%d",&Edge[i].u,&Edge[i].v,&Edge[i].w);
    sort(Edge+1,Edge+1+m,underCmp);
}
inline int underKruskal(int x)
{
    int ret=0;
    for(int i=0;i<=n+1;++i) id[i]=i;
    for(int i=1;i<=m;++i)
    {
        int p1=underFind(Edge[i].u),p2=underFind(Edge[i].v);
        if(p1!=p2&!vis[i])
        {
            if(x==1) b[cnt++]=i;
            if(x==3) f[coun++]=i;
            ret+=Edge[i].w;
            id[p2]=p1;
        }
    }
    int tp=underFind(1);
    for(int i=1;i<=n;++i) if(underFind(i)!=tp) return INF;
    return ret;
}
inline int underDeal(int cd)
{
    int tp=0,d[MAXN];
    for(int j=0;j<num;++j) if(cd&(1<<j)) d[tp++]=c[j];
    memset(vis,0,sizeof(vis));
    for(int i=0;i<tp;++i) vis[d[i]]=1;
    coun=0;
    int x1=underKruskal(3);
    for(int i=0;i<coun;++i) vis[f[i]]=1;
    for(int i=0;i<tp;++i) vis[d[i]]=0;
    int x2=underKruskal(2);
    return x1+x2;
}
inline void underAns(int x)
{
    if(x>=INF) printf("Too young too simple,sometimes naive!\n");
    else printf("%d\n",x);
}
inline void underWork()
{
    int ret=underKruskal(1);
    for(int i=0;i<cnt;++i)
    {
        memset(vis,0,sizeof(vis));
        vis[b[i]]=1;
        int tp=underKruskal(2);
        if(ret<tp) c[num++]=b[i];
    }
    int len=1<<num,ans=INF;
    for(int i=0;i<len;++i) ans=underMin(ans,underDeal(i));
    underAns(ans);
}
int main()
{
    freopen("hack.in","r",stdin);
    freopen("hack.out","w",stdout);
    while(scanf("%d",&n)!=EOF)
    {
        if(!n) break;
        underInit();
        underInPut();
        underWork();
    }
    return 0;
}
/*
2
3
1 2 10
2 1 20
1 2 30
3
3
1 2 10
1 2 20
2 3 50
0
*/

题目IV——膜拜大会（fake）

过于毒瘤，不会qwq

给一个链接

相关文章