本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}