The 2022 ICPC网络赛第二场ABEFJ

Nannan Lv5
  2023-08-21 23:50 2023-08-21 23:50 Created   2024-09-30 17:39 2024-09-30 17:39 Updated      

The 2022 ICPC Asia Regionals Online Contest (II).md

A Yet Another Remainder

题意：给你一个正整数，但是这个数被隐藏起来了。你问了电脑个问题，第轮，的第个问题：，让，,你将得到的值。之后有个询问，给你一个质数，你回答这个隐藏的整数的值是多少？

思路：首先，看问题描述我们发现几个有趣的事情：

  1. 询问的是以内的质数，但唯独不包含和，是为什么？
  2. 题目中告诉你的都是每种步长的和，为什么要告诉我这个？和它的和有什么关系？

对于第一个事情，不包含和，说明询问的p是和是互质的。

对于第二个事情，根据第一个想法，我们考虑，把一个数可以拆成以下形式：

举个例子：比如数,可以拆成：$910^8+910^7+810^6+210^5+…+3*10^0$

然后我们又发现，根据费马小定理知：如果互质有：，所以每是一个循环节。

比如以模数为为例,因为和互质，所以有，即,设，那么。也就是是一个循环节，这里的话就是。

在的意义下都是等于的，而在的意义下都等于….以此类推。

$(a[1]*10^0 + a[7]*10^6+a[13]10^{12}+…)\mod 7 = 1(a[1]+a[7]+a[13]+…)$

$(a[2]*10^1 + a[8]*10^7+a[14]10^{13}+…) \mod 7 = 3(a[2]+a[8]+a[14]+…)$

到这里，我们发现了，题目告诉我们每个步长个数的加和是为什么了。那么下面就是做法：对于模数,我们的答案在行获取(因为步长是，我们想要知道每隔个的加和)。行的第列的加和就是相等的值前面的系数了。用表示：的值是多少(预处理),用表示：步长为的第组数的和(题目输入)。对于模数是的答案就是：。

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 110;
ll c[N][N],b[N][N];
void init()
{
	for(int i = 1;i<=100;i++)
	{	
		c[i][0] = 1;
		for(int j = 1;j<=i;j++)
		{	
			c[i][j] = c[i][j-1]*10%i;
		}
	}
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
  
    int t;
    cin>>t;
    init();
    while(t--)
    {
    	int n;
    	cin>>n;
    	for(int i = 1;i <= min(n,100);i++)
    	{
    		for(int j = 1;j<=i;j++)
    		{
    			cin>>b[i][j];
    		}
    	}

    	if(n<=100)
    	{	
    		
    		int q;
    		cin>>q;
    		while(q--)
    		{
    			int p;
    			cin>>p;
    			ll ans = 0;
	    		for(int i = 1;i<=n;i++)
	    		{
	    			ans *= 10;
	    			ans%=p;
	    			ans += b[n][i];
	    			ans %= p;
	    		}
    			cout<<ans%p<<"\n";
    		}
    	}
    	else{
    		int q;
	    	cin>>q;
	    	while(q--)
	    	{
	    		int p;
	    		cin>>p;
	    		ll ans = 0;
	    		for(int i = 1;i<=p-1;i++)
	    		{
	    			ans += b[p-1][i]%p*c[p][(n-i)%(p-1)];
	    			ans%=p;
	    		}
	    		cout<<ans<<"\n";
	    	}
    	}
    }

    return 0;
}

B Non-decreasing Array

题意：给你一个不降序列，在一次操作：第一步你可以选择一个数删了或者什么也不做。第二步你可以选择一个数把它改成任意整数。

每次操作你都需要保证序列是单调不减的，你有次操作，当当前长度是的时候，贡献是。问操作次的最大值。

思路：一次操作有步：删一个数或者不删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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 110;
ll n;
ll a[N];
ll dp[N][N];
ll dfs(int idx,int k)
{
	ll &res = dp[idx][k];
	if(dp[idx][k]!=-1)return res;
	res = 0;
	for(int i = 1;i<idx;i++)
	{
		//i+1,idx-1
		int cnt = k-((idx-1)-(i+1)+1);
		if(cnt<0)continue;
		res = max(res,dfs(i,cnt)+(a[idx]-a[i])*(a[idx]-a[i]));
	}
	return res;
}

int main()
{
	cin>>n;
	for(int i = 1;i <= n; i++)
		cin>>a[i];
	memset(dp,-1,sizeof(dp));
	for(int i = 1;i <= n; i++)
	{
		int k = i*2;
		if(n-k-2<=0)cout<<(a[n]-a[1])*(a[n]-a[1])<<"\n";
		else cout<<dfs(n,k)<<"\n";
	}
	return 0;
}
/*
5
1 2 3 4 5
*/

E An Interesting Sequence

题意：给你一个，告诉你数列总长度是，让你去构造，保证，求的最小值。

思路：对于是偶数(因为不一定和偶数互质)，考虑找到与互质的第一个奇数质数，然后后面构造

对于是奇数，直接构造即可（奇数一定和互质）。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
const int N =1000010;
bool is_pri[N];
int pri[N];
int cnt;

void init(int n)
{
	memset(is_pri, true, sizeof(is_pri));
	is_pri[1] = false;
	cnt = 0;
	for (int i = 2; i <= n; i++)
	{
		if (is_pri[i])
			pri[++cnt] = i;
		for (int j = 1; j <= cnt && i * pri[j] <= n; j++)
		{
			is_pri[i * pri[j]] = false;
			if (i % pri[j] == 0)break;            
		}
	}
}

int main()
{
	init(20);
	cin>>n>>k;
	ll ans = k;
	if(k%2==0)
	{
		for(int i = 1;i<=cnt;i++)
		{
			if(pri[i]%2)
			{
				if(k%pri[i]!=0)
				{
					ans += pri[i];
					break;
				}
			}
		}
		int m = n-2;
		ans += m/2*5+(m%2)*2;
	}
	else
	{
		int m = n-1;
		ans += m/2*5+(m%2)*2;
	}
	cout<<ans<<endl;
	return 0;
}

F Infinity Tree

题意：一开始你有个节点，每秒每个节点产生个孩子。即第秒的节点个数是个。

对于一个节点，它产生的孩子是。

给你两个节点，问他们的是谁。

思路：考虑对于一个孩子，它的父亲是谁？根据题目给的公式反推得到父亲

那么我们先预处理出来每秒的节点个数，去找产生节点个数小于的最后一个，那就是它父亲那一轮的节点个数，这样可以推出它的父亲。考虑的怎么求？每次跳节点编号大的那个就行。注意，父亲不一定是孩子的上一秒产生的，所以不能单纯的用孩子的秒数-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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
inline __int128 read(){__int128 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*10+ch-'0';ch=getchar();}return x*f;}
inline void write(__int128 x){if (x < 0){putchar('-');x = -x;}if (x > 9) write(x / 10);putchar(x % 10 + '0');}
typedef __int128 ll;
ll k,x,y;
ll p[N];
ll now;
ll pre_gx,pre_gy;
void init(ll x)
{

	p[0] = 1;
	now = 1;
	if(x==1)return;
	while(1)
	{
		p[now] = p[now-1]*(k+1);
		if(p[now]>x)break;
		now++;
	}
}

ll lca(ll x,ll y)
{
	
	while(x!=y)
	{
		if(x==1||y==1)return 1;
		if(x>y)
		{
			x = (x-p[pre_gx])/k+((x-p[pre_gx])%k != 0);
			ll t = pre_gx;
			for(int i = t - 1;i>=0;i--)
				if(p[i]<x){
					pre_gx = i;
					break;
				}			

		}
		else if(y>x)
		{
			y = (y-p[pre_gy])/k+((y-p[pre_gy])%k != 0);
			ll t = pre_gy;
			for(int i = t - 1;i>=0;i--)
				if(p[i]<y){
					pre_gy = i;
					break;
				}
		}

	}
	return x;
}


int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		k = read(),x = read(),y = read();
		init(max(x,y));
		
		for(int i = 0;i<=now;i++)
			if(p[i]>x)break;
			else pre_gx = i;
		for(int i = 0;i<=now;i++)
			if(p[i]>y)break;
			else pre_gy = i;
	
		write(lca(x,y));
		cout<<"\n";
	}
	return 0;
}
/*
1
2 100000000000000000 1000000000000000
*/

J A Game about Increasing Sequences

题意：在玩游戏，每次每人选一个数，要求比上一个人选的大，而且只能从两端选取，第一个选不了了的人输。是先手，是后手，问谁赢。

思路：因为每次要选比上一个大的，那么选出来的数列一定是单增的。考虑能选多少次，如果前缀和后缀能选的次数都是偶数赢，否则。因为只要可下次数是奇数，那必赢，反之。可能你会有疑惑，那我如果某个人选了某一边而导致另一边不能选了的情况，会不会改变奇偶性呢？

举个实际的例子吧:

可能你会疑惑第一次选了左边和右边结果会不会不一样？

对应选法就是：(奇数个) (偶数个)

因为都是最优策略，以为例，如果要自己赢，那么最后一步一定是下的，是奇数步数。如果按照只下左边，那么肯定是奇数步，那如果改了，他去下右边了，那也不会影响，右边是偶数个，左边下了奇数步，那总的还是奇数步，仍为赢。

所以综上所述，只有两边都是偶数才是赢。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int n,k;
int a[N];
int pre,suf;
int main()
{
	cin>>n;
	for(int i = 1;i<=n;i++)
		cin>>a[i];
	for(int i = 1;i<=n;i++)
	{
		if(a[i]>a[i-1])
			pre++;
		else break;
	}
	for(int i = n;i>=1;i--)
	{
		if(a[i]>a[i+1])
			suf++;
		else break;
	}
	if(pre%2==0&&suf%2==0)cout<<"Bob\n";
	else cout<<"Alice\n";
	return 0;
}
  • Title: The 2022 ICPC网络赛第二场ABEFJ
  • Author: Nannan
  • Created at : 2023-08-21 23:50:00
  • Updated at : 2024-09-30 17:39:00
  • Link: https://redefine.ohevan.com/2023/08/21/The 2022 ICPC Asia Regionals Online Contest (II)/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
The 2022 ICPC网络赛第二场ABEFJ
  1. The 2022 ICPC Asia Regionals Online Contest (II).md
    1. A Yet Another Remainder
    2. B Non-decreasing Array
    3. E An Interesting Sequence
    4. F Infinity Tree
    5. J A Game about Increasing Sequences