chtholly-daisuki的小屋

「器用贫乏」

0%

cf round1060 c1、c2题解

发表于 更新于 分类于 ， ，
两道涉及到很多细节上trick的数论题[c2补题]
c1在赛中碰到了很多细节上的bug, 磨了1h做出来的
c2补题：有几处trick思路不对、能力不够，死活想不出来，看题解思路恍然大悟

c1

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
#include<bits/stdc++.h>
using namespace std;
#define maxn 200010
#define MOD 998244353
#define ll long long
#define endl '\n'

int main() {
	int t;
	cin>>t;
	while(t--) {
		int n;
		cin>>n;
		vector<int> a(n+10),b(n+10);
		
		
		int maxx=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			maxx=max(maxx,a[i]);
		}
		//cout<<":"<<maxx<<endl;
		vector<bool> ex(maxx+100);
		for(int i=1;i<=n;i++) cin>>b[i];
		//cout<<"ans:";
		int cnteven=0,cntodd=0;
		bool flag1=false;
		//ex.clear();
		for(int i=1;i<=n;i++){
			if(ex[a[i]]==true && a[i]!=1){
				//cout<<a[i]<<":"<<ex[a[i]]<<endl;
				cout<<"0"<<endl;
				flag1=true;
				break;
			}
			ex[a[i]]=1;
			for(int j=2;j*j<=a[i];j++){
				if(a[i]%j==0){
					if(ex[j]){
						cout<<"0"<<endl;
						//cout<<"ans::::"<<j<<endl;
						flag1=true;
						break;
					}
					if(ex[a[i]/j]){
						cout<<"0"<<endl;
						flag1=true;
						break;
					}
					ex[a[i]/j]=true;
					ex[j]=true;
				}
			}
			if(flag1) break;
		}
		//cout<<"$@#$"<<e[2]<<endl;
		if(flag1) continue;
		bool flag2=false;
		for(int i=1;i<=n;i++){
			if(ex[a[i]+1]){
				cout<<"1"<<endl;
				flag2=true;
				break;
			}
			for(int j=2;j*j<=a[i]+1;j++){
				if((a[i]+1)%j==0){
					//cout<<"?"<<j<<endl;
					if(ex[j]){
						cout<<"1"<<endl;
						flag2=true;
						break;
					}
					if(ex[(a[i]+1)/j]){
						cout<<"1"<<endl;
						flag2=true;
						break;
					}
				}
			}
			if(flag2) break;
		}
		if(flag2) continue;
		cout<<"2"<<endl;
	}
	return 0;
}
/*
10
7
1 3 5 7 17 11 13
1 1 1 1 1 1 1
*/

c2

题目内容

题目链接

输入（Input）
得到两个由正整数组成的数组 和 ，两者长度均为 。你可以执行以下操作任意次数（也可以不执行）：

选择一个整数 （满足 ），将 的值增加 1。该操作的成本为 。

请确定使数组满足“存在两个整数 （满足 ）且 ”所需的最小总成本。

输入（Input）

每个测试包包含多组测试用例。第一行输入测试用例的数量 （满足 ）。后续内容为各测试用例的描述：

  • 每组测试用例的第一行输入一个整数 （满足 ），表示数组 的长度。

  • 每组测试用例的第二行输入 个整数 （满足 ）。

  • 每组测试用例的第三行输入 个整数 （满足 ）。

我的代码

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>
using namespace std;
#define maxn 200010
#define MOD 998244353
#define ll long long
#define endl '\n'
struct pr{
	int aa;
	int bb;
};
bool cmp(pr x,pr y){
	return x.bb<y.bb;
}
int main() {
	int t;
	cin>>t;
	while(t--) {
		ll ans=0x7ffffffff; 
		int n;
		cin>>n;
		vector<int> a(n+10),b(n+10);
		vector<int> all;
		int cnt=0;
		vector<pr> p(n+10);
		map<ll,ll> m;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			p[i].aa=a[i];
		}
		for(int i=1;i<=n;i++){
			cin>>b[i];
			p[i].bb=b[i];
		}
		//改0个--------------------------------------------- 
		for(int i=1;i<=n;i++){
			//cout<<"1";
			if( a[i]!=1 && m.find(a[i])!=m.end() ){
				//cout<<"2";
				ans=0;
				break;
			}
			m[a[i]]=1;
			//all[++cnt]=a[i];//vector的注意点 
			//cout<<"change"<<endl;
			for(int j=2;j*j<=a[i];j++){
				if(a[i]%j==0){
					if(m.find(j)!=m.end() || m.find(a[i]/j)!=m.end()){
						ans=0;
						break;
					}
					m[j]++;
					//all[++cnt]=j;
					m[a[i]/j]++;
					//all[++cnt]=a[i]/j;
				}
			}
			if(ans==0) break;
		}
		if(ans==0){
			//cout<<"---------";
			cout<<0<<endl;
			continue;
		}
		ans=0x7fffffff;
		//---改一个：a[i] => a[i]+1----------------------------------------
		for(int i=1;i<=n;i++){
			if( m.find(a[i]+1)!=m.end() ){
				ans=min(ans,(ll)b[i]);
				//cout<<"1ans c:"<<a[i]+1<<","<<b[i]<<"=>"<<ans<<endl;
			}
			for(int j=2;j*j<=a[i]+1;j++){
				if((a[i]+1)%j==0){
					if(m.find(j)!=m.end() || m.find((a[i]+1)/j)!=m.end()){
						ans=min(ans,(ll)b[i]);
						//cout<<"2ans c:"<<a[i]+1<<","<<b[i]<<"=>"<<ans<<endl; 
					}
				}
			}
			//if(ans==0) break;
		}
		//---改两个：a[i] => a[i]+1: b[1]+b[2]----------------------------------------
		m.clear();
		sort(p.begin()+1,p.begin()+n+1,cmp);
		//for(int i=1;i<=n;i++) cout<<p[i].bb<<":";
		//cout<<endl;
		int minn=0x7fffffff;
		//	cout<<ans<<endl;
		//	cout<<(ll)p[1].bb+p[2].bb<<endl;
		ans=min(ans,(ll)p[1].bb+p[2].bb);//改两个--------------------------
		//	cout<<cnt<<endl;
		//all[p[1].aa]=0;
		m.clear();
		for(int i=2;i<=n;i++){
			m[p[i].aa]=1;
			all.push_back(p[i].aa);
			for(int j=2;j*j<=p[i].aa;j++){
				if(p[i].aa%j==0){
					m[j]=1;
					all.push_back(j);
					m[p[i].aa/j]=1;
					all.push_back(p[i].aa/j);
				}
			}
		}
		for(int i=0;i<all.size();i++){
			if(all[i]==1) continue;
			//cout<<"all:"<<all[i]<<"#*"<<(all[i]-(p[1].aa%all[i]))*p[1].bb<<endl;
			ans=min(ans,(ll)(all[i]-(p[1].aa%all[i]))*p[1].bb);
		} 
		//cout<<"ans:";
		cout<<ans<<endl;
	}
	return 0;
}