526互联

9.5 div.1

发布时间 2023-09-11 00:43:00作者: bible_w

C - Set or Decrease

思路：只有两个操作：1.ai减一 和 2.ai变aj，要让所有数总和变小且操作次数少，可以贪心的想：操作一的ai为最小的数，操作二的ai为最大的数，aj为最小的数；

那么将a排序后，枚举操作2的数量cnt，对应的可以求出在满足总和小于等于k的情况下需要操作一的最少数量，即（sum-k）/（cnt+1）（上取整），表示将大出k的部分平分给a1和进行操作2的数；

或者枚举操作2的数量后，二分求出最少的操作一的个数

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n,k;cin>>n>>k;
    vector<int>a(n+1),pre(n+1);
    for(int i=1;i<=n;++i)cin>>a[i];
    sort(a.begin()+1,a.end());
    for(int i=1;i<=n;++i)pre[i]=pre[i-1]+a[i];
    int ans=1e15;
    for(int i=0,sum,t;i<n;++i){
        sum=pre[n-i]+a[1]*i;
        t=i;
        if(sum>k)t+=(sum-k+i)/(i+1);
        ans=min(ans,t);
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
贪心
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n,k;cin>>n>>k;
    vector<int>a(n+1),pre(n+1);
    for(int i=1;i<=n;++i)cin>>a[i];
    sort(a.begin()+1,a.end());
    for(int i=1;i<=n;++i)pre[i]=pre[i-1]+a[i];
    int ans=1e15;
    auto check=[k,pre,a,n](int s,int c){
        int sum=pre[n-c]-a[1]+s*(c+1);
        return sum<=k;
    };
    for(int i=0;i<n;++i){
        int l=-1e9,r=1e9,mid,x;
        while(l<=r){
            mid=l+r>>1;
            if(check(mid,i))x=mid,l=mid+1;
            else r=mid-1;
        }
        ans=min(ans,i+max(0ll,a[1]-x));
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

G - Triangles on a Rectangle

思路：每条边至少两个点，三角形面积即为相邻最远的两个点的距离乘上高

Exact Change

思路：考虑到硬币个数要尽可能少，3的余数有0、1、2，对于所有数可以由1个1和1个2和若干个3构成；但对于4，可以为2+2和1+3；那么对于所有数，最多由1个1和2个2以及若干3构成；

枚举1和2的个数，求出构成任意数的最少硬币数量

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n;cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;++i)cin>>a[i];
    int ans=1e9;
    for(int x1=0;x1<=1;++x1)
        for(int x2=0;x2<=2;++x2){
            int t=0;
            for(int i=0,c;i<n;++i){
                c=1e9;
                for(int c1=0;c1<=x1;++c1)
                    for(int c2=0;c2<=x2;++c2){
                        int s=a[i]-c1-c2*2;
                        if(s>=0&&s%3==0)c=min(c,s/3);
                    }
                t=max(t,c);
            }
            ans=min(ans,t+x1+x2);
        }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

Replace the Numbers

思路：每个操作只与之前的操作有关，与之后的操作无关，倒叙处理每个操作即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

struct E{
    int t,x,y;
};
void solve(){
    int q;cin>>q;
    vector<E>ve;
    for(int i=0;i<q;++i){
        int t,x,y=0;cin>>t>>x;
        if(t==2)cin>>y;
        ve.push_back({t,x,y});
    }
    vector<int>f(N);
    for(int i=1;i<N;++i)f[i]=i;
    vector<int>ans;
    for(int i=q-1;i>=0;--i){
        if(ve[i].t==1)ans.push_back(f[ve[i].x]);
        else f[ve[i].x]=f[ve[i].y];
    }
    for(int i=ans.size()-1;i>=0;--i)cout<<ans[i]<<' ';
    return;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
View Code

 BA-String

 思路：每个'*'可换成0~k个'b'，对于m个连续的'*'可换成0~mk个'b'，一共mk+1种。

将串倒着计数，对于a****a***a**，每一段连续的'*'为s3、s2、s1；第一段有cnt1个，有kcnt1+1种，第二段有cnt2个，有（kcnt2+1）*（kcnt1+1）种，...

总共有（kcnt3+1）*（kcnt2+1）*（kcnt3+1）种，可以发现编号越大的s，'b'的数量越多整个串越大，类似于进制数，si表示cnti进制；由于是从0开始计数，x需要减一，求该进制数中的第x小：从后开始遍历s，该段有x%（kcnti+1）个'b'，且x=x/（kcnti+1）

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n,k,x;
    string s;
    cin>>n>>k>>x>>s;
    reverse(s.begin(),s.end());
    string ans;
    int cnt=0;
    x--;
    for(int i=0;i<n;++i){
        if(s[i]=='a'){
            int a=cnt*k+1,b=x%a;
            while(b--){
                ans.push_back('b');
            }ans.push_back('a');
            x/=a;
            cnt=0;
        }else cnt++;
    }
    int b=x%(cnt*k+1);
    while(b--){
        ans.push_back('b');
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code