总览
A题
题意一览
样例一览
你知道的，gcd(x,y)是求x和y的最大公约数，题目要求使gcd(x,y)+y的值最大，那我们就别废话，直接写个gcd逐个比较过去，A题是这样的，你只需要莽，考虑太多反而写不对。
代码如下(感谢友人pofvvvv提供代码，我的思路复杂了)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <iostream>
using namespace std;
int gcd(int a,int b)
{
if(a%b==0)return b;
return gcd(b,a%b);
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t,num,max=0,tmp=0;
cin>>t;
while(t--){
cin>>num;
for(int i=1;i<num;i++)
if(gcd(num,i)+i>max){
tmp=i;
}
cout<<tmp<<"\n";
}
}
|
B题
题意一览
样例一览
题目很简单，我也不多加解释，直接开两个下标ta,tb同时遍历a,b，我们要求是否存在b的子序列与a的前k项匹配，就从a的第一项开始逐项匹配，如果在b中可以找到对应字符，那答案也就是ta更新,如果在某一项时tb将b遍历完了也没能找到相同的字符，那就结束循环，答案就是ta
继续上友人代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t,la,lb,l;
cin>>t;
while(t--){
l=0;
string a="",b="";
cin>>la>>lb>>a>>b;
int ta=0,tb=0;
while(ta<la&&tb<lb){
if(a[ta]==b[tb]){
l++;
ta++;
tb++;
}
else
tb++;
}
cout<<l<<"\n";
}
}
|
C题
题意一览
样例一览
这题，怎么说呢，从样例可以看出来第一个数应该是第一个余数加一，然后由此推出来后面，刚开始我看样例，觉得这不对吧，这跟全部加起来有什么区别，然后我真这么写了，第二项开始就是上一项加对应余数，喜提这个
当时我就瞪大了眼睛，布什哥们，然后发现错在第五个样例，样例答案是2 7 5，我是2 3 8。刚开始我还没意识到哪里不对，然后发现8%3=2，不是5，这时我就豁然开朗，如果我构造的数足够大，大到每次加完之后新的数和上一个数差不多，就构不成一倍以上的差距，这时候取余就是想要的那个数了
代码如下
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
| #include"bits/stdc++.h"
using namespace std;
#define ll long long
#define NO cout<<"NO"<<endl
#define YES cout<<"YES"<<endl
#define mxint (1<<30)-1
ll c[200050],d[200050];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n-1;i++)
cin>>c[i];
d[1]=c[1]+1;
d[2]=d[1]*1111-1;
for(int i=3;i<=n;i++){
d[i]=d[i-1]+c[i-1];
}
for(int i=1;i<=n;i++)
cout<<d[i]<<" ";
cout<<endl;
}
return 0;
}
|
D题
题意一览
样例一览
感觉没有应有的强度，一眼贪心，只需要跳到他们得分最大的地方就是最优解，刚开始我以为每个点都能去，结果发现这两个人可能死都不会见面，只会在自己地盘打转，我们可以用dfs或者map加for循环把两个人能去到的点都给搜出来，然后就逐个点比较得分最大值，完事
上代码
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
| #include"bits/stdc++.h"
using namespace std;
#define ll long long
#define NO cout<<"NO"<<endl
#define YES cout<<"YES"<<endl
#define mxint (1<<30)-1
ll c[200050],d[200050];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
ll mx=-1;
int sum=0;
int n,k,x1,x2;
ll ans1=0,ans2=0;
cin>>n>>k>>x1>>x2;
for(int i=1;i<=n;i++)
cin>>c[i];
for(int i=1;i<=n;i++)
cin>>d[i];
if(d[x1]==mx)
ans1=mx*k;
else{
ll ans=0;
vector<int> dz;
map<int,int> ds;
while(1){
if(!ds[x1])
ds[x1]++;
else
break;
dz.push_back(x1);
x1=c[x1];
}
for(int i=0;i<min((int)dz.size(),k);i++){
ans+=d[dz[i]];
ans1=max(ans1,ans+(k-1-i)*d[dz[i]]);
}
}
if(d[x2]==mx)
ans2=mx*k;
else{
ll ans=0;
vector<int> dz;
map<int,int> ds;
dz.clear();
ds.clear();
while(1){
if(!ds[x2])
ds[x2]++;
else
break;
dz.push_back(x2);
x2=c[x2];
}
for(int i=0;i<min((int)dz.size(),k);i++){
ans+=d[dz[i]];
ans2=max(ans2,ans+(k-1-i)*d[dz[i]]);
}
}
if(ans1>ans2)
cout<<"Bodya"<<endl;
else if(ans1<ans2)
cout<<"Sasha"<<endl;
else cout<<"Draw"<<endl;
}
return 0;
}
|
结束
润
