本文章由 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;
}
鲁ICP备2025150228号