华中农业大学第五届程序设计大赛网络同步赛题解

A.Little Red Riding Hood

B.Choosy in Food

•F[i]:从第I个点到终点的期望步数

•F[i] = (F[i + k] + k ) * P[k]

•F[ed] = 0

•高斯消元求解

•注意存在从起点不能到达终点的情况

C.Friends

•F[rt][len] :节点rt的子孙里,距离rt的为len的节点个数

•ans[rt][len] : 整棵树上,距离rt为len的节点个数

•F值一次简单的深搜可以得到

•而ans[rt][len] = F[rt][len] + ans[fa(rt)][len – 1] – F[fa(rt)][len – 1]

D.GCD

E.One Stroke

•在每一个根到叶子结点的路径上用双指针即可求出一笔能画出的最多结点。

•双指针思路:枚举起点i,向右不断移动终点j,直到ij之间的和不大于k,复杂度O(nlogn)

•如果暴力优美也能过(T^T),复杂度O(nlognlogn)

F.Escape from the Darkness

G.Sequence Number

•这是一道排序可以过的题,也可以rmq+二分

•最快的写法可以用单调栈做到O(n)

H.Mathematical Game 

I.Candies

•线段树中查询一个区间里,最长的连续B区间的长度

•区间合并时考虑左间的右部连续B加上右区间的左部连续B区间可能会更新这个区间的MAX_B值

•同时更新区间的左部连续B长度时,考虑左区间全部为B时,应加上右区间的左B长度

•更新区间的右部连续长度同理

•查询时,同样要根据更新的原理来更新查询的答案

J.Color Circle

• 搜索,DFS即可

K.Deadline

•这题只要想到思路还是很简单的,假设所有工程师每天都在修复bug,那么对天数记录bug的前缀和,O(n)得到答案max(pre[i]+i-1)/i)

L.Happiness

Description

       Chicken brother is very happy today, because he attained N pieces of biscuits whose tastes are A or B. These biscuits are put into a box. Now, he can only take out one piece of biscuit from the box one time. As we all know, chicken brother is a creative man. He wants to put an A biscuit and a B biscuit together and eat them. If he take out an A biscuit from the box and then he take out a B biscuit continuously, he can put them together and eat happily. Chicken brother’s happiness will plus one when he eat A and B biscuit together one time.

      Now, you are given the arrangement of the biscuits in the box(from top to bottom) ,please output the happiness of Chicken Brother when he take out all biscuit from the box. 

Input

       The first line is an integer indicates the number of test cases.

       In each case, there is one line includes a string consists of characters ‘A’ and ‘B’.

       The length of string is not more than 1000000. 

Output

     For each test case:

    The first line output “Case #k:", k indicates the case number.    

    The second line output the answer. 

Sample Input

1
ABABBBA

Sample Output

Case #1:
2

HINT

Source

题解:

•求字符串中AB出现的次数

•遍历一次字符串即可

特别提醒:此题出题人已挖好大坑等着萌新们入坑,我也是第一次遇到这种100W就TL的情况,原因我给你们分析一下,就是这个strlen的应用,之前我将strlen放在for循环内,复杂度为100W*100W,O(n^2)必然超时,只要把strlen提出来,复杂度降为100W+100W,O(n+n),神TM知道这个函数调用也会TL!

下面附上AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 char s[1000010];
 4 int main()
 5 {
 6     int n;
 7     while(cin>>n)
 8     {
 9         int ans=0;
10         for(int i=1;i<=n;i++)
11         {
12             scanf("%s",s);
13             printf("Case #%d:\n",i);
14             int len=strlen(s);
15             int ans=0;
16             for(int j=0;j<len;j++)
17             {
18                 if(s[j]=='A'&&s[j+1]=='B')
19                     ans++;
20             }
21             printf("%d\n",ans);
22         }
23     }
24     return 0;
25 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏owent

POJ PKU 2549 Sumsets 解题报告

题目链接http://acm.pku.edu.cn/JudgeOnline/problem?id=2549

901
来自专栏数据结构与算法

洛谷 P3386 【模板】二分图匹配 Dinic版

题目背景 二分图 题目描述 给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数 输入输出格式 输入格式: 第一行,n,m,e 第二至e+1行,每...

3309
来自专栏章鱼的慢慢技术路

Luhn算法检验和验证

2256
来自专栏SeanCheney的专栏

《Pandas Cookbook》第06章 索引对齐1. 检查索引2. 求笛卡尔积3. 索引爆炸4. 用不等索引填充数值5. 从不同的DataFrame追加列6. 高亮每列的最大值7. 用链式方法重现

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

911
来自专栏计算机视觉与深度学习基础

Leetcode 164 Maximum Gap 桶排序好题

Given an unsorted array, find the maximum difference between the successive ele...

2135
来自专栏mathor

TRIE(3)

 搜索引擎现在一般都有关键词提示或者说是补全功能。就是当你在搜索框里输入一个关键词s时,搜索引擎会自动提示你一些频率比较高,同时前缀是s的关键词  这道...

982
来自专栏用户2442861的专栏

Java 8系列之重新认识HashMap

作者:美团点评技术团队 链接:https://zhuanlan.zhihu.com/p/21673805 来源:知乎 著作权归作者所有。商业转载请联系作者...

1111
来自专栏QQ音乐技术团队的专栏

Android Native 开发之 NewString 与 NewStringUtf 解析

本文将从一个 Native Crash 分析入手,带大家了解我们平时开发中,那些容易忽略但又很值得学习的底层源码知识。

1.4K9
来自专栏蜉蝣禅修之道

LeetCode之Binary Tree Maximum Path Sum

1174
来自专栏游戏开发那些事

三十分钟掌握STL

这是本小人书。原名是《using stl》,不知道是谁写的。不过我倒觉得很有趣,所以化了两个晚上把它翻译出来。我没有对翻译出来的内容校验过。如果你没法在三十分钟...

1164

扫码关注云+社区

领取腾讯云代金券