总述

这次题目除了 T3 都还行

但是……

I LOVE CCF!

T1

做法

很简单，暴力一下，大于 $10^9$ 退出即可。

srds，I use the kasumi

时间花费有亿点多。

JYL 用 pow 都能对

代码(pow.cpp)

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL MOD=(1e9);
LL a,b;
LL kasumi(LL a,LL b)
{
    LL ans=1,cnt=a;
    while(b)
    {
        if(cnt>MOD)
        {
            return -1;
        }
        if(b&1)
        {
            ans=ans*cnt;
            if(ans>MOD)
            {
                return -1;
            }
        }
        cnt=cnt*cnt;
        b>>=1;
    }
    return ans;
}
int main()
{
    freopen("pow.in","r",stdin);
    freopen("pow.out","w",stdout);
    cin>>a>>b;
    cout<<kasumi(a,b)<<"\n";
    return 0;
}

T2

做法

变形后发现是二分。

∵ 和图形大小原理差不多

∴ 当在 $p=q$ 后，就会趋势由大变小

∴ 是双峰，要 $+1 \div 2$

∴ 太棒了!我爱 CCF!

r=ppq+1>>1 -> r=ppq

$\texttt{100pts}$ -> $\texttt{0pt}$

化简后发现 $p + q = n + 2 - e \times d$

二分这个即可，判断是否 $= n$

代码(decode.cpp)

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int k;
void work()
{
    LL n,e,d,ppq,pq;
    scanf("%lld%lld%lld",&n,&e,&d);
    ppq=n+2-e*d;
    pq=n;
    LL l=0,r=ppq+1>>1;
    while(l<r)
    {
        LL mid=(l+r)>>1;
        if(mid*(ppq-mid)<pq)
        {
            l=mid+1;
        }
        else r=mid;
    }
    if(l*(ppq-l)==pq && l<=(ppq-l))
    {
        printf("%lld %lld\n",l,ppq-l);
        return;
    }
    puts("NO");
    return;
}
int main()
{
    freopen("decode.in","r",stdin);
    freopen("decode.out","w",stdout);
    scanf("%d",&k);
    while(k--)
    {
        work();
    }
    return 0;
}

T3

大模拟，万恶之源

骗了 $\texttt{40pts}$

但是花了 $\texttt{2h+}$

十分不划算

导致 T2、T4 挂了

做法

我不知道

代码(expr.cpp)

我更不会

pr我爱你

T4

一个动态编程题，但我只想到 $\texttt{60pts}$ 的动态编程做法

做法

设 $\texttt{dp[i][k]}$ 为当前为第 $i$ 个点，用了额外的 $k$ 个 外挂 整点。

$\texttt{dp[i][k]} = \max \{\texttt{dp[j][k-d]}\}$ ($1 \le j < i$，$d$ 为两点间需要用到的额外的 外挂 整点)

初始时 $\texttt{dp[i][k]}=1$

$\texttt{DP}$ 前要排序，就是把两个点，如果 $s1$ 能搁到 $s2$ 就不用变，也就是
$s1.x+s1.y<s2.x+s2.y$

代码(point.cpp)

#include<bits/stdc++.h>
using namespace std;
int ans,n,kk,f[510][110];
struct node
{
    int x,y;
}a[510];
bool cmp(node s1,node s2)
{
    return (s1.x+s1.y)<(s2.x+s2.y);
}
int main()
{
    freopen("point.in","r",stdin);
    freopen("point.out","w",stdout);
    scanf("%d%d",&n,&kk);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        for(int k=0;k<=kk;k++)
        {
            f[i][k]=1;
            for(int j=1;j<i;j++)
            {
                if(a[i].x<a[j].x || a[i].y<a[j].y) continue;
                int d=(a[i].x-a[j].x)+(a[i].y-a[j].y)-1;
                if(k>=d)
                {
                    f[i][k]=max(f[i][k],f[j][k-d]+d+1);
                }
            }
            ans=max(f[i][k]+(kk-k),ans);
        }
    }
    printf("%d\n",ans);
    return 0;
}

总结

这次比赛出了亿点点大失误，当初应该 $\texttt{T1->T2->T4}$ 然后检查，再象征性地骗点 $\texttt{T3}$ 的分。

我爱 CCF

赞美太阳!

寄!

希望明年可以 RP++

$\texttt{lzx's 2022 Round}$

END