Codeforces Round 871 (Div. 4)（A~H）

news/2024/10/18 18:25:22/

目录

比赛链接

A. Love Story

B. Blank Space

C. Mr. Perfectly Fine

D. Gold Rush

E. The Lakes

F. Forever Winter

G. Hits Different

H. Don't Blame Me

比赛链接

Dashboard - Codeforces Round 871 (Div. 4) - Codeforces

A. Love Story

找到与codeforces 有多少个不同的字符。

#include<bits/stdc++.h>
#define int long long  
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define pll pair<int,int>
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9 + 7;
using namespace std;
string s = "codeforces";
void solve() {string st;cin >> st;int ans = 0;for (int i = 0; i < st.size(); i++){if (st[i] != s[i])ans++;}cout << ans << "\n";}
signed main() {ios;TESTsolve();return 0;
}

B. Blank Space

找连续最长的0.

#include<bits/stdc++.h>
#define int long long  
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define pll pair<int,int>
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9 + 7;
using namespace std;void solve() {int n;cin >> n;int cnt = 0, ans = 0;for (int i = 1; i <= n; i++){int x;cin >> x;if (x == 0) cnt++;else{ans = max(ans, cnt);cnt = 0;}}ans = max(ans, cnt);cout << ans << "\n";
}
signed main() {ios;TESTsolve();return 0;
}

C. Mr. Perfectly Fine

分成01、10、11的三种情况，找全部的最小值，前面两个的最小值相加与第三个的最小值比较出最小值。

#include<bits/stdc++.h>
#define int long long  
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define pll pair<int,int>
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9 + 7;
using namespace std;void solve() {int n;cin >> n;int c1 = 1e9, c2 = 1e9, c3 = 1e9;for (int i = 1; i <= n; i++){int t;cin >> t;string s;cin >> s;if (s == "01") c2 = min(c2, t);if (s == "10") c1 = min(c1, t);if (s == "11") c3 = min(c3, t);}int res = min(c1 + c2, c3);if (res != 1e9)cout << min(c1 + c2, c3) << "\n";else cout << "-1\n";
}
signed main() {ios;TESTsolve();return 0;
}

D. Gold Rush

按照题意可以将一堆分成三堆，看看目标是否出现即可，搜索。

#include<bits/stdc++.h>
#define int long long  
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define pll pair<int,int>
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9 + 7;
using namespace std;void solve() {int n, m;cin >> n >> m;if (m > n){cout << "NO\n";return;}if (n == m){cout << "YES\n";return;}queue<int>q;q.push(n);while (q.size()){int k = q.front();q.pop();if (k == m){cout << "YES\n";return;}if (k < m|| k % 3 != 0) continue;int t=k / 3;q.push(t);q.push(t * 2);}cout << "NO\n";
}signed main() {ios;TESTsolve();return 0;
}

E. The Lakes

dfs染色法。

#include<bits/stdc++.h>
#define int long long  
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define pll pair<int,int>
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9 + 7;
using namespace std;
int vis[1001][1001];
int a[1001][1001];
int q[N];
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int n, m;
int sum = 0;
int ans = 0;
void dfs(int x, int y, int tag)
{vis[x][y] = tag;sum += a[x][y];ans = max(ans, sum);for (int i = 0; i < 4; i++){int tx = x + dx[i];int ty = y + dy[i];if (tx<1 || ty<1 || tx>n || ty>m) continue;if (a[tx][ty] == 0) continue;if (vis[tx][ty]) continue;dfs(tx, ty, tag);}
}
void solve() {cin >> n >> m;ans = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> a[i][j];}}int cnt = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (a[i][j] == 0) continue;if (vis[i][j]) continue;sum = 0;++cnt;dfs(i, j, cnt);}}cout << ans << "\n";for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){vis[i][j] = 0;}}
}signed main() {ios;TESTsolve();return 0;
}

F. Forever Winter

模拟一下，与出入度为1的点连接的就是与主节点连接的点，输出他们的出入度即可，与主节点连接的点，出入度需要减一。

#include<bits/stdc++.h>
#define int long long  
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define pll pair<int,int>
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9 + 7;
using namespace std;
void solve() {int n, m;cin >> n >> m;vector<vector<int>>f(n + 1);for (int i = 1; i <= m; i++){int u, v;cin >> u >> v;f[u].push_back(v);f[v].push_back(u);}set<int>q;for (int i = 1; i <= n; i++){if (f[i].size() == 1){q.insert(f[i][0]);}}int ans1;for (auto x : q){ans1 = f[x].size() - 1;break;}int ans2;for (int i = 1; i <= n; i++){set<int>tt;for (auto x : f[i]) tt.insert(x);if (tt == q){ans2 = f[i].size();break;}}cout << ans2 << ' ' << ans1 << "\n";
}signed main() {ios;TESTsolve();return 0;
}

G. Hits Different

一开始用搜索，优化半天还是超时，正解是二位数组前缀和dp。

#include<bits/stdc++.h>
#define int long long  
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define pll pair<int,int>
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9 + 7;
using namespace std;
int a[1500][1500];
int cnt=1;
int ans[N];
void solve() {int n;cin >> n;cout << ans[n] << "\n";
}signed main() {for (int i = 1; i < 1500; i++){for (int j = i - 1; j >= 1; j--){a[j][i - j] = a[j - 1][i - j] + a[j][i - j - 1] - a[j - 1][i - j - 1] + cnt * cnt;ans[cnt] = a[j][i - j];cnt++;}}ios;TESTsolve();return 0;
}

H. Don't Blame Me

找子序列所有元素的与和的二进制里1的个数等于k，数位dp。

#include<bits/stdc++.h>
#define int long long  
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define pll pair<int,int>
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9 + 7;
using namespace std;
int dp[N][64];
int a[N];
void solve()
{int n, k;cin >> n >> k;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= n; i++){dp[i][a[i]] = 1;for (int j = 0; j <= 63; j++){dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;dp[i][j & a[i]] = (dp[i][j & a[i]] + dp[i - 1][j]) % mod;}}int ans = 0;for (int i = 0; i <= 63; i++){int cnt = 0;for (int j = 0; j < 6; j++){if ((i >> j) & 1){cnt++;}}if (cnt == k){ans = (ans + dp[n][i]) % mod;}}cout << ans << "\n";for (int i = 1; i <= n; i++){for (int j = 0; j <= 63; j++){dp[i][j] = 0;}}
}
signed main() {ios;TESTsolve();return 0;
}

http://www.ppmy.cn/news/1505908.html

相关文章

嵌入式软件--C语言高级 DAY 8 函数

嵌入式软件--C语言高级 DAY 8 函数

函数是C语言尤为重要的知识点&#xff0c;再嵌入式的学习过程中&#xff0c;对51和32的单片机的学习是重中之重。 一、函数的基本概念 1.介绍 函数是一种可重复使用的代码块&#xff0c;用于执行特定的任务或操作。 函数允许我们将代码逻辑组织成独立的单元&#xff0c;从而…
阅读更多...
FFmpeg音频重采样基本流程

FFmpeg音频重采样基本流程

目录 流程概述用到的APItipsdemo样例附录 - SwrContext结构体字段 流程概述 音频重采样的基本流程为&#xff1a; 申请重采样器上下文设置重采样去上下文的参数初始化重采样器申请数据存放的缓冲区空间进行重采样 注意&#xff0c;要先设置参数再对重采样器初始化 用到的API…
阅读更多...
深入分析 Android ContentProvider (一)

深入分析 Android ContentProvider (一)

文章目录 深入分析 Android ContentProvider (一)1. Android 中的 ContentProvider 设计说明1.1. ContentProvider 的设计初衷1.2. ContentProvider 的基本结构1.3. ContentProvider 的实现示例&#xff1a;实现一个简单的 ContentProvider 1.4. ContentProvider 的使用 2. Con…
阅读更多...
CSP初赛知识点讲解（四)

CSP初赛知识点讲解（四)

CSP初赛知识点讲解&#xff08;四&#xff09; 位运算与运算(&)或运算(|)异或运算(^)取反运算(~)左移运算右移运算 存储空间时间计算例题训练&#xff08;六&#xff09; 位运算 所有的数据在计算机中都是以二进制的方式存储&#xff0c;为了方便计算&#xff0c;提供了一…
阅读更多...
使用Redis来实现JWT令牌主动失效机制

使用Redis来实现JWT令牌主动失效机制

目录 一.实现思路&#xff1a; 二.实现代码解析&#xff1a; 1.首先配置Redis的相关配置文件&#xff1a; &#xff08;1&#xff09;pom.xml&#xff1a; &#xff08;2&#xff09;在application.yml中配置相关信息&#xff1a; &#xff08;3&#xff09;编写配置类&a…
阅读更多...
Hooks是干什么的？

Hooks是干什么的？

在编程的世界里&#xff0c;“Hooks”是一个你可能会经常听到的术语&#xff0c;特别是在前端开发中。它们为开发者提供了一种优雅且高效的方式来扩展和控制代码的执行流程。本文将深入浅出地介绍Hooks是什么&#xff0c;它们的作用是什么&#xff0c;以及如何在代码中使用它们…
阅读更多...
uniapp实现可视化图表（轻量、内存小）

uniapp实现可视化图表（轻量、内存小）

图表官网&#xff1a;uCharts官网 - 秋云uCharts跨平台图表库 用原生组件&#xff1a; 选择自己需要的模块&#xff0c;以小程序为例&#xff1a; 把min.js下载下来 把min.js放到小程序代码中&#xff0c;引用即可&#xff0c;使用案例看官网&#xff0c; 在官网中选择想要的…
阅读更多...
Linux 为何不把图形用户界面写入内核？

Linux 为何不把图形用户界面写入内核？

Linux 为何不把图形用户界面写入内核&#xff1f; 早先是没能力&#xff0c;之后是没必要&#xff0c;现在是不应该 先插一句&#xff0c;现代Windows9的图形也不在内核里&#xff0c;只是还保留一组兼容。 90年代时的计算机都是两套图形系统:一套是普通软件窗口API9&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023