签到题

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%02X\n",
                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%02X\n",
                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("%d\n",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("%lld\n", 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;
	}
}