A.Remainder
题意
给定$n$位的只包含$0$和$1$的数字串，通过操作可以把其中任意$0$变成$1$，$1$变成$0$。使用最少的操作数使得最后得到的数模$10^x$得到$10^y$。
方法
- 要是操作之后满足题述要求，则要求后$x$位数除了倒数第$y+1$位为$1$之外其他都为$0$。
- 具体操作为：判断区间$[n-y+1,n]$内$1$的个数，区间$[n-x+1,n-y-1]$内$1$的个数，以及区间$[n-y,n-y]$内$0$的个数。
- 代码如下：
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
| #include<bits/stdc++.h>
using namespace std;
const int maxn(1e5+5);
string s;
int T,n,x,y,ans;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>x>>y;
cin>>s;
for(int i=0;i<y;i++){
if(s[n-1-i]=='1'){
ans++;
}
}
if(s[n-1-y]=='0'){
ans++;
}
for(int i=y+1;i<x;i++){
if(s[n-1-i]=='1'){
ans++;
}
}
cout<<ans<<"\n";
}
|
B.Polycarp Training
题意
给出$n$个题集，第$i$个题集有$a_i$个问题，要训练$m$天，必须保证第$k$天至少做$k$道题，求最多可以训练多少天。
方法
- 先把所有题集按题数从小到大排序，遍历排序后的题集，能满足当天题数要求就做这一套，不能则找下一套。
- 坑点：每套题只能做一遍，比如一套题三道题，不能第一天做一道，第二天做这套题剩下的两道。
- 代码如下：
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;
const int maxn(2e5+5);
int n,a[maxn],ans,flag[maxn];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
int id=1;
while(id<=n){
if(a[id]>=ans+1){
ans++;
}
id++;
}
cout<<ans<<"\n";
}
|
C.Good String
题意
定义一个“好字符串”，它拥有偶数个字符，并且奇数位的字符与后一个字符不相等。给一个字符串，问删除几个字符可以把这个字符串变成“好字符串”。
方法
- 逐字符读入，如果此时结果字符串长度为偶数（包括0），则直接把当前字符加入结果字符串末尾，否则比较跟结果字符串末尾字符是否相等，相等则删除字符数+1，否则加入结果字符串末尾。
- 坑点：不要用getchar()读入字符！
- 代码如下：
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
| #include<bits/stdc++.h>
using namespace std;
const int maxn(2e5+5);
string s;
char tmp;
int n,ans;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=0;i<n;i++){
cin >> tmp;
if(s.size()%2==0){
s.append(&tmp);
}
else{
if(tmp==s[s.size()-1]){
ans++;
}
else{
s.append(&tmp);
}
}
}
if(s.size()%2){
s.pop_back();
ans++;
}
cout<<ans<<"\n"<<s<<"\n";
}
|
D.Almost All Divisors
题意
给定$n$个整数，表示某个数除了$1$和它本身之外的所有因数，输出这个数，如果这个数不存在，则输出$-1$。
方法
- 先将输入的因数排序，从头尾向中间遍历，头尾相乘即可得到原数，判断每次遍历得到的两个数的积是否相等（不相等则是$-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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn(305);
ll t,n,d[maxn],ans;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--){
cin>>n;
for(ll i=0;i<n;i++){
cin>>d[i];
}
sort(d,d+n);
if(n%2){
ans=d[n/2]*d[n/2];
}
else{
ans=d[n/2]*d[n/2-1];
}
for(ll i=0;i<n/2;i++){
if(d[i]*d[n-1-i]!=ans){
ans=-1;
break;
}
}
if(ans!=-1){
ll tmp=ll(sqrt(ans)),num=0;
if(tmp*tmp==ans){
num=1;
tmp--;
}
for(ll i=2;i<=tmp;i++){
if(ans%i==0){
num+=2;
}
}
if(num!=n){
ans=-1;
}
}
cout<<ans<<endl;
}
}
|
E.Two Arrays and Sum of Functions
题意
给定两个数组$a$，$b$，定义$f(l,r)=\sum_{l\leq i\leq r} a_i\cdot b_i$，求$\sum_{1\leq l\leq r\leq n} f(l,r)$的最小值。
方法
- 对于每个$a_i\cdot b_i$，从第i个位置分为前后两段，前面有$[1,i],[2,i]…[i,i]$共$i$个区间，后面有$[i,i],[i,i+1]…[i,n]$共$n-i+1$个区间，进行组合可得到$a_i\cdot b_i$被包含在$i(n-i+1)$个区间中，所以预处理时对$a_i$乘$i(n-i+1)$，然后在对处理后$a_i$从小到大排序，$b_i$从大到小排序，然后对应相乘累加即可。
- 注意：对$a_i$做预处理时不要取模。
- 代码如下：
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
| #include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll maxn(2e5+5);
const ll mod(998244353);
ll n,a[maxn],b[maxn],ans;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(ll i=0;i<n;i++){
cin>>a[i];
a[i]=(a[i]*(1+i)*(n-i));
}
for(ll i=0;i<n;i++){
cin>>b[i];
}
sort(a,a+n,greater<ll>());
sort(b,b+n,less<ll>());
for(ll i=0;i<n;i++){
ans=(ans+a[i]%mod*b[i]%mod)%mod;
}
cout<<ans<<"\n";
}
|
F.Microtransactions
题意
给定$n$种商品每种商品的需求量，还有一些商品在某些天会打折，打折的时候购买需要花费$1$元，否则要$2$元，每天会获得一块钱，请问至少需要多少天可以把需要的商品买完。
方法
- 这题我本来是想要暴力模拟做的，但实在是想不到好的策略，只想到了越后面买越好，但就是不知道从后往前做，最后还是屈服了去看题解
- 二分做法，假设总共需要$x$件商品，不管怎么样需要的天数一定处于$[x,2x]$之间，所以在这个区间内二分，判断$d(x\leq d\leq 2x)$天能不能买完需要的商品，从后往前遍历，需要注意的是，不要使用未来的钱，即某天没有花钱的时候，到前一天之前还是要减掉一块钱。
- 代码如下：
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn(2e5+5);
ll order[maxn],n,m,ans,ordered[maxn],total,buy;
vector<ll> v[maxn<<1];
bool check(ll money){
buy=0;
ll left=0;
for(ll i=1;i<=n;i++){
ordered[i]=order[i];
}
for(ll i=money;i>0;i--){
for(ll j=0;j<v[i].size();j++){
if(ordered[v[i][j]]&&money){
ll tmp=min(ordered[v[i][j]],money);
ordered[v[i][j]]-=tmp;
money-=tmp;
buy+=tmp;
}
}
if(money>=i){
left++;
money--;
}
}
return left/2>=total-buy;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(ll i=1;i<=n;i++){
cin>>order[i];
total+=order[i];
}
for(ll i=0;i<m;i++){
ll tmp_d,tmp_t;
cin>>tmp_d>>tmp_t;
v[tmp_d].push_back(tmp_t);
}
ll l=total,r=total*2,mid;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
cout<<ans<<"\n";
}
|
return 0;
本文链接：
https://luojinrong.github.io/2019/05/23/Round-560-Div-3/
