Ryan_<

最大的感受就是要快！快！快！。。其实div2的第50名和第1700名做出来的题数都是一样的，但是时间差别就很大！

。。比赛之前睡过了，还没有看交互题说明，比赛的时候现场另外做了一道交互题才明白...好在做三道题时用时还正常(可是太弱了!)

7:40-8:50

A.Bear and Five Cards

给定5个正整数,可以去除其中2~3个相同的数,最小化剩余数之和。

去掉的数必须使cnt[a[i]]*a[i] (if cnt[a[i]]>3,cnt[a[i]]=3)最大。

变量比较少,但还是放在数组里比较方便。数组大小要注意。

int a[10],cnt[120],sum,mx;
int main()
{
	sum=0;mx=0;
	mec(a,0);mec(cnt,0);
	F(i,1,5){
		a[i]=read();
		sum+=a[i];
		cnt[a[i]]++;
	}
	F(i,1,5){
		if(cnt[a[i]]>=2 && cnt[a[i]]<=3){
			mx=max(mx,cnt[a[i]]*a[i]);
		}
		if(cnt[a[i]]>3) mx=max(mx,3*a[i]);
	}
	printf("%d\n",sum-mx);
	return 0;
}

B.Bear and Finding Criminals

n个数的01序列,站在K位置,可以知道两侧与K相同距离的数之和.给出该序列,求能够确定该位置上数为1的位置的个数.

从K向两边判断,累计答案当且仅当:

1) 一侧为1,一侧不存在

2)两侧均为1

int main()
{
	n=read();K=read();
	F(i,1,n) a[i]=read();
	int t=min(K-1,n-K);
	ans=a[K];
	F(i,1,t){
		int x=K-i,y=K+i;
		if(a[x]+a[y]==2) ans+=2;
	}
	if(K-1>n-K) F(i,1,K-t-1) ans+=a[i];
	else if(K-1<n-K) F(i,K+t+1,n) ans+=a[i];
	printf("%d\n",ans);
	return 0;
}

题解中的思路更清晰：只需要遍历每个数,判断该数是否加入答案即可!

const int N=100+10;
int n,K,ans;
int a[N];
int main()
{
	n=read();K=read();
	F(i,1,n) a[i]=read();
	ans=0;
	F(i,1,n) if(a[i]){//对于一个存在罪犯的城市,Limak是否可以抓到在该城市的罪犯
		int dis=i-K;
		int j=K-dis;//距离相同的另一个城市的位置 
		if(j<1||j>n||a[i]==a[j]) ans++;
	}
	printf("%d\n",ans);
}

C.Bear and Prime 100

比较simple的交互题！20次询问机会,判断一个[2,100]内的数是否为素数。

原先想着判断是否存在1~√100的两个素因子就可以了,竟然过了pretest!然后比赛结束前20min果断被hack掉,才改过来。。太傻了.

一个数是合数,要么它可以被某个素数的完全平方数整除,要么可以被两个不相同的素数整除.

可以知道,这两个素数一定不会超过50.(if p==2,then q<=50) 

那么只需要对4,9,25,49和15个素数进行判断即可.

另外:素数的完全平方数只需一个即可判断,但是19个数放一块判断两次(一定存在另外一个素因子)也就行了。。

int a[20]={2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49};
char s[5];
bool flag,ok;
int main()
{
	F(i,0,18){
		printf("%d\n",a[i]);
		fflush(stdout);
		scanf("%s",s);
		if(s[0]=='y'){
			if(ok){
				flag=true;
				break;
			}
			else ok=true;
		}
	}
	if(!flag) puts("prime");
	else puts("composite");
	fflush(stdout);
}

学习了一下Python的写法：

from sys import stdout

PRIMES=[x for x in range(2,100) if 0 not in [x%i for i in range(2,x)]]

NORMAL=PRIMES[:15]
SQUARES=[x*x for x in PRIMES[:4]]

for ele in SQUARES:
	print(ele)
	stdout.flush()
	x=input()
	if x=="yes":
		print("composite")
		exit(0)

yes=0
for ele in NORMAL:
	print(ele)
	stdout.flush()
	x=input()
	if x=="yes":
		yes+=1
		
print("prime" if yes <2 else "composite")

D.Bear and Tower of Cubes

给定m<=10^5,要求确定一个X<=m,每次在剩余的数的范围内选择一个最大的完全立方数,

最大化所选数的个数,在此情况下最大化X.

可以证明,设a^3是不大于m(剩余的数)的最大的完全立方数,要得到最优解,只可能是每次取a^3或者(a-1)^3.

则所有可能的a一定不大于10^5。 

递归解决，去最优值即可。

两个答案优先级不同，直接用pair保存，pair类型可直接用max比较。

证明如下:Let's see why.

• If the first block has side a then we are left with m2 = m - first_block = m - a3.
• If the first block has side a - 1 then the initial X must be at most a3 - 1 (because otherwise we would take a block

with side a), so we are left with m2 = a3 - 1 - first_block = a3 - 1 - (a - 1)3

• If the first blocks has side a - 2 then the initial X must be at most (a - 1)3 - 1, so we are left withm2 = (a - 1)3 - 1 - 

first_block = (a - 1)3 - 1 - (a - 2)3.

We want to first maximize the number of blocks we can get with new limit m2. Secondarily, we want to have the

biggest initial X. You can analyze the described above cases and see that the first block with side (a - 2)3 must

be a worse choice than (a - 1)3. It's because we start with smaller X and we are left with smaller m2. The

situation for even smaller side of the first block would be even worse.

pair<LL,LL> ans;
vector<LL> tri;
LL m;
void solve(LL m,LL num,LL val)
{
	if(!m){
		ans=max(ans,make_pair(num,val));
		return;//别忘了! 
	}
	LL t=1;//while(p(t+1)<=m) t++;
	t=upper_bound(tri.begin(),tri.end(),m)-tri.begin()-1;//这样写快了很多! 
	solve(m-p(t),num+1,val+p(t));
	if(t-1>=0) solve(p(t)-1-p(t-1),num+1,val+p(t-1)); 
}
int main()
{
	F(i,0,1e5+5) tri.push_back(1LL*i*i*i);
	m=read();
	solve(m,0,0);
	printf("%lld %lld\n",ans.first,ans.second);
	return 0;
}

E.Bear and Square Grid

n*n(n<=500)的方阵中有障碍和空地,可以将其中k*k的小方阵中的障碍格均变为空地,求所得到的最大连通空地的大小。

dfs预处理出连通块.

bool in(int x,int y)
{
	return 1<=min(x,y) && max(x,y)<=n;
}
void dfs(int x,int y,int cc)
{
	belong[x][y]=cc;
	siz[cc]++;
	F(i,0,3){
		int nx=x+dx[i];
		int	ny=y+dy[i];
		if(in(nx,ny) && g[nx][ny]=='.' && !belong[nx][ny])
			dfs(nx,ny,cc);
	}
}
/***main***/
	F(i,1,n) F(j,1,n){
		if(g[i][j]=='.'&&!belong[i][j]) 
			dfs(i,j,++cnt);
	}	

枚举K*K小方阵的位置和对应答案,每次暴力计算会超时,

预处理出放置在每行第一个的答案，向右滑动更新，处理小方块四周的连通块，计算与其相邻的空地个数。累加答案时减去小方阵覆盖前的空地个数，避免重复计算。时间复杂度O(n*k)。

第一次看很乱乱乱，写起来有些麻烦，弱(。・・)ノ.

const int N=500+10;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
char g[N][N];
int belong[N][N],cnt=0,siz[N*N],C[N*N],s[N][N];
int n,K,S,ans;
bool in(int x,int y)
{
	return 1<=min(x,y) && max(x,y)<=n;
}
void dfs(int x,int y,int cc)
{
	belong[x][y]=cc;
	siz[cc]++;
	F(i,0,3){
		int nx=x+dx[i];
		int	ny=y+dy[i];
		if(in(nx,ny) && g[nx][ny]=='.' && !belong[nx][ny])
			dfs(nx,ny,cc);
	}
}
void ins(int x,int y)
{
	int t=belong[x][y];
	if(!t) return;
	if(!C[t]) S+=siz[t];  
	C[t]++;
}
void del(int x,int y)
{
	int t=belong[x][y];
	if(!t) return;
	C[t]--;
	if(!C[t]) S-=siz[t];
}
int calc(int x,int y)//当前子方阵未被覆盖时空地数量 
{
	return s[x+K-1][y+K-1]-s[x-1][y+K-1]-s[x+K-1][y-1]+s[x-1][y-1];
}
void init()
{
	n=read();K=read();
	F(i,1,n){
		scanf("%s",g[i]+1);
		F(j,1,n){
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
			if(g[i][j]=='.') s[i][j]++;
		}
	}
	F(i,1,n) F(j,1,n){
		if(g[i][j]=='.'&&!belong[i][j]) 
			dfs(i,j,++cnt);
	}	
}
void work()
{
	F(i,1,n-K+1){//枚举行
		S=0;
	//初始状态的答案	
		F(j,1,cnt) C[j]=0;//每个连通块被统计的次数 
		F(j,i-1,i+K)  F(k,1,K) ins(j,k);
		F(j,i,i+K-1) ins(j,K+1);
		ans=max(ans,S+K*K-calc(i,1));//减去重复计算的部分(覆盖部分原空地数) 
	//向右移动更新 
		F(j,2,n-K+1){
			F(k,i,i+K-1) del(k,j-2),ins(k,j+K);
			del(i-1,j-1);
			del(i+K,j-1);
			ins(i-1,j+K-1);
			ins(i+K,j+K-1);
			ans=max(ans,S+K*K-calc(i,j));
		}
	}
	printf("%d\n",ans);                                                                                                                         
}
int main()
{
	init();
	work();
	return 0;
}

经验&&教训：

1、数组越界dev可过编译，但会wrong answer

2、不是电脑/评测机有错,是你自己太"神犇"！

3、顺序考虑,思路更清晰

4、零点之后的比赛一定要早睡,不要错过开始时间。但一旦比赛开始,就不要再想比赛之前的准备是否充分,当场补救也可以！

5、div2的都是带点技巧的暴力,怂个毛线。