首页 > 其他分享 >22.10.26校内赛

22.10.26校内赛

时间：2022-10-26 16:33:17浏览次数：81  
标签：26 校内 int mid long 22.10 整数 数组 return

 

T1.F221026A. 「阶段测试」方格求和

题目描述

一个NxN的方格中，每个格子有1个数字，你可以选择任意一点为中心，可以向上下左右四个方向行动，最多走K步，问可以到达的方格的总和最大是多少

输入格式

第一2个整数N，K

接下来是N行N列，共N^2个整数

输出格式

1个整数表示最大的总和

样例

输入数据 1

5 2
50 5 25 6 17
14 3 2 7 21
99 10 1 2 80
8 7 5 23 11
10 0 78 1 9

输出数据 1

342

[样例说明

选择3x3的位置1为中心点，可以获得总和为342

数据规模与约定

40%数据：N\le 100N≤100

100%数据:N\le 400，0\le K\le 2*NN≤400，0≤K≤2∗N

 

完了，这T1算是做不来了，上来就干了一套bfs，o(n4)准炸，但我着实没想到WA了还T了还RE（aborted）了）（老六行为！）

正解应该是将矩阵旋转45度使其成为一个菱形，但能走到的地方就从菱形化为了矩阵，这是就可以使用二维前缀和了，枚举每一块矩阵的大小，此题得解

打bfs的我就是个大冤种

上代码（你们最喜欢的环节）

#include<bits/stdc++.h>
using namespace std;
int n,m,k,g[1010][1010],a[2010][2010];
//a为旋转后数组，再处理为前缀和数组，g为原数组
int main(){
    //freopen("sum.in","r",stdin);
    //freopen("sum.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
            scanf("%d",&g[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i+j-1][n-i+j] = g[i][j];
    m = n*2-1;
    for(int i = 1;i<=m;i++)
        for(int j = 1;j<=m;j++)
            a[i][j]+=a[i][j-1];
    for(int i = 1;i<=m;i++)
        for(int j = 1;j<=m;j++)
            a[i][j]+=a[i-1][j];
    int ans = -0x7fffffff;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++){
            int x = i+j-1,y = n-i+j;
            int x1 = x-k,y1 = y-k,x2 = x+k,y2 = y+k;
            if(x1<1) x1 = 1;
            if(y1<1) y1 = 1;
            if(x2>m) x2 = m;
            if(y2>m) y2 = m;
            ans = max(ans,a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1]);
        }
    printf("%d\n",ans);
    return 0;
}

T2.F221026B. 「阶段测试」第 K 小数

题目描述

有两个正整数数列，元素个数分别为NN 和 MM。从两个数列中分别任取一个数相乘，这样 一共可以得到 N*MN∗M个数，询问这 N*MN∗M个数中第 K 小数是多少。

输入格式

输入文件包含三行。

第一行为三个正整数 N,M 和 K。

第二行为 N 个正整数，表示第一个数列。

第三行为 M 个正整数，表述第二个数列。

输出格式

输出文件包含一行，一个正整数表示第 K 小数。

样例

输入数据 1

5 5 18
7 2 3 5 8
3 1 3 2 5

输出数据 1

16

 

同样是道我骗分代码爆RE（aborted）的题，真的服辣

思路：是二分答案，但我没看出来，将a,b两个数列排序，然后再二分答案，利用a,b数列的单调性，统计小于mid的个数，以此为依据来二分

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,a[200010],b[200010];
bool check(long long mid){
    long long p = n,sum = 0;
    for(int i = 1;i<=m;i++){
        while(a[p]*b[i]>mid&&p) p--;
        sum+=p;
    }
    if(sum>=k) return true;
    return false;
} 
int main(){
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i = 1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i = 1;i<=m;i++)
        scanf("%lld",&b[i]);
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    long long l = 1,r = a[n]*b[m],ans = 0;
    while(l<=r){
        long long mid = (l+r)>>1;
        if(check(mid)) ans = mid,r = mid-1;
        else l = mid+1;
    }
    printf("%lld",ans);
    return 0;
}

T3.F221026C. 「阶段测试」大整数

题目描述

L实现了一个大整数模板（十进制） 。他的大整数有一个十分厉害的功能：它可以像提取子串那样提取出整数中的一段。

当然，这提取出的一段也是大整数。不过，L发现他的模板中这种操作的效率很低，于是想请你帮他实现这样一个功能。也就是说，在给出一 个长度为 NN 的大整数后，你的程序要能够快速求出大整数某一段的值。由于大整数在加减 中经常会有进位等状况发生，你的程序还需要支持区间修改操作，即将某一段中的数字全部 变成一个给定的数字。

注意：我们从大整数的最低位（最右边）开始标号，依次为第 0, 1, 2,..., N - 10,1,2,...,N−1位。

输入格式

第一行两个整数 N，MN，M，分别为大整数长度和操作数量。

第二行为长度为 NN 的串表示初始的大整数。

接下来 MM 行，每行描述一次操作。格式如下（第一个整数为操作类型） ：

1 l r表示询问[l, r][l,r]这一段的值

2 l r v 表示将[l, r][l,r]这一段中所有数字变为 vv

输出格式

对每个询问操作输出一行一个整数表示对应的答案。由于大整数的值可以很大，输出答案对 10^9 + 7109+7 取模后的结果即可。

样例

输入数据 1

5 3
12345
1 1 3
2 1 4 3
1 1 3

输出数据 1

234
333

数据规模与约定

对于 40%的数据，N, M <= 5000N,M<=5000。

对于另外 30%的数据，所有修改操作中l = rl=r。

对于 100%的数据，1 <= N, M <= 100000，0 <= l <= r <= N - 1, 0 <= v <= 91<=N,M<=100000，0<=l<=r<=N−1,0<=v<=9，大整数中每位数 字均在 0-90−9的范围中。

这道题我打了一个线段树但是爆了RE（segmentation fault）

我终于找道为啥RE了

mid = (t[p].l+t[p].r)>>1;

 

被我写成了

mid = (l+r)>>1;

 

正解也是线段树（应该没人不会想到线段树吧）这题特征太明显了

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
struct Node{
    long long l,r,mul,len,lazy;
}t[400010];
long long n,m,a[100010],mo[100010],ten[100010];
void pushup(long long p){
    t[p].mul = (t[p*2].mul*ten[t[p*2+1].len]%mod+t[p*2+1].mul)%mod;
}
void pushnow(long long p,long long v){
    t[p].mul = mo[t[p].len]*v%mod;
    t[p].lazy = v;
    t[p].lazy%=mod;
}
void pushdown(long long p){
    if(t[p].lazy!=-1){
        pushnow(p*2,t[p].lazy);
        pushnow(p*2+1,t[p].lazy);
        t[p].lazy = -1;
    }
}
void build(long long p,long long l,long long r){
    t[p].lazy = -1;
    t[p].l = l;
    t[p].r = r;
    t[p].len = t[p].r-t[p].l+1;
    if(l==r){
        t[p].mul = a[l];
        return;
    }
    long long mid = (t[p].l+t[p].r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);
}
void update(long long p,long long l,long long r,long long v){
    if(l<=t[p].l&&t[p].r<=r){
        pushnow(p,v);
        return;
    }
    pushdown(p);
    long long mid = (t[p].l+t[p].r)>>1;
    if(r<=mid){
        update(p*2,l,r,v);
    }else if(l>mid){
        update(p*2+1,l,r,v);
    }else{
        update(p*2,l,mid,v);
        update(p*2+1,mid+1,r,v);
    }
    pushup(p);
}
long long query(long long p,long long l,long long r){
    if(l<=t[p].l&&t[p].r<=r) 
        return t[p].mul%mod;
    pushdown(p);
    long long mid = (t[p].l+t[p].r)>>1;
    if(r<=mid)return query(p*2,l,r);
    if(l>mid)return query(p*2+1,l,r);
    int ans1 = query(p*2,l,mid),ans2 = query(p*2+1,mid+1,r);
    return (ans1*ten[min(t[p].r,r)-mid]%mod+ans2%mod)%mod;
}
int main(){
    freopen("bigint.in","r",stdin);
    freopen("bigint.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    mo[0] = 0;
    ten[0] = 1;
    for(int i = 1;i<=n;++i){
        mo[i] = (mo[i-1]<<3)%mod+(mo[i-1]<<1)%mod+1;
        mo[i]%=mod;
        ten[i] = (ten[i-1]<<3)%mod+(ten[i-1]<<1)%mod;
        ten[i]%=mod;
        char ch = getchar();
        while(ch<'0'||ch>'9') ch = getchar();
        a[i] = ch-'0';
    }
    build(1,1,n);
    while(m--){
        long long b,x,y,l,r;
        scanf("%lld%lld%lld",&b,&x,&y);
        l = n-y,r = n-x;
        if(b==1) printf("%lld\n",query(1,l,r));
        else{
            long long z;
            scanf("%lld",&z);
            update(1,l,r,z);
        }        
    }
    return 0;
}

T4.D220712B. 小 C 的数组

题目描述

小 C 有一个数组 A，其中第ii个数为 A_iAi​，不过小 C 不太喜欢他的数组。 小 C 定义了可以估计一个数组的美丽度的函数 T：

T(A)=\text {max}_{i=2}^n|A_i-A_{i-1}|T(A)=maxi=2n​∣Ai​−Ai−1​∣

小 C 认为 T(A)T(A)的值如果越小，那么 A 数组的美丽度就越大。小 C 认为他现在的数组不太美丽，所以他想要修改一些位置，使得 A 数组的美丽度尽量大。

小 C 会告诉你，他想要修改 k 个位置，每次修改可以把原来位置上的 A_iAi​ 修改为任意值。他想要你告诉他，当 A 数组的美丽度最大的时候，T(A)T(A) 的值等于多少。

输入格式

第一行两个数 n, k。

接下来一行 n 个数，第 i 个数表示A_iAi​。

输出格式

输出一个数，当 A 数组的美丽度最大时 T(A) 的值。

样例

输入数据 1

3 1
-100 0 100

输出数据 1

100

输入数据 2

6 3
1 2 3 7 8 9

输出数据 2

1

更多样例：

array2.in, array2.out

array3.in, array3.out

数据规模与约定

对于 30 % 的数据，n ≤ 100，|Ai| ≤ 10n≤100，∣Ai∣≤10。

对于 70 % 的数据，n ≤ 300，|Ai| ≤ 100n≤300，∣Ai∣≤100。

对于 100 % 的数据，n ≤ 2000，|Ai| ≤ 10^9n≤2000，∣Ai∣≤109。

woc，遇到了我做过的题。现在不会了

不过因为害怕老师抽我讲尊严，我没有抄我的源代码

光明正大的爆零

思路还是二分答案，只不过加了个DP，二分T(A)的值，f数组为第i个元素之后的最小修改次数，n-i-1为i后的部分最大修改次数（减一的原因是第一个端点可视为基准，后面的值依据它来改动），初始化f之后的for循环就是计算i+1及以后的元素的最少修改次数，abs那一句是用来与最大差值m*(j-i)作比较，若小于最大差值，则可以更新当前状态，若大于最大差值，需要修改，所以不能更新当前状态，f[j]+j-i-1是算的当前位置的状态加上后面所需的最大次数的值，f[i]+i则代表i元素之前所需的最大次数与元素之后所需的最小次数的和，若这个小于k则i元素之前所需最小次数与i元素之后所需最小次数的和，即整个数列所需最小次数一定小于k

#include<bits/stdc++.h>
using namespace std;
int n,k,a[2010],f[2010];
bool check(long long m){
    for(int i = n;i>=1;i--){
        f[i] = n-i-1;
        for(int j = i+1;j<=n;j++)
            if(abs(a[j]-a[i])<=m*(long long)(j-i)) 
                f[i] = min(f[i],f[j]+j-i-1);
        if(f[i]+i<=k) return true;
    }
    return false;
}
int main(){
    freopen("array.in","r",stdin);
    freopen("array.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
    long long l = 0,r = 2e9,ans = r;
    while(l<=r){
        long long mid = (l+r)>>1;
        if(check(mid)) r = mid-1,ans = mid;
        else l = mid+1;
    }
    printf("%lld",ans);
    return 0;
}

综上所述，我是蒟蒻

还望大佬指点

恳请大佬顺带指点一下博客如何个性化

2022-10-26 16:28:45

标签：26,校内,int,mid,long,22.10,整数,数组,return
From： https://www.cnblogs.com/cztq/p/16828452.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99