9.27 每日三题-JZTXT

思路：快速幂

#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=1e3+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

double qsm(double a,int b){
    double res=(double)1;
    while(b){
        if(b&1)res*=a;
        b>>=1;
        a*=a;
    }
    return res;
}
void solve(){
    int n,t;cin>>n>>t;
    double ans,p=1.000000011;
    ans=(double)n*qsm(p,t);
    cout<<fixed<<setprecision(20)<<ans;
}
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

B - Load Balancing

思路：若sum能整除n，那么把所有数变为sum/n；否则，有sum%n个数变为sum/n+1，那么将大于sum/n+1的数变为sum/n+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=1e3+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;


void solve(){
    int s=0,n;cin>>n;
    vector<int>ve(n);
    for(int i=0;i<n;++i){
        cin>>ve[i];s+=ve[i];
    }
    int ans=0,b=0,a=s/n;
    if(s%n){
        b=s%n;
        sort(ve.begin(),ve.end());
        for(int i=n-1;i>=0;--i){
            if(b){
                ans+=abs(ve[i]-a-1);b--;
            }else ans+=abs(ve[i]-a);
        }
    }
    else{
        for(int i=0;i<n;++i){
            ans+=abs(ve[i]-a);
        }
    }
    cout<<ans/2;
}
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

C - The Union of k-Segments

思路：可以把每个区间的端点的位置以及是左/右端点统计起来，按位置前、左端点在前排序；sum统计经过的端点数，经过左端点sum++，右端点sum--，当sum=k时，无论是经过左还是右端点，都是一段有效区间答案的端点，都统计到答案里

#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=1e3+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

struct E{
    int st,op;//10
    bool operator<(const E&e)const{
        if(st==e.st)return op>e.op;
        return st<e.st;
    }
};
void solve(){
    int k,n;cin>>n>>k;
    vector<E>ve(2*n);
    for(int i=0,p=0;i<n;++i){
        cin>>ve[p].st>>ve[p+1].st;
        ve[p++].op=1,ve[p++].op=0;
    }
    sort(ve.begin(),ve.end());
    vector<int>ans;
    for(int i=0,s=0;i<2*n;++i){
        if(ve[i].op){
            s++;
            if(s==k)ans.push_back(ve[i].st);
        }else{
            if(s==k)ans.push_back(ve[i].st);
            s--;
        }
    }
    cout<<ans.size()/2<<'\n';
    for(int i=0;i<ans.size();i+=2){
        cout<<ans[i]<<' '<<ans[i+1]<<'\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