杭电第三场题解签到题基本题进阶题高阶题

83 阅读 0 评论 55 点赞

我是靠谱客的博主爱撒娇玫瑰，最近开发中收集的这篇文章主要介绍杭电第三场题解签到题基本题进阶题高阶题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

比赛传送门
作者： fn

签到题

1011题 Segment Tree with Pruning 线段树剪枝

题目大意
给定一棵区间 $[1, n]$ 的线段树，其中最长的叶子结点区间长度不超过 $k$ ，求线段树的结点数。

考察内容
数据结构概念

分析
先通过判断左右长度是否相等判断线段树是不是完全二叉树。假设线段树上完全二叉树部分有 $n$ 层，这部分的结点数就是 $2^{n}-1$ 。如果线段树不是完全二叉树，再加上最后一行的结点数即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t,l1=0,l2=0;
ll n,k,sum[62],x,ans,lp;

ll hight_bit(ll x){
	x= x|(x>>1);              
	x= x|(x>>2);              
	x= x|(x>>4);              
	x= x|(x>>8);              
	x= x|(x>>16);             
	x= x|(x>>32);
	x= x|(x>>64);
	return (x+1) >> 1;        
}

int main(){ // AC
	sum[0]=1;
	for(int i=1;i<=61;i++){
		sum[i]=sum[i-1]*2;
	}
	cin>>t;
	while(t--){
		cin>>n>>k;
		x=n;lp=1;l1=1;l2=1;
		if(k==1){
			cout<<n*2-1<<endl;
			continue;
		}
		while(x>k){
			x=(x+1)/2;
			l1++;
		}
		while(n-lp+1>k){
			lp=(lp+n)/2+1;
			l2++;
		}
		if(l1==l2){
			ans=sum[l1]-1; // 完全 
		}
		else{ // 不完全 
			ans=hight_bit(n/k)*2-1; // 上半部分是完全二叉树，倒数第二层有n-hight_bit(n/k)*k个结点的区间会超过k 
			ans+=(n-hight_bit(n/k)*k)*2; // 每个区间超过k的结点在最下面一层长出两个叶子 
		}
		cout<<ans<<endl;
	}
	return 0;
}

基本题

1007题 Photoshop Layers Photoshop图层

题目大意
背景图层的颜色是 $(R = 0, G = 0, B = 0)$ 。
按顺序给出若干正常图层和渐变图层，正常图层直接覆盖之前的图层，渐变图层 $(R i, G i, B i)$ 会把颜色 $(R p, G p, B p)$ 变为 $(m i n (R p + R i, 255), m i n (G p + G i, 255), m i n (B p + B i, 255))$ 。

进行 $q$ 次询问，每次询问 $[l i, r i]$ 图层的颜色。

考察内容
前缀和

分析
预处理出 $n t [i]$ 表示图层 $i$ 左侧第一个正常图层。对于每个询问 $[l, r]$ ，求出 $r$ 左
侧第一个正常图层 $f r$ ，则中间的部分都是渐变图层，可以用前缀和求出结
果，最后与 255 取最小值。
时间复杂度 $O (n + q)$ 。

细节
读入字母为大写的16进制：

 scanf("%X", &a);

完整代码

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

struct node {
    int b,v[3];
} p[100005];
int t,n,m,nt[100005],pr[100005][3];
int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++) nt[i]=0;
        for(int i=1;i<=n;i++) pr[i][0]=pr[i][1]=pr[i][2]=0;
        for(int i=1,v;i<=n;i++) {
            scanf("%d %X",&p[i].b,&v); // 读入16进制 
            p[i].v[0]=v>>16;
            p[i].v[1]=(v>>8)-(p[i].v[0]<<8);
            p[i].v[2]=v-(p[i].v[1]<<8)-(p[i].v[0]<<16);
            
            if(p[i].b==1) { // 正常图层 
                pr[i][0]=pr[i][1]=pr[i][2]=0;
                nt[i]=i;
            } else { // 渐变图层 
                nt[i]=nt[i-1];
                pr[i][0]=pr[i-1][0]+p[i].v[0];
                pr[i][1]=pr[i-1][1]+p[i].v[1];
                pr[i][2]=pr[i-1][2]+p[i].v[2];
            }
        }
        
        for(int i=1,l,r;i<=m;i++) {
            scanf("%d %d",&l,&r);
            if(nt[r]<l) {
                printf("%02X%02X%02Xn",
                min(pr[r][0]-pr[l-1][0],255),
                min(pr[r][1]-pr[l-1][1],255),
                min(pr[r][2]-pr[l-1][2],255)); // 输出16进制 
            } else {
                printf("%02X%02X%02Xn",
                min(p[nt[r]].v[0]+pr[r][0],255),
                min(p[nt[r]].v[1]+pr[r][1],255),
                min(p[nt[r]].v[2]+pr[r][2],255));
            }
        }
    }
}

进阶题

1004题 Game on Plane 飞机上的游戏

题目大意
给出 $n$ 条直线，爱丽丝将在所有的n条直线中选择 $k$ 条直线 $l 1, l 2, . . ., l k$ ，然后鲍勃将画一条直线L，使 $L$ 与 $l 1, l 2, . . ., l k$ 的交点最少。
爱丽丝的选择会让交点尽可能多。

求解 $k = 1, 2, . . ., n$ 时的交点数。

考察内容
思维，复杂度优化

分析
两条直线存在公共点当且仅当它们重合或者它们斜率不同，因此 Bob 的最优策略一定是避
开斜率出现次数最多的那些直线。Alice 为了让 Bob 与尽量多的直线相交，最优策略就是最小
化斜率出现次数的最大值，所以不断从每种斜率的直线中各选一种即可。
时间复杂度 $O (n l o g n)$ 。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>P; // 相当于结构体 
const int N=100005;
int Case,n,i,j,k,f[N];
P a[N]; // 保存分数 
inline int abs(int x){return x>0?x:-x;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main(){
	
  scanf("%d",&Case);
  while(Case--){
  	
    scanf("%d",&n);
    for(i=1;i<=n;i++){
      int x1,y1,x2,y2;
      scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
      int dx=x2-x1,dy=y2-y1;
      if(dx==0)dy=1; // 斜率不存在 
      else if(dy==0)dx=1; // 斜率为0 
      else{
        if(dx<0)dx=-dx,dy=-dy; // 规定分母非负 
        int d=gcd(abs(dx),abs(dy));
        dx/=d,dy/=d; // 化最简分数 
      }
      a[i]=P(dx,dy); 
    }
    sort(a+1,a+n+1); // pair可以直接sort
	 
    for(i=1;i<=n;i++)f[i]=0; // 初始化f数组 
    
    for(i=1;i<=n;i=j){ // i指向一个斜率 
      for(j=i+1;j<=n&&a[i]==a[j];j++); // j指向i后面第一个 数值与i指向的斜率不同的 斜率 
      
      for(k=1;k<=j-i;k++)f[k]++;
    }
    
    for(i=j=1;i<=n;i++){
      while(f[j]==0)j++; // 跳过取完的数组 
      f[j]--; // 从f[j]取一个，此时最多j条平行线 
      printf("%dn",i-j); 
    }
  }
}

高阶题

1005题 Kart Race 卡丁车比赛

题目大意
地图由 $n$ 个不同的十字路口和 $m$ 条单行道组成。其中第i个交叉口位于 $(x i, y i)$ 。街道网络中没有循环，人们只能开到一些 $x$ 坐标值严格较大的交叉口。街道只能在交叉口相交。

比赛将从第 1 个交叉点开始，在第 $n$ 个交叉点结束。选手们可以自己选择路线，但他们只能沿着地图上标记的街道行驶。保证一个人可以从 1 到达任何地方，而任何地方都可以到达 $n$ ，所以任何路线都是有效的。

每个路口都有一个设置横幅的位置，如果你选择在第 $i$ 个路口设置横幅，比赛公司就会得到 $w i$ 利润。你是比赛公司的一个中间人，工作是选择一些路口设置横幅，使总利润达到最大。因为没有赛车手愿意看到多于一条的横幅，所以对于从 1 到 $n$ 的每一条可能的路线，最多选择一个交叉口。

如果有多个最优解，输出字典序最小的。

样例输入

样例输出

考察内容
主席树，树状数组，dp

分析
从 1 号点开始 DFS 整个图，并把出栈序列记下来，那么若 x 能到达 y，显然 x 晚于 y 出
栈。因为图是平面图，考虑最有代表性的两种遍历方式：顺时针遍历和逆时针遍历，那么可以
得到两个出栈序列。设 $a_{i}$ 表示顺时针遍历图时 i 点的出栈序， $b_{i}$ 表示逆时针遍历图时 i 点的出
栈序，那么 x 能到达 y 当且仅当 $a_{x}$ > $a_{y}$ 且 $b_{x}$ > $b_{y}$ 。

按照题意，选出来的点应当满足两两不可达，因此把 $a_{i}$ 看作横坐标， $b_{i}$ 看作纵坐标，那么
选了 $a_{i}, b_{i})$ 就不能选它左下角以及右上角的所有点，因此选出来的点一定满足从左往右 a 递增
且 b 递减，问题转化为求价值和最大的下降子序列，可以用树状数组优化朴素 DP 在 $O (n l o g n)$
的时间内得到最优解。

对于字典序最小最优解的求解，有一个方法是在 DP 值里直接用长度为 n 的 01 串来记录
当前方案里选了哪些点，转移的时候需要支持字典序大小的比较、拷贝以及把单点从 0 修改成
1。因此考虑使用可持久线段树来记录方案，那么单点修改的时间复杂度为 $O (n l o g n)$ ，比较两个
方案的字典序时根据左子树是否相同来决定往左还是往右递归比较，时间复杂度也为 $O (n l o g n)$ 。
在这里，注意到每个点只会加入一次，因此如果两棵线段树的根节点的指针不同，那么表示的
01 串一定不同，不需要额外维护 $H a s h$ 值。

时间复杂度 $O(n log^2 n)$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005, M = N * 21;
int Case, n, m, i, x, y, w[N], cnt, dfn1[N], dfn2[N], q[N], fin[N]; bool vis[N];
vector<int>g[N];
struct P {
	int x, y;
	P() {}
	P(int _x, int _y) { x = _x, y = _y; }
	P operator-(const P&b)const { return P(x - b.x, y - b.y); }
}a[N], pivot;
int tot, l[M], r[M];
struct E {
	ll sum; int root;
	E() {}
	E(ll _sum, int _root) { sum = _sum, root = _root; }
}bit[N], tmp, ans;
inline ll cross(const P&a, const P&b) { return 1LL * a.x*b.y - 1LL * a.y*b.x; }
inline bool cmp(int x, int y) { return cross(a[x] - pivot, a[y] - pivot)>0; }
int ins(int x, int a, int b, int c) {
	int y = ++tot;
	if (a == b)return y;
	int mid = (a + b) >> 1;
	if (c <= mid)l[y] = ins(l[x], a, mid, c), r[y] = r[x];
	else l[y] = l[x], r[y] = ins(r[x], mid + 1, b, c);
	return y;
}
inline bool smaller(int x, int y) {
	if (x == y)return 0;
	int a = 1, b = n, mid;
	while (a<b) {
		mid = (a + b) >> 1;
		if (l[x] == l[y]) {
			a = mid + 1;
			x = r[x];
			y = r[y];
		}
		else {
			b = mid;
			x = l[x];
			y = l[y];
		}
	}
	return x>y;
}
void go(int x, int a, int b) {
	if (!x)return;
	if (a == b) {
		fin[++cnt] = a;
		return;
	}
	int mid = (a + b) >> 1;
	go(l[x], a, mid);
	go(r[x], mid + 1, b);
}
inline void up(E&a, const E&b) {
	if (a.sum>b.sum)return;
	if (a.sum<b.sum) { a = b; return; }
	if (smaller(b.root, a.root))a.root = b.root;
}
void dfs1(int x) {
	if (vis[x])return;
	vis[x] = 1;
	for (int i = 0; i<g[x].size(); i++)dfs1(g[x][i]);
	dfn1[x] = ++cnt;
}
void dfs2(int x) {
	if (vis[x])return;
	vis[x] = 1;
	for (int i = ((int)g[x].size()) - 1; i >= 0; i--)dfs2(g[x][i]);
	dfn2[x] = ++cnt;
	q[cnt] = x;
}
inline void modify(int x, const E&p) { for (; x <= n; x += x&-x)up(bit[x], p); }
inline E ask(int x) { E t(0, 0); for (; x; x -= x&-x)up(t, bit[x]); return t; }
int main() {
	scanf("%d", &Case);
	while (Case--) {
		scanf("%d%d", &n, &m);
		cnt = 0;
		for (i = 0; i <= n; i++) {
			g[i].clear();
			vis[i] = 0;
			bit[i] = E(0, 0);
		}
		for (i = 1; i <= n; i++)scanf("%d%d%d", &a[i].x, &a[i].y, &w[i]);
		while (m--)scanf("%d%d", &x, &y), g[x].push_back(y);
		for (i = 1; i <= n; i++) {
			pivot = a[i];
			sort(g[i].begin(), g[i].end(), cmp);
		}
		dfs1(1);
		for (cnt = 0, i = 1; i <= n; i++)vis[i] = 0;
		dfs2(1);
		ans = E(0, 0);
		for (i = n; i; i--) {
			x = q[i];
			tmp = ask(dfn1[x]);
			tmp.sum += w[x];
			tmp.root = ins(tmp.root, 1, n, x);
			up(ans, tmp);
			modify(dfn1[x], tmp);
		}
		printf("%lldn", ans.sum);
		cnt = 0;
		go(ans.root, 1, n);
		for (i = 1; i <= cnt; i++)printf("%d%c", fin[i], i<cnt ? ' ' : 'n');
		for (i = 0; i <= tot; i++)l[i] = r[i] = 0;
		tot = 0;
	}
}