The 2021 ICPC 南京 ACJM

Nannan Lv5
  2023-10-04 12:41 2023-10-04 12:41 Created   2024-09-30 17:05:12 2024-09-30 17:05:12 Updated      

The 2021 ICPC Asia Nanjing Regional Contest (XXII Open Cup, Grand Prix of Nanjing)

A.Oops, It’s Yesterday Twice More

思路：考虑先把所有袋鼠集中在一起然后再移动。因为有步数限制()。那么分类讨论移动到四个角上，看哪个符号条件的就输出。

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
// 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,a,b;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>a>>b;
    //LU
    int x = 1,y = 1;
    if((a-x)+(b-y)<=(n-1))
    {
        for(int i = 1;i <= n-1;i++)cout<<"L";
        for(int i = 1;i <= n-1;i++)cout<<"U";
        for(int i = 1;i <= b-y;i++)cout<<"R";
        for(int i = 1;i <= a-x;i++)cout<<"D";
        return 0;
    }
    //RU
    x = 1,y = n;
    if((a-x)+(y-b)<=(n-1))
    {
        for(int i = 1;i <= n-1;i++)cout<<"R";
        for(int i = 1;i <= n-1;i++)cout<<"U";
        for(int i = 1;i <= y-b;i++)cout<<"L";
        for(int i = 1;i <= a-x;i++)cout<<"D";
        return 0;
    }
    //LD
    x = n,y = 1;
    if((x-a)+(b-y)<=(n-1))
    {
        for(int i = 1;i <= n-1;i++)cout<<"L";
        for(int i = 1;i <= n-1;i++)cout<<"D";
        for(int i = 1;i <= b-y;i++)cout<<"R";
        for(int i = 1;i <= x-a;i++)cout<<"U";
        return 0;
    }
    //RD
    x = n,y = n;
    if((x-a)+(y-b)<=(n-1))
    {
        for(int i = 1;i <= n-1;i++)cout<<"R";
        for(int i = 1;i <= n-1;i++)cout<<"D";
        for(int i = 1;i <= y-b;i++)cout<<"L";
        for(int i = 1;i <= x-a;i++)cout<<"U";
        return 0;
    }


    return 0;
}

C. Klee in Solitary Confinement

思路：

做法一：(公式推导)我们考虑枚举众数是谁，然后去写。对于众数是的情况，只有对它有贡献。那么考虑对于一段区间,我们对于众数是情况的贡献是什么呢？

![image-20230901231020613](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230901231020613.png)

如上图所示：

为了更快的处理区间问题，我们先预处理出对于某个数的前缀出现次数，和的前缀出现次数

那么对于，对于众数是的贡献是

移向得：

因为是定值，那么我们只需要后面这个东西最大就行了。我们固定左界去枚举右界，取max就是答案。

还有一个问题，如何处理出这个东西？

我们先用$vectoridx[N]存下每种值的下标，然后呢，对于众数是x+k的情况，只有x是对它有贡献的。我们把idx[x]和idx[x+k]取出来，根据下标，把它们排成一排，假设这两组数总共是有c个，那for(1～c)对两组数做前缀操作。做完以后还是for(1～c)去求pre2[n]+(pre1[R]-pre1[L-1])-(pre2[R]-pre2[L-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
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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 4e6 + 10,M = 2e6;
vector<int>idx[N];
int pos[N];
int cnt[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n,k;
    cin>>n>>k;
    ll maxn = -1e9;
    ll res = -1e18;
    for(int i = 1;i <= n; i++)
    {
        ll x;
        cin>>x;
        x += M;
        cnt[x]++;
        if(cnt[x]>res)res = cnt[x];
        maxn = max(maxn,x);
    	idx[x].push_back(i);
    }
   	//cout<<"mx = "<<maxn<<"\n";
  
    
    for(int i = 0;i <= 4e6; i++)
    {
    	int c =  0;
    	int x = i,y = i+k;
    	if(y<0||y>4e6)continue;
    	int sz1 = idx[x].size(),sz2 = idx[y].size();
    	
    	if(y<0||y>4e6||sz1==0||sz2==0)continue;
    	//cout<<"x = "<<x-M<<" y = "<<y-M<<"\n";
    	int cnt1 = 0,cnt2 = 0;
    	while(cnt1 < sz1|| cnt2 < sz2)
    	{
    		if(cnt1 == sz1)
    			pos[idx[y][cnt2]] = ++c,cnt2++;
    		else if(cnt2 == sz2)
    			pos[idx[x][cnt1]] = ++c,cnt1++;
    		else{
    			if(idx[x][cnt1] < idx[y][cnt2])
    				pos[idx[x][cnt1]] = ++c,cnt1++;
    			else pos[idx[y][cnt2]] = ++c,cnt2++;
    		}
    	}
    	// cout<<"pos1 :";
    	// for(int i = 0;i<sz1;i++)
    	// 	cout<<pos[idx[x][i]]<<" ";
    	// cout<<"\n";
    	// cout<<"pos2 :";
    	// for(int i = 0;i<sz2;i++)
    	// 	cout<<pos[idx[y][i]]<<" ";
    	// cout<<"\n";
    	vector<ll>pre1(c+1),pre2(c+1);
    	
    	for(auto j:idx[x])
    		pre1[pos[j]]++;
    	for(auto j:idx[y])
    		pre2[pos[j]]++;
    	for(int i = 1; i <= c; i++)
    		pre1[i] += pre1[i-1],pre2[i] += pre2[i-1];
    	// for(int i = 1;i <= c;i++)
    	// 	cout<<pre1[i]<<" ";
    	// cout<<"\n";
    	// for(int i = 1;i <= c;i++)
    	// 	cout<<pre2[i]<<" ";
    	// cout<<"\n";
    	ll t = 0;
    	for(int i = 1;i <= c; i++)
    	{
    		t += (pre1[i]-pre1[i-1])-(pre2[i]-pre2[i-1]);
    		if(t<0)t = 0;
    		res = max(res,t + pre2[c]);
    	}
    }
    cout<<res<<"\n";
    
    return 0;
}

做法二：

考虑一个区间带来的影响：

对于一个区间原本的数是，现在变成了，原本是的数现在变成了。

如果选择是众数，那么对于这个所选区间内的贡献是,的贡献是。那么对于给定，我们只需要找出最大贡献区间即可。但是如果枚举每个然后再去扫一遍看贡献肯定超时了，那怎么办呢？当我们枚举到第个位置的时候，我们统计和产生的贡献，也就是说，我们一遍相当于枚举了全部的。

那么如何选区间呢？从开始一直去取，直到某个位置贡献小于0了，那就不要这段了，因为从这段负的继续加不会更优。所以我们把这段区间丢掉，从新开始计算贡献。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 4e6 + 10,M = 2e6;
vector<int>idx[N];
int ret[N],a[N],pre[N],cnt[N];

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n,k;
    cin>>n>>k;
    int ans = 0;
    for(int i = 1;i <= n; i++)
    {
        cin>>a[i];
        cnt[a[i]+M]++;
        ans = max(ans,cnt[a[i]+M]);
    }   
    if(k==0){
        cout<<ans<<"\n";
        return 0;
    }

    for(int i = 1;i <= n; i++)
    {
        ret[a[i]+M]--;
        if(ret[a[i]+M]<0)ret[a[i]+M] = 0;
        ret[a[i]+k+M]++;
        ans = max(ans,cnt[a[i]+k+M]+ret[a[i]+k+M]);
    }
    cout<<ans<<"\n";
    return 0;
}

思想：边扫边统计答案，无需先确定区间再去算。

J. Xingqiu’s Joke

思路：对于同时和同时的操作，两数的差值的不变的。。

若且那么。

表示从得到的步数。我们去枚举的质因数。

而可以由和转移得到。我们去记忆化一下就可以写了。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ll int
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
vector<ll>d;
void div(ll x)
{
    for (ll i = 2; i <= x / i; i++)
    {
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0)
            {
                x = x / i;
                s++;
            }
            d.push_back(i);
        }
    }
    if (x > 1)d.push_back(x);
}
 
map<pair<ll,ll>,ll>dp;
 
ll dfs(ll a,ll c)
{
	if(a==1)return 0;
	if(c==1)return a-1;
	ll &res = dp[{a,c}];
	if(res)return res;
	res = a-1;
	for(auto g : d)
	{
		if(c % g == 0)
		{
			int left = a%g;
			ll t1 = left+1+dfs(a/g,c/g);
			ll t2 = (g-left)+1+dfs(a/g+1,c/g);
			res = min({res,t1,t2});
		}
	}
	return res;
 
}
 
 
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
 
     	ll a,b;
     	cin>>a>>b;
     	d.clear();
     	dp.clear();
     	if(a>b)swap(a,b);
     	ll c = abs(a-b);
     	div(c);
     	// for(auto g : d)
     	// 	cout<<g<<" ";
     	// cout<<"\n";
     	cout<<dfs(a,c)<<"\n";
    }
 
    return 0;
}

M. Windblume Festival

思路：分类讨论。

  1. 有正有负。用负数一直减正数。最后用正数减负数这样最优。结果是
  2. 全正。先变出一个负数之后，变成第一种情况。
  3. 全负。先变出一个正数之后，变成第一种情况。

因为不知道变哪个，需要一遍。

注意：特判的情况。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
ll a[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int cntn = 0,cntp = 0;
        ll sum = 0;
        for(int i = 0;i < n; i++)
        {
           cin>>a[i];
           sum += abs(a[i]);
           if(a[i]<0)cntn++;
           else if(a[i]>0)cntp++;
        }
        if(n==1)
        {
            cout<<a[0]<<"\n";
            continue;
        }
        ll ans = -1e18;
        if(cntn>0&&cntp>0)
        {
            ans = sum;
        }
        else if(cntn)
        {
            for(int i = 0;i < n; i++)
            {
                if(a[i]-a[(i+1)%n]>=0)
                    ans = max(ans,(a[i]-a[(i+1)%n])+sum+a[i]+a[(i+1)%n]);
            }
        }
        else if(cntp)
        {
            for(int i = 0;i < n; i++)
            {
                if(a[i]-a[(i+1)%n]<=0)
                   ans = max(ans,sum-(a[i]-a[(i+1)%n])-a[i]-a[(i+1)%n]);
            }
        }
        else ans = 0;
        cout<<ans<<"\n";
    }
    return 0;
}
  • Title: The 2021 ICPC 南京 ACJM
  • Author: Nannan
  • Created at : 2023-10-04 12:41:00
  • Updated at : 2024-09-30 17:05:12
  • Link: https://redefine.ohevan.com/2023/10/04/The 2021 ICPC Asia Nanjing Regional Contest (XXII Open Cup, Grand Prix of Nanjing)/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
The 2021 ICPC 南京 ACJM
  1. The 2021 ICPC Asia Nanjing Regional Contest (XXII Open Cup, Grand Prix of Nanjing)
    1. A.Oops, It’s Yesterday Twice More
    2. C. Klee in Solitary Confinement
    3. J. Xingqiu’s Joke
    4. M. Windblume Festival