A. Required Remainder
题意：
T
T
T组询问，给定
x
,
y
,
n
(
2
≤
x
≤
1
0
9
;
0
≤
y
<
x
;
y
≤
n
≤
1
0
9
)
x,y,n (2≤x≤10^9; 0≤y<x; y≤n≤10^9)
x,y,n(2≤x≤109;0≤y<x;y≤n≤109),求最大的整数
k
k
k，满足
0
≤
k
≤
n
且
k
m
o
d
x
=
y
0≤k≤n且k mod x=y
0≤k≤n且kmodx=y
思路：
转换公式
k
=
k
1
∗
x
+
y
，
k
1
∈
R
k=k1*x+y，k1∈R
k=k1∗x+y，k1∈R ，则需要找到最大的
k
1
k1
k1，使得
k
1
∗
x
+
y
<
=
n
k1*x+y<=n
k1∗x+y<=n，则
k
1
m
a
x
=
(
n
−
y
)
/
x
k1_{max}=(n-y)/x
k1max=(n−y)/x，套入第一个式子即可。
Code:
int main(){
int t
;
t
=read();
while(t
--){
ll x
,y
,n
;
scanll3(x
,y
,n
);
printf("%lld\n",(n
-y
)/x
*x
+y
);
}
return 0;
}
B. Multiply by 2, divide by 6
题意：
T
T
T组询问，给定一个
n
,
1
≤
n
≤
1
0
9
n,1≤n≤10^9
n,1≤n≤109，每次操作将
n
n
n乘
6
6
6（能被
6
6
6整除），或者将
n
n
n乘
2
2
2。问最少多少次操作可以将
n
n
n变换乘
1
1
1。否则输出
−
1
-1
−1。
思路：
暴力+贪心，当前能除
6
6
6就除，否则乘2，
−
1
-1
−1的情况在暴力的情况下设置上界是不会超时的。然而正确的解法是数学，这里不做描述。
Code:
int main(){
int t
;
t
=read();
while(t
--){
ll n
;
n
=read();
int f
=0;
if(n
==1){
puts("0");
continue;
}
int cnt
=0;
while(n
!=1&&n
<=1e9){
if(n
%6==0){
n
/=6;
cnt
++;
}
else {
n
*=2;
cnt
++;
}
}
if(n
!=1)puts("-1");
else printf("%d\n",cnt
);
}
return 0;
}
C. Move Brackets
题意：
T
T
T组询问，每组给定一个长度为
n
n
n的括号字符串，一个括号字符串合法定义如下：
"
(
)
"
"()"
"()" is regular bracket sequence;if
s
s
s regular bracket sequence then
"
(
"
+
s
+
"
)
"
"(" + s+")"
"("+s+")" is regular bracket sequence;if
s
s
s and
t
t
t are regular bracket sequences then
s
s
s +
t
t
t is regular bracket sequence.
每次移动可以将一个括号移动至头部或者尾部，问最少多少次移动使得给定字符串合法。输入满足，
n
n
n是偶数，有
n
2
\frac{n}{2}
2n个
)
)
)，
n
2
\frac{n}{2}
2n个
(
(
(。
思路：
先做括号匹配，考虑需要移动的情况，需要移动的字符串一定是
)
)
)
.
.
.
(
(
(
)))...(((
)))...(((的形式，那么做法就很显然了，正常做括号匹配，需要移动的次数就是最后栈大小的一半。
Code:
int main(){
int t
;
t
=read();
while(t
--){
ll n
;
n
=read();
stack
<char>Q
;
string s
;
cin
>>s
;
rep(i
,0,n
-1){
if(Q
.empty()){
Q
.push(s
[i
]);
continue;
}
char tp
=Q
.top();
if(s
[i
]==')'&&tp
=='('){
Q
.pop();
continue;
}
Q
.push(s
[i
]);
}
cout
<<Q
.size()/2<<"\n";
}
return 0;
}
D. Zero Remainder Array
题意：
给一个长度为
n
n
n的数组
a
a
a，起初，有一个整数
x
=
0
x=0
x=0，每一次操作可以选择将数组中的一个数
a
i
，
a
i
=
a
i
+
x
a_i，a_i=ai+x
ai，ai=ai+x，随后
x
=
x
+
1
x=x+1
x=x+1，或者只执行
x
=
x
+
1
x=x+1
x=x+1，问需要最少多少次操作使数组
a
a
a中的数都能整除
k
k
k。
思路：
可以看出，每个数
a
i
a_i
ai需要加上某个
x
i
x_i
xi，才能被
k
k
k整除。前
k
k
k次操作，可以使得那些只出现了一次
x
i
x_i
xi的全部与之对应的
a
i
a_i
ai变为
k
k
k的倍数，前
2
k
2k
2k次操作，可以使得那些只出现了两次
x
i
x_i
xi的全部与之对应的
a
i
a_i
ai变为
k
k
k的倍数…
预处理出每个数
a
i
a_i
ai需要的
x
i
x_i
xi，当
x
i
x_i
xi相同的个数为
c
n
t
x
i
cnt_{x_i}
cntxi时，需要执行到
x
i
+
(
c
n
t
x
i
−
1
)
k
x_i+(cnt_{x_i}-1)k
xi+(cntxi−1)k次… 所以答案就是，维护出最大的
(
c
n
t
x
i
−
1
)
(cnt_{x_i}-1)
(cntxi−1)，表示要执行多少次
k
k
k，再维护出最大的
x
i
x_i
xi，需要再执行
x
i
x_i
xi次，最后再加
1
1
1即可(
0
0
0开始的第一步）。
ps:个人写的比较复杂，仅供参考。
Code:
ll q
[N
];
map
<ll
,ll
>mp
;
int main(){
int t
;
t
=read();
while(t
--){
ll n
;
n
=read();
ll k
;
k
=read();
ll maxxy
=-3e18;
ll maxxz
=-3e18;
int f
=0;
rep(i
,1,n
){
q
[i
]=read();
ll y
=((k
-q
[i
])%k
+k
)%k
;
if(y
==0){
continue;
}
f
=1;
if(mp
[y
]==0){
mp
[y
]++;
}
else{
mp
[y
+k
*mp
[y
]]=mp
[y
]+1;
mp
[y
]++;
}
}
if(f
==0){
puts("0");
mp
.clear();
continue;
}
for(auto it
: mp
){
maxxz
=max(maxxz
,it
.second
);
}
for(auto it
: mp
){
if(it
.second
==maxxz
)
maxxy
=max(maxxy
,((it
.first
)%k
));
}
printf("%lld\n",(maxxz
-1ll)*k
+maxxy
+1ll);
mp
.clear();
}
return 0;
}
E1. Reading Books (easy version)
题意：
给定
n
n
n本书，每本书有
3
3
3个属性，分别表示
t
,
a
,
b
t,a,b
t,a,b,读这本数需要的时间，是否被Alice喜欢，是否被Bob喜欢。 两人必须一起读书，必须同时有书在手上。找出一种方案，使得Alice和Bob都至少读
k
k
k本书，问最少的读书时间。
思路：
这题偏向理解，赛时没注意到不会出现一人没书读的情况，疯狂WA5，最后自闭。
首先对于两者都不喜欢的书，可以直接忽略。考虑贪心，将其他三种书分类排序（从小到大）。
两者都喜欢的书所需最短时间
≤
≤
≤A喜欢的书的最短时间+B喜欢的书的最短时间，选两者都喜欢的最少时间的。两者都喜欢的书所需最短时间
>
>
>A喜欢的书的最短时间+B喜欢的书的最短时间，选一本A喜欢的最少时间的，一本B喜欢的最少时间的。A喜欢的书已经取完了或者B喜欢的书已经取完了，则只能选一本两者都喜欢的书。
如果觉得数组模拟困难可以考虑multiset或者优先队列queue维护。
Code:
ll q
[N
];
ll a
[N
];
ll b
[N
];
ll t
[N
];
multiset
<ll
>s1
,s2
,s3
;
multiset
<ll
>::iterator it
;
int main(){
int n
;
n
=read();
int k
;
k
=read();
int cnt
=0;
rep(i
,1,n
){
scanll3(t
[i
],a
[i
],b
[i
]);
if(a
[i
]==0&&b
[i
]==1){
s3
.insert(t
[i
]);
cnt
++;
}
if(a
[i
]==1&&b
[i
]==1){
s2
.insert(t
[i
]);
cnt
+=2;
}
if(a
[i
]==1&&b
[i
]==0){
s1
.insert(t
[i
]);
cnt
++;
}
}
int con
=0;
ll ans
=0;
int cnt1
,cnt2
;
cnt1
=cnt2
=0;
while(1){
long long it1
,it2
,it3
;
it1
=it2
=it3
=0;
if(s1
.size()!=0)it1
=*(s1
.begin());
if(s2
.size()!=0)it2
=*(s2
.begin());
if(s3
.size()!=0)it3
=*(s3
.begin());
if(cnt1
>=k
&&cnt2
>=k
)break;
if(s1
.size()==0&&s2
.size()==0&&s3
.size()==0)break;
if((it1
==0||it3
==0)&&it2
==0)break;
if(it1
+it3
<it2
&&it1
!=0&&it2
!=0&&it3
!=0){
if(it1
!=0)cnt1
++;
if(it3
!=0)cnt2
++;
ans
+=it1
+it3
;
it
=s1
.find(it1
);
s1
.erase(it
);
it
=s3
.find(it3
);
s3
.erase(it
);
}
else if(it1
+it3
>=it2
&&it1
!=0&&it2
!=0&&it3
!=0){
cnt1
++;
cnt2
++;
ans
+=it2
;
it
=s2
.find(it2
);
s2
.erase(it
);
}
else if(it1
==0&&it3
==0&&it2
!=0){
cnt1
++;
cnt2
++;
ans
+=it2
;
it
=s2
.find(it2
);
s2
.erase(it
);
}
else if(it1
!=0&&it3
!=0&&it2
==0){
cnt1
++;
cnt2
++;
ans
+=it1
+it3
;
it
=s1
.find(it1
);
s1
.erase(it
);
it
=s3
.find(it3
);
s3
.erase(it
);
}
else if(it1
!=0&&it3
==0&&it2
!=0){
cnt1
++;
cnt2
++;
ans
+=it2
;
it
=s2
.find(it2
);
s2
.erase(it
);
}
else if(it1
==0&&it3
!=0&&it2
!=0){
cnt1
++;
cnt2
++;
ans
+=it2
;
it
=s2
.find(it2
);
s2
.erase(it
);
}
}
if(cnt1
<k
||cnt2
<k
){
cout
<<"-1";
return 0;
}
cout
<<ans
;
return 0;
}
小坑点：
值得一提的是，multiset中的erase(x)，如果x是元素值，会将多个x全部删去，而不是只删去一个。正确的做法，是先find(x)找到迭代器再erase即可。 此题使用优先队列会更为方便。如果用multiset必须注意如上小坑点，否则你会因此不断WA5…
其他题待补
