第七届传智杯全国IT技能大赛程序设计赛道 省赛（第一场）前三题

1.A. 小苯的计算器

样例输入：

3
3 2
7 4
2 2

样例输出： 

3=1*2+1
7=1*4+3
2=1*2+0

说明： 

我们可以证明，对于任意 a 和 b ，存在唯一的 k 和 p 满足 a = k*b + p 。

直接模拟即可

 代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;cin>>t;
    while(t--)
    {
        int a,b;cin>>a>>b;
        int ant1=a/b;int ant2=a%b;
        cout<<a<<"="<<ant1<<"*"<<b<<"+"<<ant2;
        cout<<endl;
    }
    return 0;
}

2.C. 小苯的水果园

样例输入：

1
8 3
1 2 3 3 2 3 4 4
1 2 4

样例输出： 

7 3 0

说明： 

me 的思路是 map+前缀和 。 ant前缀和数组：出现次数不超过 i 的数字个数 。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,q;
        cin>>n>>q;
        map<int , int> T;
        for(int i=0;i<n;i++)
        {
            int x;cin>>x;
            T[x]++;
        }
        vector<int> ant(n+1);
        for(auto is :T)
            ant[is.second]+=is.second;
        for(int i=1;i<=n;i++)//前缀和
            ant[i]=ant[i-1]+ant[i];
        for(int i=0;i<q;i++)
        {
            int x;cin>>x;
            x=min(x,n);
            cout<<n-ant[x]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

3. D. 小苯的数组最值

样例输入： 

1
3 3
1 1 1
1 1 2
2 2 3
3 3 4

样例输出： 

665496240

说明： 

差分+快速幂求逆元+模拟+前缀+后缀，嗯，这个题真的是考察综合算法能力的一道算法题，暴力写超时。

 代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 998244353;
int qmi(int a, int b, int p) //快速幂
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * (int)a % p;
        b >>= 1;
    }
    return res;
}
void solove()
{
    int n,m;
    cin>>n>>m;
    int a[n+1];a[0]=0;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int ch[n+2];ch[0]=0,ch[n+1]=0; 
	  
     for(int i=1;i<=n;i++)//差分
         ch[i]=a[i]-a[i-1];
    int L[m+1],R[m+1],D[m+1];L[0]=0,R[0]=0,D[0]=0;
    for(int i=1;i<=m;i++)
    {
        int l,r,d;
        cin>>l>>r>>d;
        L[i]=l,R[i]=r,D[i]=d;
        ch[l]+=d;
        ch[r+1]-=d;
    }
    for(int i=1;i<=n;i++)
        ch[i]+=ch[i-1];
        
    int pro[n+1];pro[0]=0;
    int suf[n+2];suf[0]=0,suf[n+1]=0;
    for(int i=1;i<=n;i++)//前缀的最大值
        pro[i]=max(pro[i-1],ch[i]);
    for(int i=n;i>0;i--)//后缀的最大值
        suf[i]=max(suf[i+1],ch[i]);
    int ant=0;
    for(int i=1;i<=m;i++)
    {
        int l=L[i],r=R[i],d=D[i];
        if(pro[l-1]==pro[n]||suf[r+1]==suf[1])//说明当前区间没有包含全部的数组最大值
            ant+=pro[n];
        else
            ant += max(pro[n] - d, max(pro[l - 1], suf[r + 1]));
        ant%=N;
    }
    ant*= qmi(m, N - 2, N);
    ant%=N;
    cout<<ant<<endl;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solove();
    }
    return 0;
}