T1 小田不想打怪兽

总结

一道简单的打卡题，最终成绩 100 ，但是第一次交了一个稳拿 50 的及其暴力解，而且满分解也是折半的循环乘二，从 $10^9$ 的范围下幸存下来。

错误：没有发现解决每只怪兽与它分裂后的小怪兽的时间的关系，导致只能用朴素的循环计数。

题解

解决每一只怪兽的时间实际上是解决它所分裂的两只小怪兽的次数之和+1，也就是：

$$f(i)=f(i/2)\times 2+1$$

这个公式同时适用于循环和递归的思想，这样就能比较快速地求出解决血量为 $h$ 的怪兽的光线次数。

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e7+5;
int h,res=1;

signed main(){
	freopen("aoteman.in","r",stdin);
	freopen("aoteman.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>h;
	while(h){
		h/=2;
		res*=2;
	}  
	cout<<res-1;
	return 0;
}

T2 小田的异或炸弹

总结

没有提交 ，赛时思路是直接模拟 $m$ 次爆炸，但是想得满分明显超时，而且后来发现所有特殊测试点都没有输出，所以直接放弃提交。

错误：使用基础算法的经验不够，在涉及快速改变区间的问题中没有想到 差分 ，而且直接用了 bool 数组进行异或，想到了但是没有应用异或次数对答案的影响。

题解

由于每个炸弹爆炸会影响一个区间内的所有元素，所以需要使用 差分 算法对一个区间的元素进行快速的修改，又由于炸弹所影响的区间并非矩形，所以并不能使用二维差分，只能使用多个一维差分。

题目中的 异或 运算代表在二进制上：两数不同为 true ，相同为 false ，题目中的二维数组的初始状态都是 0 ，0 异或 1 得到 1 ，1 异或 1 得到 0 ，稍作计算即可发现，当一个元素受到异或运算的次数为奇数次时，得到 1 ，为偶数时，得到 0 。

由上可以知道，我们实际上不需要真的进行异或运算，只需要让每次被爆炸影响的所有元素都加一，最后再判断奇偶计算 1 出现的次数就可以了。

每次爆炸所影响的范围是一个类似菱形的图形，题面里给出了 曼哈顿距离 公式：

$$d=|x_1-x_2|+|y_1-y_2|$$

我们从 $1$ 到 $n$ 枚举可能被影响的第 $i$ 行，$x$ 是爆炸中心的行数，$i$ 是现在的行数，定义一个 $t$ 为 $r-|x-i|$ ，表示当前行被爆炸影响的最远的两个元素的列到爆炸中心的列的距离，由此就可以推出：第一个被影响的元素的列是 $y-t$ ，最后一个被影响的元素的列是 $y+t$ ，现在再用差分公式 $d[l]+=c, d[r+1]-=c$ 来让所有被影响的元素加一。

最后用前缀和公式 $s[i]=s[i-1]+a[i]$ 得出最终的二维数组，再遍历它统计是 1 的元素的数量。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e3+5;
int n,m,x,y,r,cnt;
int s[N][N],d[N][N];

signed main(){
	freopen("boom.in","r",stdin);
	freopen("boom.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	while(m--){
		cin>>x>>y>>r;
		for(int i=1;i<=n;i++){
			int t=r-abs(x-i);
			int ll=y-t,rr=t+y;
			if(t<0) continue;
			if(ll<1) ll=1;
			if(rr>n) rr=n;
			d[i][ll]++;
			d[i][rr+1]--;
		} 
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			s[i][j]=s[i][j-1]+d[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(s[i][j]%2!=0) cnt++;
		}
	}
	cout<<cnt;
	return 0;
}