sicily专题
sicily 1225. 电子眼
/图其实是一个树加了一条边，我们找到这个环，然后枚举其中一条边的两端，看是在哪里安装电子眼。剩下的就是普通的树形dp了。。 #include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int MAXN = 101000; vector<
sicily 4425Easy Sort
进行一次翻转之后，接下的翻转肯定只交换相邻的数，统计逆序对。 用树状数组做，新序列保存在arr中， 没读入一个arr[i],就在c[arr[i]]位置加1，这时候arr[i]与之前输入的i个数中构成逆序的就是i-sum(arr[i])拉。。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm
sicily 4876. PLAĆE 每周一赛二
树形结构转线性结构，先dfs，得到每一个结点的开始和结束访问时间s，t 记录一个数组A[1...t] 那么更新一个结点的就是A[s]+=v,A[t]-=v 采用树状数组做，OMlog2*N复杂度 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector>
sicily 1876. Basic Graph Problem 线段树+并查集+路径压缩
线段树或者RMQ都可以做，虽然是不是动态变化的，但是用线段树做也不错，，而且最近才开始弄线段树，当练练手。。。 一定要路径压缩的并查集，，不然线性的话，耗时过高。。。 而且不能写递归的路径压缩，我猜得。。。 因为n<=100000，一般20000就会栈爆的，，，， #include<iostream> #include<cstdio> #include<cstring> using
Sicily 1099 Packing Passengers
Constraints Time Limit: 1 secs, Memory Limit: 32 MB Description PTA, Pack ‘em Tight Airlines is attempting the seemingly impossible—to fly with only full planes and still make a profit. Their strategy
Sicily Shortest path in unweighted graph
Source: http://soj.sysu.edu.cn/show_problem.php?pid=1003&cid=2104 Description 输入一个无向图，指定一个顶点s开始bfs遍历，求出s到图中每个点的最短距离。 如果不存在s到t的路径，则记s到t的距离为-1。 Sample Input 输入的第一行包含两个整数n和m，n是图的顶点数，m是边数。1<=n<=1000
Sicily Connect components in undirected graph
Source: http://soj.sysu.edu.cn/show_problem.php?pid=1002&cid=2104 Description 输入一个简单无向图，求出图中连通块的数目。 Sample Input 输入的第一行包含两个整数n和m，n是图的顶点数，m是边数。1<=n<=1000，0<=m<=10000。 以下m行，每行是一个数对v y，表示存在边(v,y)。顶
Sicily 图的广度优先搜索
Source: http://soj.sysu.edu.cn/show_problem.php?pid=1000&cid=2104 Description 读入图的邻接矩阵以及一个顶点的编号（图中顶点的编号为从1开始的连续正整数。顶点在邻接矩阵的行和列上按编号递增的顺序排列。邻接矩阵中元素值为1，表示对应顶点间有一条边，元素值为0，表示对应顶点间没有边），输出从该顶点开始进行广度优先搜索（B
Sicily 1753 解码
Source: http://soj.sysu.edu.cn/1753 Description ZX是另一头04级的牛，他现在在UPen。他跟LLK经常通信，但他不喜欢直接把信息发给LLK，而是把信息通过一个规则转换后再发给LLK，这让LLK很郁闷。他的规则如下：如果字符x出现的n次，则将这几个连在一起的字符表示为xn，例如aaa->a3。为了能读取ZX的信息，亲爱的师弟师妹们，你们可以帮L
sicily 10359 Valuable Jewellery
贪心 题意: 背包问题,n个物品,有重量有价值.不同的是,有k个背包,每个背包有重量上限,且最多只能放一个物品.问最大价值 数据范围: n,k<=300000,重量,价值<=10^6,背包上限<=10^8 思路: 每个背包最多只能放一个物品,那这题一下子就水了 贪心,背包用一个map存放,物品按价值递减排序.扫描每个物品,每次在map里找这个物
sicily 1215. 脱离地牢
Description 在一个神秘的国度里，年轻的王子Paris与美丽的公主Helen在一起过着幸福的生活。他们都随身带有一块带磁性的阴阳魔法石，身居地狱的魔王Satan早就想得到这两块石头了，只要把它们熔化，Satan就能吸收其精华大增自己的魔力。于是有一天他趁二人不留意，把他们带到了自己的地牢，分别困在了不同的地方。然后Satan念起了咒语，准备炼狱，界时二人都将葬身于这地牢里。 危险！
sicily 1024 magic island
发现n年前草稿。。 最直接思路就是深搜，用 T *g[] 这种形式来构造邻接链表，注意是无向图。 从出发点开始搜，标记已访问点，遍历未访问的邻接点，把所有可能都计算一次， 全局变量记录最大距离。 很不幸，不知为何超时。（后来发现时忘记 把图清空了） 后来想了想，似乎没说图中有无环，有无孤立点。 应该做访问标记的是 边，而不是点。于是开始胡思乱想怎么才能快速判断 边 是否已访问。
sicily 1003 水题
//简单的模拟..//wengsht#include <iostream>#include <cstdio>#include <queue>using namespace std;int t,n,c[10],card;int no_count;queue<int> q[11];int main(){//freopen("1.txt","r",stdin);scanf("%d
sicily 1136 山海经
//听过大牛线段树讲座。。感觉新手赛要多用线段树//这题线段树RMQ。。一开始真以为是普通RMQ，水了点代码交上去果断TLE//下来看discuss找到建树方法，但是想不出find方法。。放了3天后才重新拿起//find一个区间的时候可以建一条它的线段，处理好左右孩子的有效量转移就可以了/*线段记录:left,right 左右端点xl mxl 从左端到xl有
sicily 1321 dijkstra
//优先队列+dijkstra//很久没写图生疏了//输入处理麻烦一点，有权棋盘两点间最短路，没个棋格都有一个权值#include<iostream>#include<cstring>#include<queue>#include<cstdio>#include<vector>#define INF 9999999999using namespace std;int sa[]
sicily 1214 信号分析
//找出从1到L的二进制回文数个数//a2n = an a4n+1 = 2*a2n-an a4n+3 = 3*a2n+1 - 2*an//难点在于看出公式是回文式//模拟下OK#include <iostream>using namespace std;int s[34];int f( int L ){int result = 0;while( L ) { result++
sicily 1142 迭代深搜
//迭代深搜，继续百度之//第一次裸深搜，只不过听了同学说最多2*n加了个小剪枝 时间超过10s//第二次广搜+字典树存状态，神勇到达0.8s但是 内存超过32m...//如此如此。。//最后百度之才知道有种迭代深搜，就是逐层增加搜索次数，这样实现结果从小到大状态搜索//有点像BFS+DFS。。//题意，给过最多26个数字，输出最小排序翻转次数，煎饼堆排序#include <iost
sicily 1686
//一整天被卡在这道题中。。//经过5次小改函数，3次大改刷了重写。。//TLE 4次 WA 七八次//一开始一位是水题用自己种过的树水。。4次TLE后//重新看看那篇大牛写的文章。。原来处理一段数据需要用标记。。果断重写//之后更纠结，因为把本来标记线段节点当线段边界用，果断WA4次//之后还水，各种数据一直给力，各种WA。。//好吧。。我算是服了，重写。。//Accept出来，
sicily 1684
//找匹配，要求保证最大权有最小值//一开始开挂 优先队列+无限增广 直接水 3.04s过，发现status都1s内的。。那么水//修改保留每次增边已得匹配边 直接0.1s过~~~#include <iostream>#include <queue>#include <cstring>#include <cstdio>#define INF (1<<29)using namespa
sicily 1876 1949 不相交集+线段树
//不相交集+线段树//输入 s[1..n]//输入 si,ei s[si..ei]之间最小值与最大值无向连通 //一开始以为直接 si ei连起。。悲剧//找段最小值最大值用线段树 貌似比较慢//不相交集用树#include <iostream>#include <cstdio>#define mx 100001#define __mx(a,b) (a>b)?a:b#def
sicily 1089 欧拉函数递推
//f[n] = f[n-1] + fai[n] //欧拉函数 质因子个数/n 包括本身//fai[n] = n * (1 - 1/a)*.... a为质因子#include <iostream>#include <cstring>#include <cmath>#define mx 1000010using namespace std;int prime[mx];bool i