Codeforces Round #653 (Div. 3)
这一场比赛比较简单水 ，但是我还是实力不够，做出的不多而且后几次提交经常WR。
A. Required Remainder time limit per test1 second memory limit per
test256 megabytes inputstandard input outputstandard output You are
given three integers x,y and n. Your task is to find the maximum
integer k such that 0≤k≤n that kmodx=y, where mod is modulo operation.
Many programming languages use percent operator % to implement it.In other words, with given x,y and n you need to find the maximum
possible integer from 0 to n that has the remainder y modulo x.You have to answer t independent test cases. It is guaranteed that
such k exists for each test case.Input The first line of the input contains one integer t (1≤t≤5⋅104) —
the number of test cases. The next t lines contain test cases.The only line of the test case contains three integers x,y and n
(2≤x≤109; 0≤y<x; y≤n≤109).It can be shown that such k always exists under the given constraints.
Output For each test case, print the answer — maximum non-negative
integer k such that 0≤k≤n and kmodx=y. It is guaranteed that the
answer always exists.Example inputCopy 7 7 5 12345 5 0 4 10 5 15 17 8 54321 499999993 9
1000000000 10 5 187 2 0 999999999 outputCopy 12339 0 15 54306
999999995 185 999999998 Note In the first test case of the example,
the answer is 12339=7⋅1762+5 (thus, 12339mod7=5). It is obvious that
there is no greater integer not exceeding 12345 which has the
remainder 5 modulo 7.
#include <iostream>
#include <algorithm>
#include <cmath>
#include<cstring>
#include <vector>
#include <map>
using namespace std;
#define ll long long
inline bool bigger(long long x, long long y)
{
return x > y;
}
inline bool smalonglonger(long long x, long long y)
{
return x < y;
}
long long judgebpri(long long x, long long y)
{
return y == 0 ? x : judgebpri(y, x % y);
}
void initvectorlonglong(vector<long long> &a, long long n)
{
for (long long i = 0; i < n; i++)
{
long long t;
cin >> t;
a.push_back(t);
}
}
void showlonglong(vector<long long> &a, long long beg, long long enl)
{
auto it = a.begin() + beg;
auto its = a.begin() + enl;
for (it; it < its; it++)
cout << *it << ' ';
cout << endl;
}
long long binfind(long long x,vector<long long>&a)
{
long long l=0,r=a.size()-1;
while(l<=r)
{
long long mid=(l+r)>>1;
if(a[mid]>x)r=mid-1;
else l=mid+1;
}
return l-1;
} //返回第一个小于
int main()
{
int x,y,n;
int t;
cin>>t;
while(t--)
{
cin>>x>>y>>n;
int g=n%x;
if(g!=y)
if(g>y)n-=(g-y);
else n-=(x-y+g);
cout<<n<<endl;
}
}
B. Multiply by 2, divide by 6 time limit per test1 second memory limit
per test256 megabytes inputstandard input outputstandard output You
are given an integer n. In one move, you can either multiply n by two
or divide n by 6 (if it is divisible by 6 without the remainder).Your task is to find the minimum number of moves needed to obtain 1
from n or determine if it’s impossible to do that.You have to answer t independent test cases.
Input The first line of the input contains one integer t (1≤t≤2⋅104) —
the number of test cases. Then t test cases follow.The only line of the test case contains one integer n (1≤n≤109).
Output For each test case, print the answer — the minimum number of
moves needed to obtain 1 from n if it’s possible to do that or -1 if
it’s impossible to obtain 1 from n.Example inputCopy 7 1 2 3 12 12345 15116544 387420489 outputCopy 0
-1 2
-1
-1 12 36 Note Consider the sixth test case of the example. The answer can be obtained by the following sequence of moves from the given
integer 15116544:Divide by 6 and get 2519424; divide by 6 and get 419904; divide by 6
and get 69984; divide by 6 and get 11664; multiply by 2 and get 23328;
divide by 6 and get 3888; divide by 6 and get 648; divide by 6 and get
108; multiply by 2 and get 216; divide by 6 and get 36; divide by 6
and get 6; divide by 6 and get 1.
注意2，3因子的个数。
#include <iostream>
#include <algorithm>
#include <cmath>
#include<cstring>
#include <vector>
#include <map>
using namespace std;
#define ll long long
inline bool bigger(long long x, long long y)
{
return x > y;
}
inline bool smalonglonger(long long x, long long y)
{
return x < y;
}
long long judgebpri(long long x, long long y)
{
return y == 0 ? x : judgebpri(y, x % y);
}
void initvectorlonglong(vector<long long> &a, long long n)
{
for (long long i = 0; i < n; i++)
{
long long t;
cin >> t;
a.push_back(t);
}
}
void showlonglong(vector<long long> &a, long long beg, long long enl)
{
auto it = a.begin() + beg;
auto its = a.begin() + enl;
for (it; it < its; it++)
cout << *it << ' ';
cout << endl;
}
long long binfind(long long x,vector<long long>&a)
{
long long l=0,r=a.size()-1;
while(l<=r)
{
long long mid=(l+r)>>1;
if(a[mid]>x)r=mid-1;
else l=mid+1;
}
return l-1;
} //返回第一个小于
int main()
{
int t;
cin>>t;
while(t--)
{
int x;
cin>>x;
int two=0,three=0;
if(x==1){cout<<0<<endl;continue;}
while(x%2==0){two++;x/=2;}
while(x%3==0){three++;x/=3;}
if(three==0||two>three||x!=1){
cout<<-1<<endl;continue;
}
cout<<abs(three-two)+three<<endl;
}
}
C. Move Brackets time limit per test1 second memory limit per test256
megabytes inputstandard input outputstandard output You are given a
bracket sequence s of length n, where n is even (divisible by two).
The string s consists of n2 opening brackets ‘(’ and n2 closing
brackets ‘)’.In one move, you can choose exactly one bracket and move it to the
beginning of the string or to the end of the string (i.e. you choose
some index i, remove the i-th character of s and insert it before or
after all remaining characters of s).Your task is to find the minimum number of moves required to obtain
regular bracket sequence from s. It can be proved that the answer
always exists under the given constraints.Recall what the regular bracket sequence is:
“()” is regular bracket sequence; if s is regular bracket sequence
then “(” + s + “)” is regular bracket sequence; if s and t are regular
bracket sequences then s + t is regular bracket sequence. For example,
“()()”, “(())()”, “(())” and “()” are regular bracket sequences, but
“)(”, “()(” and “)))” are not.You have to answer t independent test cases.
Input The first line of the input contains one integer t (1≤t≤2000) —
the number of test cases. Then t test cases follow.The first line of the test case contains one integer n (2≤n≤50) — the
length of s. It is guaranteed that n is even. The second line of the
test case containg the string s consisting of n2 opening and n2
closing brackets.Output For each test case, print the answer — the minimum number of
moves required to obtain regular bracket sequence from s. It can be
proved that the answer always exists under the given constraints.Example inputCopy 4 2 )( 4 ()() 8 ())()()( 10 )))((((()) outputCopy 1
0 1 3 Note In the first test case of the example, it is sufficient to
move the first bracket to the end of the string.In the third test case of the example, it is sufficient to move the
last bracket to the beginning of the string.In the fourth test case of the example, we can choose last three
openning brackets, move them to the beginning of the string and obtain
“((()))(())”.
简单的栈操作
#include <iostream>
#include <algorithm>
#include <cmath>
#include<stack>
#include<cstring>
#include <vector>
#include <map>
using namespace std;
#define ll long long
inline bool bigger(long long x, long long y)
{
return x > y;
}
inline bool smalonglonger(long long x, long long y)
{
return x < y;
}
long long judgebpri(long long x, long long y)
{
return y == 0 ? x : judgebpri(y, x % y);
}
void initvectorlonglong(vector<long long> &a, long long n)
{
for (long long i = 0; i < n; i++)
{
long long t;
cin >> t;
a.push_back(t);
}
}
void showlonglong(vector<long long> &a, long long beg, long long enl)
{
auto it = a.begin() + beg;
auto its = a.begin() + enl;
for (it; it < its; it++)
cout << *it << ' ';
cout << endl;
}
long long binfind(long long x,vector<long long>&a)
{
long long l=0,r=a.size()-1;
while(l<=r)
{
long long mid=(l+r)>>1;
if(a[mid]>x)r=mid-1;
else l=mid+1;
}
return l-1;
} //返回第一个小于
int main()
{
int t;
cin>>t;
while(t--)
{ stack<char>str;
int len;
cin>>len;
for(int i=1;i<=len;i++)
{
char ee;
cin>>ee;
if(str.empty())
{
str.push(ee);
}
else {
if(str.top()=='('&&ee==')')
str.pop();
else str.push(ee);
}
}
cout<<str.size()/2<<endl;
}
}
D. Zero Remainder Array time limit per test2 seconds memory limit per
test256 megabytes inputstandard input outputstandard output You are
given an array a consisting of n positive integers.Initially, you have an integer x=0. During one move, you can do one of
the following two operations:Choose exactly one i from 1 to n and increase ai by x (ai:=ai+x), then
increase x by 1 (x:=x+1). Just increase x by 1 (x:=x+1). The first
operation can be applied no more than once to each i from 1 to n.Your task is to find the minimum number of moves required to obtain
such an array that each its element is divisible by k (the value k is
given).You have to answer t independent test cases.
Input The first line of the input contains one integer t (1≤t≤2⋅104) —
the number of test cases. Then t test cases follow.The first line of the test case contains two integers n and k
(1≤n≤2⋅105;1≤k≤109) — the length of a and the required divisior. The
second line of the test case contains n integers a1,a2,…,an
(1≤ai≤109), where ai is the i-th element of a.It is guaranteed that the sum of n does not exceed 2⋅105 (∑n≤2⋅105).
Output For each test case, print the answer — the minimum number of
moves required to obtain such an array that each its element is
divisible by k.Example inputCopy 5 4 3 1 2 1 3 10 6 8 7 1 8 3 7 5 10 8 9 5 10 20 100
50 20 100500 10 25 24 24 24 24 24 24 24 24 24 24 8 8 1 2 3 4 5 6 7 8
outputCopy 6 18 0 227 8 Note Consider the first test case of the
example:x=0, a=[1,2,1,3]. Just increase x; x=1, a=[1,2,1,3]. Add x to the
second element and increase x; x=2, a=[1,3,1,3]. Add x to the third
element and increase x; x=3, a=[1,3,3,3]. Add x to the fourth element
and increase x; x=4, a=[1,3,3,6]. Just increase x; x=5, a=[1,3,3,6].
Add x to the first element and increase x; x=6, a=[6,3,3,6]. We
obtained the required array. Note that you can’t add x to the same
element more than once.
找重复余数最多的一项
#include <iostream>
#include <algorithm>
#include <cmath>
#include<stack>
#include<cstring>
#include <vector>
#include <map>
using namespace std;
#define ll long long
inline bool bigger(long long x, long long y)
{
return x > y;
}
inline bool smalonglonger(long long x, long long y)
{
return x < y;
}
long long judgebpri(long long x, long long y)
{
return y == 0 ? x : judgebpri(y, x % y);
}
void initvectorlonglong(vector<long long> &a, long long n)
{
for (long long i = 0; i < n; i++)
{
long long t;
cin >> t;
a.push_back(t);
}
}
void showlonglong(vector<long long> &a, long long beg, long long enl)
{
auto it = a.begin() + beg;
auto its = a.begin() + enl;
for (it; it < its; it++)
cout << *it << ' ';
cout << endl;
}
long long binfind(long long x,vector<long long>&a)
{
long long l=0,r=a.size()-1;
while(l<=r)
{
long long mid=(l+r)>>1;
if(a[mid]>x)r=mid-1;
else l=mid+1;
}
return l-1;
} //返回第一个小于
int main()
{
ll t;
cin>>t;
while(t--)
{
map<ll,ll>xx;
ll n,k;
cin>>n>>k;
for(ll i=1;i<=n;i++)
{
ll j;
cin>>j;
xx[j%k]++;
}
ll maxx=0;
ll index=0;
map<ll,ll>::iterator is=xx.begin();
for(;is!=xx.end();is++)
if(maxx<is->second&&is->first)
{
maxx=is->second;
index=is->first;
}
if(maxx==0&&index==0){
cout<<0<<endl;continue;
}
cout<<k*(maxx-1)+(k-index)+1<<endl;
}
}
E1. Reading Books (easy version) time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output
Easy and hard versions are actually different problems, so read
statements of both problems completely and carefully.Summer vacation has started so Alice and Bob want to play and joy,
but… Their mom doesn’t think so. She says that they have to read
some amount of books before all entertainments. Alice and Bob will
read each book together to end this exercise faster.There are n books in the family library. The i-th book is described by
three integers: ti — the amount of time Alice and Bob need to spend to
read it, ai (equals 1 if Alice likes the i-th book and 0 if not), and
bi (equals 1 if Bob likes the i-th book and 0 if not).So they need to choose some books from the given n books in such a way
that:Alice likes at least k books from the chosen set and Bob likes at
least k books from the chosen set; the total reading time of these
books is minimized (they are children and want to play and joy as soon
a possible). The set they choose is the same for both Alice an Bob
(it’s shared between them) and they read all books together, so the
total reading time is the sum of ti over all books that are in the
chosen set.Your task is to help them and find any suitable set of books or
determine that it is impossible to find such a set.Input The first line of the input contains two integers n and k
(1≤k≤n≤2⋅105).The next n lines contain descriptions of books, one description per
line: the i-th line contains three integers ti, ai and bi (1≤ti≤104,
0≤ai,bi≤1), where:ti — the amount of time required for reading the i-th book; ai equals
1 if Alice likes the i-th book and 0 otherwise; bi equals 1 if Bob
likes the i-th book and 0 otherwise. Output If there is no solution,
print only one integer -1. Otherwise print one integer T — the minimum
total reading time of the suitable set of books.Examples inputCopy 8 4 7 1 1 2 1 1 4 0 1 8 1 1 1 0 1 1 1 1 1 0 1 3 0 0
outputCopy 18 inputCopy 5 2 6 0 0 9 0 0 1 0 1 2 1 1 5 1 0 outputCopy 8
inputCopy 5 3 3 0 0 2 1 0 3 1 0 5 0 1 3 0 1 outputCopy
-1
现将都喜爱的书籍，单个喜爱的书籍从自小到大排序。
先找同两人喜爱相同的书籍时间与alice，bob单个喜爱的书籍时间之和相比较小的，然后如果都喜爱书籍有剩余，将剩余的书籍加入直到k个。如果Alice，bob单个喜爱的书有剩余，将两者的书籍计入,直到每个都到k个。
#include <iostream>
#include <algorithm>
#include <cmath>
#include<stack>
#include<cstring>
#include <vector>
#include <map>
using namespace std;
#define ll long long
void sortvector(vector<ll>&a)
{
sort(a.begin(),a.end());
}
int main()
{
ll n,k;
cin>>n>>k;
vector<ll>alice;
vector<ll>bob;
vector<ll>both;
for(ll i=1;i<=n;i++)
{
ll time,a,b;
cin>>time>>a>>b;
if(a==1&&b==1)both.push_back(time);
else if(a==1)alice.push_back(time);
else if(b==1)bob.push_back(time);
}
if(alice.size()+both.size()<k||bob.size()+both.size()<k){
cout<<-1<<endl;return 0;
}
sortvector(both);
sortvector(alice);
sortvector(bob);
ll numberk=min((ll)bob.size(),(ll)alice.size());
numberk=min(numberk,k);
numberk=min((ll)both.size(),numberk);
ll sum=0;
ll totalab=0,totalnum=0;
for(;totalnum!=numberk&&totalab!=numberk&&(totalab+totalnum!=k);)
{
if(bob[totalab]+alice[totalab]<both[totalnum]){
sum+=(bob[totalab]+alice[totalab]);totalab++;
}else{
sum+=both[totalnum];totalnum++;}
}
ll kk=k-totalab-totalnum;
ll retboth=min(kk,(ll)(both.size()-totalnum));
for(ll i=totalnum;i<retboth+totalnum;i++){
sum+=both[i];
}
ll ret=k-retboth-totalnum;
if(n==0&&k==0){
cout<<kk<<endl;
cout<<alice.size()<<' '<<bob.size()<<' '<<both.size()<<endl;
cout<<totalab<<' '<<totalnum<<endl;
cout<<retboth<<' '<<ret<<endl;
}
for(ll i=totalab;i<ret;i++)
sum+=(bob[i]+alice[i]);
cout<<sum<<endl;
}