csu专题
csu(背包的变形题)
题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物，m个人，每个人的魔法消耗和魔法伤害不同，求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）
这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
CSU - 1556 Jerry's trouble(快速幂取模)
【题目链接】：click here 【题目大意】：计算x1^m+x2^m+..xn^m(1<=x1<=n)（ 1 <= n < 1 000 000, 1 <= m < 1000） 【解题思路】：快速幂取模 代码： solution one: #include<bits/stdc++.h>#define LL long longusing namespace std;const
[CSU - 1811 （湖南省赛16）] Tree Intersection （dfs序维护子树+离线询问+树状数组）
CSU - 1811 （湖南省赛16） 给定一棵树，每个节点都有一个颜色 问割掉任意一条边，生成的两个子树中颜色集合的交集大小 这个是 dfs序处理子树 + 离线询问 + bit维护 的解法 首先问题转化为求解一个子树中有多少种颜色以及独有颜色的数量 用总的颜色数量减去独有颜色数量即为这棵子树的答案 先做一遍 dfs，再按 dfs序重新组建颜色序列 这样对子树的询问，就变成
[CSU - 1811 （湖南省赛16）] Tree Intersection （启发式合并）
CSU - 1811 （湖南省赛16） 给定一棵树，每个节点都有一个颜色 问割掉任意一条边，生成的两个子树中颜色集合的交集大小 问题可以转化为任意一棵子树中， 这个子树中的颜色数量和只在这个子树中出现的颜色的数量 用总的颜色数量减去独有颜色数量即为这棵子树的答案 从 lcy大爷那里学到了机智的启发式合并的做法 对每个点维护一个 map 来记录这个点为根的子树中颜色的及其数
csu 1541: There is No Alternative（最小生成树 Kruskal）
题目链接：点击打开链接 题意就是 求出图中最小生成树的必要边的个数以及这些边权值的和 首先用Kruskal求出最小生成树的值 保存最小生成树中的边 然后枚举每条边 如果这条边是在刚才最小生成树中的边 则把它删除再求最小生成树的值 与之前的进行比较 如果值大了 则这条边是必须的 保存这条边的值 #include<cstdio>#include<cstdlib>#incl
csu 1526: Beam me out!（强连通分量 Tarjan）
从1开始的所有路径 是否都能到达n 所用的步数是否是无限的 1）判断n是否可达 2）判断是否有环 3）判断是否所有的点都可以从1开始可达 #include <cstdio>#include <iostream>#include <cstring>#include <cmath>#include <algorithm>#include <string.h>#includ
CSU 1623 Inspectors（二分图最大权匹配 KM算法）（UVAlive 6879）
题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1623 选用一些边 覆盖所有的点 使得这些边的权值和最小 比赛时的想法是用一般图最大权匹配 样例也过了 但是提交总是WA 看kuangbin模版中写的是点的个数必须是偶数。。是不是有可能是这个原因 改用二分图最大权匹配之后就过了。。。。 #include <cstdio>
csu 1601 War（并查集）
1601: War Time Limit: 1 Sec Memory Limit: 128 MB Submit: 82 Solved: 24 [ Submit][ Status][ Web Board] Description AME decided to destroy CH’s country. In CH’ country, There are N vill
CSU - 1446 Modified LCS
Description Input Output Sample Input 35 3 4 15 3 110 2 2 7 3 3100 1 1 100 1 2 Sample Output 4350 题意：求两个等差序列相同的元素个数 思路： 首先我们可以假设得到解是当 F1 + D1 * K1 = F2 + D
CSU 1620: A Cure for the Common Code（KMP+区间DP）
Description Input Output Sample Input abcbcbcbcaabbbcdcdcdabbbcdcdcd0 Sample Output Case 1: 7Case 2: 11 HINT 题意：给一个小写子母的串，相邻相同的子串可以合在一起，问这个串合并后最短可得多长。 解题：KM
CSU 1335: 高桥和低桥(扫描线) 13年省赛题
1335: 高桥和低桥 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 957 Solved: 279 [ Submit][ Status][ Web Board] Description 有个脑筋急转弯是这样的：有距离很近的一高一低两座桥，两次洪水之后高桥被淹了两次，低桥却只被淹了一次，为什么？答案是：因为低桥太低了，第一次洪
CSU 1329: 一行盒子(双向链表)经典 13年省赛题
1329: 一行盒子 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 872 Solved: 176 [ Submit][ Status][ Web Board] Description 你有一行盒子，从左到右依次编号为1, 2, 3,…, n。你可以执行四种指令： 1 X Y表示把盒子X移动到盒子Y左边（如果X已经在Y的左边
CSU 2172 买一送一
题目：点击打开链接 题意：略。 题解：首先要看出来这是一棵树，然后就想怎么去重 设当前节点为u，商品类型为a[u]，父节点为fa 在dfs的过程中维护这几个信息： 1、 上一个以a[u]为第二分量的二元对的数目pre[a[u]] 2、 从根到fa的不同商品类型的数目num，即以当前a[u]为第二分量的二元对的数目 3、 从根到fa的答案ans[fa] 那么当前的答案就是ans[u]
科罗拉多州立大学发布 CSU-MLP 模型，用随机森林算法预测中期恶劣天气
： By 超神经 内容一览：近期，来自美国科罗拉多州立大学与 SPC 的相关学者联合发布了一个基于随机森林的机器学习模型 CSU-MLP，该模型能够对中期 (4-8天) 范围内恶劣天气进行准确预报。目前该成果刊已发表在《Weather and Forecasting》期刊上。 关键词：恶劣天气 机器学习 随机森林 作者 | 缓缓 编辑 | 三羊 天气预报尤其是恶劣天气预报对人们日常
CSU 1204 Rectangles (二分)
1204: Rectangles Time Limit: 1 Sec Memory Limit: 128 MB Submit: 732 Solved: 104 [ Submit][ Status][ Web Board] Description 如果限定矩形的边长必须为整数，且周长为定值L，那么面积在[A, B]范围内不同的矩形一共有多少个呢？ 在这个问题中，当且仅当两个
CSU 1337 费马大定理
CSU 1337 Time Limit:1000MS Memory Limit:131072KB 64bit IO Format:%lld & %llu Description 费马大定理：当n>2时，不定方程an+bn=cn没有正整数解。比如a^3+b^3=c^3没有正整数解。为了活跃气氛，我们不妨来个搞笑版：把方程改成a^3+b^3=c3，这样就有解了，比如a=4, b=
csu 1803 16年湖南省赛
1803: 2016 Time Limit: 5 Sec Memory Limit: 128 MB Submit: 628 Solved: 413 [ Submit][ Status][ Web Board] Description 给出正整数 n 和 m，统计满足以下条件的正整数对 (a,b) 的数量： 1. 1≤a≤n,1≤b≤m; 2. a×b 是 2
CSU Monthly 2012 Aug.
http://acm.csu.edu.cn/OnlineJudge/contest.php?cid=2026 这次参加比赛，结果就被完虐了 B题 我用的bfs ，随便写写竟然1A，我以为题目肯定还有我没有考虑到的情况 #include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using
[ACM] CSU 1548 Design road （三分）
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1548 第一次接触三分，题意和代码参考的网上的。 题意：修路：从(0,0)~(x,y)，n个数表示有第二行开始有n行表示有n条河，tx是河的起始位置，ty是河的宽度，有水的地方要修桥，而x，y表示修路的端点，C1表示修路每米的花费，C2表示修桥每米的花费，问你最后花费的最少金额！ 思路：先把有
[ACM] CSU 1553 Good subsequence(尺取法）
题目地址：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1553 给定n的数的序列，求最长连续区间满足区间内的数最大值与最小值的差<=k (尺取法) const int maxn=10010;int num[maxn];int n,k;int MIN,MAX;int main(){while(scanf("%d%d",&n,&k)
csu 1950: 谈笑风生 卡特兰数
题目链接点这里 基佬出的毒瘤题啊。。。 看完题目我们很容易把第x个左括号和其右括号内的看成独立一部分设为Q，枚举这个里面的括号数。这里很简单，， 然后那？，，然后还剩下Q左右的2部分。。接下来该怎么考虑？。。一开始我是把2部分放在一起考虑的，结果非常复杂，考虑的东西非常多 其实那，我们只需要单独考虑2部份就可以了。 我们需要知道一个公式：Cm(i,j)=C(i+j,j)
G - Parenthesis （CSU - 1809） 湖南省赛平衡串交换（线段树+RMQ）
找了半天的规律 发现居然是这样。。 序列中第 i 个字符是 ‘(‘, pre[i]=pre[i]+1 ;序列中第 i 个字符是 ‘)’, pre[i]=pre[i]−1 ; 这样, 又因为最初的序列是平衡的。当序列不“平衡”当且仅当存在一个数k，使得 pre[k]<0(1≤k≤N) 。 只需要用线段树或者RMQ维护区间最小值。 当将第 a 个字符与第 b 个字符交换（假定
CSU 1726: 你经历过绝望吗？两次！ BFS,优先队列求解
1726: 你经历过绝望吗？两次！ Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 507 Solved: 162 Description 4月16日，日本熊本地区强震后，受灾严重的阿苏市一养猪场倒塌，幸运的是，猪圈里很多头猪依然坚强存活。当地15名消防员耗时一天解救围困
CSU 1224 ACM小组的古怪象棋BFS
Description ACM小组的Samsara和Staginner对中国象棋特别感兴趣，尤其对马（可能是因为这个棋子的走法比较多吧）的使用进行深入研究。今天他们又在 构思一个古怪的棋局:假如Samsara只有一个马了，而Staginner又只剩下一个将，两个棋子都在棋盘的一边，马不能出这一半棋盘的范围，另外这 一半棋盘的大小很奇特(n行m列)。Samsara想知道他的马最少需要跳几