题目链接
Codeforces Round #582 (Div. 3)
C
思路
注意到每个的贡献都是一个循环，打个表后，直接取贡献。
代码实现
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
int all[11];
int num[11];
int pre[10][11];
int presum[10][11];
void init()
{
for(int i=1;i<=9;i++)
{
int cnt = i;
int ccnt = 1;
while(cnt)
{
pre[i][ccnt++]=cnt;
cnt+=i;
cnt%=10;
}
num[i]=ccnt;
}
for(int i=1;i<=9;i++)
{
for(int j=2;j<11;j++)
{
pre[i][j]+=pre[i][j-1];
}
all[i]=pre[i][10];
}
}
int main()
{
int q;
scanf("%d",&q);
init();
while(q--)
{
ll l,r;
cin>>l>>r;
int num1=r%10;
long long ans = 0;
long long a = l/r;
if(a==0||num1==0)
{
printf("0\n");
continue;
}
a/=num[num1];
ans+=(a*all[num1]);
long long b =(l/r)%num[num1];
ans+=(pre[num1][b]);
cout<<ans<<endl;
}
}
|
D
思路
这道题其实要弄清楚复杂度，然后暴力就可以了，因为数据范围是2e5，所以就二进制而言，不超过20位。
所以，每个数字只能操作20次之内，这样的话，我们就能直接暴力处理问题了。
代码实现
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5+10;
vector<int>v[maxn];
int main()
{
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)
{
int x;
scanf("%d",&x);
int cnt = 0;
while(1)
{
v[x].push_back(cnt);
if(x==0)break;
cnt++;
x/=2;
}
}
int ans = 1e8;
for(int i=0;i<maxn;i++)
{
if(v[i].size()<k)continue;
sort(v[i].begin(),v[i].end());
int sum = 0;
for(int j=0;j<k;j++)
{
sum+=v[i][j];
}
ans=min(ans,sum);
}
cout<<ans<<endl;
}
|
E
思路
构造题，这题abc的全排列只有6种，并且题目只有两种禁止情况，所以我们列出全部的情况后就一定有符合条件的。
abc
acb
bca
bac
cab
cba
上面就是6种全排列，但是还有一种情况，就是若条件给出了ab,ac，那么a就只能放在最后面，那么就是bbccaa了，所以还要加上上述排列的n倍情况来考虑。
实际上，不会输出NO（感兴趣可以自己分类证明
代码实现
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;
vector<string>v;
int main()
{
string abc="abc";
int n;
scanf("%d",&n);
string s,t;
cin>>s>>t;
do
{ string cur;
for(int i=0;i<n;i++)cur+=abc;
v.push_back(cur);
v.push_back(string(n,abc[0])+string(n,abc[1])+string(n,abc[2]));
}while(next_permutation(abc.begin(),abc.end()));
for(auto ans : v)
{
if(ans.find(s)==ans.npos&&ans.find(t)==ans.npos)
{ cout<<"YES"<<endl;
cout<<ans<<endl;
return 0;
}
}
assert(false);
cout<<"NO"<<endl;
return 0;
}
|