正文 

当前位置： 首页 > 开发 > java教程

平时二十二测(代码片段)

edsheeran edsheeran     2023-01-14     742

关键词：

 

技术分享图片

技术分享图片

技术分享图片

技术分享图片

技术分享图片

技术分享图片

技术分享图片

技术分享图片

技术分享图片

技术分享图片

第一题水题未放，今天第二题又读入超时2000*2000的读入要快读啊，上次没长教训

第二题：

图论题.二维前缀和的应用. 

最重要的：技术分享图片

这就是一棵树啊

标算为:对于不包含环的图,连通块数目=点数-边数,所以利用二维前缀和进行预处理,O(1)求出矩形区域内的边数和点数.

技术分享图片 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2005;
int sum[maxn][maxn], row[maxn][maxn], line[maxn][maxn], a[maxn][maxn];
int read()
    int x = 0; int f = 1; char c = getchar();
    while(c<‘0‘||c>‘9‘)if(c==‘-‘)f=-1;c=getchar();
    while(c<=‘9‘&&c>=‘0‘)x=x*10+c-‘0‘;c=getchar();
    return x*=f;

char s[2005];

int main()
    freopen("duty.in","r",stdin);
    freopen("duty.out","w",stdout);
    int N = read(), M = read(), Q = read();
    for(int i = 1; i <= N; i++)
        scanf("%s", s);
        
        for(int j = 1; j <= M; j++)
            a[i][j] = s[j - 1] -‘0‘;
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
        
    
        
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++) 
            if(a[i][j] && a[i+1][j]) line[i][j]++;
            line[i][j] += line[i][j - 1];
        
    for(int i = 1; i <= N; i++)//?
        for(int j = 1; j <= M; j++) line[i][j] += line[i - 1][j];
    
    for(int j = 1; j <= M; j++)
        for(int i = 1; i <= N; i++) 
            if(a[i][j] && a[i][j+1]) row[i][j]++;
            row[i][j] += row[i - 1][j];
        
    for(int j = 1; j <= M; j++)
        for(int i = 1; i <= N; i++) row[i][j] += row[i][j - 1];    
    while(Q--)
        int xl = read(), yl = read(), xr = read(), yr = read();
        int point = sum[xr][yr] - sum[xr][yl-1] - sum[xl-1][yr] + sum[xl-1][yl-1];
        int edge1 = line[xr-1][yr] - line[xr-1][yl-1] - line[xl-1][yr] + line[xl-1][yl-1];
        int edge2 = row[xr][yr-1] - row[xr][yl-1] - row[xl-1][yr-1] + row[xl-1][yl-1];
        //printf("%d %d %d
", edge1, edge2, point);
        printf("%d
", point - edge1 - edge2);
View Code

 

第三题：

推性质：答案就是x[1],x[2]…x[n]这个序列的逆序对个数.

采用经典的树状数组或分治法在O(nlogn)的时间内求出逆序对数目即可.

可以得到n<=100000时的40分.

x[1]=a的数据告诉我们,x[i]=i*a%mod

假设x[i]=x[i-1]+a(也就是x[i-1]+a<mod),且x[i-1]和前面所有数字形成了m个逆序对,同时,除去x[i-1]和x[i]所在的等差数列,x[i]前面的所有数字可以分成k段等差序列,那么x[i]将和前面所有数字组成m-k个逆序对.

原因在于:每段等差序列中必然有一个数字和x[i-1]能组成逆序对,但不能和x[i]组成逆序对.那么每段等差数列的贡献都会减1.

因此我们可以O(1)从x[i-1]的贡献得到x[i]的贡献.

如果x[i]<a,不存在对应的x[i-1],我们需要直接计算它的贡献.前面有i-1个数字,我们数出有多少个数字不产生贡献(即小于x[i]的数字个数),即可求出有多少个数字形成了逆序对.用树状数组维护小于a的所有数值,可以在O(loga)的时间内完成一次这样的计算.小于a的数字至多有a个,所以这一部分的时间复杂度为O(aloga),空间复杂度为O(a)

总的时间复杂度为O(aloga+n)

可以得到x[1]=a的20分.

算法7:

算法6几乎就是满分做法了.现在x[1]!=a,我们只需针对最开始的一段不完整等差数列加一些特判就可以通过本题.

可以得到100分.

算法8:

实际上存在更加优越的算法,复杂度为O(aloga),不需要带有一个O(n)

考虑算法6,7中我们都把整个序列划分为了O(a)段.实际上同一段中所有元素的贡献是一个等差数列的形式,可以直接求和.细节可能较多.

技术分享图片 
#include<bits/stdc++.h>
using namespace std;
const int M = 1e5 + 5;
int c[M], a;

int query(int x)
    int ret = 0;
    x++;
    for( ; x; x -= x&(-x)) ret += c[x];
    return ret;

void add(int x)
    x++;
    for(; x <= a; x += x&(-x)) c[x]++;


int main()
    freopen("fly.in","r",stdin);
    freopen("fly.out","w",stdout);
    int n, mod, x1;
    long long ans=0;
    scanf("%d%d%d%d",&n,&x1,&a,&mod);
    int x = x1;
    int del = 0, cir = 0;
    for(int i = 1; i <= n; i++)
        if(x >= a)
            del -= cir;
            if(x < x1) del++;
            ans += del;
        
        else 
            del = (i-1) - query(x);
            ans += del;
            add(x);
        
        x += a;
        if(x >= mod)
            cir++; x -= mod;
        
    
    printf("%lld
",ans);
View Code

 

今天题难度还不错，但一天考两次我真的受不了了

暑假第十二测(代码片段)

 题解：第一题：打表找规律，从12以后每次加49，我一直在前十找规律，，找了半天，以后还是多打点，学聪明点#include<bits/stdc++.h>#definelllonglongusingnamespacestd;intzl[4]=1,5,10,50;llans[]=0,4,10,20,35,56,83,116,155,198,244,292,341,390,4 查看详情

react学习案例二十二(代码片段)

React学习案例二十二MyComponent.propTypes=//可以声明prop为指定的JS基本数据类型，默认情况，这些数据是可选的optionalArray:React.PropTypes.array,optionalBool:React.PropTypes.bool,optionalFunc:React.PropTypes.func,optional 查看详情

第二十二节——反射(代码片段)

类加载器一、类加载器ClassLoader中的两个方法staticClassLoadergetSystemClassLoader()：返回用于委派的系统类加载器ClassLoadergetParent()：返回父类加载器进行委派例子publicclassClassLoaderDemo publicstaticvoidmain(String[]args) //sta 查看详情

leetcode刷题mysql题解二十二(代码片段)

leetcode刷题MySQL题解二十二题目叙述表：DailySales±------------±--------+|ColumnName|Type|±------------±--------+|date_id|date||make_name|varchar||lead_id|int||partner_id|int|±------------±--------&# 查看详情

vue教程(二十二)$children$ref属性(代码片段)

Vue教程(二十二)children、children、children、ref属性要点模板属性ref可以根据名称获取元素代码实现<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metahttp-equiv="X-U 查看详情

第二十二bbs(代码片段)

1.对评论内容进行评论1.1.增加评论按钮comment_hander.pydefrender_tree_node(tree_dic,margin_val):html=""#展示子集评论fork,vintree_dic.items():#合成评论、日期、用户名及评论按钮ele="<divclass=‘comment-node‘style=‘margin-left:%spx‘>"%mar 查看详情

beatsmetricbeat快速入门（二十二）(代码片段)

Metricbeat介绍　　Metricbeat是一种轻量级的托运人，可以将其安装在服务器上，以定期从操作系统和服务器上运行的服务收集指标。Metricbeat会收集它收集的度量标准和统计信息，并将其运送到指定的输出，例如Elasticsearch或Logstash。... 查看详情

408数据结构与算法—归并排序（二十二）(代码片段)

【408数据结构与算法】—归并排序（二十二）一、归并排序基本思想基本思想：将两个或两个以上的有序子序列归并为一个有序的序列。在内部排序中，通常采用的是2-路归并排序归并排序（MergeSort）就是... 查看详情

408数据结构与算法—归并排序（二十二）(代码片段)

【408数据结构与算法】—归并排序（二十二）一、归并排序基本思想基本思想：将两个或两个以上的有序子序列归并为一个有序的序列。在内部排序中，通常采用的是2-路归并排序归并排序（MergeSort）就是... 查看详情

平时二十测(代码片段)

    题解；第一题：#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintM=2e5+5;constllP=1e9+7;llksm(lla,llb)llret=1;for(;b;b>>=1,a=a*a%P)if(b&1)ret=ret*a%P;r 查看详情

第二十二课单链表的具体实现(代码片段)

本节目标：添加LinkList.h文件：1#ifndefLINKLIST_H2#defineLINKLIST_H34#include"List.h"5#include"Exception.h"67namespaceDTLib8910template<typenameT>11classLinkList:publicList<T>1213protected:14struct 查看详情

爬虫学习笔记（二十二）——mitmproxy(代码片段)

文章目录一、简介和安装1.1、概念和作用1.2、安装1.3、工具介绍二、设置代理2.1、PC端设置代理2.2、PC端安装证书2.3、移动端设置代理三、mitmdump3.1、插件使用3.2、常用事件3.2.1、request事件3.2.2、response事件3.3、下载图片一、简介... 查看详情

px4模块设计之二十二：flightmodemanager模块(代码片段)

PX4模块设计之二十二：FlightModeManager模块1.FlightModeManager简介2.FlightModeManager启动3.FlightModeManager模块重要实现3.1custom_command3.2print_usage3.3instantiate3.4task_spawn3.4init3.5Run3.6start_flight_task4.Fl 查看详情

easyclickhtmlui第二十二节jquery事件代理(代码片段)

EasyClickHtmlUI第二十二节jQuery事件代理事件代理介绍事件代理就是利用事件冒泡的原理(事件冒泡就是事件会向它的父级一级一级传递),把事件加到父级上，通过判断事件来源，执行相应的子元素的操作，事件代理首先可... 查看详情

alink(二十二)：特征离散化简介(代码片段)

来源：https://blog.csdn.net/weixin_39552874/article/details/1123256291特征离散化方法和实现特征离散化指的是将连续特征划分离散的过程：将原始定量特征的一个区间一一映射到单一的值。在下文中，我们也将离散化过程表述为分箱(Binning)... 查看详情

实现图像压缩神经网络二十二(代码片段)

BP神经网络压缩的实现>>%基于BP神经网络的图像压缩clearallrng(0)%%压缩率控制K=4;N=2;row=256;col=256;%%输入数据I=imread('lena.bmp');%统一将形状转换为row*colI=imresize(I,[row,col]);%%划分图像块，形成K^2*N的 查看详情

实现图像压缩神经网络二十二(代码片段)

BP神经网络压缩的实现>>%基于BP神经网络的图像压缩clearallrng(0)%%压缩率控制K=4;N=2;row=256;col=256;%%输入数据I=imread('lena.bmp');%统一将形状转换为row*colI=imresize(I,[row,col]);%%划分图像块，形成K^2*N的 查看详情

《pyinstaller打包实战指南》第二十二节单文件模式打包playwright(代码片段)

第二十二节单文件模式打包Playwright打包时解决掉的问题：ImportError:DLLloadfailedwhileimporting_greenlet:动态链接库(DLL)初始化例程失败。Executabledoesn\'texistat C:\\Users\\user\\Desktop\\la_vie\\dist\\belle\\playwright\\driver\\pac 查看详情