A. 小田不想打怪兽

题目类型：循环模拟

思路

可以在每次循环中将怪物数量乘二，再将总次数加怪物数量乘四。

代码

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

这道题我在写的时候将

freopen("aoteman.in","r",stdin);  
freopen("aoteman.out","w",stdout);

写成

freopen("aoteman.in","r",stdin);  freopen("aoteman.in","w",stdout);

了。 所以下次要仔细检查，一定不能再犯这种低级的错误了。

B. 小田的异或炸弹

题目类型：差分

思路

这里分享两种做法。

暴力模拟（40分）

• 初始化，将a[i][j]定义为0。
• 循环，用曼哈顿距离公式来判断。
• 若判断满足，则取反。
• 循环，用计数器判断a[i][j]是否=1；
• 若判断满足，计数器++。
• 最后输出答案即可。

则代码为：

#include<bits/stdc++.h>
using namespace std;
const int N=3e3+10;
int a[N][N];
long long ans;
int main(){
	freopen("boom.in","r",stdin);
	freopen("boom.out","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			a[i][j]=0;
		}
	}
	while(m--){
		int x,y,r;
		cin>>x>>y>>r;
		for(int i=1;i<=n;i++){
		    for(int j=1;j<=n;j++){
			    if(abs(x-j)+abs(y-i)<=r){
			    	if(a[i][j]==1) a[i][j]=0;
			    	else a[i][j]=1;
				}
		    }
	    }
	}
	for(int i=1;i<=n;i++){
	    for(int j=1;j<=n;j++){
	    	if(a[i][j]==1) ans++;
		}
	}
	cout<<ans;
	return 0;
}

用暴力模拟虽然能对，但会超时，只能拿40分（我就是写了暴力模拟，所以只拿了40分），所以要换一种方法。

差分（100分）

通过读题我们可以发现，其实异或1就是总共变换的次数%2，因为异或1会取反，而a[i][j]定义为0。我们再看一下，可以用差分，因为我们要把一个区间+1。

代码

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

这道题我就是写了暴力模拟，所以只拿了40分，下次要注意数据范围。

C. 小田的钻石

题目类型：双指针

思路

首先对于这道题我们可以想到排序，再一个一个1至n去遍历，但是这样有个BAG（漏洞），就是他不能标记整个区间的第一个数，导致有一些样例无法得出正确的答案，就不能AC，我们再看一下题目，就可以想到用双指针来做，那这样的话我们可以先排序，再用l[i]来表示1至i的最大小于等于k的区间数量，用r[i]来表示i+1至n的最大小于等于k的区间数量，来进行遍历（l是1至n，r是n至1），然后遍历1至n，将l[i]+r[i+1]的最大值用ans存起来，最后输出即可。

代码

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

这题在写的时候想到了双指针，但不知道怎么写，要加深对双指针的理解。

D. 小田的01背包

题目类型：位运算

思路

对于这道题目我们只要知道位运算的一个性质就可以解决这个问题了：两个数相&（按位与），结果只会小或相等之前的数，那我们就不用担心体积了，直接求最大值即可。从4e4开始枚举。若(w[j]&i)==i，0x7fffffff&=v[j]，随后再看体积，同时更新最大值。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int v[N],w[N];
int main(){
	freopen("bag.in","r",stdin);
	freopen("bag.out","w",stdout);
	int n,k,a;
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=4e4;i>=0;i--){
    	a=0x7fffffff;
    	for(int j=1;j<=n;j++) if((w[j]&i)==i) a&=v[j];
		if(a<=k){
			cout<<i;
			break;
		}
	}
	return 0;
}

这道题目完全没有思路，所以就放弃了，下一次不能轻易放弃。

E. 小田抓牛

题目类型：搜索

思路

这道题目其实就是DFS模版改一下即可。

代码

#include<bits/stdc++.h>
using namespace std;
int a[15][15],dx[4]={-1,0,1,0},dy[4]={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){
			t++;
			if(t==4) t=0;
			nt=1;
		}
		if(ci<1||cj<1||ci>10||cj>10){
			c++;
			if(c==4) c=0;
			nc=1;
		}
		if(a[ti][tj]==1){
			t++;
			if(t==4) t=0;
			nt=1;
		}
		if(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>160000){
			cout<<"0";
			return 0;
		}
	}
	cout<<cnt;
	return 0;
}
int main(){
	freopen("cow.in","r",stdin);
	freopen("cow.out","w",stdout);
	int t_i=0,t_j=0,c_i=0,c_j=0;
	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;
}

这道题在写的时候模版写出来了，但有一个地方没有改，下一次还是要根据题目做出改变。

F. 小田的分数转换

题目类型：模拟

思路

这道题目就是一个大模拟，按题目要求来就行，但是注意判循环节时建议来个次数数组。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int mp[N];
int main(){
	freopen("fs.in","r",stdin);
	freopen("fs.out","w",stdout);
	int n,d;
	cin>>n>>d;
	int a=n%d;
	int b=n/d;
	int sum=0;
	cout<<n/d<<".";
	if(a==0){
		cout<<0;
		return 0;
	}
	if(b==0) sum=1;
	else{
		while(b){
		b/=10;
		sum++;
	    }
	}
	int ans=sum+1,cnt=0;
	vector<int> A;
	memset(mp,-1,sizeof mp);
	while(1){
		if(a==0){
			for(int i=0;i<A.size();i++){
				cout<<A[i];
				ans++;
				if(ans==76){
					cout<<endl;
					ans=0;
				}
			}
			return 0;
		}
		if(mp[a]!=-1){
			for(int i=0;i<=mp[a]-1;i++){
				cout<<A[i];
				ans++;
				if(ans==76){
					cout<<endl;
					ans=0;
				}
			}
			cout<<"(";
			ans++;
			if(ans==76){
				cout<<endl;
				ans=0;
			}
			for(int i=mp[a];i<A.size();i++){
				cout<<A[i];
				ans++;
				if(ans==76){
					cout<<endl;
					ans=0;
				}
			}
			cout<<")";
			ans++;
			if(ans==76){
				cout<<endl;
				ans=0;
			}
			return 0;
	    }
		mp[a]=cnt;
		a*=10;
		A.push_back(a/d);
		a%=d;
		cnt++; 
	}
	return 0;
}

这道题目完全没有思路，所以就放弃了，下一次不能轻易放弃。