AtCoder Beginner Contest 248

下载PDF，获得别样的观看体验

A - Lacked Number

题意：

给出10个数字，输出0~9中未出现的那个数字。

思路：

统计数字出现情况即可。

时间复杂度：

O(1)O(1)

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
typedef long long ll;
const int N = 2e5+10,M = 2e5+10,INF = 0x3f3f3f3f,mod = 32768;


int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int cnt[10] = {0};
    std::string s;
    std::cin>>s;
    for(auto c : s)cnt[c-'0']++;
    for(int i = 0 ; i < 10 ; i++)if(!cnt[i])std::cout<<i;
    return 0;
}

B - Slimes

题意：

给定A,B,KA,B,K三个数字,每次操作可以使A=A∗KA=A*K,输出A≥BA\geq B的最小次数

思路：

直接模拟即可。

时间复杂度：

O(BAK)O(\frac{B}{AK})

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
typedef long long ll;
const int N = 2e5+10,M = 2e5+10,INF = 0x3f3f3f3f,mod = 32768;


int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    ll a,b,k;
    std::cin>>a>>b>>k;
    int cnt = 0;
    while(b > a)cnt++,a *= k;
    std::cout<<cnt;
    return 0;
}

C - Dice Sum

题意：

现要求找到一个长度为NN的序列，对于其中的每一个元素，满足如下要求：

  1. 1≤Ai≤M1\leq A_i\leq M
  2. ∑i=1NAi≤K\sum _{i=1}^{N}A_i\leq K

询问满足要求的序列个数。

思路：

考虑动态规划

设有dp[N][K]dp[N][K]：

  1. 第一维表示当前序列长度
  2. 第二维表示当前序列的和
  3. 数组的值表示方案数

枚举所有长度以及序列和，进行状态转移即可。

转移方程：

1
2
3
4
5
6
for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            for(int o = i + j - 1; o <= k ; o++)
            {
                dp[i][o] = (dp[i][o] + dp[i-1][o-j])%mod;
            }

时间复杂度：

O(NK)O(NK)

AC代码：

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
#include<bits/stdc++.h>
typedef long long ll;
const int N = 60,M = 2e5+10,INF = 0x3f3f3f3f,mod = 998244353;

ll dp[N][N*N];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n,m,k;
    std::cin>>n>>m>>k;
    dp[0][0] = 1;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            for(int o = i + j - 1; o <= k ; o++)
            {
                dp[i][o] = (dp[i][o] + dp[i-1][o-j])%mod;
            }
    ll sum = 0;
    for(int i = n ; i<= k ; i++)sum = (sum + dp[n][i])%mod;
    std::cout<<sum;
    return 0;
}

D - Range Count Query

题意：

给定一个长度为nn的序列，和qq个询问，询问格式如下：

给定L,R,XL,R,X,要求输出序列中LL到RR区间内值为$X的个数。

思路：

因为1≤Ai≤N1\leq A_i\leq N，所以我们可以用一个数组，把每一个数字的所有下标分别存起来，然后用二分解决询问即可。

时间复杂度：

O(qlogn)O(qlogn)

AC代码：

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
#include<bits/stdc++.h>
typedef long long ll;
const int N = 2e5+10,M = 2e5+10,INF = 0x3f3f3f3f,mod = 998244353;

std::vector<int> v[N];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n,q;
    std::cin>>n;
    for(int i = 1 ; i <= n ; i++)
    {
        int x;
        std::cin>>x;
        v[x].push_back(i);
    }
    std::cin>>q;
    while(q--)
    {
        int l,r,x;
        std::cin>>l>>r>>x;
        auto it1 = std::lower_bound(v[x].begin(),v[x].end(),l);
        if(it1==v[x].end())
        {
            std::cout<<0<<'\n';
            continue;
        }
        auto it2 = std::upper_bound(v[x].begin(),v[x].end(),r);
        if(it2==v[x].begin())
        {
            std::cout<<0<<'\n';
            continue;
        }
        it2--;
        std::cout<<(it2-it1+1)<<'\n';
    }
    return 0;
}

E - K-colinear Line

题意：

在坐标平面内存在NN个点，每个点的坐标为(Xi,Yi)(X_i,Y_i)，询问存在多少条不同的直线，穿过至少KK个点。

思路：

因为两点可以确定一条直线，而且点数N≤300N\leq 300，所以可以进行如下处理：

  1. 两两枚举所有的点
  2. 在确定完一条直线后，枚举所有的点判断这条直线穿过了多少点

三个点在一条直线上，显然有AC⃗=kAB⃗\vec{AC}=k \vec{AB}

y3−y2x3−x2=y3−y1x3−x1⇒(y3−y2)(x3−x1)=(x3−x2)(y3−y1)\frac{y_3-y_2}{x_3-x_2}=\frac{y_3-y_1}{x_3-x_1}\Rightarrow(y_3-y_2)(x_3-x_1)=(x_3-x_2)(y_3-y_1)

将所有满足条件的直线统计出来即可。

时间复杂度：

O(n3)O(n^3)

AC代码：

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
#include<bits/stdc++.h>
typedef long long ll;
const int N = 310,M = 2e5+10,INF = 0x3f3f3f3f,mod = 998244353;
struct Node{
    ll x,y;
}a[N];
bool book[N][N];

bool OK(Node x,Node y,Node z)
{
    return (z.y-y.y)*(z.x-x.x)==(z.y-x.y)*(z.x-y.x);
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int ans = 0;
    int n,k;
    std::cin>>n>>k;
    if(k==1)
    {
        std::cout<<"Infinity";
        return 0;
    }
    for(int i = 1 ; i <= n ; i++)std::cin>>a[i].x>>a[i].y;
    for(int i = 1 ; i < n ; i++)
        for(int j = i + 1 ; j <= n ; j++)
            if(!book[i][j])
            {
                int cnt = 2;
                std::vector<int> b;
                for(int o = 1 ; o <= n ; o++)
                {
                    if(o == i || o == j)continue;
                    if(OK(a[i],a[j],a[o]))
                    {
                        cnt++;
                        b.push_back(o);
                    }
                }
                b.push_back(i);
                b.push_back(j);
                for(auto x : b)
                    for(auto y : b)book[x][y] = true;
                if(cnt >= k)ans++;
            }
    std::cout<<ans;
    return 0;
}

F - Keep Connect

题意：

给出这样的一个连通图，对于每一个i(1≤i≤n−1)i(1\leq i\leq n-1)，输出删除ii条边并且仍然保持连通性的方案数。

思路：

考虑动态规划

设有dp[i][j][2]dp[i][j][2]:

  1. ii表示前ii组点
  2. jj表示删除的边数
  3. 第三维记录的是第ii组点之间的连通性(第ii组的两个点当前能否连通)
  4. 数组值表示方案数

我们用三个boolbool值a,b,ca,b,c来代表三条边，表示这条边是否删除。

  1. 那么当第i−1i-1组点是不连通的时候，显然是要保证a,ba,b两条边都相连，否则整张图必然失去连通性。
  2. 当第i−1i-1组点是连通的时候，我们只需要保证a,ba,b有一条边是连通的即可，如果a,b,ca,b,c三边中相连了至少两条边，那么就可以保证第ii组点是连通的。

有转移方程

1
2
3
4
5
6
7
8
9
10
if(!k)
{
    if(!a||!b)continue;
    dp[i+1][j+1-c][c] = (dp[i+1][j+1-dp[i][j][k])%Mod;
}
else
{
    if(!a&&!b)continue;
    dp[i+1][j+3-a-b-c][(a+b+c)>=2] = [j+3-a-b-c][(a+b+c)>=2] + dp[i%Mod;
}

时间复杂度：

O(n2)O(n^2)

AC代码：

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
#include<bits/stdc++.h>
typedef long long ll;
const int N = 3010,M = 2e5+10,INF = 0x3f3f3f3f,mod = 998244353;

ll dp[N][N][2];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    dp[1][0][1] = dp[1][1][0] = 1;
    int n;
    ll Mod;
    std::cin>>n>>Mod;
    for(int i = 1 ; i < n ; i++)
        for(int j = 0 ; j <= n ; j++)
            for(int k = 0 ; k < 2 ; k++)
                if(dp[i][j][k])
                    for(int a = 0 ; a < 2 ; a++)
                        for(int b = 0 ; b < 2 ; b++)
                            for(int c = 0 ; c < 2 ; c++)
                            {
                               if(!k)
                               {
                                   if(!a||!b)continue;
                                   dp[i+1][j+1-c][c] = (dp[i+1][j+1-c][c] + dp[i][j][k])%Mod;
                               }
                               else
                               {
                                   if(!a&&!b)continue;
                                   dp[i+1][j+3-a-b-c][(a+b+c)>=2] = (dp[i+1][j+3-a-b-c][(a+b+c)>=2] + dp[i][j][k])%Mod;
                               }
                            }
    for(int i = 1 ; i < n ; i++)std::cout<<dp[n][i][1]<<' ';
    return 0;
}

Ex - Beautiful Subsequences

题意：

给定一个长度为nn的全排列,询问满足如下条件的区间个数：

  • 1≤L≤R≤N1\leq L\leq R\leq N
  • max(PL,…,PR)−min(PL,…,PR)≤R−L+Kmax(P_L,\dots,P_R)-min(P_L,\dots,P_R)\leq R-L+K

思路：

线段树+单调栈：

  1. 线段树：我们先固定一个RR,然后尝试去维护一个序列，这个序列中的第ii个点记录的值为max(Pi,…,PR)−min(Pi,…,PR)−R+imax(P_i,\dots,P_R)-min(P_i,\dots,P_R)-R+i，如果这个值val≤Kval\leq K,那么这个点所代表的区间就是一个合法区间，此外，因为这个序列是全排列，所以不难发现valval不会是负数。我们用线段树去维护这一段区间，区间内记录valval的最小值，并且记录下val+1,val+2,…,val+kval+1,val+2,\dots,val+k的点的个数。
    然后就可以通过根节点的信息推知答案。
  2. 单调栈：我们可以通过单调栈动态的确定区间最值，确定完最值以后通过线段树区间修改即可。

时间复杂度：

O(NKlogN)O(NKlogN)

AC代码：

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
#include<bits/stdc++.h>
typedef long long ll;
const int N = 150000,M = 2e5+10,INF = 0x3f3f3f3f,mod = 998244353;
struct Node{
    int l,r;
    int val,add,cnt[4];
}tr[N*4];
int w[N],k;

void pushup(int u)
{
    tr[u].val = std::min(tr[u<<1].val,tr[u<<1|1].val);
    for(int i = 0 ; i <= k ; i++)
    {
        tr[u].cnt[i] = 0;
        int temp = tr[u].val - tr[u<<1].val + i;
        if(temp >= 0)tr[u].cnt[i] += tr[u<<1].cnt[temp];
        temp = tr[u].val - tr[u<<1|1].val + i;
        if(temp >= 0)tr[u].cnt[i] += tr[u<<1|1].cnt[temp];
    }
}

void pushdown(int u)
{
    if(tr[u].add)
    {
        tr[u<<1].val += tr[u].add;
        tr[u<<1|1].val += tr[u].add;
        tr[u<<1].add += tr[u].add;
        tr[u<<1|1].add += tr[u].add;
        tr[u].add = 0;
    }
}

void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u] = {l,r};
        tr[u].cnt[0] = 1;
        tr[u].val = INF;
    }
    else
    {
        tr[u] = {l,r};
        int mid = l + r >> 1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    }
}

void modify(int u,int l,int r,int v)
{
    if(l > r)return;
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].val += v;
        tr[u].add += v;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid)modify(u<<1,l,r,v);
        if(r > mid)modify(u<<1|1,l,r,v);
        pushup(u);
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n;
    std::cin>>n>>k;
    for(int i = 1 ; i <= n ; i++)std::cin>>w[i];
    build(1,1,n);
    std::stack<std::pair<std::pair<int,int>,int>> stk1,stk2;
    ll ans = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        modify(1,i,i,-INF);
        modify(1,1,i-1,-1);
        int x1 = i,x2 = i;
        while(!stk1.empty())
        {
            if(w[i] < stk1.top().second)
            {
                modify(1,stk1.top().first.first,stk1.top().first.second,stk1.top().second);
                x1 = stk1.top().first.first;
                stk1.pop();
            }
            else break;
        }
        while(!stk2.empty())
        {
            if(w[i] > stk2.top().second)
            {
                modify(1,stk2.top().first.first,stk2.top().first.second,-stk2.top().second);
                x2 = stk2.top().first.first;
                stk2.pop();
            }
            else break;
        }
        stk1.push({{x1,i},w[i]});
        stk2.push({{x2,i},w[i]});
        modify(1,x1,i,-w[i]);
        modify(1,x2,i,w[i]);
        for(int c = 0 ; c <= k ; c++)
            if(tr[1].val + c <= k)ans += tr[1].cnt[c];
    }
    std::cout<<ans;
    return 0;
}

此外，大家也可以看dls的视频讲解，在这里附上链接