小田不想打怪兽（模拟）

思路没想到的原因

没有想到模拟，还以为要找规律呢。以后看清题。

思路

定义变量$i$，然后循环直到$2^i-1>n$，最后输出$2^i-1$。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
	freopen("aoteman.in","r",stdin);
	freopen("aoteman.out","w",stdout);
	long long h;
	cin >>h;
	long long n=1;
	for(int i=1;n<=h;i++){
		n=(1<<i)-1;
	}
	cout <<n;
	return 0;
}

小田的异或炸弹（前缀和与差分）

思路没想到的原因

还以为要用异或，后来才发现异或是“障碍物”。以后多审题。

思路

先求出每一行的差分数组，再用一维差分求出轰炸范围，并用差分把轰炸范围里的数字$+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;
}

小田的钻石（模拟）

思路没想到的原因

太难了，没有想出来。以后要多积累模拟。

思路

定义两个辅助数组$l$与$r$，它们的定义如下：

• $l[i]$表示从$1\sim i$最多有多少个钻石放在一起
• $r[i]$表示从$i\sim n$最多有多少个钻石放在一起

代码

#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,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;
	}
	int max_n=0;
	for(int i=n;i>0;i--){
		r[i]=max(r[i+1],r[i]);
	}
	for(int i=1;i<=n;i++){
		max_n=max(l[i]+r[i+1],max_n);
	}
	cout <<max_n;
	return 0;
}

小田的01背包（01背包）

待更新……

小田抓牛（dfs深搜）

思路没想到的原因

当时时间规划还不够，以后要注意规划时间。

思路

纯暴搜，记得加几个特判！

• 判断是否超出边界：$ti<1||tj<1||ti>10||tj>10$或$ci<1||cj<1||ci>10||cj>10$。
• 是障碍物：$a[ti][tj]==1$或$a[ci][cj]==1$。

代码

#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){
            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==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;
}

小田的分数转换（模拟）

待更新……

谢谢