CF-551:部分题目总结
2024-10-08 18:45:51
题目链接:http://codeforces.com/contest/1153
A .Serval and Bus
pro:给出n种公交车的首班车时间和两班车之间的时间间隔,找t时间以后的第一辆车是第几种车
sol:对于每种车,找到t时间以后的第一班车的时间,计算这个时间和t的差距,然后找离t最近的
- 暴力
#include "bits/stdc++.h"
using namespace std;
const int MAXN = ;
const int INF = 0x3f3f3f3f;
int ans, k = INF;
int main() {
int n, t, a, b, c;
scanf("%d%d", &n, &t);
for (int i = ; i <= n; i++) {
scanf("%d%d", &a, &b);
if (a >= t) {
c = a - t;
} else {
c = ((a - t) % b + b) % b;
}
if (c < k) {
k = c;
ans = i;
}
}
printf("%d\n", ans);
return ;
}最后一个取余忘了,然后就被hack......甚是无语
B .Serval and Toy Bricks
pro:给出三视图每一列的高度,俯视图有点特殊,只有0或1,求俯视图每一格的高度
sol:结果不唯一,对于俯视图每一格,找到对应的左视图和前视图,取其中高度小的就必能配成正确的俯视图
- 贪心
#include "bits/stdc++.h"
using namespace std;
const int MAXN = ;
int mp[MAXN][MAXN];
int f[MAXN], l[MAXN];
int main() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = ; i <= m; i++)
scanf("%d", &f[i]);
for (int i = ; i <= n; i++)
scanf("%d", &l[i]);
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
scanf("%d", &mp[i][j]);
if (mp[i][j]) mp[i][j] = min(f[j], l[i]);
}
}
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++)
printf("%d ", mp[i][j]);
puts("");
}
return ;
}
C .Serval and Parenthesis Sequence
pro:给出一个括号串,其中一部分被用'?'代替,补全括号串,使得括号串除自身以外每个前缀串都不是合法括号串,但是自身是合法括号串,若无法补全,输出":(";
sol:还是贪心,因为要补成合法括号串,所以左括号个数为(|s| / 2)个,从左往右扫,遇到'?'如果能补左括号就补左括号,补不了左括号再补右括号,如果还没到末尾就合法了,输出":(",如果到末尾还不是合法括号串,也输出":(",否则输出补好的串。CF贪心的题好多啊
- 贪心
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 3e5 + ;
char s[MAXN];
int n, k, l;
int main() {
scanf("%d%s", &n, &s);
k = n >> ;
for (int i = ; i < n; i++)
if (s[i] == '(') k--;
for (int i = ; i < n; i++) {
if (s[i] == '?') {
if (k > ) {
s[i] = '(';
k--;
} else {
s[i] = ')';
}
}
}
for (int i = ; i < n - ; i++) {
if (s[i] == '(') {
l++;
} else {
l--;
}
if (l <= ) {
puts(":(");
return ;
}
}
if (s[n - ] == ')') {
l--;
} else {
l++;
}
if (l == ) {
puts(s);
} else {
puts(":(");
}
return ;
}
D . Serval and Rooted Tree
pro:给出一棵树,除叶子节点外每个节点有一个属性,0表示该节点的值等于子节点中最大值,1表示该节点的值等于子节点中最小值,将1到k填入k个子节点,使得根节点值最大。
sol:树形dp + dfs,dfs(i) 表示叶子节点的个数减去i节点的最大值,所以用叶子节点个数减dfs(i)就是i节点最大值,至于树形dp那一块,看代码应该能懂了。
- 树形dp + 深度优先搜索 + 好像也有点贪心在里面吧
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 3e5 + ;
const int INF = 0x3f3f3f3f;
vector<int> v[MAXN];
int arr[MAXN], val[MAXN];
int leaf;
int dfs(int k) {
if (v[k].empty()) return ;
if (arr[k] == ) {
int mn = INF;
for (int i = ; i < v[k].size(); i++)
mn = min(mn, dfs(v[k][i]));
return mn;
} else {
int sum = ;
for (int i = ; i < v[k].size(); i++)
sum += dfs(v[k][i]);
return sum + v[k].size() - ;
}
}
int main() {
int n, k;
scanf("%d", &n); leaf = n;
for (int i = ; i <= n; i++)
scanf("%d", &arr[i]);
for (int i = ; i <= n; i++) {
scanf("%d", &k);
if (v[k].empty()) leaf--;
v[k].push_back(i);
}
printf("%d\n", leaf - dfs());
return ;
}思路来源于今年蓝桥杯省赛的一道求雨题,不过这两题比赛当场都没能完成。都是比赛结束之后才想通的。继续努力
最新文章
- Bootstrap源码分析之transition、affix
- 使用bakefile编译C工程代码
- Senparc.Weixin.MP.Sample 配置redis服务器密码
- 不下载SDK启动Android Studio
- JavaScript中的位置坐标
- 五毛的cocos2d-x学习笔记01-创建项目
- DDD之:Repository仓储模式
- 【Selenium】idea的selenium环境配置
- Conference-Web Search and Data Mining
- 解读经典《C#高级编程》泛型 页114-122.章4
- python:Crypto模块的下载
- numpy 和tensorflow 中的乘法
- 100道c++面试题(上)
- 各个JSON技术的比较(Jackson,Gson,Fastjson)的对比
- element ui 的Notification通知如何加 a 标签和按钮,并弹多个
- 算警示吧——此文来自张鑫旭(说说CSS学习中的瓶颈)
- ORB_SLAM2_Android
- class path resource [logback.xml] cannot be resolved to URL because it does not exist 问题解决
- Linux中使用Crontab定时监测维护Tomcat应用程序的方法
- Duilib教程-自动布局1
热门文章
- PROOF|ADOBE READER
- 小结spring给项目开发的好处
- UITableViewCell 的selectedBackgroundView
- 86.QuerySet API常用的方法详解:get方法
- 4418之Android Eclipse导入应用程序在开发板上调试
- PAT Basic 1075 链表元素分类(25) [链表]
- python学习笔记-函数与可变长参数
- 题解 P2738 【[USACO4.1]篱笆回路Fence Loops】
- 反射(hasattr和setattr和delattr)
- Python笔记_第一篇_面向过程_第一部分_5.Python数据类型之字典类型(dict)