2022″杭电杯”中超联赛·第二场(1001虚树,1011线段树)

2022年7月23日 上午12:26 比赛总结

比赛链接杭电多校第二场-hduoj
这次过了五题,又又又又绝杀了...这回时间是04:59:49,原因是1003数据太过简单,暴力就可以,zyx最后11s交上AC。

总体来说一开始的两个数学题有点炸心态(1012,1009),队伍排名有所下降,上一次是164,要不定一个目标吧,就定在前300。补题有1001还打算补1011,最近太累了,先更新部分的,还是按题目顺序来。


1002.C++ to Python(签到)

这个题我第一反应是这个CF190C - Codeforces,自信的接下了这个题,但是没想到这个这么简单...我以为可以像cf这个题去用递归...实际上只需要for循环判断,输出想要的即可。

可以再看看这个CF190C:题意通过输入的pairint来最后输出总的类型,例如:

Input:
3
pair pair int int int
Output:
pair<pair<int,int>,int>

可以用递归来,如果是pair则在递归前加上<,>这类即可。十分巧妙。

void dfs()
{
    if(cin >> s)
    {
        ans+=s;
        if(s=="pair")
        {
            ans+="<";
            dfs();
            ans+=",";
            dfs();
            ans+=">";
        }
    } else ok=1;
}

本题代码也十分简单:

inline void Case_Test()
{
    cin>>s;
    n=s.size();
    for (int i=0;i<n;i++)
    {
        if (s[i]>='0'&&s[i]<='9')//我写[1,9]wa了一发...罪犯
            cout<<s[i];
        else if (s[i]=='('||s[i]==')'||s[i]==','||s[i]=='-')
            cout<<s[i];
    }
    cout<<endl;
}

1007.Snatch Groceries(贪心,签到)

阅读理解题,题面很长

题意:给你若干个区间,从时间小的开始安排任务,如果在某个时间点有冲突则表示不能继续下去,求冲突前最多能够有多少个任务可以完成。

思路:按区间的左端点排序,然后每次用下一个的左端点比较当前的右端点,如果可以则计数,否则break

代码

struct node
{
    int l,r;
}a[N];
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i].l>>a[i].r;
    sort(a+1,a+1+n,[](node a,node b){return a.l<b.l;});
    int ans = 0;
    a[n+1].l = inf;
    for (int i=2;i<=n+1;i++)
    {
        if (a[i].l>a[i-1].r) ans++;//计数
        else break;//退出
    }
    cout<<ans<<endl;
}

1012.Luxury cruise ship(思维+背包)

题意:给出正整数$n(n\leq 10^{18})$,求正整数$x,y,z$满足方程$7x+31y+365z=n$的条件下,$(x+y+z)_{min}$

思路:这个题十分巧妙,收获很大。首先观察这三个互质,这是十分重要的,并且可以得出$lcm=7\times 31\times 365=79205$.
对于一个$n$首先分成两部分:

  • 整除。为$lcm$的整数倍。对于一个$lcm$我们可以一直可以选择$365$去减少,一直选择$7\times 31$个$365$。这样保证了最小,又满足了达到$lcm$。

    Question:会不会可以少选一个$365$,在$79205$的基础上加一个小的$x$是的其他用$7$或者$31$填满呢?
    Answer:其实我这里写的“不会”但是越想越不对劲,因为实际上是可以的,例如我这里的$x=6$,现在我可以少减去一个$365$,在剩下的$365+6=371$里面每次减$7$(为$7$的倍数),所以是可以的...但是以我的程序是不可以的...

  • 余数。小于$lcm$的部分。
    ...继续写下去吧...小的部分就用完全背包dp[i]表示能够选i的最小个数,例如dp[14]=2dp[45]=dp[14+31]=3

那么如何解决这个问题,实际上像std一样预处理多一些就好了,我只预处理到了lcm=79205。所以这个hack数据79211应该输出245,但是我输出-1...小数据肯定在预处理范围内,大数据直接用上面方法用$365$减完就好。

代码

int dp[N];
inline void init(int n)//n=lcm
{
    for (int i=1;i<n;i++)
        dp[i] = inf;
    dp[0] = 0;
    for (int i=1;i<n;i++)
    {
        if (i>=7) dp[i] = Min(dp[i],dp[i-7]+1);
        if (i>=31) dp[i] = Min(dp[i],dp[i-31]+1);
        if (i>=365) dp[i] = Min(dp[i],dp[i-365]+1);
    }
}//预处理,应该预处理更多的
inline void Case_Test()
{
    cin>>n;
    ans = n/lcm*(7*31);
    n%=lcm;
    if (dp[n]!=inf) cout<<ans+dp[n]<<endl;
    else cout<<-1<<endl;
}

1009.ShuanQ(数学,质因数分解)

题意:给你两个加密解密方式分别是:
$$
Encryption \space formula: \space E=R \times P \space mod \space M \ Decryption \space formula: \space R=E\times Q \space mod \space M
$$

现在已知$P,Q,E(P,Q,E\leq 2\times 10^6)$,并且$P\times Q \equiv 1 \space mod \space M$,并且$M$是质数

思路:这个问题主要是不知道$m$的范围,我首先写了一发线筛,每次枚举$2e6$内的质数$m$,但是其实是要枚举$4e12$的...因为是$P\times Q$

通过$P\times Q \equiv 1 \space mod \space M$可以来推测$M$,可以得到存在一个$k$满足,$P\times Q-1=k\times M$(倍数关系),这里可以得到$kM$,那么题目中的质数$M$与其的关系是什么呢?这里的$M$是$kM$的一个质因子,并且一定要比$P,Q$要

因为是质因子,所以只需要对$M$质因数分解即可,$k$肯定不用管。

最多只有一个质因子满足要求,如果有多个满足要求$M_1,M_2$质因子,那么$kM=M_1\times M_2 \gt P\times Q$ 矛盾

然后枚举每次质数进行判断,是否满足上面两个式子即可,但是注意这里的取模要比$P,Q$要大,不然会wa。

代码

vector<int> divide(int x)
{
    vector<int> ans;
    for (int i=2;i*i<=x;i++)
    {
        if (x%i==0)
        {
            ans.push_back(i);
            while (x%i==0)
                x/=i;
        }
    }
    if (x>1)
        ans.push_back(x);
    return ans;
}//质因数分解,队友竟然还有不会写的!

inline void Case_Test()
{
    cin>>p>>q>>e;
    n = p*q-1;
    vector<int> res = divide(n);
    for (auto m:res)
    {
        if (e>=m||p>=m||q>=m) continue;//一定判p>=m,q>=m,m一定要大于他们俩
        int r = e*q%m;
        if (e==r*p%m)
        {
            cout<<r<<endl;
            return;
        }//满足条件
    }
    cout<<"shuanQ"<<endl;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注