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]='#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);
}
';
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);
}
