小田不想打怪兽

光线名字换一个吧！听着肉麻

思路

就是一颗二叉树，用ans1来记录当前怪兽数量，ans2记录当前怪兽血量 递推公式：

$$ans+=ans2*2$$

代码

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

小田的异或炸弹

思路

1. 用差分，分成几行，来进行运算
2. 当f[i][j]%2==1时，就是1！

代码

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

小田的钻石

他哪里有钻石啊，在做白日梦呢

思路

本题要用前缀和与双指针：

1. 将输入的值排序。
2. 计算前缀和后缀（不是正经的）。
3. 找出最佳答案

代码

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

小田抓牛

思路

纯模拟

代码

#include <bits/stdc++.h>
using namespace std;
int a[15][15];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int dfs(int t_i,int t_j,int c_i,int c_j){
	int t=0,c=0,cnt=0;
	while(t_i!=c_i||t_j!=c_j){
		int ti=t_i+dx[t],tj=t_j+dy[t];
		int ci=c_i+dx[c],cj=c_j+dy[c];
		bool nt=0,nc=0;
		if(ti<1||tj<1||ti>10||tj>10||a[ti][tj]==1){
			t++;
			if(t==4) t=0;
			nt=1;
		}
		if(ci<1||cj<1||ci>10||cj>10||a[ci][cj]==1){
			c++;
			if(c==4) c=0;
			nc=1;
		}
		if(nt==0||nc==0){
			if(nt==0){
				t_i=ti,t_j=tj;
			}if(nc==0){
				c_i=ci,c_j=cj;
			}
		}
		cnt++;
		if(cnt==1e7){
			cout <<"0";
			return 0;
		}
	}
	cout <<cnt;
	return 0;
}

int main(){
	freopen("cow.in","r",stdin);
	freopen("cow.out","w",stdout);
	int t_i,t_j,c_i,c_j;
	for(int i=1;i<=10;i++){
		for(int j=1;j<=10;j++){
			char c;
			cin >>c;
			if(c=='*') a[i][j]=1;
			else a[i][j]=0;
			if(c=='T') t_i=i,t_j=j;
			if(c=='C') c_i=i,c_j=j;
		}
	}
	dfs(t_i,t_j,c_i,c_j);
	return 0;
}