CF-544:部分题目总结
2024-09-06 18:33:28
-------------------昨天打的重现赛,感觉是我打的发挥的最好的一场比赛了,六题都一次AC。那么就来总结一下吧
题目链接:http://codeforces.com/contest/1133
A .Middle of the Contest
sol:简单模拟,注意一下跨天的情况就好了。
- 模拟
#include "bits/stdc++.h"
using namespace std;
int main() {
int h1, m1, h2, m2, k;
scanf("%d:%d%d:%d", &h1, &m1, &h2, &m2);
// 把第二个时间加24小时,就能保证第二个时间比第一个时间大
k = (m2 - m1 + (h2 + - h1) * ) % ( * ) >> ;
m1 += k;
h1 = (h1 + m1 / ) % ;
m1 %= ;
printf("%02d:%02d", h1, m1);
return ;
}
B .Preparation for International Women's Day
sol:如果(a + b) % k == 0,那么(a % k) + (b % k) == 0 || (a % k) + (b % k) == k。注意等于0的情况不要忽略掉。遍历一遍,对于第d[i],查看是否在前面出现过还未配对的余数和d[i]余数相加等于0或k的情况。
- 同余
#include "bits/stdc++.h"
using namespace std;
const int MAXN = ;
int n, k, v, ans;
int cnt[MAXN];
int main() {
scanf("%d%d", &n, &k);
for (int i = ; i <= n; i++) {
scanf("%d", &v);
v %= k;
if (cnt[(k - v) % k]) {
ans += ;
cnt[(k - v) % k]--;
} else {
cnt[v]++;
}
}
printf("%d\n", ans);
return ;
}
C .Balanced Team
sol:尺取法,先排序,定义l = r = 1。然后让l和r一起往右移。
- 尺取法
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + ;
int arr[MAXN], n, ans;
int main() {
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%d", &arr[i]);
}
sort(arr + , arr + + n);
int l = , r = ;
while (r <= n) {
while (arr[r] - arr[l] > ) l++;
ans = max(ans, r - l + );
r++;
}
printf("%d\n", ans);
return ;
}
D .Zero Quantity Maximization
sol:首先换个姿势看这个问题,c[i] = d * a[i] + b[i],求c数组0最多有几个,那么我让题目变成c[i] = a[i]和b[i]的比。求相同比最多的次数。用map计数就行了。但是这个比不能用double来计,会产生精度丢失。所以我是用pair来计比的。还有就要说说这题的样例了,a[i] == 0这种属于特殊数据怎么能放到样例里呢,虽然我一开始也没考虑到。注意约分的时候a[i]为0的情况;
- 这题考细心
#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> PII;
const int MAXN = 2e5 + ;
map<PII, int> mp;
int a[MAXN], b[MAXN];
int ans, n, k, g;
int main() {
scanf("%d", &n);
for (int i = ; i <= n; i++)
scanf("%d", &a[i]);
for (int i = ; i <= n; i++)
scanf("%d", &b[i]);
for (int i = ; i <= n; i++) {
if (a[i] == ) {
k += (b[i] == );
continue;
}
g = __gcd(a[i], b[i]);
a[i] /= g, b[i] /= g;
mp[{a[i], b[i]}]++;
ans = max(ans, mp[{a[i], b[i]}]);
}
printf("%d\n", ans + k);
return ;
}
E .K Balanced Teams
sol:动态规划,先sort一下。dp[i][j]表示从第i个队员到最后一个队员组成j个队伍最多的人数。
ps:除了动态规划的部分,其他的和C题都一样。不过数据范围比较小,尺取法不是关键考点。用暴力也能过。
- 动态规划
#include "bits/stdc++.h"
using namespace std;
const int MAXN = ;
int arr[MAXN];
int dp[MAXN][MAXN];
int ans;
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++)
scanf("%d", &arr[i]);
sort(arr + , arr + + n);
for (int i = n; i >= ; i--) {
int k = i;
while (k <= n && arr[k] - arr[i] <= ) k++;
for (int j = ; j <= m; j++) {
dp[i][j] = max(dp[i + ][j], k - i + dp[k][j - ]);
ans = max(ans, dp[i][j]);
}
}
printf("%d\n", ans);
return ;
}
F1 .Spanning Tree with Maximum Degree
sol:找到度数最大的节点,以度数最大的节点为起点bfs遍历全图
- 图算法
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + ;
vector<int> edge[MAXN];
int maxdg, pos;
bool use[MAXN];
void bfs(int pos) {
queue<int> que;
que.push(pos);
use[pos] = true;
while (!que.empty()) {
pos = que.front();
que.pop();
for (int i = ; i < edge[pos].size(); i++) {
if (!use[edge[pos][i]]) {
printf("%d %d\n", pos, edge[pos][i]);
que.push(edge[pos][i]);
use[edge[pos][i]] = true;
}
}
}
}
int main() {
int n, m, u, v;
scanf("%d%d", &n, &m);
for (int i = ; i <= m; i++) {
scanf("%d%d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
if (edge[u].size() > maxdg) {
maxdg = edge[u].size();
pos = u;
}
if (edge[v].size() > maxdg) {
maxdg = edge[v].size();
pos = v;
}
}
bfs(pos);
return ;
}
最新文章
- jquery修改带!important的css样式
- PS切图篇
- Tomcat双向Https验证搭建,亲自实现与主流浏览器、Android/iOS移动客户端超安全通信
- ThinkCMF-如何收藏
- android播放器如何获取音乐文件信息
- IIS不能对网站添加默认文档(由于权限不足而无法写入配置文件)
- NSArry的常见方法
- 在Linux环境下安装和配置phpmyadmin
- 自定义web服务器(四)
- 【HDU1402】【FNT版】A * B Problem Plus
- 学渣上手 LaTeX 完成毕业论文
- 修改合同号的bapi
- C#分部类型解析
- gevent实现基于epoll和协程的服务器
- linux中用composer安装yii框架
- 前端示例MVC网站
- 2018.08.16 POJ1183反正切函数的应用(简单数学)
- 转 生成 HTMLTestRunner 测试报告
- 【matlab】使用VideoReader提取视频的每一帧,不能用aviread函数~
- bash&;nbsp;shell笔记2&;nbsp;结构化命令
热门文章
- PAT Advanced 1147 Heaps (30) [堆,树的遍历]
- 客户主题分析(tableau)—客户留存
- 1.2 NumPy数组基础
- cisco3900板卡sm-es3g-24-p使用方法
- MyBatis从入门到精通(第5章):5.4 Example 介绍
- PAT Advanced 1015 Reversible Primes (20) [素数]
- Pmw大控件
- tensorflow deeplabv3 训练自己的数据集
- 八皇后问题 2n皇后问题
- 爬虫加入数据post请求