知识点模块
1.x=(y2-z2)，x=（y-z）*（y+z）；说明x由两个奇偶性相同的数相乘而得
令y-z=a，y+z=b，消元一下得出2*y=（a+b），因为y为整数，所以a+b为偶数，所以a和b的奇偶性肯定是相同的
2.一个数由两个偶数相乘而得到
那么它一定是4的倍数
题解模块
P8635 [蓝桥杯 2016 省 AB] 四平方和
这题做过两次了，还有3个点超时，注意一下三层循环里要把i那层写成i * i<n,把j那层写成i*i+j * j<n，把k那层写成i * i+j * j +k * k<n
点击查看代码
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
for(int i=0;i*i<n;i++)
{
for(int j=i;i*i+j*j<n;j++)
{
for(int k=j;i*i+j*j+k*k<n;k++)
{
int m=n-i*i-j*j-k*k;
int h=(int)sqrt(m);
if(h*h==m){
cout<<i<<" "<<j<<" "<<k<<" "<<h;
return ;
}
}
}
}
}
int main()
{
int t=1;
while(t--)
{
solve();
}
return 0;
}
P9231 [蓝桥杯 2023 省 A] 平方差
1.其实我们做题总是倾向于按照题目给的思路来，但真正的做题不是这样的，这就考察我们的思维和思考角度了这一题，具体看知识点1。
2.根据知识点1，我们可以得知当x为奇数时，x由1和它本身相乘而得，当x为偶数时，它由两个偶数构成，一个数的两个质因数都是偶数，那么这个数就是4的倍数
3.所以答案就是l和r之间，奇数的个数+4的倍数的个数
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
#define all(v) v.begin(),v.end()
typedef long long ll;
int j(int x)
{
if(!x) return 0;
else return (x+1)/2;
}
int o(int x)
{
return x/4;
}
void solve()
{
int l,r;
cin>>l>>r;
cout<<j(r)-j(l-1)+o(r)-o(l-1);
}
signed main()
{
int t=1;
//cin>>t;
while(t-- ) solve();
return 0;
}
P8605 [蓝桥杯 2013 国 AC] 网络寻路
1.先把每个点连接的图，画出来，每个点和多少个其他的点连接称为节点的度，联通的点固定一下路径，然后看这两个节点所连的其他节点有哪些，尝试枚举一下，其实其他节点就是度数-1。
2.以这个图为例子，我们固定1-2，那么与1连接的点有除2以外的3，4；那么则有4->1->2->3 , 4->1->3->2，那么实际上这样的路径就有（u的度数-1 * v的度数-1），由于是可以双向的，所以还要×2
3.所以开三个数组，d，u，v存度数，和每次的路线的两个点，然后按照上面公式算结果即可
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
#define all(v) v.begin(),v.end()
typedef long long ll;
int p[1005];
void solve()
{
int n,m;
cin>>n>>m;
int d[10005]={0},u[100005]={0},v[100005]={0};
for(int i=1;i<=m;i++){
cin>>u[i]>>v[i];
d[u[i]]++;
d[v[i]]++;
}
int ans=0;
for(int i=1;i<=m;i++)
{
ans+=(d[u[i]]-1)*(d[v[i]]-1)*2;
}
cout<<ans;
}
signed main()
{
int t=1;
//cin>>t;
while(t-- ) solve();
return 0;
}
P8604 [蓝桥杯 2013 国 C] 危险系数
1.要找关键点，其实一个点到另一个点的关键点，可以通过这个点被经过的次数，和总路径的次数比较，如果是相等的，那么就是关键点，可以画图出来理解
2.第一种方法就是简单的dfs遍历，寻找u和v间的总路径数，并统计每个点走过的次数，但是如果不会敲dfs就写不出来
3.第二种方法，是我的天才队友想出来的，可以通过并查集来解决，思路大概就是每次删除一个点以后，重新对所有的点找最终的父亲，如果说这个点被删了导致u和v的父亲不一样，那么这个点就是关键点，也就是删除点后再检查联通性
dfs的写法
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
#define all(v) v.begin(),v.end()
typedef long long ll;
int n,m,u,v,a[1005][1005],ans,sum;
int cnt[1005];
bool st[1005];
void dfs(int x)//x代表遍历的深度
{
if(x==v)
{
sum++;
for(int i=1;i<=n;i++) if(st[i]) cnt[i]++;
}else{
for(int i=1;i<=n;i++)
{
if(a[x][i]==1&&!st[i])
{
st[i]=1;
dfs(i);//搜索这个通的点
st[i]=0;
}
}
}
}
void solve()
{
cin>>n>>m;
while(m--)
{
cin>>u>>v;
a[u][v]=a[v][u]=1;
}
cin>>u>>v;
dfs(u);
if(sum>0){
for(int i=1;i<=n;i++)
{
if(cnt[i]==sum) ans++;
}
cout<<ans-1;
}else cout<<-1;
}
signed main()
{
int t=1;
//cin>>t;
while(t-- ) solve();
return 0;
}
并查集的写法
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
#define all(v) v.begin(),v.end()
typedef long long ll;
int n,m,ans;
int p[1005];
pii a[1005];
int find(int x)
{
return p[x]==x?x:p[x]=find(p[x]);
}
void solve()
{
//点是1 2 3 4 5 不是我们输入这个点对哈 不要理解成点对
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a[i].first>>a[i].second;
}
int u,v;
cin>>u>>v;
for(int i=1;i<=n;i++)
{
iota(p,p+n+1,0);
if(i==u||i==v) continue;
for(int j=1;j<=m;j++){
if(a[j].first==i||a[j].second==i) continue;//这个就是删除操作
int xx=find(a[j].first),yy=find(a[j].second);
p[xx]=yy;
}
//上面删完枚举的点以后 重新找了u和v的父亲
//删完以后如果u和v的父亲不一样了就是不联通了
if(find(u)!=find(v)) ans++;
}
cout<<ans;
}
signed main()
{
int t=1;
//cin>>t;
while(t-- ) solve();
return 0;
}