搜网站网,平面设计模板素材网站,天猫网站建设目的,网站建设的市场题目目录 A-时间表查询#xff01;解题思路参考代码 B-一起做很甜的梦#xff01;解题思路参考代码 C-翻之解题思路参考代码 D-乘之解题思路参考代码 E-在树上游玩解题思路参考代码 A-时间表查询#xff01; \hspace{15pt} 今天是2025年1月25日#xff0c;今年的六场牛客寒… 题目目录 A-时间表查询解题思路参考代码 B-一起做很甜的梦解题思路参考代码 C-翻之解题思路参考代码 D-乘之解题思路参考代码 E-在树上游玩解题思路参考代码 A-时间表查询 \hspace{15pt} 今天是2025年1月25日今年的六场牛客寒假算法基础集训营中前两场比赛已经依次于 20250121、20250123 举行而后四场比赛将依次于 20250126、20250206、20250208、20250211 举行。 \hspace{15pt} 小歪想知道第 x x x 场比赛是否已经举行你能帮帮他吗
解题思路
直接输出。
参考代码
#includebits/stdc.h
using namespace std;
using i64 long long;
const int N 2e5 10;void solve(){int n;cin n;if(n 2){cout YES\n;}else{cout NO\n;}
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t 1;
// cin t;while(t --){solve();}
}B-一起做很甜的梦 \hspace{15pt} 梦境是由我们的记忆碎片重组后再次演绎的结果。对于一个拥有 n n n 段记忆的人我们可以使用 1 ∼ n 1 \sim n 1∼n 这 n n n 个整数来表示每一段记忆。将这 n n n 段记忆打乱后重新组合就得到了一个梦。 \hspace{15pt} 作为牛客星球的首席梦境研究员牛可乐在研究中发现如果一个梦境中任意连续的 k k k 段记忆其中 1 k n 1 k n 1kn都无法完整还原出一段真实经历时即不构成一个排列这个梦就会特别甜美。这种恰到好处的记忆重组方式让梦境与现实保持着微妙的距离创造出令人陶醉的朦胧美感。 \hspace{15pt} 现在牛可乐想请你帮忙设计一些这样的甜美梦境来继续他的天才研究。 \hspace{15pt} 长度为 n n n 的排列是由 1 ∼ n 1 \sim n 1∼n 这 n n n 个整数、按任意顺序组成的数组其中每个整数恰好出现一次。例如 { 2 , 3 , 1 , 5 , 4 } \{2,3,1,5,4\} {2,3,1,5,4} 是一个长度为 5 5 5 的排列而 { 1 , 2 , 2 } \{1,2,2\} {1,2,2} 和 { 1 , 3 , 4 } \{1,3,4\} {1,3,4} 都不是排列因为前者存在重复元素后者包含了超出范围的数。
解题思路
要求任意连续的子区间都不能构成排列奇数从小到大偶数从大到小输出即可。
参考代码
#includebits/stdc.h
using namespace std;
using i64 long long;
const int N 2e5 10;void solve(){int n;cin n;vectorint ans1,ans2;for(int i 1;i n;i ){if(i 1){ans1.push_back(i);}else{ans2.push_back(i);}}for(auto x : ans1){cout x ;}sort(ans2.begin(),ans2.end(),greaterint());for(auto x : ans2){cout x ;}
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t 1;
// cin t;while(t --){solve();}
}C-翻之 \hspace{15pt} 对于给定的 n n n 行 m m m 列的矩阵每一个元素要么是 ‘0’ \texttt{0} ‘0’要么是 ‘1’ \texttt{1} ‘1’。 \hspace{15pt} 每一轮你可以进行一次以下操作 ∙ \hspace{23pt}\bullet\, ∙选择一行的元素将其全部反置即 ‘0’ \texttt{0} ‘0’ 变为 ‘1’ \texttt{1} ‘1’ ‘1’ \texttt{1} ‘1’ 变为 ‘0’ \texttt{0} ‘0’。 \hspace{15pt} 请你帮助小歪判断若能进行任意多轮操作也可以不进行操作至多能使得多少列的元素均为 ‘1’ \texttt{1} ‘1’。你只需要输出这个最大值。
解题思路
每次操作将一行的元素都会进行反置那么其实对于每一列的元素都会有影响。 所以两列如果能够同时为全1列的话那么必然这两列初始状态就是相同的。 比如下面的一个矩阵
0 0 1 1 1
1 0 0 0 0
1 0 1 1 1
1 0 1 1 0取第三列为1 0 1 1 取第五列为1 0 1 0 无论如何进行操作都无法将第三列和第五列都变为1 1 1 1。 因为每次操作是将两列同一位置的元素进行反置如果同一位置的两个元素不同的话无论如何反置都无法相同。只有相同才能变相同不同必不相同。 所以答案就是取相同列的最大值。
参考代码
#includebits/stdc.h
using namespace std;
using i64 long long;
const int N 2e5 10;
void solve(){int n,m;cin n m;vectorstring s(m 1);for(int i 1;i n;i ){for(int j 1;j m;j ){char c;cin c;s[j] c;}}mapstring,int mp;int ans 1;for(int i 1;i m;i ){mp[s[i]] ;ans max(ans,mp[s[i]]);}cout ans;}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t 1;
// cin t;while(t --){solve();}
}D-乘之 \hspace{15pt} 对于给定的由 n n n 个整数组成的数组 { a 1 , a 2 , … , a n } \{a_1,a_2,\dots,a_n\} {a1,a2,…,an}小龙和小蛇借助于此数组进行游戏。 \hspace{15pt} 游戏步骤如下 1. {\hspace{20pt}}_\texttt{1.}\, 1.小龙选择一个非空区间 [ a , b ] [a, b] [a,b] 2. {\hspace{20pt}}_\texttt{2.}\, 2.小蛇选择一个非空区间 [ c , d ] [c, d] [c,d] 3. {\hspace{20pt}}_\texttt{3.}\, 3.将选中的区间中的全部元素均乘上 k k k得到数组 a ′ a a′ \hspace{15pt} 游戏只进行一轮三个步骤结束后立即停止。 \hspace{15pt} 小龙想要让数组 a ′ a a′ 的元素之和尽可能大小蛇想要让数组 a ′ a a′ 的元素之和尽可能小。假设双方都采取的是最优策略请你计算操作后得到的数组 a ′ a a′ 的元素之和。 \hspace{15pt} 请注意区间 [ a , b ] [a, b] [a,b] 和 [ c , d ] [c, d] [c,d] 可以相交但只结算一次即若某一个位置被小龙和小蛇同时选中依旧只乘一次。
解题思路
一开始用的区间最大值、最小值去做的这题但是好像可以通过最优策略得出结论。 先说结论整个数组乘以k就是答案。 听起来是不是有点神秘但其实通过最优策略确实是这么个道理。 首先第一个人选取的区间肯定是最利于他自己的那么剩下的区间可能是0个、1个、2个就是不利于第一个人的但是一定是利于第二个人的。并且题目说了两个人取得区间交集不会重复计算那么无论在第一个人取了区间后剩下多少个区间第二个人都可以把剩下的区间当作一个区间来取走。 所以在两个人的最优策略下整个数组的元素会刚好被使用一次。 参考代码
#includebits/stdc.h
using namespace std;
using i64 long long;
const int N 2e5 10;void solve(){int n,k;cin n k;vectori64 a(n 1);for(int i 1;i n;i ){cin a[i];}i64 ans 0;for(int i 1;i n;i ){ans a[i] * k;}cout ans \n;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t 1;cin t; while(t --){solve();}
}E-在树上游玩 \hspace{15pt} 对于给定的由 n n n 个节点组成的无根树每一条边都可以被染上颜色初始时全部边均为白色。 \hspace{15pt} 现在选中树上 k k k 个不同的点并将它们标记随后定义如果一条树边 ( u , v ) (u, v) (u,v) 满足节点 u u u 和 v v v 同时被标记那么这条树边自动被染为红色不需要花费任何代价。 \hspace{15pt} 现在你可以额外选择一些树边将它们染成红色每染一条边需要花费 1 1 1 点代价。 \hspace{15pt} 请你计算最小的染色代价使得任意一个被标记的点都可以通过被染成红色的边到达至少一个未被标记的点。并输出不同的染色方案数量。
解题思路
用dsu计算红边相连的连通块有几个然后每个连通块的最近子节点的个数相乘就是ans。 每个红圈代表一个连通块蓝色的字表示有几个最近子节点黄色的是哪几个最近子节点。
参考代码
#includebits/stdc.h
#define int long long
using namespace std;
using i64 long long;
const int N 2e5 10;
const int mod 1e9 7;
void solve(){int n,k;cin n k;vectorint sig(n 1);for(int i 1;i k;i ){int x;cin x;sig[x] 1;}vectorvectorint g(n 1);vectorint fa(n 1),cnt(n 1);for(int i 1;i n;i ){fa[i] i;cnt[i] 0;}auto find [](auto find,int x)- int{if(fa[x] ! x){return fa[x] find(find,fa[x]);}return fa[x];};for(int i 1;i n;i ){int u,v;cin u v;if(sig[u] !sig[v]){cnt[find(find,u)] ;}if(sig[v] !sig[u]){cnt[find(find,v)] ;}if(sig[u] sig[v]){int fa1 find(find,u);int fa2 find(find,v);if(fa1 fa2){continue;}cnt[fa1] cnt[fa2];fa[fa2] fa1;}}int ans1 0,ans2 1;for(int i 1;i n;i ){if(sig[i] fa[i] i){ans1 ;ans2 ans2 * cnt[i] % mod;}}cout ans1 ans2 \n;
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t 1;
// cin t;while(t --){solve();}
}
