题目链接
Educational Codeforces Round 70 (Rated for Div. 2)
A
题解
找到第二个字符串的最后一个1，让他能够与第一个字符串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
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
string s,s1;
cin>>s>>s1;
if(s1[s1.size()-1]=='1'&&s[s.size()-1]=='1')
{
printf("0\n");
continue;
}
int pos1;
for(int i=0;i<s1.size();i++)
{
if(s1[i]=='1')pos1=s1.size()-i;
}
for(int i=s.size()-pos1;i>=0;i--)
{
if(s[i]=='1')
{
printf("%d\n",s.size()-pos1-i);
break;
}
}
}
}
|
B
思路
首先读懂题目的意思之后，对于每一种类的计算机，我们可以用floyd求出他的距离，也就是从i-j需要插入多少个数，然后再匹配字符串就好了
代码实现
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
| #include<bits/stdc++.h>
using namespace std;
long long dp[11][11];
long long ans[11][11];
int n;
string s;
void floyd(int x,int y)
{
memset(dp,0x3f,sizeof(dp));
for(int i =0;i<10;i++)
{
dp[i][(i+x)%10]=1;
dp[i][(i+y)%10]=1;
}
for(int k=0;k<100;k++)
{
for(int i=0;i<10;i++)
{
for(int j=0;j<10;j++)
{
dp[i][(j+x)%10]=min(dp[i][j]+1,dp[i][(j+x)%10]);
dp[i][(j+y)%10]=min(dp[i][j]+1,dp[i][(j+y)%10]);
}
}
}
}
long long solve()
{
long long res = 0;
for(int i=0;i<n-1;i++)
{
if(dp[s[i]-'0'][s[i+1]-'0']-1>1e17)return -1;
res +=dp[s[i]-'0'][s[i+1]-'0']-1;
}
if(res>1e17)return -1;
return res;
}
int main()
{
cin>>s;
n=s.size();
for(int i=0;i<10;i++)
{
for(int j=0;j<=i;j++)
{
floyd(i,j);
ans[i][j]=solve();
ans[j][i]=ans[i][j];
}
}
for(int i=0;i<10;i++)
{
for(int j=0;j<10;j++)
{
printf("%d ",ans[i][j]);
}
printf("\n");
}
}
|
D
思路
首先两个3能够为我们提供一个组合数C_{n}^{2},然后我们可以找出至少几个3，然后缺的一部分我们可以在后面补上1即可.
总体的形式就是先构建1(3~)(1~)337这样的话n就被分成两部分，第一部分(3~)可以用C_{n}^{2}来表示，第二部分就是n-C_{n}^{2}.
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ll n,len3;
scanf("%I64d",&n);
for(len3=2;len3*(len3-1)/2<=n;)len3++;
len3--;
ll len1 = n-len3*(len3-1)/2;
printf("1");
for(ll i=1;i<=len3-2;i++)printf("3");
for(ll i=1;i<=len1;i++)printf("1");
printf("337\n");
}
}
|