T1 小田不想打怪兽(暴力)

问题

无(太简单了)

思路（水题讲什么思路)

因为每一次怪物被分裂后都会变为x/2，所以只会出现$log(n)$种体型，只要每次记录下数量和大小即可

附AC代码(本来不想附的)

#include<bits/stdc++.h>
using namespace std;
int h,ans,s=1;
int main()
{
	freopen("aoteman.in","r",stdin);
	freopen("aoteman.out","w",stdout);
	cin>>h;
	while(h)
	{
		ans+=s;
		h/=2;
		s*=2;
	}
	cout<<ans;
	return 0;
}

T2 小田的异或炸弹(差分)

问题

1.时间计算问题：没有考虑暴力的最坏时间复杂度，粗略估计下可以就写了

2.先是代码的问题 其次出现bug没有用草稿纸自己模拟自己推(记事本也行)，那个程序debug完有70分(应该)的

思路

主要难点在于想到用差分优化 想到就很简单了 只要用一个二维数组把若干个一维差分保存下来，再在每次爆炸时更新即可

附AC代码

#include<bits/stdc++.h>
using namespace std;
int cf[3010][3010],n,m;
int main()
{
	freopen("boom.in","r",stdin);
	freopen("boom.out","w",stdout);
	cin>>n>>m; 
	for(int i=1;i<=m;i++)
	{
		int x,y,r;
		cin>>x>>y>>r;
		for(int j=max(1,x-r);j<=min(n,x+r);j++)
		{
			int l=max(y-(r-(abs(j-x))),1),ri=min(y+(r-(abs(j-x))),n);
			cf[j][l]++;
			cf[j][ri+1]--; 
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cf[i][j]=cf[i][j-1]+cf[i][j];
			if(cf[i][j]%2==1) ans++; 
		}
	}
	cout<<ans;
	return 0;
}

T3小田的钻石(双指针)

问题

思路是往双指针的方向走的(后面按我思路走对了) 主要是代码能力问题(最近好像就这俩问题) 就在这两题上debug浪费一个半www

思路

这道题想到思路比较难 但思路其实很简单

主要问题在他有两个展柜 我们可以找到一个分界点 ( 比如 i ~ i +1中间) 那么两个展柜的钻石一定会从 1~i 和 i+1~n 这两个区间中得到 所以我们只需要两个数组分别存下 1 ~ i 和 i ~ n的最大可放宝石数在便利一下即可

附AC代码（有点长）

#include<bits/stdc++.h>
using namespace std;
int a[100010],d1,d2,n,k,l[100010],r[100010];
int main()
{	
    freopen("demon.in","r",stdin);
	freopen("demon.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	for(int i=1,j=1;j<=n;)
	{
		while(j+1<=n&&a[j+1]-a[i]<=k)
		{
			j++;
		}
		l[j]=j-i+1;
		j++;
		if(j>n) break;
		while(a[j]-a[i]>k&&i<=j)
		{
			i++;
		}
	}
	for(int i=1;i<=n;i++) l[i]=max(l[i],l[i-1]);
	for(int i=n,j=n;j>=1;)
	{
		while(j-1>=1&&a[i]-a[j-1]<=k)
		{
			j--;
		}
		r[j]=i-j+1;
		j--;
		if(j<1) break;
		while(a[i]-a[j]>k&&i>=j)
		{
			i--;
		}
	}
	for(int i=n;i>=1;i--) r[i]=max(r[i],r[i+1]);
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,l[i]+r[i+1]);
//	for(int i=1;i<=n;i++) cout<<l[i]<<" ";//调试代码
//	cout<<endl;
//	for(int i=1;i<=n;i++) cout<<r[i]<<" ";
	cout<<ans;
	return 0;
}

T5小田抓牛（模拟）

题目传送门

总结（自己）

虽然A了 但也是因为数据出水了，死循环判断应该是16万

思路

模拟就行 主要是对-1的计算，因为