[EOJ]2019 ECNU XCPC March Selection #2_weixin_30768661的博客-程序员秘密

技术标签: 数据结构与算法  

rank 14

solved 2

 

(自闭...其实这次题全都很可做,结果因为E题的严重失误彻底GG了。以后一个题交两三次还没A就一定要想算法的问题了...)

 

A(dp)

题意:有n个人要从A点到B点,已知每个人到达A点的时间。有一辆无限载客量的车,开始时在A点,已知往返时间为m。怎样安排可以使所有人的等待总时间最短。

(dp数组应该开m+TMAX......考场上因为只开了TMAX一直WA)

upsolved

 

B(暴力)

题意:坐标系中有n个点(n<=500,max(x,y)<=1000),求一个含最多白点且不含黑点的矩形,求该矩形的最小面积。

一定有白点在矩形的边界上,因此可以O(n^2)枚举上下边界,通过预处理纵向前缀和,可以用O(x)求出包含最多白点且不含黑点的左右边界。实际上离散化后可以复杂度O(n^3)。

O(n^2logn)的做法?

upsolved

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=1;i<=n;i++)
#define pii pair<int,int>
#define pb push_back 
#define st first
#define nd second
#define mp make_pair


typedef long long LL;

const int N = 1e3+7;
const LL inf =1e18; 

int n,m;

int sum[N][N][2],vis[N],l,R,t,b;

int a[N];

int main(){
    scanf("%d",&n);
    
    l=b=1000;
    
    rep(i,n){
        int x,y;
        char c;
        scanf("%d%d %c",&x,&y,&c);
        x++;
        y++;
        if(c=='H'){
            l=min(l,x);
            R=max(R,x);
            b=min(b,y);
            t=max(t,y);
            sum[x][y][0]++;
            if(!vis[y]){
                a[++m]=y;
                vis[y]=1;
            }
        }
        else {
            sum[x][y][1]++;
        }
    }
    
    sort(a+1,a+1+m);
    
    for(int i=l;i<=R;i++)
        for(int j=b;j<=t;j++){
        sum[i][j][0]+=sum[i][j-1][0];
        sum[i][j][1]+=sum[i][j-1][1];
    }
    
    int maxcnt=0,minarea=1e7;
    
    rep(i,m)
        for(int j=i;j<=m;j++){
            int cnt=0,s=-1,end=-1;
            for(int k=l;k<=R;k++){
                if(sum[k][a[j]][1]-sum[k][a[i]-1][1]){
                    if(cnt>maxcnt){
                        maxcnt=cnt;
                        minarea=(end-s)*(a[j]-a[i]);
                    }
                    else if(cnt==maxcnt&&minarea>(end-s)*(a[j]-a[i])){
                        minarea=(end-s)*(a[j]-a[i]);
                    }
                    cnt=0;
                    s=-1;
                    end=-1;
                }
                else {
                    if(sum[k][a[j]][0]-sum[k][a[i]-1][0]){
                        if(!cnt){
                            s=k;
                        }
                        cnt+=sum[k][a[j]][0]-sum[k][a[i]-1][0];
                        end=k;
                    }
                }
            }
            if(cnt>maxcnt){
                        maxcnt=cnt;
                        minarea=(end-s)*(a[j]-a[i]);
                    }
                    else if(cnt==maxcnt&&minarea>(end-s)*(a[j]-a[i])){
                        minarea=(end-s)*(a[j]-a[i]);
                    }
    }
    if(maxcnt==0)printf("0\n0");
    else printf("%d\n%d",maxcnt,minarea);
}
View Code

 

C(树,暴力)

题意:若一棵点权二叉树(n<=1e6)中所有左右儿子互换后的新树和原树完全相同,则称他为一棵对称二叉树。给出一棵树,求最大的对称二叉子树。

暴力判断每一颗子树,首先要满足左右儿子相等,因此大量判断都只需要O(1),而当需要大量递归判断的时候树只能趋近于平衡二叉树,因此可以证明(?)最差也能O(nlogn)完成判断。

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=1;i<=n;i++)
#define pii pair<int,int>
#define pb push_back 
#define st first
#define nd second
#define mp make_pair


typedef long long LL;

const int N = 1e6+3;
const LL inf =1e18; 

int l[N],r[N],v[N],L[N],R[N],sz[N],can[N];

int ans,n;

void init(int node){
    sz[node]=1;
    if(l[node]!=-1)init(l[node]),sz[node]+=sz[l[node]];
    if(r[node]!=-1)init(r[node]),sz[node]+=sz[r[node]];
}

void dfs(int node,int bef_node){
    if(v[L[node]]!=v[l[bef_node]]||v[R[node]]!=v[r[bef_node]]){
        can[node]=0;
        return ; 
    }
    can[node]=1;
    if(L[node]!=-1){
        dfs(L[node],l[bef_node]);
        if(!can[L[node]])can[node]=0;
    }
    if(R[node]!=-1){
        dfs(R[node],r[bef_node]);
        if(!can[R[node]])can[node]=0;
    }
    if(v[L[node]]!=v[l[bef_node]]||v[R[node]]!=v[r[bef_node]])can[node]=0;
}

int main(){
    scanf("%d",&n);
    rep(i,n)scanf("%d",&v[i]);
    rep(i,n)scanf("%d%d",&l[i],&r[i]);
    rep(i,n)L[i]=r[i],R[i]=l[i];
    init(1);
    rep(i,n){
        can[i]=0;
        if(sz[i]>ans)dfs(i,i);
        if(can[i]&&sz[i]>ans)ans=sz[i];
    }
    printf("%d",ans);
}
View Code

 

D(二分)

题意:有n个人要跳舞(n<=1e4),每个人要跳一定时间,舞池容量为k时,前k个人一起开始跳,有人跳完后第k+1个人加入。给出T,确定最大的k使所有人跳完花费的时间小于等于T。

显然二分k,优先队列判断即可。

(纯签到题,结果开始没发现,去做了自闭的E题...)

2A(1:05)

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=1;i<=n;i++)
#define pii pair<int,int>
#define pb push_back 
#define st first
#define nd second
#define mp make_pair

typedef long long LL;

const int N = 1e4+3;
const LL inf =1e18; 

int n,t;

int a[N];

int check(int k){
    priority_queue<int,vector<int>,greater<int> > q;
    int now=0,id=k;
    rep(i,k)q.push(a[i]);
    while(!q.empty()){
        if(q.top()<=now){
            q.pop();
        }
        else {
            now=q.top();
            q.pop();
        }
        if(id<n)q.push(a[++id]+now);
        if(now>t)return 0;
    }
    return 1;
}

int main(){
    cin>>n>>t;
    int l=1,r=n;
    rep(i,n)cin>>a[i];
    int ans=n;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }

    cout<<ans;
}
View Code

 

E(bfs)

题意:给出一个n*n的矩阵,每走一步需要时间t,每走三步到(x,y)需要时间a[x][y],求从(1,1)到(n,n)的最短时间。

每个点拆成三个点,最基础的bfs即可。

(也是纯签到题...开始不知道为啥写了dfs,T了最后几个点之后一直以为改改常数就能过,结果一改就是两小时T了十几次,直接导致GG,以后最短路一定得写bfs啊啊啊)

17A...(1:52)

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=1;i<=n;i++)
#define pii pair<int,int>
#define pb push_back 
#define st first
#define nd second
#define mp make_pair


typedef long long LL;

const int N = 1e2+3;
const LL inf =1e18; 

const int dx[4]={
     0,1,0,-1};
const int dy[4]={
     1,0,-1,0};


int n,t;

LL a[N][N],mem[N][N][4];

int valid(int x,int y){
    if(x>n||y>n)return 0;
    if(x<1||y<1)return 0;
    return 1;
}

int main(){
    cin>>n>>t;
    rep(i,n)
    rep(j,n){
    cin>>a[i][j];
     }

    rep(i,n)
    rep(j,n)mem[i][j][0]=mem[i][j][1]=mem[i][j][2]=inf;
    
    mem[1][1][0]=0;
    queue< pair<pii,int> > q;
    
    q.push(mp(mp(1,1),0));
    
    
    while(!q.empty()){
        pair<pii,int> h=q.front();
        q.pop();
        int x=h.st.st;
        int y=h.st.nd;
        int step=h.nd;
        for(int i=0;i<4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(valid(nx,ny)&&mem[nx][ny][(step+1)%3]>mem[x][y][step]+t+(step==2? a[nx][ny]:0)){
        q.push(mp(mp(nx,ny),(step+1)%3));
        mem[nx][ny][(step+1)%3]=mem[x][y][step]+t+(step==2? a[nx][ny]:0);
         }
        }
    }
    
    cout<<min(min(mem[n][n][0],mem[n][n][1]),mem[n][n][2]);
}
View Code

 

转载于:https://www.cnblogs.com/xutianshu/p/10497782.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30768661/article/details/95189128

智能推荐

Mac上wireshark无法抓包报错_Chary Liu的博客-程序员秘密

以免自己忘记问题mac打开wireshark抓包报错,显示权限不允许“The capture session could not be initiated on interface ‘en0’ (You don’t have permission to capture on that device).Please check to make sure you have sufficient permissions.If you installed Wireshark using the packa

【问题笔记】Mac无法使用wireshark进行抓包,报错_Steve_Stone的博客-程序员秘密_wireshark开启混杂模式报错

#打开wireshark开启抓包时报错#Mac使用wireshark进行抓包时报错Mac wireshark报错The capture session could not be initiated on interface今天打开wireshark想抓个包,发现打开混杂模式失败,抓不了,报错如下:“The capture session could not be initiated on ...

HBase常用命令(超全超详细)_小财迷,嘻嘻的博客-程序员秘密_hbase命令

一、基本命令打开Hbase Shell:hbase shell1.1获取帮助#获取帮助help#获取命令的详细信息help 'status'1.2查看服务器状态status1.3查看版本信息version二、表操作2.1查看所有的表list2.1创建表命令格式1:create ‘表名’,‘列簇名1’,‘列簇名2’…命名格式2:create ‘表名’,{NAME=&gt;‘列簇名1’},{NAME=&gt;‘列簇名2’}…#创建一张名为Student的表,包含基本信息(ba

FLINK 设计文档_weixin_30653097的博客-程序员秘密

https://cwiki.apache.org/confluence/display/FLINK/Apache+Flink+Homehttps://cwiki.apache.org/confluence/display/FLINK/Flink+Roadmaphttps://cwiki.apache.org/confluence/display/FLINK/Design+Documents...

redis 值字符串前面部分乱码_Spring-RedisTemplate写入数据乱码问题的复现与解决_张氏文武的博客-程序员秘密

org.springframework.data.redis是Spring框架对Redis的默认集成,我们在实际项目中,也经常使用它的RedisTemplate去操作Redis,一般来说没什么问题,但是细心一点的同学会发现,经过这种方法写入redis的数据会出现乱码问题问题复现项目依赖org.springframework.bootspring-boot-starter-weborg.spring...

matlab相关性分析_luxurie的博客-程序员秘密_matlab相关性分析

相关性分析一、皮尔逊相关系数(person)计算公式:样本协方差:Cov(x,y)=∑i=1n(Xi−Xˉ)(Yi−Yˉ)n−1{Cov(x,y)=\frac{\sum_{i=1}^n(X_i-\bar{X})(Y_i-\bar{Y})}{n-1}}Cov(x,y)=n−1∑i=1n​(Xi​−Xˉ)(Yi​−Yˉ)​样本标准差Sx=∑i=1n(Xi−Xˉ)2n−1{S_x=\sqrt{\frac{\sum_{i=1}^n(X_i-\bar{X})^2}{n-1}}}Sx​=n−1∑i=1n​(X_1671465600

随便推点

javac,wsimport不是内部或者外部命令的解决方法win7系统_weixin_30808693的博客-程序员秘密

问题:1. webservice在输入命令的时候wsimport的时候会出现如下错误:wsimport不是内部或者外部命令。2. javac不是内部或者外部命令3 java 就可以显示配置成功。网上搜了一堆,全都是说配置不对,可是我们仔细检查并没有发现什么配置错误,令人发狂!最后找到了方法,整理如下:解决方法:运行cmd在控制台中运行以下命令设置java环境变...

获取设备IP及路由器地址_Mr-hhp的博客-程序员秘密_程序获取设备ip 经过路由器的设备ip

1.获取IP地址的话,网上有许多相关的例子,这里我上传个常用的demo;IP地址源码2.这里我主要还是说下获取路由器地址,在最近的项目上需要用到,所以搜了下google,发现了一个不错的demo,在最下方会上传相应的代码,这里贴出如何调用以实现效果:导入头文件:#import "getgateway.h"#import #import

qt调用import sys库_import sysfrom PyQt5.QtWidgets_weixin_39800331的博客-程序员秘密

该楼层疑似违规已被系统折叠隐藏此楼查看此楼import sysfrom PyQt5.QtWidgets import QMainWindow, QPushButton, QApplicationfrom PyQt5.QtWidgets import (QWidget, QPushButton, QLineEdit,QInputDialog, QApplication)import sysfrom...

如何在Oracle中写出性能优良的SQL语句(一)_shuanggeshi的博客-程序员秘密

[size=small][b]如何能够写出高性能的SQL语句,是对程序员的基本要求。[table]|(1)FROM后面的表的顺序有说法:ORACLE的解析器按照从右到左的顺序处理FROM子句中的表,FROM子句中写在最后的表是基础表。a.你必须选择记录条数最少的表作为基础表。b.如果有3个以上的表连接查询, 那就需要选择交叉表作为基础表, 交叉表是指那个被其他表所引用的表。...

关于pyspark.sql.functions导入时提示未声明的方法的解决办法_JOKER1911的博客-程序员秘密

我以为下载错了版本,然后去看了看官方文档,functions中存在col这个方法排除版本错误后,我在想是否能通过from pyspark.sql.functions import *导入,很遗憾失败了,于是我又尝试了import pyspark.sql.functions as funs在程序中使用funs.col(),发现是可用的,问题成功解决,下面再提供一个国外网友的方法,因为比较复杂我就没试验...

推荐文章

热门文章

相关标签