2024杭电6

2024-09-03 02:28
文章标签 2024 杭电

本文主要是介绍2024杭电6,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1001.造花(简单版)

题意:
菊花图:n-1个节点都连接同一节点的树。
给定一棵树,删掉一个节点和连向这个点的所有边,使剩下两个连通块都构成菊花图,问是否可以做到。

题解:
菊花图只有中心节点的度可以没有限制,其余节点的度都是1。
要删除一个节点,要求剩下两个连通块,那就只能删掉度为2的节点,剩下两个菊花图,菊花图最多一个度不是1的节点。
所以度不是1的节点数最多为5,如图。
在这里插入图片描述
所以度不是1的节点数大于5就是不可能。

再枚举删除度为2的节点,判断删除节点后的两个连通图是不是菊花图。
可以找到中心点,判断与中心点连接的点的度是不是都是1,特判只是一个点时也是菊花图。

代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+6;
int p[N];
vector<int>a[N],s; void solve()
{int n;cin>>n;int u,v;s.clear();for(int i=1;i<=n;i++){a[i].clear();p[i]=0;}for(int i=1;i<n;i++){cin>>u>>v;a[u].push_back(v);a[v].push_back(u);p[u]++;p[v]++;}int f=0;for(int i=1;i<=n;i++){if(p[i]>=2){s.push_back(i);}}if(s.size()>5){cout<<"No\n";return ;}int x,y,xx,yy;for(auto i:s){if(p[i]!=2)continue;u=a[i][0];v=a[i][1];for(auto j:a[i]){p[j]--;}x=1,y=1;if(p[u]==1){xx=a[u][0];yy=a[u][1];if(xx!=i)u=xx;else u=yy;}	for(auto j:a[u]){if(j==i)continue;if(p[j]!=1){x=0;}}if(p[v]==1){xx=a[v][0];yy=a[v][1];if(xx!=i)v=xx;else v=yy;}	for(auto j:a[v]){if(j==i)continue;if(p[j]!=1){y=0;}}if(x&&y){f=1;break;}for(auto j:a[i]){p[j]++;}}if(f){cout<<"Yes\n";}else cout<<"No\n";
}
signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int T=1;cin>>T;while(T--)solve();
}

1003.飞车狂飙

题意:
给定一个赛道轨道,L代表左转,R代码右转,S代表直形的轨道。
问轨道是否重叠,如果不重叠是否成环。

题解:
模拟一遍,用map存走过的点,假如重复就是重叠了,没有的话,判断是否成环而且发现相同。

代码:

#include <bits/stdc++.h>
#define int long long
using ll = long long;
using PII = std::array<int, 2>;
using namespace std;
const ll INF = 2E18 + 10;
#ifdef __clang__template <typename T>inline int my_lg(T n) {return (n > 0) ? static_cast<int>(log2(n)) : -1;}#define __lg my_lg#define __gcd gcd
#endif
#ifndef ONLINE_JUDGE#include "_debug.h"
#endif
// struct cmp{bool operator()(const int & x, const int &y) const{ return x<y;}};
const int N = 2E6 + 10;PII ds[]={{1,0},{0,1},{-1,0},{0,-1}};void SINGLE_TEST() 
{int n;cin>>n;string s;cin>>s;map<PII,bool> vis;int x=0,y=0;int tow=0;bool ok1=0,ok2=0;for(int i=0;i<n;i++){if(s[i]=='R'){x+=ds[tow][0];y+=ds[tow][1];tow--;if(tow<0)tow+=4;}else if(s[i]=='L'){x+=ds[tow][0];y+=ds[tow][1];tow++;tow%=4;}else{x+=ds[tow][0];y+=ds[tow][1];}if(vis[{x,y}]){ok1=1;}vis[{x,y}]=true;// cerr<<x<<" "<<y<<" "<<tow<<"\n";}if(x==0 && y==0 && tow==0){ok2=1;}if(ok1){cout<<-1<<"\n";}else if(!ok2){cout<<0<<"\n";}else{cout<<1<<"\n";}
}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int SAMPLES = 1;cin >> SAMPLES;for(int CUR=1;CUR<=SAMPLES;CUR++){SINGLE_TEST();}
}

1004.不醒人室

题意:
给定n节课的时间段,m段睡觉的时间段。
睡觉 x x x时间后,会有 2 x 2x 2x的时间不困。
问是否会在上课时间睡觉或者困。

题解:
在上课时间睡觉就是上课时间段,和时间时间段有重合,我们把两个加在一起排序,看是否会有重合部分就行了。
也可以用二分在不困的时间段找到上课时间段,如果每个上课时间段都可以在不困的时间段,而且没有睡觉时间与上课时间重叠就是yes。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef __int128 i128;
typedef long long ll;
typedef double db;const db PI = acos(-1);
typedef array<ll, 2> PII; // vector<PII> a(n + 1);
const ll inf = 2e18 + 10;
const int mod = 998244353;
const int maxn = 2e5 + 10;
bool multi = 1;void Solve() {ll n, m; cin >> n >> m;vector<ll> al(n + 1), ar(n + 1), bl(m + 1), br(m + 1);for(ll i = 1; i <= n; i ++ ) {cin >> al[i] >> ar[i];}for(ll i = 1; i <= m; i ++ ) {cin >> bl[i] >> br[i];}ll res = 1, x;for(ll i = 1; i <= m; i ++ ) {if(br[i] > al[res]) {cout << "No\n"; return ;}if(i < m)x = min(br[i] + 2 * (br[i] - bl[i]), bl[i + 1]);else x = br[i] + 2 * (br[i] - bl[i]);ll pos = lower_bound(al.begin() + res + 1, al.end(), x) - al.begin();if(x < ar[pos - 1]) {cout << "No\n"; return ;}res = pos;}if(res == n + 1)cout << "Yes\n";else cout << "No\n";
}signed main() {// freopen("test.in","r",stdin);  // freopen("code.out","w",stdout);    ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);ll T = 1;if(multi) cin >> T;while(T -- ) {Solve();}return 0;
}

这篇关于2024杭电6的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1131762

相关文章

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

高效录音转文字:2024年四大工具精选!

在快节奏的工作生活中,能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候,一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具! 365在线转文字 直达链接:https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具,它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件,只

2024网安周今日开幕,亚信安全亮相30城

2024年国家网络安全宣传周今天在广州拉开帷幕。今年网安周继续以“网络安全为人民,网络安全靠人民”为主题。2024年国家网络安全宣传周涵盖了1场开幕式、1场高峰论坛、5个重要活动、15场分论坛/座谈会/闭门会、6个主题日活动和网络安全“六进”活动。亚信安全出席2024年国家网络安全宣传周开幕式和主论坛,并将通过线下宣讲、创意科普、成果展示等多种形式,让广大民众看得懂、记得住安全知识,同时还

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(

论文翻译:arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染:一项综述 文章目录 大规模语言模型的基准数据污染:一项综述摘要1 引言 摘要 大规模语言模型(LLMs),如GPT-4、Claude-3和Gemini的快

免费也能高质量!2024年免费录屏软件深度对比评测

我公司因为客户覆盖面广的原因经常会开远程会议,有时候说的内容比较广需要引用多份的数据,我记录起来有一定难度,所以一般都用录屏工具来记录会议内容。这次我们来一起探索有什么免费录屏工具可以提高我们的工作效率吧。 1.福晰录屏大师 链接直达:https://www.foxitsoftware.cn/REC/  录屏软件录屏功能就是本职,这款录屏工具在录屏模式上提供了多种选项,可以选择屏幕录制、窗口

论文翻译:ICLR-2024 PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS

PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS https://openreview.net/forum?id=KS8mIvetg2 验证测试集污染在黑盒语言模型中 文章目录 验证测试集污染在黑盒语言模型中摘要1 引言 摘要 大型语言模型是在大量互联网数据上训练的,这引发了人们的担忧和猜测,即它们可能已

轻松录制每一刻:探索2024年免费高清录屏应用

你不会还在用一些社交工具来录屏吧?现在的市面上有不少免费录屏的软件了。别看如软件是免费的,它的功能比起社交工具的录屏功能来说全面的多。这次我就分享几款我用过的录屏工具。 1.福晰录屏大师 链接直达:https://www.foxitsoftware.cn/REC/  这个软件的操作方式非常简单,打开软件之后从界面设计就能看出来这个软件操作的便捷性。界面的设计简单明了基本一打眼你就会轻松驾驭啦

梳理2024年,螺丝钉们爱用的3款剪辑软件

这年头,视频到处都是,就跟天上的星星一样数不清。不管你是公司里的新面孔,还是职场上的老狐狸,学会怎么剪视频,就好比找到了赢的秘诀。不管是给上司汇报工作,展示你的产品,还是自己搞点小视频记录生活,只要是剪辑得漂亮,肯定能一下子吸引大家的目光,让人记得你。咱们今天就来侃侃现在超火的三款视频剪辑工具,尤其是PR剪辑,你肯定听说过,这货在剪辑界可是大名鼎鼎,用它剪视频,既专业又麻利。 NO1. 福昕轻松