莆田一中2022级测试赛 Round 5 题解

· · 个人记录

注：本篇题解提供的代码仅为主体部分

T1 尺码(Size)

idea&sol:xxh

依题意进行模拟即可，需要注意 S 码是 X 越多越小。

由于第 length-1 位（末位）表示种类，所以进行一个分类讨论即可。

int l1,l2;  
string s1,s2;
cin>>s1>>s2;
l1=s1.length();
l2=s2.length();
if(s1==s2)  cout<<"=";
else if(s1[l1-1]!=s2[l2-1])
{
    if(s1[l1-1]=='L')       cout<<">";
    else if(s2[l2-1]=='L')  cout<<"<";
    else if(s1[l1-1]=='M')  cout<<">";
    else                    cout<<"<";
}
else
{
    if(s1[l1-1]=='L'&&l1>l2)        cout<<">";
    else if(s1[l1-1]=='L'&&l1<l2)   cout<<"<";
    else if(s1[l1-1]=='S'&&l1>l2)   cout<<"<";
    else if(s1[l1-1]=='S'&&l1<l2)   cout<<">";
}

T2 付钱(Cost)

idea&sol:lyc

警惕诈骗题---来自 xxh

如果您做出了本题，请自动跳到下一题题解，以防本题题解浪费您宝贵的时间。

解法一：推理法

我们以样例 10 为例，首先，我们肯定要一包 1 元钱，否则无法支付价格为 1 元的商品。

那下一包该装多少钱呢？如果也装 1 元钱的话，那么我们现在可以支付价格为 1,2 元的商品，但是这显然不是最优解，如果第二包放 2 元钱，那么我们可以支付价格为 1,2,3 元的商品，这显然比刚才优的（包数相同情况下可以支付的钱更多）。易得，第二包不能放 3 元钱，因为这样子无法支付价格为 2 元的商品，所以第二包放 2 元钱。

之后还剩下 3 元钱没处放，怎么办呢？由上可知，我们还剩下 8,9,10 三种金额不能支付，我们可以把这三种金额进行拆分，变成 5+3;6+3;7+3 元，显然，5,6,7 三种金额是我们已经可以凑出来的了，所以我们只要把这三块钱全部放进第四包里，我们就可以支付 1~10 间的任意金额了。

以上我们能找到什么规律呢，据观察可得，前三包的金额分别为 2^0,2^1,2^2 ，所以我们就找到规律了：我们要找到一个最小的 k ，使 \sum_{i=0}^k 2^i \geq n 。而这一操作用循环实现即可。

当然，这是可以严格证明的，证明在解法二。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,a=1,ans=0,sum=0;
    scanf("%lld",&n);
    if(n==0){
        printf("0");
        return 0;
    }
    for(;sum<n;a*=2,ans++){
        sum+=a;
    }
    printf("%lld",ans);
    return 0;
}

解法二：数学法

我们首先考虑特殊情况 n=2^k-1,k\in N。

$n=3$ 时，$3$ 的二进制表示为 $0011_{(2)}$ ，可以拆分为 $0010_{(2)}$ （就是十进制的 $2$ ）和 $0001_{(2)}$ ，此时我们分为两包 $1,2$ 元。 $n=7$ 时，$5$ 的二进制表示为 $0111_{(2)}$ , 可以拆分为 $0100$ （十进制的 $4$ ） 和 $0011_{(2)}$ ，所以我们就比 $n=3$ 的情况多了一包 $4$ 元。 由此我们可以推出，当 $n=2^k-1,k\in N$ 时，我们只需把 $n$ 拆分成所有小于 $n$ 的 $2$ 指数幂就可以支付 $1$~$n$ 中的任意金额。 接下来扩展到一般情况。 首先给结论，对于任意的 $n$ ，我们令 $n=2^k-1+a$ ，且 $a\le 2^k-1$ ，则有 $a\in[2^k-1,2^{k+1}-1)$ ，此时针对 $a$ 进行分类讨论。 若 $a=0$ 则分为 $k$ 包，否则分为 $k+1$ 包。 以下进行证明。 对于任意的 $n$ ，我们必然能找到一个 $k$ ，使 $2^k-1\leq n\lt 2^{k+1}-1$ 。 我们假设 $n=2^k-1+a,a\in N$ ，则 $2^k-1+a\lt 2^{k+1}-1$ ， 因为 $n\in N^* $ ，所以 $2^k-1+a\le 2^{k+1}-2$ ，即 $2^k-1+a\le 2\times (2^k-1)$ ，所以 $a\le 2^k-1$ 。 在特殊情况中，我们已经证明了任意金额 $m\leq 2^k-1$ 元的商品都可以通过拆分被支付，我们现在证明对于任意金额 $m\gt 2^k-1$ ，只需把多出来的 $a$ 元放在新的一包中即可支付。 假设我们支付的金额 $m=2^k-1+x$ ，则 $\forall x\in [1,a]$ 。 所以 $2^k-1+x\leq 2^k-1+a$ ，即 $2^k-1+x-a\le 2^k-1$ 。 所以我们选取装有 $a$ 元的这包之后，我们只要选取 $2^k-1+x-a$ 元就可支付商品，而 $2^k-1+x-a\le 2^k-1$ ，所以我们就回到特殊情况的拆分了。 所以可得，对于 $\forall k\in N$ ，$n=2^k-1+a,a\le 2^k-1$ ，将分为 $k(+1)$ 包： $$ \begin{cases} 2^k-1 元分为 k 包\\ a 元放 1 包,if(a>0) \end{cases} $$ 由对数得 $n \neq 0$ 时，$k=\lfloor \log_2n \rfloor$，$k+1=\lfloor \log_2n \rfloor+1 所以对于 $\forall n\in N^* $ , 答案为 $\lfloor \log_2n \rfloor+1$。 代码： ```cpp #include <bits/stdc++.h> using namespace std; int main() { long long n; cin>>n; if(n==0) cout<<0; else cout<<(int)log2(n)+1; return 0; } ``` ## T3 异或(Xor) idea&sol:xxh 由于 `^` 运算具有交换律和结合律，且题目要求查询区间异或和，我们可以使用前缀和的思想，令 $sum_i=a_1~xor~a_2~...~xor~a_i$。 那么查询区间 $l$ ~ $r$ 就可以用前缀和的方式抵消 $1$ ~ $l-1$ 的异或值，显然异或上 $sum_{l-1}$ 就可以了。 不理解的可以画一个线段图，显然被两条线段同时覆盖的数会被抵消为 $0$。 ``` const int N = 1e5 + 5; int sum[N]={0}; int i,n,q,k,l,r; cin>>n>>q; for(i=1;i<=n;i++) { cin>>k; sum[i]=sum[i-1]^k; } while(q--) { cin>>l>>r; cout<<(sum[r]^sum[l-1])<<endl; } ``` ## T4 字符串匹配(Char) idea&sol:xxh 此题有多种做法，这里只介绍两种基于 STL 的做法。 1. 字符串数组排序 C++ 的 `sort` 函数是支持字符串数组的排序的，所以可以对字符串进行一次排序，然后扫一遍判断重复的字符串的数量，用 $n$ 减去即可。 ``` const int N = 1e4 + 5; string s[N]; ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int i,j,n,m,ans; cin>>n; ans=n; for(i=1;i<=n;i++) cin>>s[i]; sort(s+1,s+n+1); for(i=2;i<=n;i++) if(s[i]==s[i-1]) ans--; cout<<ans; ``` 2. map 去重 使用 STL 库中的 `map` 数据结构，定义一个类型为 `<string, bool>` 的 `map` 来记录某个字符串是否出现过，没有出现过的才累加。 ``` map <string, bool> mp; ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); string s; int i,j,n,m,ans=0,res,t; cin>>n; for(i=1;i<=n;i++) { cin>>s; if(!mp[s]) mp[s]=true,ans++; } cout<<ans; ``` 当然，暴力枚举字符串并匹配相等也可以，不过由于是暴力写法，这里不做展开。 ## T5 消除(Remove) idea&sol:xxh 由于这个删除操作可以把在最前面的一些元素 `撤销`，所以考虑用栈来实现。 用一个结构体栈来维护每一个数之前的相同的数的个数，放入数时累加，达到 $k$ 时将这些数全部出栈即可。 用样例来做解释（$st$ 是栈空间，$sum$ 为连续个数）： $st:~~~~~2 sum:~1 st:~~~~~2~6~6 sum:~1~1~2 st:~~~~~2~6~6~6 sum:~1~1~2~3

此时 sum=k，连续出栈 k 次。

st:~~~~~2 sum:~1 st:~~~~~2~6~3~2 sum:~1~1~1~1 st:~~~~~2~6~3~2~2~5~5~5 sum:~1~1~1~1~2~1~2~3

然后把 5 都拉出来

st:~~~~~2~6~3~2~2 sum:~1~1~1~1~2 st:~~~~~2~6~3~2~2~2 sum:~1~1~1~1~2~3

再次进栈：2 也达到了要求。

st:~~~~~2~6~3 sum:~1~1~1 st:~~~~~2~6~3~1~4~4 sum:~1~1~1~1~1~2

然后反向输出栈内元素即可。

struct pi{int x,w;}p;
stack <pi> st,ts;

ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int i,j,n,m,k,l,x;
cin>>n>>k;
for(i=1;i<=n;i++)
{
    cin>>p.x;
    if(st.empty())  
    {
        p.w=1;
        st.push(p);
        continue;
    }
    if(st.top().x==p.x) p.w=st.top().w+1;
    else                p.w=1;
    st.push(p);
    if(p.w==k)  
    {
        for(j=1;j<=k;j++)   
            st.pop();
    }   
}
while(!st.empty())  ts.push(st.top()),st.pop();
while(!ts.empty())  cout<<ts.top().x<<" ",ts.pop();

T6 排列(Array)

idea&sol:xxh

可以发现，数值相等的位置的顺序可以被任意调换，那么一种出现 k 的数的排列总数为 A_{k}^{k} 即 k!。

根据乘法原理，将其累乘即可。

由于模数较大，数据类型需要开 long long。

#define int long long

const int N = 1e6 + 5;
const int M = 1e9 + 7;
int fac[N],a[N],b[N],sum[N]={0};

ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int i,n,ans=1;
for(i=1,fac[0]=1;i<=1e6;i++)    fac[i]=fac[i-1]*i%M;
cin>>n;
for(i=1;i<=n;i++)   cin>>a[i];
for(i=1;i<=n;i++)   cin>>b[i];
for(i=1;i<=n;i++)   sum[a[i]]++;
for(i=1;i<=1e6;i++) ans=ans*fac[sum[i]]%M;
cout<<ans;

T7 探险(Explore)

idea&sol:lyc

《尊重出题人的愿望》

#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
struct node{
    int d,o;
}nod[maxn];
bool cmp(node a,node b)
{
    return a.d<b.d;
}
priority_queue< int,vector<int>,less<int> >q;
int n,l,p,cnt=0;
double k,tot;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>l>>p>>k;
    for(int i=1;i<=n;i++)
        cin>>nod[i].d>>nod[i].o;
    sort(nod+1,nod+n+1,cmp);

    tot=1.0*k*p;
    int idx=1;
    while(nod[idx].d<=tot&&idx<=n)
    {
        q.push(nod[idx].o);
        idx++;
    }
    while(tot<l&&!q.empty())
    {
        tot=tot+1.0*k*q.top();
        q.pop();
        while(nod[idx].d<=tot&&idx<=n)
        {
            q.push(nod[idx].o);
            idx++;
        }
        cnt++;
    }
    if(tot<l)   cout<<(int)tot;
    else    cout<<cnt;
    return 0;
}

T8 相等(Equal)

idea&sol:xxh

首先可以将三个数的数值转为差值 x=b-a,y=c-b，显然，当 x=y=0 时三个数相等。

那么，由于 i 次操作可以使数值变化的总和为 \dfrac{i\times(i+1)}{2}，操作次数最少的情况下需要保证 \dfrac{i\times(i+1)}{2} \geq x+y，而在满足这个条件下我们一定可以构造出一种方案，使得其中的一些数组成 x，另一些数组成 y：

先选出一个数 z=\dfrac{i\times(i+1)}{2}-x-y，将它从 1 ~ n 中剔除，而T2（Cost）启发了一种分割方式：只需要拆分为二进制数值就可以表示出任意的一个数。

接下来分类讨论：

  3. 如果 z=2^k(k\geq2)，那么它一定可以由 2^{k-1}+1 和 2^{k-1}-1 分割而成，所以一定可以通过替代法来找出一些数字组成 x，剩下数字之和也就是 y。

  4. 如果 z 不是 2^k 形式的数，显然去掉它无影响（因为总是可以用其他的数来拼出 z）。

所以答案是最小的 i，使得 \dfrac{i\times(i+1)}{2} \geq x+y。

现在的问题就转化为：求这个 i。

化简：\dfrac{1}{2}i^2+\dfrac{1}{2}i-(x+y)\geq 0

\to i^2+i-2(x+y)\geq 0 \to i = \lceil\dfrac{\sqrt{8\times (x+y)+1}-1}{2}\rceil

所以输出这个结果就可以了。

long long a,b,c,i;
cin>>a>>b>>c;   
cout<<(long long)ceil((sqrt(8.0*(c-a)+1)-1)/2);