当前位置:网站首页>2022夏每日一题(一)
2022夏每日一题(一)
2022-07-06 20:48:00 【摩卡摩卡~】
一、校庆(哈希)
4269
题意:首先给校友的身份证,再给来宾的身份证,在来宾的身份证里面找校友的身份证,如果有校友,那么输出最年长的,否则,输出来宾中最年长的。
做法:哈希!熟练掌握!
输入样例:
5
372928196906118710
610481197806202213
440684198612150417
13072819571002001X
150702193604190912
6
530125197901260019
150702193604190912
220221196701020034
610481197806202213
440684198612150417
370205198709275042
输出样例:
3
150702193604190912
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>>n;
unordered_set<string>hash;
while(n--)
{
string name;
cin>>name;
hash.insert(name);
}
cin>>m;
string a,b;
int cnt=0;
while(m--)
{
string name;
cin>>name;
if(hash.count(name))
{
cnt++;
if(a.empty()||a.substr(6,8)>name.substr(6,8))a=name;
}
if(b.empty()||b.substr(6,8)>name.substr(6,8))b=name;
}
cout<<cnt<<endl;
if(cnt)cout<<a<<endl;
else cout<<b<<endl;
return 0;
}
y总评价非常简单的一道题!
二、性感素数(素数)
4268
题意:给一个数N,如果他是性感素数,那我输出比他小于6的一个数,如果不是的话,那就找到一个比他大的最小性感素数并输出。
线性筛
#include<bits/stdc++.h>
using namespace std;
const int N=100000010;
int n;
int primes[N],cnt;
bool st[N];
void get_primes(int n)//线性筛
{
for(int i=2;i<=n;i++)
{
if(!st[i])primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0)break;
}
}
}
int main()
{
scanf("%d",&n);
get_primes(n);
printf("%d\n",cnt);//输出的是线性筛筛到的最大的素数
return 0;
}
最后AC代码。
#include<bits/stdc++.h>
using namespace std;
bool is_prime(int x)//判断是否是素数
{
if(x<2)return false;
for(int i=2;i<=x/i;i++)
if(x%i==0)
return false;
return true;
}
int main()
{
int n;
cin>>n;
for(int i=n-6;i<=n+6;i+=12)
if(is_prime(i)&&is_prime(n))
{
cout<<"Yes"<<endl;
cout<<i<<endl;
return 0;
}
for(int i=n+1;;i++)
if(is_prime(i)&&(is_prime(i+6)||is_prime(i-6)))
{
cout<<"No"<<endl;
cout<<i<<endl;
return 0;
}
return 0;
}
三、链表合并(单链表、模拟)
4273
我们当然是转化为数组来做。
题意:就是一个长的链表和一个短的链表,我们将短的链表翻转,然后将短的链表从前往后隔两个插入长的链表。
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
#define x first
#define y second
int h1,h2,n;
typedef pair<int,int>PII;
int v[N],ne[N];
int main()
{
cin>>h1>>h2>>n;
int add,data,next;
for(int i=0; i<n; i++)
{
cin>>add>>data>>next;
v[add]=data;
ne[add]=next;
}
vector<PII> a,b;
for(int i=h1; i!=-1; i=ne[i])
{
a.push_back({
i,v[i]});
}
for(int i=h2; i!=-1; i=ne[i])
{
b.push_back({
i,v[i]});
}
if(a.size()<b.size())swap(a,b);
vector<PII>c;
for(int i=0,j=b.size()-1; i<a.size()||j>=0; i+=2,j--)
{
c.push_back(a[i]);
if(i+1<a.size())c.push_back(a[i+1]);
if(j>=0)c.push_back(b[j]);
}
for(int i=0; i<c.size(); i++)
{
printf("%05d %d ",c[i].x,c[i].y);
if(i+1<c.size())printf("%05d\n",c[i+1].x);
else puts("-1");
}
return 0;
}
四、后缀表达式(树的遍历)
4274
题意:后序遍历啦!递归调用
#include<bits/stdc++.h>
using namespace std;
const int N=25;
string v[N];
int l[N],r[N],n;
bool st[N];//来判断这个点有没有父节点
void dfs(int rt)
{
cout<<"(";
if(l[rt]!=-1&&r[rt]!=-1)
{
dfs(l[rt]);
dfs(r[rt]);
cout<<v[rt];
}
else if(l[rt]==-1&&r[rt]==-1)
{
cout<<v[rt];
}
else {
cout<<v[rt];
dfs(r[rt]);
}
cout<<")";
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>l[i]>>r[i];
if(l[i]!=-1)st[l[i]]=true;
if(r[i]!=-1)st[r[i]]=true;
}
int root;//来记录根节点
for(int i=1;i<=n;i++)
if(!st[i])
root=i;
dfs(root);
return 0;
}
五、Dijkstra序列(最短路)
4275
dijstra:每次取得当前距离原点最近的点。即dist[i]最小的的点。那么它的dist序列是递增序列。
这道题目的开头每一次都不一样,所以每一次都要重新算一下。
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N],dist[N];
int n,m;
bool st[N];
int q[N];
bool dijkstra()
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
dist[q[0]] = 0;
for (int i = 0; i < n; i ++ )
{
int t = q[i];
for (int j = 1; j <= n; j ++ )
if (!st[j] && dist[j] < dist[t])
return false;
st[t] = true;
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
return true;
}
int main()
{
cin>>n>>m;
int a,b,c;
memset(g,0x3f,sizeof g);
for(int i=0;i<m;i++)
{
cin>>a>>b>>c;
g[a][b]=g[b][a]=c;
}
int k;
cin>>k;
while(k--)
{
for(int i=0;i<n;i++)
cin>>q[i];
if(dijkstra())puts("Yes");
else puts("No");
}
return 0;
}
六、最长算数(双指针、差分)
任意门
题意:给你一个数组,要求你在这个数组找到一个子数组,然后这个要求这个子数组的每相邻的两个数之间的差值是相等的。
双指针可以将我们O(n2)的枚举优化到O(n)
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int a[N];
int n,t;
int main()
{
cin>>t;
for(int cse=0;cse<t;cse++)
{
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
int res=0;
for(int i=0;i<n;i++)
{
int j=i+2;
while(j<n&&a[j]-a[j-1]==a[j-1]-a[j-2])j++;
res=max(res,j-i);
i=j-2;
}
printf("Case #%d: %d\n",cse+1,res);
}
return 0;
}
边栏推荐
猜你喜欢
随机推荐
Construction of Hisilicon universal platform: color space conversion YUV2RGB
Open3d mesh filtering
C# Task拓展方法
Jerry's phonebook acquisition [chapter]
Jericho is in non Bluetooth mode. Do not jump back to Bluetooth mode when connecting the mobile phone [chapter]
变量、流程控制与游标(MySQL)
23.(arcgis api for js篇)arcgis api for js椭圆采集(SketchViewModel)
体会设计细节
About Tolerance Intervals
19.(arcgis api for js篇)arcgis api for js线采集(SketchViewModel)
图形化工具打包YOLOv5,生成可执行文件EXE
VHDL implementation of arbitrary size matrix multiplication
Ubuntu 20 installation des enregistrements redisjson
Que savez - vous de la sérialisation et de l'anti - séquence?
Jerry's RTC clock development [chapter]
Index of MySQL
Leetcode-02 (linked list question)
[dpdk] dpdk sample source code analysis III: dpdk-l3fwd_ 001
复杂因子计算优化案例:深度不平衡、买卖压力指标、波动率计算
太方便了,钉钉上就可完成代码发布审批啦!