场外选手口胡的 2022 j 组题解

· · 个人记录

T1

模拟应该没人不会吧。判掉 a=1 后超过 10^9 乘法次数是 \log 级别的。

#include<cstdio>
const int lim=1e9;
int a,b;
int main(){
    scanf("%d%d",&a,&b);
    long long res=1;
    if(a==1)return printf("1"),0;
    while(b--){
        res*=a;
        if(res>lim)return printf("-1"),0;
    }
    printf("%lld",res);
}

T2

快乐解方程

\begin{cases}xy=n\\xy-x-y=de-2\iff x+y=n-de+2=k\end{cases}

(这里设的 k 就是题面里的 m)

换元 x=y-k，y^2-ky-n=0，套求根公式。由于要求解是正的，取 y=\frac{k+\sqrt{k^2+4n}}{2}。代回去求解 x 即可。无解就是根号开不开、开完上面是奇数。复杂度 O(1)。由于保证 k\le 10^9,n\le10^{18}，直接计算即可(感谢 TheCliffSwallow 指正)

出题人的想法应该是换元得到 k=x+\frac n{x}。这是经典的对勾函数（单谷），在 x=\sqrt n 处是谷底，两端均单调。左端二分 x，右端计算 y。复杂度 O(\log\sqrt n)。

个人认为后者确实更好写。

#include<cstdio>
#include<cmath>
long long a,b,n,t;
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld%lld",&n,&a,&b);
        long long k=n-a*b+2,l=1,r=sqrt(n),res=0;
        while(l<=r){
            long long mid=l+r>>1;
            if(mid+n/mid<k)r=mid-1;
            else res=mid,l=mid+1;
        }
        if(n%res||res+n/res!=k){
            printf("NO\n");
            continue;
        }
        printf("%lld %lld\n",res,n/res);
    }
}

T3

首先将中缀表达式转后缀表达式，然后建立表达式树。

先序遍历表达式树，看左子树传过来的值是否满足短路，满足统计二问答案，不满足遍历右子树计算点值。

复杂度 O(|s|)（过了民间数据应该没假吧）

#include<cstdio>
#include<cstring>
char s[1000001];
char hz[1000001],stk[1000001];
int n,m,p,d7,dh,top,cnt;
int tp[2000001],son[2000001][2],val[2000001],id[2000001];
int sk[1000001];
void dfs(int x){
    if(tp[x]<=1)return;
    dfs(son[x][0]);
    if(tp[x]==2&&!val[son[x][0]]){
        d7++;
        return;
    }
    if(tp[x]==3&&val[son[x][0]]){
        dh++;
        val[x]=1;
        return;
    }
    dfs(son[x][1]);
    val[x]=val[son[x][1]];
}
int main(){
    int i;
    scanf("%s",s+1);
    n=strlen(s+1);
    for(i=1;i<=n;i++){
        if(s[i]=='0'||s[i]=='1')hz[++m]=s[i];
        else if(s[i]=='(')stk[++top]=s[i];
        else if(s[i]==')'){
            while(top&&stk[top]!='(')hz[++m]=stk[top--];
            top--;
            continue;
        }
        else{
            if(s[i]=='&')while(top&&stk[top]=='&')hz[++m]=stk[top--];
            else while(top&&stk[top]!='(')hz[++m]=stk[top--];
            stk[++top]=s[i];
        }
    }
    while(top)hz[++m]=stk[top--];
    n=m;top=0;
    for(i=1;i<=n;i++){
        if(hz[i]=='0'||hz[i]=='1'){
            id[i]=++cnt;
            tp[cnt]=val[cnt]=hz[i]-'0';
        }
    }
    for(i=1;i<=n;i++){
        if(id[i])sk[++top]=id[i];
        else{
            int p=sk[top--],q=sk[top--];
            sk[++top]=++cnt;
            son[cnt][0]=q;son[cnt][1]=p;
            if(hz[i]=='&')tp[cnt]=2;
            else tp[cnt]=3;
        }
    }
    int rt=sk[top];
    dfs(rt);
    printf("%d\n%d %d",val[rt],d7,dh);
}

T4

定义实点为给定的 n 个点，虚点为我们插入的点。

初值：$dp[i][0]=1$。这个转移的时候也要顺带转移 转移：先按 $x$ 第一关键字，$y$ 第二关键字排序。$dp_{i,j}=\max\limits_{k<j,y_k\le y_j}\{dp_{k,j-dis+1}+1\}$，$dis$ 为两点曼哈顿距离。复杂度 $O(n^2k) 
#include<cstdio>
#include<algorithm>
using namespace std;
struct pts{
    int x,y;
}a[100001];
bool operator<(pts x,pts y){
    return x.x==y.x?x.y<y.y:x.x<y.x;
}
int dp[501][101],n,m;
int main(){
    int i,j,k;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+n+1);
    for(i=1;i<=n;i++){
        dp[i][0]=1;
        for(k=0;k<=m;k++){
            for(j=1;j<i;j++){
                if(a[j].y>a[i].y)continue;
                int ds=a[i].x-a[j].x+a[i].y-a[j].y-1;
                if(ds>k)continue;
                dp[i][k]=max(dp[i][k],dp[j][k-ds]+ds+1);
            }
        }
    }
    int ans=0;
    for(i=1;i<=n;i++)for(j=0;j<=m;j++)ans=max(ans,dp[i][j]+m-j);
    printf("%d",ans);
}

小结：今年的题还行

T2 感觉很多人被降智了的说...

T3 比较花，考的中缀转后缀和表达式树的知识，有一定意思。

T4 比较板的 dp，但也有点意思。不是很理解 O(n^2) 做法。毕竟最坏情况下边数 n^2 级别的，似乎也会退化成 O(n^2k)。