本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-17 14:27:50

T14281 单栈排序

题意简述

给定一个栈和一个 n 的全排列作为入栈序列，试通过调整出栈次序，得到字典序最大的 出栈序列。

解法一

暴力枚举每次是入栈还是出栈，即穷举所有可能的出栈序列，从而得到字典序最大的出栈序列。 时间复杂度：$O(C(n))$，其中 $C(n)$ 为卡特兰数列的第 $n $项，期望得分 $40 $ 分。

解法二

使用各种神奇的贪心算法，求解字典序最大的出栈序列。由算法复杂度及正确性决定最后 得分。 期望得分 0−100 分。

解法三

依旧考虑贪心算法。要求字典序最大，故我们可以从 $n ... 1$ 贪心地试探每个数能否加入 出栈序列。 假设我们已经枚举到了 $i$，若栈顶元素比 $i$ 大，我们则可以弹出栈顶元素，将其加 入出栈序列，直到栈顶元素≤ i。 若 $i$ 未在栈中，我们则将入栈序列中在 $i$ 前面且未入栈的数入栈，并将 $i$ 加入出栈序列； 若 $i$ 在栈中且是栈顶元素，我们则将 $i$ 弹出栈，并加入出栈序列； 若 $i$ 已经在栈中且不是栈顶元素，则说明若将 $i$ 加入出栈序列，之前必然要把比 $i$ 小的数 弹出栈，我们不这样做，继续枚举 $i−1$。 注意由于涉及大规模文件处理，此题需要使用输入输出优化。 时间复杂度为$ O(n)$，期望得分 $100$ 分。

参考代码

#include <cstdio>
#include <cstdlib>
#include <iostream>
#define N 1111111
using namespace std;
int stack[N], a[N];
bool in_stack[N], is_print[N];
int getint()
{
	char ch;
	do
	{
		ch=getchar();
	}while (ch!='-'&&(ch<'0'||ch>'9'));
	int ans=0,f=0;
	if (ch=='-') f=1; else ans=ch-'0';
	while (isdigit(ch=getchar())) ans=ans*10+ch-'0';
	if (f) ans*=-1;
	return ans;
}


int main() {

	int n = getint();
	for (int i = 1; i <= n; i++) a[i] = getint();
	int top = 0, pos = 0;
	for (int i = n; i >= 1; i--) {
		if (is_print[i]) continue;
		if (in_stack[i] && stack[top] != i) continue;
		while (top > 0 && stack[top] > i) {
			int t = stack[top]; top--;
			in_stack[t] = false;
			is_print[t] = true;
			cout<<t<<" ";
		}
		while(!in_stack[i]) {
			stack[++top] = a[++pos];
			in_stack[a[pos]] = true;
		}
		top--;
		in_stack[i] = false;
		is_print[i] = true;
		cout<<i<<" ";;
	}
	while (top > 0) {
		int t = stack[top]; top--;
		cout<<t<<" ";
	}
	return 0;
}

T14211 勤劳的蜜蜂

题目分析

每只蜜蜂的时间为$x+y$, $x+y+z$,...$x+y+iz$,得到一个等差数列求和的公式。 $$ \sum_{i=0}^j(x+y+iz)\leq t\ z \times i^2 +(2x+2y+z) \times i -2t \leq 0

$$ 求出符合要求的最大整数 $j$。

得到完整的周期后，再计算不完整周期中有多少工作时间。

参考代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long

const int MAXN=100000+2;
int N;
ll Ans,l,a,t,x[MAXN],y[MAXN],z[MAXN];

double Calc(double x,double y,double z,double t){
    if(z==0) return floor(t\/(x+y));
       
    z\/=2;
    double a=z,b=x+y-z,c=-t;
    double d=b*b-4*a*c;
    return floor((-b+sqrt(d))\/(2*a));
}

int main(){
    cin >> N >> t;
    for(int i=1;i<=N;i++) scanf("%lld %lld %lld",x+i,y+i,z+i);
    
    for(int i=1;i<=N;i++){
        ll n=(ll)Calc((double)x[i],(double)y[i],(double)z[i],(double)t);
        a=y[i]*n+z[i]*(n-1)*n\/2,l=t-a-(n+1)*x[i],Ans+=a;
        if(l>0) Ans+=l;
\/\/cout << n << " " << a << endl;
    }
    cout << Ans << endl;
    
    return 0;
}

T14938 展示牌

题目分析

如果先去掉旋转限制，本题方法是枚举最大高度H,贪心分类讨论:

贪心策略：

在高度不超过限制的情况下，使宽度增加尽可能少。 设h,w分别为当前人的高和宽，那么：

(1)h>H:

• w>H:旋转还是会超出高度，不合法直接跳出。
• w<=H:旋转

(2)h<=H:

• h>=w:站着(这样宽度增加得少)
• h<w:旋转，但是由于旋转的人数有限制，所以有一部分还是要站着。 因此特殊处理这种需要决策的情况(在h<=H&&h<w的这种情况下)：问题：这些人站着躺着的高度都不会超出H,因此考虑怎样选择使得总宽度最少。

解决方案：

先让每个人都站着，此时总宽度设为W,然后再让n/2个人旋转：每个人旋转，那么这个人对W将加上值(h-w) (意思是将宽换成高的长),那么我们希望(h-w)尽量小，因此从小到大排序然后取前n/2个躺着就可以了。

参考代码

#include <bits\/stdc++.h>
using namespace std;
set<int> ::iterator sit;
int ans,sum,p[1005],i,a[1005],b[1005],cnt,CNT,j,ANS,n;
int cmp(int i,int j) {return i>j;}
bool FLAG;
int main()
{
    ANS=1000000000;
    scanf("%d",&n);
    for (i=1; i<=n; i++)
      scanf("%d%d",&a[i],&b[i]);
    for (i=1; i<=1000; i++)
    {
        sum=0; FLAG=true; cnt=0; CNT=0;
        for (j=1; j<=n; j++)
          if (b[j]<=i && (a[j]<=b[j] || a[j]>i)) sum+=a[j]; else
            if (a[j]>i && b[j]>i) {FLAG=false; break;} else
              if (b[j]>i) {cnt++; sum+=b[j];} else
              {
                  p[++CNT]=a[j]-b[j];
                  sum+=a[j];
              }
        if (!FLAG) continue;
        if (cnt>n\/2) continue;
        sort(p+1,p+CNT+1,cmp);
        for (j=1; j<=min(n\/2-cnt,CNT); j++) sum-=p[j];
        ANS=min(ANS,sum*i);
    }
    cout<<ANS;
    return 0;
}

T564027 幸运数

题目分析

本题是前面 P4446 [AHOI2018初中组] 根式化简 的一个变形题目。

两种形式可以归结为一种，因为$x,y >0$

• 形式1：$y^1,y^2$都是偶数
  $x^2y^2 =（xy)^2 $ 找出$10^9$范围内$xy$，在$40000$范围内筛质数即可.
• 形式2：：$y^1,y^2$有一个奇数,

例如 $x^4y^9=（x^2y^3）^2*y^3 $

• 形式3：y1y2都是奇数

  $$ x^5y^9\ =x^5y5y4\ =(xy)^5(y^2)^2\ =(xyy^2)^2*(xy)^3 $$

  可以转化为平方数$x^2y^2$或者$x^2y^3$形式。

  long long 范围内质因子的个数不超过$235*7...$不会超过20个质因子。

  因为包含因子1，所有的形式可以汇总为平方数，立方数和$x^2y^3$形式的数

• 平方数 立方数可以直接通过pow判断

$x^2y^3 <=10^{18} < min(x,y)^5 $ 最大到$4000^5 =1024*10^15=10^{18}$ 筛出4000以内的质数

参考代码

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll; 

const int N = 40000 + 10;
int T, len;
ll n, p[N];
bool isp[N];

void getprime(int n){
	for(int i=2;i<=n;i++){
		if(!isp[i])
			p[++len] = i;
		for(int j=1;j<=len&&i*p[j]<=n;j++){
			isp[i * p[j]] = 1;
			if(i % p[j] == 0)
				break;
		}
	}
	return;
}

bool pow3(ll m){
	ll t3=pow(m,1.0\/3);
	for(ll i=t3-1;i<=t3+1;i++)
		if(i*i*i==m)return true;
	return false;
}
bool pow2(ll m){
	ll t3=pow(m,1.0\/2);
	for(ll i=t3-1;i<=t3+1;i++)
		if(i*i==m)return true;
	return false;
}

string work(){
	cin>>n;
	ll m = n;
	if(pow2(n))return "yes";	
	if(pow3(n))return "yes";
	ll lim = ceil(pow(m, 0.2)) + 2;\/\/再找x^2,y^3 
	for(int i=1;i<=len&&p[i]<=lim;i++){
		ll pp = p[i] * p[i];
		if(m % pp == 0){
			m \/= pp;
			while(m % p[i] == 0)
				m \/= p[i];
		}
	}
	if(pow2(m)||pow3(m))return  "yes";
	return "no";
}

int main(){
	cin>>T;
	getprime(N - 10);
	while(T--)
		cout<<work()<<"\n";
	return 0;
}