A. Road To Zero
题意
两个操作：操作1：花费a元使某个数加1或减1
操作2：花费b元使两个数都加1或减1
问使两个数都变为0的最小花费
思路
因为不知道a，b的大小，需要考虑所有情况，比较得出最小值
Code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+5;
ll t,x,y,a,b;
int main(){
cin>>t;
while(t--){
cin>>x>>y>>a>>b;
if(x>y) swap(x,y);
ll ans=0,ans1=0;
ans1=(abs(x)+abs(y))*a;
ll x1=min(abs(x),abs(y));//考虑了x，y小于0的情况，此题可以不用绝对值
ll y1=max(abs(x),abs(y));
if(x*y>0){
ans=x1*b+(y1-x1)*a;
}
else {
ans=x1*b+(x1+y1)*a;
}
cout<<min(ans,ans1)<<"
";
}
return 0;
}
B. Binary Period
题意
给出t字符串，找出s字符串，t是s的子序列，并且s的周期最小
思路
由于s由'0','1'组成，所以s周期最多为2
code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+5;
int n;
string t;
int main(){
cin>>n;
while(n--){
cin>>t;
string s="";
int flag1=0,flag2=0,flag=0;
for(int i=0;i<t.length();i++){
if(t[i]=='0') flag++,flag1++;
else if(t[i]=='1') flag++,flag2++;
}
if(flag1>0&&flag2>0){
if(t[0]=='0'){
for(int i=0;i<flag1+flag2;i++){
s+="01";
}
}
else {
for(int i=0;i<flag1+flag2;i++){
s+="10";
}
}
}
else s=t;
cout<<s<<'
';
}
return 0;
}
C. Yet Another Counting Problem
题意
在[l,r]中找到x%a%b!=x%b%a的个数
思路
打表可以发现以lcm(a,b)为周期,使x%a%b= =x%b%a的数是lcm(a,b)~lcm(a,b)+max(a,b)-1,然后在每个周期将这些数减掉即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,m,a,b,q,l,r;
ll solve(ll x,ll mx,ll lcm)
{
if(x%lcm>=mx) return x/lcm*(lcm-mx)+(x%lcm)-mx+1;
else
{
return x/lcm*(lcm-mx);
}
}
int main(){
cin>>t;
while(t--){
cin>>a>>b>>q;
ll mx=max(a,b),lcm=a*b/__gcd(a,b);
while(q--)
{
cin>>l>>r;
cout<<solve(r,mx,lcm)-solve(l-1,mx,lcm)<<'
';
}
}
return 0;
}
D. Multiple Testcases
题意
将一些测试的数组重新分配在一些测试样例中，每个新的测试样例中大于等于i的数组数目必须小于等于c[i]
解题思路
方法1：先将m数组排序，res数组统计每个样例中放入数组的数目，将m数组中的元素从大到小放入vector,x表示第一个小于c[m[i]]的数，
方法2：另一种方法，找到最大分组数，然后将数组分别加入最大分组数即可(来自https://www.cnblogs.com/stelayuri/p/12785409.html)
Code：
//方法1代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
ll m[N],c[N],res[N],n,k;
vector<ll>ve[N];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>m[i];
for(int i=1;i<=k;i++) cin>>c[i];
sort(m+1,m+n+1);
ll ans=1;
for(int i=n;i;i--){//res表示重新分配的样例中数组数量的负值
int x=upper_bound(res+1,res+ans+1,-c[m[i]])-res;
if(x<=ans){
ve[x].push_back(m[i]);
res[x]--;
}
else ve[++ans].push_back(m[i]),res[x]--;
}
cout<<ans<<'
';
for(int i=1;i<=ans;i++){
cout<<ve[i].size();
for(int j=0;j<ve[i].size();j++){
cout<<' '<<ve[i][j];
}
cout<<'
';
}
return 0;
}
//方法2代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
ll m[N],c[N],res[N],n,k;
vector<ll>ve[N];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>m[i];
res[m[i]]++;
}
for(int i=1;i<=k;i++) cin>>c[i];
sort(m+1,m+n+1);
ll q=1;
for(int i=k;i;i--){
res[i]+=res[i+1];//表示大于等于i的数字数量
ll tmp=ceil(1.0*res[i]/c[i]);
q=max(q,tmp);//最大分组数
}
for(int i=1;i<=n;i++){
ve[i%q].push_back(m[i]);
}
cout<<q<<'
';
for(int i=0;i<q;i++)
{
cout<<ve[i].size();
for(auto it:ve[i])
cout<<' '<<it;
cout<<'
';
}
return 0;
}