Codeforces Round #625 (Div. 2)
Contest Info
Solved | A | B | C | D | E | F |
---|---|---|---|---|---|---|
4/6 | O | O | Ø | Ø |
- O 在比赛中通过
- Ø 赛后通过
- ! 尝试了但是失败了
- - 没有尝试
Solutions
C.Remove Adjacent
题意:
给定一个由小写字母组成的字符串,对于字符串中某个字符,假如它相邻的字符中存在其在字符集中的前一个字符,那么就可以将它移除,求这个字符串最多移除的字符数
思路:
贪心的选取当前能删除的最大的字符,为什么这样是对的呢?
我们消去的是最靠后的元素,它不会对之后的元素能否被消除造成影响(因为没有更靠后的元素)
假如你消除的不是最靠后的元素,就有可能会对之后的元素能否被消除造成影响,导致某些字符不能被消除,比如$abbcda$我先消除$c$会造成这里的$d$无法被消除
经过上面分析,显然这种贪心策略是最优的
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, ans;
char s[110];
bool vis[110];
int main(){
scanf("%d%s", &n, s+1);
s[0] = s[n+1] = '0';
while(1){
int id = 0;
for(int i = 1; i <= n; i++){
if(vis[i]) continue;
int l = i-1, r = i+1;
while(vis[l]) l--;
while(vis[r]) r++;
char tmp = s[i] - 1;
if((s[l]==tmp||s[r]==tmp)&&s[i]>s[id])
id = i;
}
if(id) vis[id] = 1, ans++;
else break;
}
printf("%d", ans);
}
D.Navigation System
题意:
给定一个无向图和一条$s$到$t$的路线$<s,t>$,然后从$s$出发沿着这个路线走,每个点导航仪都会给出到终点$t$的最短路径,假如最短路的路径变化的话会重新导航,求在$<s,t>$这条路径上重新导航次数的最小值和最大值
思路:
这个题目是真的又臭又长,我还理解错了意思,看半天都没看懂代码。之前现场赛也是因为题目意思没理解清楚就栽了坑,还是要多注意
对于两点$u->v$的移动,很明显,最短路径变化有两种情况:
①$u->v$ 的时候 距离终点的距离没有$-1$
(比如说$u$距离终点$3$,那么$v$距离终点的距离应该为$2$,否则就会重新导航)
②$u->v$ 的时候 距离终点的距离$-1$ 但是有其他最短路径的选择
(比如说$u->v->$终点和$u->w>$终点,那么导航就会有可能由第二条变成第一条)
最小值只需要考虑①,最大值就需要①+②
所以只要反向建图,求出终点到其他点的最短路,然后再一一判断即可(求最短路的话$bfs$就够用了)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define pb push_back
using namespace std;
const int maxn = 2e5+100;
int n, m, k, u, v, ans1, ans2, p[maxn], d[maxn];
int cnt, head[maxn];
vector<int> g[maxn];
struct edge{
int to, nxt;
}e[maxn];
void add(int u, int v){
e[++cnt].nxt = head[u], e[cnt].to = v;
head[u] = cnt;
}
void bfs(int t){
for(int i = 1; i <= n; i++) d[i] = -1;
queue<int> que;
d[t] = 0, que.push(t);
while(!que.empty()){
int u = que.front(); que.pop();
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(d[v]<0)
d[v] = d[u] + 1, que.push(v);
}
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++){
scanf("%d%d", &u, &v);
add(v, u), g[u].pb(v);
}
scanf("%d", &k);
for(int i = 1; i <= k; i++) scanf("%d", &p[i]);
bfs(p[k]);
for(int i = 1; i < k; i++){
int u = p[i], v = p[i+1];
if(d[v]!=d[u]-1) ans1++, ans2++;
else{
for(int i = 0; i < g[u].size(); i++){
int w = g[u][i];
if(d[w]==d[u]-1&&w!=v){
ans2++; break;
}
}
}
}
printf("%d %d", ans1, ans2); }
Refences:
https://codeforces.ml/blog/entry/74431#comment-585195
https://blog.csdn.net/Herr_Shiiiii/article/details/104635793
https://blog.csdn.net/JiangHxin/article/details/104607515/
https://www.cnblogs.com/starve/p/12398306.html
最新文章
- 2000条你应知的WPF小姿势 基础篇<;15-21>;
- jQuery中的100个技巧
- bootstrap分页
- Service之三种服务方式
- 让VisualVM+BTrace进入unsafe mode
- [转]System.Reflection.AssemblySignatureKeyAttribute
- Excel加载期间出现问题 解决方案
- XJOI网上同步测试DAY14 T2
- PHP数据访问修改和多条件查询(20161030)
- Unity UGUI基础之Slider、Scrollbar
- Struts-ValueStack和OGNL总结
- spring-framework-x.x.x.RELEASE-dist下载教程
- elasticsearch配置文件详解
- 性能测试-6.VUG脚本参数化
- sublime text 3 3143
- MySQL管理.md
- iOS- 如何将应用集成发短信、发邮件、打电话
- XCOde 5 的界面布局一些新特性
- mysql where语句中 or 和 and连用注意点
- 【week2】 四则运算改进