20250117-公益AB班测试

wflengxuenong · 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+i*z,得到一个等差数列求和的公式。

\sum_{i=0}^j(x+y+i*z)\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都是偶数
形式2：：y^1,y^2有一个奇数,

例如

x^4*y^9=（x^2*y^3）^2*y^3

形式3：y1y2都是奇数
x^5*y^9\\ =x^5*y5*y4\\ =(xy)^5*(y^2)^2\\ =(x*y*y^2)^2*(xy)^3
可以转化为平方数x^2y^2或者x^2y^3形式。

long long 范围内质因子的个数不超过2*3*5*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;
}

20250117-公益AB班测试

T14281 单栈排序

题意简述

解法一

解法二

解法三

参考代码

T14211 勤劳的蜜蜂

题目分析

参考代码

T14938 展示牌

题目分析

贪心策略：

(1)h>H:

(2)h<=H:

解决方案：

参考代码

T564027 幸运数

题目分析

参考代码