最优路线  解题思路 这题就是Floyd算法 但是要加许多玄学优化 比如： inline 加在子程序前 快读（两个） 加在输入上 register 加在定义和循环前 O2优化 加在开头 把i++改为++i AC代码 #pragma GCC optimize(2)//O2玄学 #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> using namespace std; long long n,m,x,y,z,v[5000005],b[505][505],...

总结 你以为我在水博客 没错不 可能（哎呀，不小心把 不打进删除线中了 ，算了，我懒，不改了，大家都懂 ） 整整40多天的暑假，被直接压缩成10多天（乱猜的，差不多就对了） 我直接裂开了 DAY 1（7.20）（兴奋） 这一天，我们学习了hash表 可能是因为太久没学编程 所以这一天还有点小兴奋 DAY 2（7.21）（开心） 我们学习了并查集 这东西，我和dzj神仙在纪中培训时就学会了 还刷了点题目，所以学起来毫无压力 DAY 3（7.22）（兴奋） 我们学习了离散化和线段树 虽然知识量有点多 但是 邪恶的 善良的老师 让我们可以回家做 可是还要刷往年的普及组题目 虽然有点不情愿 但因为下午...

这是一棵树吗?  解题思路 这题就是一图论 首先，我们要知道 树中结点数 = 总分叉数 +1 其中总分叉数=每个节点的子树和 但题目中的树的度则是父节点和子节点个数的和 因为树中每个节点最多只有一个父亲 所以每个节点都要-1 但是因为根节点没有父亲，所以还要+1 所以公式为  树 中 节 点 数 = n 个 整 数 的 和 − n + 1 + 1 树中节点数=n个整数的和-n+1+1 树中节点数=n个整数的和−n+1+1 特判 当n=1,x=0时，要输出Possible 当n=3,x[1]=1,x[2]=0,x[2]=3时，要输出Impossible 所以要特判0的存在 AC代码 #inclu...

P6704 [COCI2010-2011#7] GITARA 题目传送门 解题思路 这题可以利用栈的思想 将每一种弦都用一种栈（本人太蒟，不会用STL） 如果有数进来时 就和栈顶比较大小 如果栈顶>进来的数 就要出栈 注意： 当1 5 1 6 1 5时，虽然已经按过1 5，但是也要先松开1 6的键，然后可以不用按1 5 （用其他方法的小朋友们！敲黑板！做笔记！） AC代码（有注释） #include<iostream> #include<cstdio> using namespace std; int n,p,x,y,s,sum[7],a[7][300005]; ...

字符串 时间限制:1000MS 内存限制:128000KB 题目描述 小熊有一个由小写英文字母组成的字符串s = s1s2…sn。小熊想要计算s中有多少子串包含字符串“bear”，也就是找出满足字符串x(i, j)= sisi+1…sj 包含至少一个字符串“bear”的 (i, j)对数（1≤i≤j≤n）。 字符串x(i, j)包含字符串“bear”定义为存在一个整数k（i≤k≤j-3），满足sk=b，sk+1=e，sk+2=a，sk+3=r。 请帮助小熊解决这个问题。 输入 输入共1行，包含一个非空字符串s。数据保证字符串s中只包含小写英文字母。 输出 输出共1行，包含一个整数，表示这个问题...

序列 时间限制:1000MS 内存限制:128000KB 题目描述 一个长度为k的整数序列b1，b2，…，bk（1≤b1≤b2≤…≤bk≤N）称为“好序列”当且仅当后一个数是前一个数的倍数，即bi+1是bi的倍数对任意的i（1≤i≤k-1）成立。 给定N和k，请算出有多少个长度为k的“好序列”，答案对1000000007取模。 输入 输入共1行，包含2个用空格隔开的整数N和k。 输出 输出共1行，包含一个整数，表示长度为k的“好序列”的个数对1000000007取模后的结果。 输入样例 3 2 输出样例 5 说明 【输入输出样例说明】 “好序列”为：[1,1]，[1,2]，[1,3]，[2,2...

树 时间限制:10000MS 内存限制:512000KB 题目描述 小L非常喜欢树。最近，他发现了一棵有趣的树。这棵树有n个节点(1到n编号)，节点i有一个初始的权值ai。这棵树的根是节点1。 这棵树有一个特殊的性质：当你给节点i的权值加 val 的时候，节点i的所有儿子的权值都会加 -val。注意当你给节点i的儿子的权值加 -val 时，节点i的这个儿子的所有儿子的权值都会加 -(-val)，以此类推。样例说明可以很好地帮助你理解这个性质。 有2种操作： 操作(a).“1 x val”表示给节点x的权值加val。 操作(b).“2 x”输出节点x当前的权值。 为了帮助小L更好地理解这棵树，你...

游戏 时间限制:1000MS 内存限制:128000KB 题目描述 小G正在玩一款游戏，游戏地图上有N个点（1到N编号），这些点之间有M条无向边（没有重边）。一次系统刷新会在某个时刻在某点刷新出一定数量的怪物，系统刷新出来的怪物只会存在1秒，下一秒就会消失。如果那个时刻小G正好在那个点，那么小G可以秒杀（秒杀所用时间忽略不计，下同）这个点上的所有怪物。 另外，小G还有B次放大招的机会，每次放大招可以秒杀当前点及与其直接相邻的点上的所有怪物。大招有5秒的冷却时间，也就是说每次放大招后要经过5秒才能再次放大招（假设在第1秒时发了大招，那下一次发大招的最早时间是第6秒）。 小G可以从任意点开始。系统...

普及组模拟 总结 T1 用了10分钟 做了第一种方法 后来自己测数据发现不对（会自己出数据了 ☺） 思考了10分钟 用10分钟做了AC的方法 T2 开始知道用dp 用20分钟手推了一些答案 用了10分钟思考 一直思考不出答案间的关系 后来自己打了个暴力才知道手推答案有问题 但是改完后还是不知道关系 最后决定按照《选数》的思路来dfs 得了60分 看了老师的解题报告才知道dp思路 后面AC T3 留到最后才写的 用bfs打了个暴力 一直弄到11:20 还没有过样例 但最后莫名骗到20 后面看了老师思路 但还是不懂 T4 开始觉得用线段树来做 后面做着做着 发现用邻接表来做更简单 所以用邻接表暴力...

表达式（波兰式：前缀表达式 逆波兰式：后缀表达式） 中序求后缀（后缀和后序差不多）  注意：比赛中表达式求后缀中的表达式一般是中序 答案可能有多个  我们拿一个式子讲：a*(b+c)-d 我们先找到最后才运算的符号 - 将 - 号放在根部 -  然后它的左边为左子树，右边为右子树 因为右边只有一个d 所以d就可以直接进树  - \ d  接着，我们看它的左子树 a*(b+c) 重复第一步，找到最后才运算的符号 * 将 * 号放在左子树的根节点  - / \ * d  然后同理，它的左边为左子树，右边为右子树 因为左边只有一个a 所以a就可以直接进树  - / \ * d / a  右边还有（b...

普及组模拟赛 1.Problem 1. 小 X 的加法难题 Input file: sum.in Output file: sum.out Time limit: 1 second Memory limit: 256 MB  第一节编程课上，老师要求大家写一个程序计算两个正整数的和。 看到小 X 不屑的眼神后，老师决定给小 X 增加难度。以求 12 和 3 的和为例，老师在 12 + 3 这个 原始式子里加入一些无用的空格，再把它交给小 X。 这下小 X 傻眼了，希望你帮帮他。 Input 第一行包含一个字符串，表示老师给小 X 的式子。 Output 若式子的结果不超过 108，则第一行包含...

2020-10-24

模拟赛 1.斐波那契 题目描述  输入格式  输出格式  输入输出样例 输入 666 10086 输出 7126 说明/提示  题意分析 求斐波那契数列%k后的值 解题思路 暴力 注：1%1=0 AC代码 #include<cstdio> using namespace std; long long n,k,f[1000005]; int main() {  scanf("%lld%lld",&n,&k); f[1]=f[2]=1; //初值 for(long long i=3;i<=n;i++)//斐波那契 f[i]=((f[i-1]%k...

模拟赛 1.魔法部落  题意分析 就是求30+31+……+3n 解题思路 快速幂+逆元 首先将30+31+……+3n *3 变成31+32+……+3n+3n+1 用第二个式子-第一个式子 得 (3n+1-30)/2=(3n+1-1)/2 用快速幂求出3n+1 再用玄学逆元/2 AC代码 #include<cmath> #include<cstdio> using namespace std; const long long MOD=1000000007; long long n; long long ksm(long long x,long long y)//快速幂 {...