陕西住房和建设厅网站,西宁网站建设哪家强,江门公司建站模板,企业cms建站系统A - On and OffA - On and Off 题目大意
一个人每天在指定的时间点打开房间的灯#xff0c;并在另一个时间点关闭灯。问题是确定在给定的时间点#xff0c;灯是否亮着。
思路分析
注意时间24小时制#xff0c;同一天和隔夜两种情况 确定给定的时间点是否在灯亮的时间范围…A - On and OffA - On and Off 题目大意
一个人每天在指定的时间点打开房间的灯并在另一个时间点关闭灯。问题是确定在给定的时间点灯是否亮着。
思路分析
注意时间24小时制同一天和隔夜两种情况 确定给定的时间点是否在灯亮的时间范围内。根据题目给出的约束条件可以使用以下逻辑来判断
同一天如果 s 小于等于 x 并且 x 小于 t 隔夜s 大于 t 并且 (x 大于等于 s 或者 x 小于 t)则灯亮。 否则灯不亮。
时间复杂度
O(1)
AC代码
#includeiostream
using namespace std;int main()
{int s, t, x;cin s t x;if ((s x x t) || (s t (x s || x t))){cout Yes endl;}else{cout No endl;}return 0;
}B - Takahashi’s Secret B - Takahashi’s Secret 题目大意
Takahashi有N个朋友他们都有昵称Friend 1, Friend 2, …, Friend N。 有一天Takahashi不小心让他的一个朋友Friend X知道了他的秘密。 对于每个i 1, 2, …, N当Friend i得知秘密时如果Friend Ai还没有得知秘密则他/她会与Friend Ai分享秘密。 最后有多少个Takahashi的朋友会知道这个秘密
思路分析
解题关键:何时终结 直到找到一个已经知道秘密的朋友 可以使用一个布尔数组b记录哪些朋友已经知道秘密。用一个数组a来表示每个朋友所知道的秘密的来源即a[i]表示Friend i得知秘密时他/她从哪个朋友那里得知的。初始时所有朋友都未知秘密即a[i]i。然后从Friend X开始逐步迭代找到秘密的来源直到找到一个已经知道秘密的朋友。
时间复杂度
O(N)
AC代码
#includebits/stdc.h
using namespace std;int main()
{int n,x;cinnx;int a[100001];bool b[100001];// 输入每个朋友的秘密来源for(int i1;in;i)cina[i];int ix;int ans0;do{b[i]true; // 标记当前朋友已知秘密ia[i]; // 更新当前朋友的秘密来源ans;}while(!b[i]); // 直到找到一个已知秘密的朋友coutansendl; return 0;
}C - Final DayC - Final Day 题目大意
N个学生参加了一场为期4天的考试。每天有一个300分的测试总共有1200分。已经过去了头三天的考试现在即将开始第四天的考试。第i个学生1≤i≤N在第j天1≤j≤3上得到了Pi,j分。 对于每个学生确定他/她是否有可能在第四天之后排名前KK。
思路分析
看该学生的总分加上300第四天的最高分是否大于等于排名前K的学生前三天的总分第四天的最低分。
时间复杂度
O(NlogN)
AC代码
#include bits/stdc.h
using namespace std;int main() {int n, k;cin n k; k - 1; // 将KK减去1以便与数组索引对应vectorint p(n); // 定义一个保存每个学生总分的数组for (int x : p) {int a, b, c;cin a b c; x a b c; // 计算每个学生的总分并保存在数组中}vectorint q p; // 复制总分数组sort(begin(q), end(q), greater()); // 对总分数组进行降序排序for (int x : p) {cout (x 300 q[k] ? Yes : No) \n; // 判断每个学生是否有可能在第四天之后排名前k}
}
