论如何 AK 2024.5.4 Luogu Div.3

__vector__ · 2024-05-04 16:25:39 · 个人记录

AK 了，感觉比较偏于诈骗题。

T1

分类讨论原始时间为 6:00 ~ 23:59 和 0:00 ~ 5:59 就好了。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int T;
int h,m;
void print(int x){
    if(x<10){
        putchar('0');
    }
    printf("%d",x);
}
void solve(){
    scanf("%d:%d",&h,&m);
    if(h>=6&&h<=23){
        print(h);
        putchar(':');
        print(m);
        putchar(10);
    }else{
        h+=24;
        print(h);
        putchar(':');
        print(m);
        putchar(10);
    }
}
int main()
{
    T=1;
    while(T--){
        solve();
    }
    return 0;
}

T2

打表发现，随着 p 的增加，答案先降后升。
然后做完了。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int T;
pair<double,double> midnode(double x1,double y1,double x2,double y2,double p){
    // (x1,y1) 到 (x2,y2) 的到 p 位置的节点
    if(abs(x2-x1)<1e-10){
        // 竖线，不能再这样用
        return make_pair(x2,y1+(y2-y1)*p);
    }
    double k=(y2-y1)/(x2-x1);
    double b=y1-k*x1;
    double mid_x = x1+(x2-x1)*p;
    double mid_y = k*mid_x+b;
    return make_pair(mid_x,mid_y);
}
double dis(pair<double,double> u,pair<double,double> v){
    return sqrt((v.first-u.first)*(v.first-u.first)+(v.second-u.second)*(v.second-u.second));
}
double hl(double a,double b,double c){
    double _p=(a+b+c)/2.0;
    return sqrt(_p*(_p-a)*(_p-b)*(_p-c));
}
double calc(double x1,double y1,double x2,double y2,double x3,double y3,double p){
    auto f=midnode(x1,y1,x2,y2,p);
    auto d=midnode(x2,y2,x3,y3,p);
    auto e=midnode(x3,y3,x1,y1,p);
    double a=dis(f,d);
    double b=dis(d,e);
    double c=dis(e,f);
    return hl(a,b,c);
}
void solve(){
    double l,r,x1,y1,x2,y2,x3,y3;
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&l,&r,&x1,&y1,&x2,&y2,&x3,&y3);
    if(r<0.5){
        printf("%.10lf\n",calc(x1,y1,x2,y2,x3,y3,r));
    }else if(l>0.5){
        printf("%.10lf\n",calc(x1,y1,x2,y2,x3,y3,l));
    }else{
        printf("%.10lf\n",calc(x1,y1,x2,y2,x3,y3,0.5));
    }
}
int main()
{
    T=1;
    while(T--){
        solve();
    }
    return 0;
}

T3

• 如果有偶数个不同质因数，那么两个一组删掉，显然答案是 1。
• 否则，如果只有一个质因数，那么无法操作，答案是输入的数。
• 否则，有不同质因数的数量大于等于 3，且数量为奇数，那么考虑这样操作：选择两个因数，先将它们在接下来的操作中排除。然后，对于剩下的因数（显然是奇数个），两两一组消掉，最后只会剩下一个因数 p。
  然后从一开始选择的两个因数中选择一个，将其次数减一，并消掉 p。然后最后一次操作，将一开始选择的两个因数同时选择，消掉，最后答案是 1。
  但是，上述操作能实现的前提是至少有 1 个质因数的次数大于 1，否则答案是最小的质因数的值。

复杂度 O(\sqrt n)，瓶颈在于质因数分解。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
/*
case1：偶数个不同因数，那么答案是 1
case2：1 个不同因数，答案是这个因数
case3：>=3 个奇数个不同因数：  
那么考虑保留两个不同因数，剩下互相 pvp。  
这要求，有一个因数次数>=2
*/
int T;
int x;
void solve(){
    scanf("%d",&x);
    int oldx=x;
    vector<pii> div;
    int mxp=0,mndiv=1e9;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            int cnt=0;
            while(x%i==0){
                cnt++;
                x/=i;
            } 
            mndiv=min(mndiv,i);
            mxp=max(mxp,cnt); 
            div.emplace_back(make_pair(i,cnt));
           // printf("%d ^ %d\n",i,cnt);
        }
    }
    if(x>1){
        mndiv=min(mndiv,x);
        div.emplace_back(make_pair(x,1));
     //   printf("%d ^ %d\n",x,1);
    }
    if(div.size()%2==0){
        puts("1");
    }else{
        if(div.size()==1){
            printf("%d\n",oldx);
        }
        else if(mxp>1){
            puts("1");
        }else{
            printf("%d\n",mndiv);
        }
    }
}
int main()
{
    T=1;
    while(T--){
        solve();
    }
    return 0;
}

T4

有一个结论：如果数组总和大于等于 0，那么这个数组合法。
证明：

显然，设 p 为最小前缀和，s 为最大后缀和，那么如果 p+s \ge 0，那么序列合法。
如果 p \ge 0，那么显然，由于 tot \ge 0，序列合法。
现在探讨 p \lt 0 的情况。
假设 p = \sum\limits_{i=1}^{k} a_i ，设总和 tot = \sum a_i，那么显然 k+1 开头的后缀和是 x = tot - p，易得 x+p = tot \ge 0。

所以，只有 1,2 操作是有效的，排个序贪心就行，注意别删完。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int T;
const int maxn=1e5+5;
int n;
ll a[maxn];
ll p,q,r;
void solve(){
    scanf("%d",&n);
    scanf("%lld%lld%lld",&p,&q,&r);
    ll tot=0;
    FOR(i,1,n){
        scanf("%lld",&a[i]);
        tot+=a[i];
    }
    if(n==1){
        if(tot>=0){
            puts("0");
        }
        else printf("%lld\n",-tot*p);
        return;
    }
    if(tot>=0){
        puts("0");
    }else{
        int delcnt=0;
        sort(a+1,a+n+1);
        ll ans=0;
        FOR(i,1,n){
            if(a[i]<0){
                ll cha=min(-a[i],-tot);// 当前元素变成 0（或者，只要把 tot 变成 0）  需要增加多少次
                ll hf1=cha*p;// 把当前元素变成 0  的代价 1
                ll hf2=q;// 变成 0 的代价 2
                tot+=cha;
                if(delcnt==n-1){
                    ans+=hf1;
                }else{
                    ans+=min(hf1,hf2);
                    delcnt+=(hf2<hf1);
                }
            }
        }
        ans+=(-tot*p);
        printf("%lld\n",ans);
    }
}
int main()
{
    T=1;
    while(T--){
        solve();
    }
    return 0;
}