第十三届蓝桥杯C++ B组

经推导可得，第k棵树(k为1~n)的最大高度为，k-1 或 n-k 的最大值*2

【问题描述】 进制规定了数字在数位上逢几进一。 X 进制是一种很神奇的进制，因为其每一数位的进制并不固定！例如说某 种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则 X 进制数 321 转换为十进制数为 65 。 现在有两个 X 进制表示的整数 A 和 B ，但是其具体每一数位的进制还不确 定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进 制。请你算出 A − B 的结果最小可能是多少。 请注意，你需要保证 A 和 B 在 X 进制下都是合法的，即每一数位上的数 字要小于其进制。 【输入格式】 第一行一个正整数 N ，含义如题面所述。 第二行一个正整数 M a ，表示 X 进制数 A 的位数。 第三行 M a 个用空格分开的整数，表示 X 进制数 A 按从高位到低位顺序各 个数位上的数字在十进制下的表示。 第四行一个正整数 M b ，表示 X 进制数 B 的位数。 第五行 M b 个用空格分开的整数，表示 X 进制数 B 按从高位到低位顺序各 个数位上的数字在十进制下的表示。 请注意，输入中的所有数字都是十进制的。 【输出格式】 输出一行一个整数，表示 X 进制数 A − B 的结果的最小可能值转换为十进 制后再模 1000000007 的结果。 【样例输入】 11 3 10 4 0 3 1 2 0 【样例输出】 94 【样例说明】 当进制为：最低位 2 进制，第二数位 5 进制，第三数位 11 进制时，减法 得到的差最小。此时 A 在十进制下是 108 ， B 在十进制下是 14 ，差值是 94 。 【评测用例规模与约定】 对于 30 % 的数据， N ≤ 10; M a , M b ≤ 8 . 对于 100 % 的数据， 2 ≤ N ≤ 1000; 1 ≤ M a , M b ≤ 100000; A ≥ B

做到这个地方，理解题意已经开始困难了，开始没搞懂他给的样例是怎么转换的，就先看了后面的二维前缀和，读懂题目之后，其实当时的我并不知道这会是一个贪心题目，只是能够感觉到，X应该是a[i]+1,b[i]+1中的最大值，想到这里就很明晰了，先算出X，再用该位进制*(a[i]-b[i])即可

#include

using namespace std;

const int mod=1000000007;
const int N=1e5+10;
int n,A,B;
int a[N],b[N],x[N];
long long ans;
signed main()
{
    cin>>n;//n用不到
    cin>>A;//A的位数
    for(int i=A;i>0;i--)cin>>a[i];
    cin>>B;//B的位数
    for(int i=B;i>0;i--)cin>>b[i];
    //比较算出x，注意x最小为2
    for(int i=1;i<=A;i++)
    {
        x[i]=max(a[i]+1,b[i]+1);
        if(x[i]<2)x[i]=2;
    }
    
    long long int k=1;
    for(int i=1;i<=A;i++)
    {
        ans+=((a[i]-b[i])*k)%mod;

        ans=(ans+mod)%mod;//可能出现负数

        k=(k*x[i])%mod;//对进制累乘
    }
    cout<

#include
#define int long long 
using namespace std;

const int N=510;

int n,m,k;
int a[N][N];
int res;

signed main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%lld",&a[i][j]);
            a[i][j]+=a[i-1][j];
        }

    for(int i=1;i<=n;i++)//矩阵上端点
        for(int j=i;j<=n;j++)//矩阵下端点
            for(int l=1,r=1,sum=0;r<=m;r++)
            {
                sum+=a[j][r]-a[i-1][r];
                while(sum>k)
                {
                    sum-=a[j][l]-a[i-1][l];
                    l++;
                }
                res+=r-l+1;
            }
    cout<