Codeforces Round #582 (Div. 3)

A. Chips Moving

time limit per test1 second memory limit per test256 megabytes

You are given 𝑛n chips on a number line. The 𝑖i-th chip is placed at the integer coordinate 𝑥𝑖xi. Some chips can have equal coordinates.

You can perform each of the two following types of moves any (possibly, zero) number of times on any chip:

  • Move the chip 𝑖i by 22 to the left or 22 to the right for free (i.e. replace the current coordinate 𝑥𝑖xi with 𝑥𝑖−2xi−2 or with 𝑥𝑖+2xi+2);
  • move the chip 𝑖i by 11 to the left or 11 to the right and pay one coin for this move (i.e. replace the current coordinate 𝑥𝑖xi with 𝑥𝑖−1xi−1 or with 𝑥𝑖+1xi+1).

Note that it’s allowed to move chips to any integer coordinate, including negative and zero.

Your task is to find the minimum total number of coins required to move all 𝑛n chips to the same coordinate (i.e. all 𝑥𝑖xi should be equal after some sequence of moves).Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤1001≤n≤100) — the number of chips.

The second line of the input contains 𝑛n integers 𝑥1,𝑥2,…,𝑥𝑛x1,x2,…,xn (1≤𝑥𝑖≤1091≤xi≤109), where 𝑥𝑖xi is the coordinate of the 𝑖i-th chip.Output

Print one integer — the minimum total number of coins required to move all 𝑛n chips to the same coordinate.

ExamplesinputCopy

3
1 2 3

outputCopy

1

inputCopy

5
2 2 2 3 3

outputCopy

2

Note

In the first example you need to move the first chip by 22 to the right and the second chip by 11 to the right or move the third chip by 22 to the left and the second chip by 11 to the left so the answer is 11.

In the second example you need to move two chips with coordinate 33 by 11 to the left so the answer is 22.

签到题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const ll INF=(ll)1e18+100;
int n,a[110];
int main(){
    scanf("%d",&n);
    ll ans=INF;
    rep(i,1,n) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    rep(i,1,n){
        ll tmp=0;
        rep(j,1,n) if(a[j]!=a[i]) tmp+=(abs(a[i]-a[j])%2);
        ans=min(ans,tmp);
    }
    printf("%lld\n",ans);
}


B. Bad Prices

time limit per test1 second memory limit per test256 megabytes

Polycarp analyzes the prices of the new berPhone. At his disposal are the prices for 𝑛n last days: 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an, where 𝑎𝑖ai is the price of berPhone on the day 𝑖i.

Polycarp considers the price on the day 𝑖i to be bad if later (that is, a day with a greater number) berPhone was sold at a lower price. For example, if 𝑛=6n=6 and 𝑎=[3,9,4,6,7,5]a=[3,9,4,6,7,5], then the number of days with a bad price is 33 — these are days 22 (𝑎2=9a2=9), 44 (𝑎4=6a4=6) and 55(𝑎5=7a5=7).

Print the number of days with a bad price.

You have to answer 𝑡t independent data sets.Input

The first line contains an integer 𝑡t (1≤𝑡≤100001≤t≤10000) — the number of sets of input data in the test. Input data sets must be processed independently, one after another.

Each input data set consists of two lines. The first line contains an integer 𝑛n (1≤𝑛≤1500001≤n≤150000) — the number of days. The second line contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤1061≤ai≤106), where 𝑎𝑖ai is the price on the 𝑖i-th day.

It is guaranteed that the sum of 𝑛n over all data sets in the test does not exceed 150000150000.Output

Print 𝑡t integers, the 𝑗j-th of which should be equal to the number of days with a bad price in the 𝑗j-th input data set.

ExampleinputCopy

5
6
3 9 4 6 7 5
1
1000000
2
2 1
10
31 41 59 26 53 58 97 93 23 84
7
3 2 1 2 3 4 5

outputCopy

3
0
1
8
2

模拟即可

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const ll INF=(ll)1e18+100;
int n,a[maxn];
void solve(){
    scanf("%d",&n);
    rep(i,1,n) scanf("%d",&a[i]);
    int minx=a[n],ans=0;
    dep(i,n,1){
        minx=min(minx,a[i]);
        if(a[i]>minx) ans++;
    }
    printf("%d\n",ans);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}


C. Book Reading

time limit per test1 second memory limit per test256 megabytes

Polycarp is reading a book consisting of 𝑛n pages numbered from 11 to 𝑛n. Every time he finishes the page with the number divisible by 𝑚m, he writes down the last digit of this page number. For example, if 𝑛=15n=15 and 𝑚=5m=5, pages divisible by 𝑚m are 5,10,155,10,15. Their last digits are 5,0,55,0,5 correspondingly, their sum is 1010.

Your task is to calculate the sum of all digits Polycarp has written down.

You have to answer 𝑞q independent queries.Input

The first line of the input contains one integer 𝑞q (1≤𝑞≤10001≤q≤1000) — the number of queries.

The following 𝑞q lines contain queries, one per line. Each query is given as two integers 𝑛n and 𝑚m (1≤𝑛,𝑚≤10161≤n,m≤1016) — the number of pages in the book and required divisor, respectively.Output

For each query print the answer for it — the sum of digits written down by Polycarp.

ExampleinputCopy

7
1 1
10 1
100 3
1024 14
998244353 1337
123 144
1234312817382646 13

outputCopy

1
45
153
294
3359835
0
427262129093995

推个公式就好了,容易知道循环节是10

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const ll INF=(ll)1e18+100;
ll n,m;
void solve(){
    scanf("%lld%lld",&n,&m);
    ll num=n/m,tmp;
    ll t1=num/10,t2=num%10;
    int la=m%10;
    if(la==0) tmp=0;
    else if(la==5) tmp=25;
    else if(la%2) tmp=45;
    else tmp=40;
    ll ans=tmp*t1,tt=la;
    rep(i,1,t2){
        ans+=tt;
        tt=(tt+la)%10;
    }
    printf("%lld\n",ans);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}


D2. Equalizing by Division (hard version)

time limit per test2 seconds memory limit per test256 megabytes

The only difference between easy and hard versions is the number of elements in the array.

You are given an array 𝑎a consisting of 𝑛n integers. In one move you can choose any 𝑎𝑖ai and divide it by 22 rounding down (in other words, in one move you can set 𝑎𝑖:=⌊𝑎𝑖2⌋ai:=⌊ai2⌋).

You can perform such an operation any (possibly, zero) number of times with any 𝑎𝑖ai.

Your task is to calculate the minimum possible number of operations required to obtain at least 𝑘k equal numbers in the array.

Don’t forget that it is possible to have 𝑎𝑖=0ai=0 after some operations, thus the answer always exists.Input

The first line of the input contains two integers 𝑛n and 𝑘k (1≤𝑘≤𝑛≤2⋅1051≤k≤n≤2⋅105) — the number of elements in the array and the number of equal numbers required.

The second line of the input contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤2⋅1051≤ai≤2⋅105), where 𝑎𝑖ai is the 𝑖i-th element of 𝑎a.Output

Print one integer — the minimum possible number of operations required to obtain at least 𝑘k equal numbers in the array.

ExamplesinputCopy

5 3
1 2 2 4 5

outputCopy

1

inputCopy

5 3
1 2 3 4 5

outputCopy

2

inputCopy

5 3
1 2 3 3 3

outputCopy

0

直接暴力找最大的就可以了,很暴力

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=(int)1e9+100;
int n,k,a[maxn],maxx=0;
vector<int> vec[maxn];
int main(){
    scanf("%d%d",&n,&k);
    rep(i,1,n){
        int x,t=0;scanf("%d",&x);
        maxx=max(maxx,x);
        while(x){
            vec[x].pb(t);
            x/=2;t++;
        }
    }
    int ans=INF;
    rep(i,1,maxx) if(vec[i].size()>=k){
        sort(vec[i].begin(),vec[i].end());
        ans=min(ans,accumulate(vec[i].begin(),vec[i].begin()+k,0));
    }
    printf("%d\n",ans);
}


E. Two Small Strings

time limit per test2 seconds memory limit per test256 megabytes

You are given two strings 𝑠s and 𝑡t both of length 22 and both consisting only of characters ‘a’, ‘b’ and ‘c’.

Possible examples of strings 𝑠s and 𝑡t: “ab”, “ca”, “bb”.

You have to find a string 𝑟𝑒𝑠res consisting of 3𝑛3n characters, 𝑛n characters should be ‘a’, 𝑛n characters should be ‘b’ and 𝑛n characters should be ‘c’ and 𝑠s and 𝑡t should not occur in 𝑟𝑒𝑠res as substrings.

A substring of a string is a contiguous subsequence of that string. So, the strings “ab”, “ac” and “cc” are substrings of the string “abacc”, but the strings “bc”, “aa” and “cb” are not substrings of the string “abacc”.

If there are multiple answers, you can print any of them.Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤1051≤n≤105) — the number of characters ‘a’, ‘b’ and ‘c’ in the resulting string.

The second line of the input contains one string 𝑠s of length 22 consisting of characters ‘a’, ‘b’ and ‘c’.

The third line of the input contains one string 𝑡t of length 22 consisting of characters ‘a’, ‘b’ and ‘c’.Output

If it is impossible to find the suitable string, print “NO” on the first line.

Otherwise print “YES” on the first line and string 𝑟𝑒𝑠res on the second line. 𝑟𝑒𝑠res should consist of 3𝑛3n characters, 𝑛n characters should be ‘a’, 𝑛n characters should be ‘b’ and 𝑛n characters should be ‘c’ and 𝑠s and 𝑡t should not occur in 𝑟𝑒𝑠res as substrings.

If there are multiple answers, you can print any of them.

ExamplesinputCopy

2
ab
bc

outputCopy

YES
acbbac

inputCopy

3
aa
bc

outputCopy

YES
cacbacbab

inputCopy

1
cb
ac

outputCopy

YES
abc

这道题的策略是,如果有一个串是aa或者bb或者cc形式的就不用考虑,如果两个都不是的话,那么比如第一个串是ab,那么在a和b中间插入一个c,这时候如果出现了与第二个串冲突的情况就换一下顺序,之后每个字母输出n次就好啦

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)3e5+100;
const int INF=(int)1e9+100;
int n;
string s[3];
int main(){
    scanf("%d",&n);
    cin>>s[1]>>s[2];
    int f1=0,f2=0;
    if(s[1][0]==s[1][1]) f1=1;
    if(s[2][0]==s[2][1]) f2=1;
    puts("YES");
    if(f1&&f2) rep(i,1,n) printf("abc");
    else if(f1){
        rep(i,0,2) if('a'+i!=s[2][0]&&'a'+i!=s[2][1]){
            rep(j,1,n) printf("%c%c%c",s[2][0],'a'+i,s[2][1]);
        }
    }
    else if(f2){
        rep(i,0,2) if('a'+i!=s[1][0]&&'a'+i!=s[1][1]){
            rep(j,1,n) printf("%c%c%c",s[1][0],'a'+i,s[1][1]);
        }
    }
    else{
        char res[10];
        rep(i,0,2) if('a'+i!=s[1][0]&&'a'+i!=s[1][1]){
            res[0]=s[1][0]; res[1]='a'+i; res[2]=s[1][1];
        }
        if(res[0]==s[2][0]&&res[1]==s[2][1]) swap(res[0],res[2]);
        if(res[1]==s[2][0]&&res[2]==s[2][1]) swap(res[0],res[2]);
        rep(j,1,n) printf("%c",res[0]);
        rep(j,1,n) printf("%c",res[1]);
        rep(j,1,n) printf("%c",res[2]);
    }
}

 


F. Unstable String Sort

time limit per test2 seconds memory limit per test256 megabytes

Authors have come up with the string 𝑠s consisting of 𝑛n lowercase Latin letters.

You are given two permutations of its indices (not necessary equal) 𝑝p and 𝑞q (both of length 𝑛n). Recall that the permutation is the array of length 𝑛n which contains each integer from 11 to 𝑛n exactly once.

For all 𝑖i from 11 to 𝑛−1n−1 the following properties hold: 𝑠[𝑝𝑖]≤𝑠[𝑝𝑖+1]s[pi]≤s[pi+1] and 𝑠[𝑞𝑖]≤𝑠[𝑞𝑖+1]s[qi]≤s[qi+1]. It means that if you will write down all characters of 𝑠s in order of permutation indices, the resulting string will be sorted in the non-decreasing order.

Your task is to restore any such string 𝑠s of length 𝑛n consisting of at least 𝑘k distinct lowercase Latin letters which suits the given permutations.

If there are multiple answers, you can print any of them.Input

The first line of the input contains two integers 𝑛n and 𝑘k (1≤𝑛≤2⋅105,1≤𝑘≤261≤n≤2⋅105,1≤k≤26) — the length of the string and the number of distinct characters required.

The second line of the input contains 𝑛n integers 𝑝1,𝑝2,…,𝑝𝑛p1,p2,…,pn (1≤𝑝𝑖≤𝑛1≤pi≤n, all 𝑝𝑖pi are distinct integers from 11 to 𝑛n) — the permutation 𝑝p.

The third line of the input contains 𝑛n integers 𝑞1,𝑞2,…,𝑞𝑛q1,q2,…,qn (1≤𝑞𝑖≤𝑛1≤qi≤n, all 𝑞𝑖qi are distinct integers from 11 to 𝑛n) — the permutation 𝑞q.Output

If it is impossible to find the suitable string, print “NO” on the first line.

Otherwise print “YES” on the first line and string 𝑠s on the second line. It should consist of 𝑛n lowercase Latin letters, contain at least 𝑘kdistinct characters and suit the given permutations.

If there are multiple answers, you can print any of them.

ExampleinputCopy

3 2
1 2 3
1 3 2

outputCopy

YES
abb

乍一看很像拓扑排序,但是其实不用这么复杂;
考虑一段子串,如果p1和p2中某一段的元素是完全相同的,那么显然对于这一段的下一个元素,我们构造的字母要变大1位

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int INF=(int)1e9+100;
char s[maxn];
int lim[maxn],p[maxn],n,m,k,c;
int main(){
    scanf("%d %d",&n,&k); c=1;
    for(int i=1;i<=n;++i){
        scanf("%d",&m); lim[m]=i;
    }
    for(int i=1;i<=n;++i) scanf("%d",&p[i]);
    m=1; s[n+1]='\0';
    for(int i=1;i<=n;++i){
        m=max(m,lim[p[i]]); s[p[i]]=c+'a'-1;
        if(i<n&&i==m&&c<k) c++; 
    }
    if(c<k) printf("NO\n");
    else printf("YES\n%s\n",s+1);
}

 


G. Path Queries

time limit per test3 seconds memory limit per test256 megabytes

You are given a weighted tree consisting of 𝑛n vertices. Recall that a tree is a connected graph without cycles. Vertices 𝑢𝑖ui and 𝑣𝑖vi are connected by an edge with weight 𝑤𝑖wi.

You are given 𝑚m queries. The 𝑖i-th query is given as an integer 𝑞𝑖qi. In this query you need to calculate the number of pairs of vertices (𝑢,𝑣)(u,v) (𝑢<𝑣u<v) such that the maximum weight of an edge on a simple path between 𝑢u and 𝑣v doesn’t exceed 𝑞𝑖qi.Input

The first line of the input contains two integers 𝑛n and 𝑚m (1≤𝑛,𝑚≤2⋅1051≤n,m≤2⋅105) — the number of vertices in the tree and the number of queries.

Each of the next 𝑛−1n−1 lines describes an edge of the tree. Edge 𝑖i is denoted by three integers 𝑢𝑖ui, 𝑣𝑖vi and 𝑤𝑖wi — the labels of vertices it connects (1≤𝑢𝑖,𝑣𝑖≤𝑛1≤ui,vi≤n, 𝑢𝑖≠𝑣𝑖ui≠vi) and the weight of the edge (1≤𝑤𝑖≤2⋅1051≤wi≤2⋅105). It is guaranteed that the given edges form a tree.

The last line of the input contains 𝑚m integers 𝑞1,𝑞2,…,𝑞𝑚q1,q2,…,qm (1≤𝑞𝑖≤2⋅1051≤qi≤2⋅105), where 𝑞𝑖qi is the maximum weight of an edge in the 𝑖i-th query.Output

Print 𝑚m integers — the answers to the queries. The 𝑖i-th value should be equal to the number of pairs of vertices (𝑢,𝑣)(u,v) (𝑢<𝑣u<v) such that the maximum weight of an edge on a simple path between 𝑢u and 𝑣v doesn’t exceed 𝑞𝑖qi.

Queries are numbered from 11 to 𝑚m in the order of the input.

ExamplesinputCopy

7 5
1 2 1
3 2 3
2 4 1
4 5 2
5 7 4
3 6 2
5 2 3 4 1

outputCopy

21 7 15 21 3 

inputCopy

1 2
1 2

outputCopy

0 0 

inputCopy

3 3
1 2 1
2 3 2
1 3 2

outputCopy

1 3 3 

Note

The picture shows the tree from the first example:

最小生成树模版题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=(int)1e9+100;
int n,m;
int pre[maxn],tot[maxn],Rank[maxn];
ll ans=0;
struct node{
    int u,v,w;
    bool operator<(const node &b)const{return w<b.w;}
}g[maxn];
struct que{
    int ww,id;
    ll ans;
    bool operator<(const que &b)const{return ww<b.ww;}
}q[maxn];
int cmp(que a,que b){return a.id<b.id;}
int find(int x){return x==pre[x]?x:pre[x]=find(pre[x]);}
void join(int x, int y){
    x=find(x);y=find(y);
    if(x==y) return;
    ans-=(1ll*tot[x]*(tot[x]-1))/2;
    ans-=(1ll*tot[y]*(tot[y]-1))/2;
    ans+=(1ll*(tot[x]+tot[y])*(tot[x]+tot[y]-1))/2;
    if(Rank[x]>Rank[y]){
        pre[y]=x;
        if(x!=y) tot[x]+=tot[y];
    }
    else{
        pre[x]=y;
        if(x!=y) tot[y]+=tot[x];
        if(Rank[x]==Rank[y]) Rank[y]++;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n-1) scanf("%d%d%d",&g[i].u,&g[i].v,&g[i].w);
    sort(g+1,g+n);
    rep(i,1,m) scanf("%d",&q[i].ww),q[i].id=i;
    sort(q+1,q+1+m);
    rep(i,1,n) pre[i]=i,tot[i]=1;
    int pt=1;
    rep(i,1,m){
        while(pt<n&&g[pt].w<=q[i].ww) join(g[pt].u,g[pt].v),pt++;
        q[i].ans=ans;
        //rep(j,1,n) if(pre[j]==j) q[i].ans+=(1ll*tot[j]*(tot[j]-1))/2;
    }
    sort(q+1,q+1+m,cmp);
    rep(i,1,m) printf("%lld ",q[i].ans);
}

 

发表评论,支持MarkDown语法