挑战赛 26
2025-12-28 22:03:44
发布于：广东
101阅读
0回复
0点赞
原来是挑战赛啊，我还以为是欢乐赛呢。
T1
好的，T1 是一个四舍五入，round 秒了。
namespace cjdst{
void solve(){
double n;
std::cin >> n;
std::cout << int(round(n) + 1e-5) << '\n';
}
}
时间复杂度：。
诶我是不是没用 roundl 啊。算了过了就行。
T2
嗯。
我去我怎么被这题卡了 5min 了还没想好怎么写。
哦就是求每个人总分加上 的排名是吧。
懒得用 std::lower_bound 了，直接上最高礼仪树状数组大炮打蚊子。
又花了 10min 终于写好了。我为什么会在这么简单的题浪费这么多时间。
卧槽怎么 T 了。
哦总分可以为 ，得加一个偏移。和我玩心理博弈是吧。出题人你赢了。
namespace cjdst{
template <typename T>
class Fenwick_Tree{
std::vector <T> tr;
int n;
public:
Fenwick_Tree(){}
Fenwick_Tree(int n){
tr.resize(n + 5, 0);
this -> n = n;
}
void modify(int idx, T val){
for(int i = idx; i <= n; i += (i & (-i))) tr[i] += val;
}
T query(int idx){
T ans = 0;
for(int i = idx; i; i -= (i & (-i))) ans += tr[i];
return ans;
}
};
void solve(){
int n, m;
std::cin >> n >> m;
std::vector <int> a(n + 5);
for(int i = 1; i <= n; i++){
int x, y, z;
std::cin >> x >> y >> z;
a[i] = x + y + z + 1;
}
Fenwick_Tree <int> tr(1505);
for(int i = 1; i <= n; i++){
tr.modify(a[i], 1);
}
for(int i = 1; i <= n; i++){
std::cout << (n - tr.query(a[i] + 300) < m ? "Yes\n" : "No\n");
}
}
}
时间复杂度 。
T3
链表题。
尝试使用 std::list 无果，愤怒地手搓链表。
假设链表结尾的下一个，开头的上一个，指向自身，这样操作 只需要一直遍历到指向的为自身。
操作 就是将 的下一个指向 ， 的上一个指向 。
操作 就是将 的下一个指向 ， 的上一个指向 。
我去怎么这么简单我刚刚是糖人吗。
#include <bits/stdc++.h>
namespace cjdst{
void solve(){
int n, m;
std::cin >> n >> m;
std::vector <int> a(n + 5), b(n + 5);
for(int i = 1; i <= n; i++){
a[i] = i;
b[i] = i;
}
while(m--){
int tmp;
std::cin >> tmp;
if(tmp == 1){
int x, y;
std::cin >> x >> y;
a[x] = y, b[y] = x;
}else if(tmp == 2){
int x, y;
std::cin >> x >> y;
a[x] = x, b[y] = y;
}else{
int idx;
std::cin >> idx;
while(b[idx] != idx) idx = b[idx];
std::vector <int> ans{idx};
while(a[idx] != idx){
idx = a[idx];
ans.push_back(idx);
}
std::cout << ans.size() << ' ';
for(int i:ans) std::cout << i << ' ';
std::cout << '\n';
}
}
}
}
时间复杂度 。
T4
何意味。这啥必做的题啊。
这不就一个 std::lower_bound？
我去怎么只过两个啊。
哦我草我忘排序了。前面忘了，后面忘了，出题人你赢了。
namespace cjdst{
void solve(){
int n, m;
std::cin >> n >> m;
std::vector <int> a(n + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i];
}
std::sort(a.begin() + 1, a.begin() + n + 1);
while(m--){
int val;
std::cin >> val;
std::cout << n - (lower_bound(a.begin() + 1, a.begin() + n + 1, val) - a.begin()) + 1 << '\n';
}
}
}
时间复杂度 。
T5
怎么还有拓扑排序板子啊。何意味何意味何意味何意味何意味。
反向连边，然后拓扑 DP 看看哪些需要学。甚至从后往前拓扑就行了，不需要 queue。
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <int> a(n + 5), vis(n + 5);
std::vector <std::vector <int>> v(n + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i];
int len;
std::cin >> len;
for(int j = 1; j <= len; j++){
int idx;
std::cin >> idx;
v[i].push_back(idx);
}
}
vis[n] = 1;
for(int i = n; i; i--){
if(!vis[i]) continue;
for(int j:v[i]) vis[j] = 1;
}
ll ans = 0;
for(int i = 1; i <= n; i++){
if(vis[i]) ans += a[i];
}
std::cout << ans << '\n';
}
}
时间复杂度 。
T6
啥题啊这。DP 一下就行了。
#include <bits/stdc++.h>
namespace cjdst{
void solve(){
int n, m;
std::cin >> n >> m;
std::vector <std::string> a(n + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i];
a[i] = " " + a[i] + " ";
}
std::vector <std::vector <int>> dp(n + 5, std::vector <int>(m + 5));
if(a[1][1] == '.') dp[1][1] = 1;
int ans = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(i == 1 && j == 1) continue;
if(a[i][j] == '#') continue;
if(i > 1 && a[i - 1][j] == '.' && dp[i - 1][j]) dp[i][j] = dp[i - 1][j] + 1;
if(j > 1 && a[i][j - 1] == '.' && dp[i][j - 1]) dp[i][j] = dp[i][j - 1] + 1;
ans = std::max(ans, dp[i][j]);
}
}
std::cout << ans << '\n';
}
}
时间复杂度 。
有帮助，赞一个