A-子数整除

该题有视频讲解，故在此只放出代码：

#include<bits/stdc++.h>
using namespace std;
int k;
bool check(int t)
{
int a[5];
for(int i=0;i<5;i++)
{
a[i]=t%10;
t/=10;
}
int x=a[4]*100+a[3]*10+a[2];
int y=a[3]*100+a[2]*10+a[1];
int z=a[2]*100+a[1]*10+a[0];
if(x%k==0&&y%k==0&&z%k==0) return 1;
else return 0;
}
int main()
{
cin>>k;
int flag=0;
for(int i=10000;i<=30000;i++)
{
if(check(i))
{
cout<<i<<endl;
flag=1;
}
}
if(flag==0) cout<<"No";
return 0;
}

B-连续自然数和

解法1：暴力

可以直接用双重循环枚举左右端点，虽然看起来是n^2的时间复杂度，但实际复杂度远远达不到，因为一旦和>=M就会退出循环。

同时，左端点枚举到M/2即可，因为左端点若大于M/2一定找不到解。

#include<bits/stdc++.h>
using namespace std;
int main()
{
int M,sum,i,j;
scanf("%d",&M);
for(i=1; i<=M/2; i++)
{
sum=0;
for(j=i; j<=M; j++)
{
sum+=j;
if(sum>=M) break;
}
if(sum==M) printf("%d %d\n",i,j);
}
return 0;
}

解法2：双指针/尺取法

用i，j代表区间的左右端点。

当sum小于目标值M时，将右端点右移（j++），sum会变大。

当sum大于目标值M时，将左端点右移（i++），sum会变小。

在双指针移动的过程中，如果有sum==M的情况就输出。

因为两个指针都是单调向右移动，也只扫一遍，可以证明时间复杂度为O(n)。

左端点大于m/2时即可停止，因为只要长度为2的连续序列和就一定大于m。

#include<bits/stdc++.h>
using namespace std;
int main()
{
int M;
scanf("%d",&M);
int i=1,j=2,sum=3; //初始化左右端点
while(i<=M/2)
{
if(sum==M)
{
printf("%d %d\n",i,j);
sum-=i;//找到答案后 继续把左端点向右移动
i++;
}
else if(sum<M) //当sum小于目标值M时，将右端点右移
{
j++;
sum+=j;
}
else //当sum大于目标值M时，将左端点右移
{
sum-=i;
i++;
}
}
return 0;
}

解法3：等差数列求和（该方法了解即可）

设首项为 L，末项为 R，那么 {\rm sum}(L,R)=\dfrac{(L+R)(R-L+1)}{2}=M.

即 (L+R)(R-L+1)=2M.

可以把 2M 分解成两个数之积，枚举假设分成了两个数k_1,k_2，我们令 k_1，

可以列一个二元一次方程组\begin{cases} R-L+1=k_1\\ L+R=k_2 \end{cases}​​，

解得 \begin{cases} L=\dfrac{k_2-k_1+1}{2}\\ R=\dfrac{k_1+k_2-1}{2} \end{cases}.

显然当 k_1,k_2​ 一奇一偶 时，L,R 才是整数.

但是 L=R 的情况是被不允许的，

即 \dfrac{k_2-k_1+1}{2}\neq\dfrac{k_1+k_2-1}{2}​，即 k_1\neq1.

#include<bits/stdc++.h>
using namespace std;
int m;
int main()
{
cin>>m;
for(int k1=sqrt(2*m); k1>1; k1--) //枚举k1(注意是k1>1而不是k1>=1)
{
if(2*m%k1==0 && (k1+2*m/k1)%2) //如果K2是整数而且与K1一奇一偶
{
int k2=2*m/k1;
cout<<(k2-k1+1)/2<<" "<<(k1+k2-1)/2<<endl;//输出答案
}
}
return 0;
}

C-数列分段

思路：二分答案+贪心

看到求最大值的最小化，直接联想到二分答案。这道题我们可以很容易知道想答案的最小值为数列中最大的数，答案的最大值为所有数的和，所以据此初始化l和r。

然后就是二分答案的常见模板：

while(l<=r)
{
mid=(l+r)/2;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}

check(mid)函数用于检验mid这个答案是否可能存在，如果可能存在，就说明我们这个答案是可行的，但我们还需要找到最小的可行答案，所以还要在左边区间里去找更小的满足条件的值；如果不可能存在，就说明这个答案太小以至于找不到这种划分方式，所以要在右边区间里去找可行解。

那么现在主要问题是如何快速检验一个答案是否可行，即如何写check函数。

考虑一个贪心的思路，即在保证每一段的和都不超过mid的前提下，数列中的数能加在前一段的就加上，不能则新开一段。对于二分的值mid，我们从数列w从前往后扫，如果这一段的和sum加上当前这个数之后大于了mid，我们就不加，而是新开一段，并使sum=w[i]，总段数cnt++。最后只需判断cnt是否小于m就行了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
ll w[100010];
bool check(ll mid)
{
int cnt=1;
ll sum=0;
for(int i=1; i<=n; i++)
{
if(sum+w[i]>mid)
{
sum=w[i];
cnt++;
}
else sum+=w[i];
}
if(cnt<=m) return 1;
else return 0;
}
int main()
{
ll l=0,r=0,mid,ans;
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
{
scanf("%lld",&w[i]);
l=max(l,w[i]);
r+=w[i];
}
while(l<=r)
{
mid=(l+r)/2;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%lld",ans);
return 0;
}

D-奶酪

思路：搜索

这道题其实是一个比较简单的搜索题，关键在于大家要有一些空间想象能力。

要去上表面，我们首先要找到和下表面相连的空洞，以便我们能够进入到奶酪中去，所以我们要做的第一步就是找到所有与下表面相连的空洞，它们都可以作为搜索的起点。

如何判断一个空洞是否和下表面相连？z<=r即可。同理，和上表面相连，只需要h-z<=r即可。

现在的问题是搜索时，怎么去找到与这个空洞相连的空洞。相连证明这两个球体相交或相切，那么只需要判断这两个空洞球心的距离dist与r的关系：若dist<=2r，这两个空洞相连，我们就可以将这些空洞作为我们可以到达的下一个结点，继续搜索。求dist的方法已经在题目中给出。

直到搜到一个与上表面相连的点，就表明我们已经到达了终点，可以退出循环。

由于只有1000个空洞，为了方便，我们可以预处理出每个洞之间是否相连，并加入对应点的邻接表中；还可以预处理出哪些洞与上表面相连，哪些洞与下表面相连，这样方便我们写代码。

有了这样的思路后，之后用bfs和dfs均可，代码中使用了bfs。

需要注意，代码中使用了dist^2和(2r)^2进行比较以防止出现小数 ，所有需要做平方的变量需要开long long以防越界。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
ll x,y,z;
}P[1010];
struct edge
{
int to,next;
}e[1000010];//注意数组要开到n^2
int n,h;
ll r; //一定注意check函数中要做乘法的变量需要开long long
int book[1010];//搜索时的标记数组
int up[1010];//记录每个空洞是否与上表面相连
int head[1010],k; // 邻接表
queue<int> q;//用于bfs的队列
void clear()
{
k=0;
for(int i=1;i<=n;i++)
{
head[i]=0;
up[i]=0;
book[i]=0;
}
while(!q.empty()) q.pop();
}
bool check(node a,node b)//判断两个空洞是否相连
{
ll dist2=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
//为了避免double的精度误差，这里求的是dist的平方 没有开方
if(dist2<=2*r*2*r) return 1;//相连 由于dist没开方 所以2r要平方
else return 0;//没有相连
}
void adde(int u,int v)
{
k++;
e[k].next=head[u];
e[k].to=v;
head[u]=k;
}
bool bfs()//函数返回是否能从下表面跑到上表面
{
while(!q.empty())
{
int u=q.front();
q.pop();
if(up[u]) return 1;//找到了与上表面相连的点
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(book[v]) continue;//标记过就不用再入队了
q.push(v);
book[v]=1;
}
}
return 0; //到最后都没找到
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>h>>r;
for(int i=1;i<=n;i++) cin>>P[i].x>>P[i].y>>P[i].z;
clear();//要清空上一次用过的数组
for(int i=1;i<=n;i++)
{
if(P[i].z<=r)
{
q.push(i); //如果与下表面相连 就加入bfs队列中作为搜索起点
book[i]=1;//在队列中的点要标记
}
if(h-P[i].z<=r) up[i]=1; //如果与上表面相连
for(int j=1;j<=n;j++)
{
if(check(P[i],P[j])==1)//两个洞相连 就在两点之间连边
{
adde(i,j);
adde(j,i);
}
}
}
if(bfs()) cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}