T1 光

20pt

$n^4$ 枚举每一盏灯的耗电量，然后按照公式计算每一个格子的亮度是否符合要求。

70pt

$n^3$ 枚举三盏灯的耗电量，计算出此时每个格子的亮度，算出每个格子当前亮度与需求亮度的差值，这个差值由第四盏灯来填补。即枚举好三盏灯之后，我们可以 O(1) 算出第四盏灯的最低耗电量。

100pt

本题显然具有二分性，考虑二分答案。假设总共有 $mid$ 的耗电量可以分配给四盏灯，我们考虑如何分配：$n^2$ 枚举对角线的两盏灯的耗电量，假设枚举的是左上角 $a$ 和右下角 $b$。那么我们可以发现，右上角这个格子当前亮度为 $\lfloor \frac a 2 \rfloor + \lfloor \frac b 2 \rfloor$，左下角的格子的亮度也一样。我们可以算出这两个格子的亮度与需求的差值，再将 $mid - a- b$ 的耗电量分配给这两盏灯。

一种减少写代码细节的小技巧是：算出左下角格子的大致耗电量，然后用 for 循环在估计值的附近枚举即可，这样就不需要判断边界条件了。

T2 爬

考虑每个位置每个二进制位对答案的贡献。

例如考虑某一点 A 上的第 m 位二进制对答案的贡献。（第 $m$ 位的权值是 $2^m$）

统计 A 点以及 A 点的直接孩子（只有直接孩子才可以爬到 A 点）中，有多少只蚂蚁的第 M 位二进制是 1，我们把这种蚂蚁称为好蚂蚁，不是 1 的则称为坏蚂蚁。

如果有奇数只好蚂蚁爬到 A 点，那么他们就可以异或出这个数字。假设好蚂蚁的数量为 N，那么这些好蚂蚁爬到 A 点的方案数就是 $C_N^1+C_N^3+C_N^5+...=2^{n-1}$。然后我们还要统计其他对答案没有影响的蚂蚁的方案数，例如坏蚂蚁。或者是压根与 A 点无关的蚂蚁，要记得我们刚刚只是统计所有和 A 点直接相关的蚂蚁是好的还是坏的，但还有很多蚂蚁我们根本没有统计，那些蚂蚁也会形成一些方案。每一只坏蚂蚁都可以向上爬或者不爬两种都行，那么我们这个方案数就是一个2的幂次；还有其他的蚂蚁，也是可以向上爬或者不爬，他的方案数也是 2 的幂次。但是我们要特殊判断根结点不能向上爬的情况，以及 A 点只有一只好蚂蚁的情况（如果某一点只有一只蚂蚁，那么它是不能异或对答案产生贡献的）

T3 字符串

50pt

$O(n^3)$ 的动态规划，dp[i][j][0/1] 表示当前看到第 $i$ 个位置，已经选了 $j$ 个字母 A，上一个是字母 $A/B$。转移的时候要枚举上一个位置 $k$，然后将 $k \sim i$ 这一段全部弄成 A 或者 B。所以 $dp$ 是 $n^3$ 的。

100pt

首先对三条规则进行简单分析

1. 对于规则 3 来说，假设 $c=3$，那么如果想要通过 AB 切换来获得价值，那字符串就应该形如 BBBABBBABBBA 这样，即每 3 个 B 就切换成 A。
2. 对于规则 1.2 来说，把字母放在连续的一段地方，第一次产生价值需要 $a+1$ 个 A 或者 $b+1$ 个 B，第二次及以后产生价值只需要 $a$ 个 A 或者 $b$ 个 B

我们可以枚举 A 和 B 切换了多少次，假定我们切换的方式就是 BBBABBBABBBA，即每一段 A 的长度都为 1，我们又知道 AB 的切换次数，就可以知道现在已经用掉了几个 A，然后我们先考虑把 A 全部用完。

1. 在 BBBABBBA 的形式前面 只需要花费一个 A 就可以拿到一个价值
2. 然后将多余的 A 填充进字符串中，因为每一段 A 的长度都是 1，所以此时本质上是每多 $a$ 个 A，答案 +1。

然后再考虑将剩余的 B 用完。

1. 如果倒数第二个位置是 A 的话，那么最后一个只需要花费一个 B 就能拿到一个价值
2. 例如 $b=4,c=3$，本来我们填充的是 BBBABBBABBBA，根据规则 2，当一段 B 的长度达到 5 的时候又可以使得价值 +1，所以我们尽量将每一段 B 都填充到长度为 5。如果全部填充好了且还有多余的 B，那么每多 $b$ 个 B，答案 +1。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin >> t;
//bbbbabbbba
	while(t--){
		int n,m,a,b,c;
		cin >> n >> m >> a >> b >> c;
		int maxn = 0;
		for(int i = 0; i <= min(n,m / c); i++){
			int sum = 0;
			if(i == 0){
				sum++;
				sum += (n - 1) / a;
				sum += (m - 1) / b;
			}else{
				sum++;
				sum += (i - 1) * 2;
				if(n - i >= 1){
					sum++;
					int x = n - i - 1;
					sum += x / a;
				}
				
				if(c > b){
					sum += (c - 1) / b * i;
				}
				
				if(m - c * i >= 1){
					sum++;
				
					int x = m - i * c - 1;
					int mod = (((c - 1) / b + 1) * b) - (c - 1);
					if(x / mod >= i) sum += i,x -= mod * i;
					else{
						sum += x / mod;
						x -= x / mod * mod;
					}
					sum += x / b;
					
				}
			}
			maxn = max(maxn,sum);
		}
		cout << maxn + 1 << endl;
		
		
		
	}
	return 0;
}

T4 奇怪的函数

测试点 1 ：

$O(nq)$暴力。

测试点 2~6 ：

容易看出这是一个分段函数，形如：

$$F(x) = \begin{cases} A, & \text {x$\leq$ L}\\ x+T, & \text {L<x<R}\\ B, & \text {x $\geq$ R} \end{cases} $$

我们只需要通过二分找到这个分段函数的三个断点，就可以在$O(1)$的时间回答每一个询问了。

测试点 7~11：

最多只有$10$个取$min,max$的位置，那么直接维护$1$操作对应区间内的和，对于每一次询问，分段算答案即可，树状数组可以解决这个问题。

测试点12~16：

可以直接$DDP$来处理取$min$操作，就变成$DDP$模板题了：

对于只有取$min$操作的询问，我们可以构造一个如下的矩阵乘法操作：

$C_{i,j}=\min_{k}(a_{i,k}+b_{k,j})$

对于一个当前的数字$x$与$v$取$min$，我们只需要构造矩阵

$$\begin{bmatrix} 0 & \inf \\ v & 0 \\ \end{bmatrix} $$

即可。

对于一个当前的数字$x$加$v$，我们只需要构造矩阵

$$\begin{bmatrix} v & \inf \\ \inf & 0 \\ \end{bmatrix} $$

即可。

那么对于一次询问$F(x)$，就相当于是让矩阵$[x,0]$依次乘以这些矩阵，由于上述矩阵的乘法依旧满足结合律，我们用线段树维护这些矩阵的乘积即可。

除此之外这个部分分还有一个单纯用线段树维护后续起作用的$min$操作的位置的做法，大致结论是：对于任意一个位置开始向后，最多只有一个位置的取$min$操作生效了，我们维护那个唯一生效的取$min$位置即可，但这是某个验题人的做法，出题人并不清楚细节，所以不展开描述。

测试点1~20：我们知道这是一个分段函数，那么就可以直接在线段树上来维护它了。

参考测试点2~6，我们知道把任意一段区间$[L,R]$的操作按顺序考虑，它都是一个形如测试点2~6题解所示的分段函数，如果我们知道区间$[L,mid]$对应的分段函数，以及区间$[mid+1,R]$对应的分段函数，那么我们可以在$O(3+3)$的时间内求出区间$[L,R]$所对应的分段函数，那么我们就可以直接用线段树来维护这个分段函数，在$O(logn)$的时间里完成一个修改操作的更新，在$O(1)$的时间里回答一次询问。

这个做法最难写的部分是合并两个分段函数，出题人的写法相对比较通用，直接用双指针来扫描两个分段函数的值域， 然后动态的合并它，常数比分类讨论略大。

void pushup(int now)
{
	temp.clear();
	int sz1=f[ls].size(),sz2=f[rs].size();
	int tt=0;
	for (int i=0;i<sz1;i++) //枚举左边的每一个区间 
	{
		int L,R,l,r,v;
		l=f[ls][i].l; r=f[ls][i].r; v=f[ls][i].v;
		if (f[ls][i].tp==1) L=l+v,R=r+v; else L=R=v;
		if (L==R && L>MAX) continue;
		
		if (R>MAX) {int len=R-MAX; R-=len; r-=len;} //如果超过维护的区间，就给他们减掉

		while (tt<sz2 && f[rs][tt].r<L) tt++; //找到第一个跟你相交的区间

		if (f[ls][i].tp==2)//特例1：l,r的取值区间是单点，则直接处理掉 
		{
			int zhi;
			if (f[rs][tt].tp==2) 
			{
				zhi=f[rs][tt].v;
			}
			else
			{
				zhi=L+f[rs][tt].v;
			}
			temp+=nod(l,r,2,zhi); 
			continue;
		}
		
		//l,r-->L,R
		while (l<=r && tt<sz2)
		{
			int LL,RR; //LL,RR是rs对应的起点区间
			LL=f[rs][tt].l; RR=f[rs][tt].r;		
			int tl,tr;
			tl=max(L,LL); tr=min(R,RR); //tl,tr是你们相交的区间 
			int len=tr-tl+1;
			if (len==0) {tt++; continue;}
			int ll,rr;
			ll=l+(tl-L),rr=ll+(tr-tl); 
			if (f[rs][tt].tp==2) //如果你是赋值的单点
			{
				temp+=nod(ll,rr,2,f[rs][tt].v);
				l=rr+1; L=tr+1;
				continue; 
			}
			else //你是区间+操作 
			{
				temp+=nod(ll,rr,1,f[rs][tt].v+v);
				l=rr+1; L=tr+1;
			}
		} 
	}
	
	f[now].clear();
	int flag=0; nod x;
	for (nod tt:temp)
	{
		if (flag==0) {x=tt; flag=1;}
		if (x.tp==tt.tp && x.v==tt.v)
		{
			x.r=tt.r;
			continue;		
		}
		else
		{
			f[now]+=x;
			x=tt;
		}
	}
	f[now]+=x;
}