当前位置:网站首页>2022夏暑假每日一题(六)
2022夏暑假每日一题(六)
2022-08-02 06:19:00 【摩卡摩卡~】
一、正方形数组的数目(dfs)
任意门
题意:很基础的dfs,就是给你n个数,然后让你给这些数排序,然后每相邻的两个之和是一个完全平方数,然后问你有多少种解法。
#include <bits/stdc++.h>
using namespace std;
int a[20];
int n,res;
bool st[20];
bool check(int num)
{
int p=(int)sqrt(num);
return p*p==num;
}
void dfs(int u,int last)
{
if(u>=n)
{
res++;
return;
}
for(int i=0;i<n;i++)
{
if(i>0&&!st[i-1]&&a[i]==a[i-1])continue;
if(st[i])continue;
if(check(last+a[i]))
{
st[i]=true;
dfs(u+1,a[i]);//递归下一位置
st[i]=false;
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
st[i]=false;//没有访问过
}
sort(a,a+n);//排序,方便删除重复元素
for(int i=0;i<n;i++)
{
if(i&&a[i]==a[i-1])continue;
st[i]=true;
dfs(1,a[i]);
st[i]=false;
}
cout<<res<<endl;
return 0;
}
二、二叉树(找规律)
任意门
题意:给你一个二叉树,然后再给你两个数,让你找他们的公共父节点。
我的写法:
其实根本都不用建树那些的,只用找到根和左右儿子之间的关系即可。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x,y;
cin>>x>>y;
if(x>y)
{
int res=x;
x=y;
y=res;
}
while(x||y)
{
// cout<<x<<" "<<y<<endl;
if(y==x)
{
cout<<x<<endl;
return 0;
}
if((y-1)%2==0)y=(y-1)/2;
else y/=2;
if(y<x)
{
if((x-1)%2==0)x=(x-1)/2;
else x/=2;
}
}
return 0;
}
然而,y总的更加简洁
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x,y;
cin>>x>>y;
while(x!=y)
{
if(x>y)x/=2;
else y/=2;
}
return 0;
}
三、围圈报数(模拟、链表)
任意门
题意:有n个人开始1,2,3报数,每次报到3的那个人就得退出去,直到所有的人都退出去。
我们可以运用环形链表来求解。
#include <bits/stdc++.h>
using namespace std;
const int N=55;
int ne[N];
int main()
{
int T,n;
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<n;i++)
ne[i]=i+1;
ne[n]=1;
int p=n;
for(int i=0;i<n;i++)
{
p=ne[ne[p]];//每次都是跳两个
cout<<ne[p]<<" ";
ne[p]=ne[ne[p]];
}
cout<<endl;
}
return 0;
}
四、排列与二进制(数论、阶层分解)
任意门
题意:给两个数,看这两个数组合成的排列数中有多少个因子2。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(int n,int m)
{
ll res=0;
for(int i=n-m+1;i<=n;i++)
{
if(i%2==0)
{
int k=i;
while(k)
{
if(k%2!=0)break;
res++;
k/=2;
}
}
}
return res;
}
int main()
{
int n,m;
while(cin>>n>>m,n&&m)
{
ll ans=f(n,m);
cout<<ans<<endl;
}
return 0;
}
阶层分解
y总这道题用的是一个公式,阶层分解
f(n,p)后面的表达式表示的是n!中包含p元素的个数是多少
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(int n,int m)
{
ll res=0;
for(int i=n-m+1;i<=n;i++)
{
if(i%2==0)
{
int k=i;
while(k)
{
if(k%2!=0)break;
res++;
k/=2;
}
}
}
return res;
}
int main()
{
int n,m;
while(cin>>n>>m,n&&m)
{
ll ans=f(n,m);
cout<<ans<<endl;
}
return 0;
}
五、二叉树(图上最短路–dfs,dijkstra、lca最近公共祖先问题)
任意门
题意:二叉树中询问两个结点中的最短距离。
这道题目的数据范围为:
所以,我们只用把数据范围控制到 n 2 n^2 n2以内即可。
树上的两个结点之间的距离是唯一的。所以dfs就可以了。
树上最短路径—》LCA
如果是最近公共祖先(LCA)来做题的话,我们就要找到他们的最近公共节点,然后算出两个点到这个公共节点的距离相加即可。
我们这里就是用最短路径LCA来求的。
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N=1010;
int l[N],r[N],p[N];//左儿子、右儿子、父节点
int dist[N];
void dfs(int u,int d)
{
dist[u]=d;
if(l[u]!=-1)dfs(l[u],d+1);
if(r[u]!=-1)dfs(r[u],d+1);
}
int get_lca(int a,int b)
{
if(dist[a]<dist[b])return get_lca(b,a);
while(dist[a]>dist[b])a=p[a];
while(a!=b)a=p[a],b=p[b];
return a;
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int a,b;
cin>>a>>b;
l[i]=a,r[i]=b;
if(a!=-1)p[a]=i;
if(b!=-1)p[b]=i;
}
dfs(1,0);
while(m--)
{
int a,b;
cin>>a>>b;
int c=get_lca(a,b);
cout<<dist[a]+dist[b]-2*dist[c]<<endl;
}
}
return 0;
}
六、质数(bfs、dfs、试除法、暴力枚举)
题意:即题目,给定一个正整数 X,请你在 X 后面添加若干位数字(至少添加一位数字;添加的数不能有前导0),使得结果为质数,在这个前提下所得的结果应尽量小。
#include <bits/stdc++.h>
using namespace std;
bool is_prime(int x)//试除法
{
if(x<2)return false;
for(int i=2;i*i<=x;i++)
if(x%i==0)return false;
return true;
}
int main()
{
int T;
cin>>T;
while(T--)
{
int x;
cin>>x;
for(int i=1;;i++)
{
string str=to_string(x)+to_string(i);//先用字符串拼接起来
int y=stoi(str);//然后再转化为数字
if(is_prime(y))
{
cout<<y<<endl;
break;
}
}
}
return 0;
}
边栏推荐
- Xgboost报错ValueError:无效的形状:标签(1650 2)
- punch day05
- 【论文精读】Geometric Structure Preserving Warp for Natural Image Stitching
- July 18-July 31, 2022 (Ue4 video tutorials and documentation, 20 hours. Total 1412 hours, 8588 hours left)
- 实验8 VLAN综合实验
- MySql -- 不存在则插入,存在则更新或忽略
- MySQL Advanced SQL Statements (2)
- (Notes are not completed) [Graph Theory] Traversal of graphs
- Redis 常用命令和基本数据结构(数据类型)
- APP专项测试:流量测试
猜你喜欢
Nodejs installation tutorial
rhce homework
yml字符串读取时转成数字了怎么解决
正则表达式的理解学习
【21天学习挑战赛】顺序查找
解决:- SPY: No data found for this date range, symbol may be delisted报错
MySQL high-level statements (1)
DNS resolution process
(Part of it is not understood, and the notes are not completed) [Graph Theory] Difference Constraints
速看!PMP新考纲、PMBOK第七版解读
随机推荐
堡垒机、堡垒机的原理
实例029:反向输出
笔记本开机黑屏提示:ERROR 0199:System Security-Security password retry count exceeded
System.Security.SecurityException: 未找到源,但未能搜索某些或全部事件日志。不可 访问的日志: Security
实例031:字母识词
See the picture to understand | How to choose sales indicators to measure the health of business growth
HCIP 第三天实验
交换部分 VLAN
Neo4j 中文开发者月刊 - 202207期
[21天学习挑战赛——内核笔记](一)——设备树的概述(硬件、目标、效果、文件类型)
Unity Shader学习(七)纹理图像的简单使用
(部分不懂,笔记整理未完成)【图论】差分约束
typescript ‘props‘ is declared but its value is never read 解决办法
Servlet
.NET Static Code Weaving - Rougamo Release 1.1.0
Dataset:机器学习中常用数据集下载链接集合之详细攻略
[npm install error report collection] - npm ERR! code ENOTEMPTY npm ERR! syscall rmdir
Servlet
Node installation and environment configuration
Wuhan 2022 organizing of the high-performance computing added new ecological development of high-performance computing