Div2的A和B，是680A和680B
Div2的CDE，是679的A，B和C
给链接：680A
这次比赛，其实算是比较简单的，比赛的时候40分钟搞出来ABC，赛后补题可以补完D和E，div1还是确实不会
需要练1A的能力
A：给5个数字，均不超过100。可以删去两个相同的或者三个相同的，使得和最小
当时wa了一发，就是没有想明白两个和三个的坑点在哪
举两个数据：3 3 3 4 4，这个应该是删去3 3 3，得到的最小和是4+4=8
3 3 3 5 5，这个是删去5 5，得到的最小和是3+3+3=9
所以只需要把数据hash一下，然后判断，是删去三个还是两个的
代码：
int main(){
//input;
while(scanf("%d%d%d%d%d",&t1,&t2,&t3,&t4,&t5)!=EOF){
memset(num,0,sizeof(num));
ans=t1+t2+t3+t4+t5;
num[t1]++;num[t2]++;num[t3]++;num[t4]++;num[t5]++;
for(i=100;i>=1;i--)
if (num[i]>=3) break;
for(j=100;j>=1;j--)
if (num[j]==2) break;
if (i==0&&j==0) cout<<ans<<endl;
else if (i>0&&j==0) cout<<ans-i*3<<endl;
else if (i==0&&j>0) cout<<ans-j*2<<endl;
else cout<<min(ans-i*3,ans-j*2)<<endl;
}
return 0;
}
B：从1到n个节点，你在a这个点上，从x到y的距离是abs（x-y）
t1，t2，t3……，tn表示当前格子是否有罪犯
根据题意，如果你的位置和当前格子的距离是有罪犯的，BCD这个工具就会有反应
所以，只需要枚举距离值就好
细节：要判断位置+距离是不是越界，位置-距离是不是出界
int main(){
//input;
while(scanf("%d%d",&n,&a)!=EOF){
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
if (num[a]==1) ans=1;
else ans=0;
for(int i=1;i<=n;i++)
if (a-i>=1&&a+i<=n&&num[a-i]==1&&num[a+i]==1) ans+=2;
else if (a-i>=1&&a+i>n&&num[a-i]==1) ans++;
else if (a-i<1&&a+i<=n&&num[a+i]==1) ans++;
cout<<ans<<endl;
}
return 0;
}C：典型脑洞题的
题意描述得很困难的样子：电脑随机生成a一个区间在【2，100】内，你猜一个数
你输入x，如果x是a的约数，那么返回yes，否则返回no
猜每个数的时候，最多询问20次，问你是否给出判断方案
这种题，20次，首先想到的是，【2，100】内有多少素数
百度了一下：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97这么多
数一下，不止20个啊，怎么办？有的是没有用的哎，不小于53的素数是不用尝试的
所以：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47共15个依次询问一遍，就可以得到是不是了
这样搞，wa了一发，想想为什么？平方数。素数的平方数会影响结论，即4，9，25，36
对这19个数问一遍，统计yes的个数，不超过1，说明是素数，否则是合数
int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,4,9,25,49};
string str[50];
int flag;
int ans;
int main(){
flag=0;
for(int i=0;i<19;i++){
//fflush(p[i]);
cout<<p[i]<<endl;
cin>>str[i];
if (str[i]=="yes") flag++;
}
if (flag<=1) cout<<"prime"<<endl;
else cout<<"composite"<<endl;
return 0;
}
D：贴个地址就好
自己一开始想的是，删除得越多越好，想用贪心搞。但是不知道标准
其实这个题不要看m最多是1e15，其实立方数就1e6个，然后因为证明的数学规律给剪枝了很大一部分，每一步骤的选择，其实最多就是两种方案，所以，可以直接像贴的题解一样暴力搞好
代码就不贴了，链接中有
E：在n*n的地图中，允许自己添加一个k*k的联通块，求最大的联通的点的数量
这个题，第一想法我是搞对了的，先dfs，把图中的所有的联通块用1，2，3，4，……，x来标记出来，可以知道每一块多大，在哪
之后的呢，就是学习到了其他大神的题解
把k*k的矩阵，平移，在其与外面相连的4条边来统计，即：k*k+外面联通了多少
平移的时候，涉及到重复的问题，设计到k*k的矩阵中原有的数联通块的问题
细节分析见代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=550;
char mp[maxn][maxn];
int cc[maxn][maxn];
int ccsize[maxn*maxn];
int added[maxn*maxn];
int dx[]={0,0,0,1,-1};
int dy[]={0,1,-1,0,0};
int n,k;
bool ok(int x,int y){
if (x>=1&&x<=n&&y>=1&&y<=n) return true;
return false;
}
void dfs(int x,int y,int num){
cc[x][y]=num;
++ccsize[num];
for(int i=1;i<=4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if (ok(nx,ny)&&mp[nx][ny]=='.'&&cc[nx][ny]==0) dfs(nx,ny,num);
}
}
void add(int x,int y,int &ans,int num){
//如果k*k外面的四条边中有联通块
//而且之前没有加过，那么需要算进来
if (ok(x,y)&&mp[x][y]=='.'){
int id=cc[x][y];
if (added[id]!=num){
added[id]=num;
ans+=ccsize[id];
}
}
}
int main(){
//freopen("input.txt","r",stdin);
int i,j,x,y,xlow,ylow;
while(scanf("%d%d",&n,&k)!=EOF){
for(i=1;i<=n;i++) scanf("%s",mp[i]+1);
memset(cc,0,sizeof(cc));
memset(ccsize,0,sizeof(ccsize));
memset(added,0,sizeof(added));
int cnt=0;
//最简单的深搜
//把所有的联通块处理好
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (mp[i][j]=='.'&&cc[i][j]==0)
dfs(i,j,++cnt);
int id=1;
int ans=0;
//开始移动k*k的小矩阵
for(ylow=1;ylow+k-1<=n;ylow++){
//如果k*k里有数，是联通块的一部分
//那么需要先减掉，以免算重复
for(x=1;x<=k;x++)
for(y=ylow;y<ylow+k;y++)
--ccsize[cc[x][y]];
for(xlow=1;xlow+k-1<=n;xlow++){
int tmp=k*k;
for(x=xlow;x<xlow+k;x++){
add(x,ylow-1,tmp,id);//左边的一列
add(x,ylow+k,tmp,id);//右边的一列
}
for(y=ylow;y<ylow+k;y++){
add(xlow-1,y,tmp,id);//上边的一行
add(xlow+k,y,tmp,id);//下边的一行
}
++id;
ans=max(ans,tmp);
if (xlow+k<=n)
for(y=ylow;y<ylow+k;y++){
//这次算完之后，要平移了
//就要把左边的一列的值补回去
//右边的值先删去联通块内的部分
++ccsize[cc[xlow][y]];
--ccsize[cc[xlow+k][y]];
}
}
//这次的k*k全都移动完毕之后
//要把值都恢复回来
for(x=n-k+1;x<=n;x++)
for(y=ylow;y<ylow+k;y++)
++ccsize[cc[x][y]];
}
cout<<ans<<endl;
}
return 0;
}
京公网安备 11010502036488号