Codeforces Round 888 (Div. 3)DEF

Nannan Lv5
  2024-09-25 22:31 2024-09-25 22:31 Created   2024-09-30 20:01:19 2024-09-30 20:01:19 Updated      

Codeforces Round 888 (Div. 3) DEF

D. Prefix Permutation Sums

题意：给你一个长度为 的数组，是否能找出一个长度为 的排列，求出这个排列的前缀和，去掉前缀和数组的任意一个元素之后和原来的数组相等。

例如 ，可以是排列 的前缀和 去掉元素 。

思路：维护差分数组，记录已经有了的，还需要的元素和额外的元素。最后去check是否满足。

因为只删除了一个元素，所以如果额外的元素大于1了肯定是不对的(需要的元素(如果有的的话是2个)一定加起来等于这一个额外的)。当然也有可能删除的是最后一个，那就不存在额外的元素，所以如果没有额外的元素也是正确的。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N],d[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        map<ll,bool>hav;

        for(int i = 1;i < n; i++)
            cin>>a[i];
        for(int i = 1;i < n; i++)
            d[i] = a[i]-a[i-1];
        // for(int i = 1;i < n; i++)
        //     cout<<d[i]<<" ";
        // cout<<"\n";
        vector<ll>exa,need;
        for(int i = 1;i < n; i++)
        {
            if(d[i]>=1&&d[i]<=n&&!hav[d[i]])
                hav[d[i]] = true;
            else{
                exa.push_back(d[i]);
            }
        }
        if(exa.empty())
        {
            cout<<"YES\n";
            continue;
        }
        if(exa.size()>1)
        {
            cout<<"NO\n";
            continue;
        }
        for(int i = 1;i <= n; i++)
        {
            if(hav[i])continue;
            need.push_back(i);
        }
        // cout<<"need: ";
        // for(auto x : need)
        //     cout<<x<<" ";
        // cout<<"\n";
        // cout<<"exa: ";
        // for(auto x : exa)
        //     cout<<x<<" ";
        // cout<<"\n";
        if(need.size()>2)cout<<"NO\n";
        else{
            if(need.size()==0)cout<<"YES\n";
            else if(need.size()==1&&exa.size()==0)cout<<"YES\n";
            else{
                if(need.size()==2&&exa.size()==1){
                    if(exa[0]==need[0]+need[1])cout<<"YES\n";
                    else cout<<"NO\n";
                }else cout<<"NO\n";
            }
        }

        // if(need.size()==2&&(exa[0]==need[0]+need[1]))
        //     cout<<"YES\n";
        // else cout<<"NO\n";
    }   
    return 0;
}

E.Nastya and Potions

题意：炼金术士 Nastya 很喜欢合成药水。现有 种药水，第 种药水可以用 个金币买入。

任何一种药水的合成方案都不超过 种。在合成某种药水的过程中，作为原料的药水将会被完全消耗。任何药水都不能直接或间接合成它本身。

作为一个经验老道的炼金术士，Nastya 已经可以无限制地获得 这 种药水，可是她却没法决定接下来要合成哪些药水。于是，她求助于你。对于 ，她需要你求出获得第 种药水所需的最少的金币数。

思路：记忆化搜索+dp

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,k,c[N];
bool hav[N];
vector<int>e[N];
ll dp[N],ans[N];
ll dfs(int x)
{
    if(hav[x])return 0ll;
    ll &res = dp[x];
    if(res!=-1)return res;
    res = c[x];
    if(e[x].size())
    {
        ll tmp = 0;
        for(auto y : e[x])
            tmp += dfs(y);
        res = min(res,tmp);
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i = 1;i <= n; i++)
            cin>>c[i],hav[i] = 0,dp[i] = -1;
        for(int i = 1;i <= k; i++)
        {
            int x; cin>>x;
            hav[x] = true;
        }

        for(int i = 1;i <= n; i++)
        {
            int m; cin>>m;
            e[i].clear();
            for(int j = 1;j <= m; j++)
            {
                int x; cin>>x;
                e[i].push_back(x);
            }
        }
        for(int i = 1;i <= n; i++)
        {
            cout<<dfs(i)<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

F.Lisa and the Martians

题意：给定长度为 的序列 和一个正整数 ，保证 。求满足 且 的三元组 使得 最大。如果有多组符合要求的输出任意一组即可。

多组数据。

思路：对于两个数的每一位进行考虑。

设两个数的同一个位置的值分别为

  • 当，此时这一位取，使得Misplaced &&之后为
  • 当，此时这一位取，使得Misplaced &&之后为
  • 当时，无论怎么取结果都是。

为了尽可能达到最大值，高位尽可能相同。我们知道两个数越接近高位的数越相同。那么我们排序之后在相邻两个数之间考虑就行了。注意结果可能是0，maxx初始化为-1。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
array<int,2>a[N];
bool cmp(array<int,2>a,array<int,2>b)
{
	return a[0]>b[0];
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,k;
		cin>>n>>k;
		for(int i = 1;i <= n; i++)
		{
			cin>>a[i][0];
			a[i][1] = i;
		}
		sort(a+1,a+1+n);
		ll maxx = -1,pos1 = 0,pos2 = 0,tt = 0;
		for(int i = 1;i < n; i++)
		{
			int x = a[i][0],y = a[i+1][0];
			ll w = 0,t = 0;
			for(int j = k-1;j >= 0;j--)
			{
				if(((x>>j)&1)==((y>>j)&1))
				{
					w |= (1<<j);
					if(((x>>j)&1)==0)
						t |= (1<<j);
				}
			}
			if(w>maxx)
				pos1 = a[i][1],pos2 = a[i+1][1],tt = t,maxx = w;
		}
		cout<<pos1<<" "<<pos2<<" "<<tt<<"\n";
	}
	return 0;
}
  • Title: Codeforces Round 888 (Div. 3)DEF
  • Author: Nannan
  • Created at : 2024-09-25 22:31:00
  • Updated at : 2024-09-30 20:01:19
  • Link: https://redefine.ohevan.com/2024/09/25/Codeforces Round 888 (Div. 3)DEF/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
Codeforces Round 888 (Div. 3)DEF
  1. Codeforces Round 888 (Div. 3) DEF
    1. D. Prefix Permutation Sums
    2. E.Nastya and Potions
    3. F.Lisa and the Martians