这个题自己当时主要还是思维限制，只想着怎么能有类似于dfs序线段树那种操作，或者是就某个点对他的子树做一个什么类似于线段树的打标记处理。。但是感觉太复杂了，没搞出来，而且也没有把可以离线这个点利用起来，还是too young
正解是在dfs过程中维护一个线段树，这棵树的下标是代表了当前dfs到的深度（而非节点），看到这儿就感觉是个很妙的操作，这样的话只需要每次进入到一个节点的时候把对应的属于该节点的所有的操作（这个需要离线处理，把对应的操作存用个vector存起来就可以了）都处理一遍，也就是把对应的所有的区间上的数值加上，dfs离开的时候把对应的区间上的数值减去，回滚一下，就可以保证在dfs过程中就把所有的操作处理完了。
这个题倒是不难，但是我当时对于题目的理解导致写出来很复杂，所以记一下踩的坑。其实就是最短路树的应用，我的想法是先删掉不在树上的边，然后对于树上的边先删除连叶子的边，以此类推。这样写倒是没有错也可以过。
但是！这个题题面里说的是最多k个，所以其实根本不用考虑去掉非树边什么的，假如k>n-1的话只输出n-1条树边也是对的！这就省了好多代码了。其次，根本不用使用拓扑排序那样的处理过程（就是先去掉叶子这种），因为想一下dijkstra的过程就可以发现，每次从优先队列中取出来一个节点后，这个节点的前驱最短路其实已经确定了，只要在这时候把其前驱记录下来，根据dijkstra的每一步往外扩展一步的操作，按照这个顺序搞下去最后的记录表中的顺序其实就是拓扑序。。。。依次输出即可。 继续阅读“[CF][图论][最短路树] codeforces 1076D Edge Deletion”
https://cn.vjudge.net/problem/UVALive-4064
简单的极角排序应用，枚举每个点作为角点，然后按照角度顺时针枚举另一个点，在这个过程中递推记录下对于枚举的点有多少个钝角/直角出现。由于一个钝角/直角唯一的对应一个钝角/直角三角形，因此最后只需要把C(n,3)-钝角数量作为答案即可。
坑点：lrj的书上和各位dalao的blog都说的是锐角或直角，呵呵，wa了两个多小时最后翻别人代码发现是只能锐角不能直角，服了，改了就过了，也不知道网上这么多人都写得锐角或者直角是怎么写出来只能锐角的代码的。
继续阅读“[坑][计算几何][极角排序][利用已有信息] UVALive 4064 Magnetic Train Tracks”
题目链接 https://cn.vjudge.net/problem/UVA-1634
最近有把紫书dp这一章的习题搞完的打算。。。这个题本来看vjudge上就不到20个人做想放弃的，强迫症导致开了题就得ac。
其实和之前的那个极角排序的题目感觉很像，只不过如果还是按照那个思维来的话会遇到一个问题无法解决，就是不能在保证为凸多边形的情况下满足无后效性。。。这个光从样例就可以试出来，所以就卡了半小时没有头绪。索性直接搜了。。。但是没想到这个搜题解讲的也很迷而且做的人很少，就直接去vjudge看了代码，看到dp是二维的和转移方程顿时懂了，和之前那个题一样都是枚举左下角的点，但是这个要求dp的时候考虑两维，也就是dp[i][j]表示当前左下角点对应的以i为顺时针倒数第一个点（也就是紧挨着枚举点s的点）且以就j为顺时针倒数第二个点的最大多边形面积。 继续阅读“[紫书][DP][计算几何] UVA1634 The Picnic”
题目链接 https://cn.vjudge.net/problem/UVALive-4080
最短路基础题，有意思的部分在于最短路树这个东西的应用，还有对复杂度的正确估算（莽
看题目意思，基本上能确定枚举那条要去除的边然后算每种情况的c，但是如果直接这样的话复杂度会是n*m²*logn,就题目数据量而言基本上不可能过的。所以就要找其他方法来降低复杂度，考虑到，去掉一条边也许不会对以某些点为原点的到每个点的单源最短路产生影响（也就是不在这些点的最短路树上的边），可以试着预处理出来初始状态下每个边的影响到的点的集合，在枚举到这条边的时候只需要重新计算这些点的最短路而不用每次都计算所有点的最短路，这样的话可以把复杂度降低到n²mlogn。不得不吐槽一下这个解法，说实话感觉并没有降低多少就卡过了时限，数据刻意友好么。。。。比赛的话就算能想到这个也不一定敢写吧emmm
坑点是有重边，果然做图论最重要的是搞清楚图的类型。。。重边啊自环啊什么的真的烦,还有一开始小根堆写成大根堆了，又是wa又是t的 继续阅读“[蓝书][图论][最短路][坑] UVALive 4080 Walfare And Logistics”
题目链接 https://cn.vjudge.net/problem/UVA-11529
（复习期末期间日常的小题
想到了考虑每个点被多少个三角形包围，但是没想到怎么算。。。主要还是计算几何太萎le，完全没有想到可以极角排序处理emmm。
具体的就是，考虑每一个点被多少个三角形包含，但是直接考虑也不好计算，可以考虑反向计算出不被多少个三角形包含，这个计算就要用到极角排序了。。。循环遍历每个点，在每个xi点，都对所有的其他点（姑且称为角点吧）相对于这个xi点的极角做一个排序，然后利用三角形的性质，选一个方向（顺时针或者逆时针都行），依次考虑“以每个角点为最小极角与之角度差小于pi的最大角度点之间有多少个点“，可能难以理解，画个图就好了，算出来点的数量p（p包含最大的那个点）之后C(p,2)就是“包含当前最小角点的所有的不覆盖xi点的三角形数量”，依次累加就好了。。。
另外，画个图就会发现，还需要考虑圆周转一圈的情况，所以要把排序后的极角数组复制一遍，而且复制出来的这个数组每个元素还要加2pi！（这个自己试试就知道了）
然后就是找最大点的步骤要小心，很容易写错。。莫名其妙，也可能是我最近复习微机原理复习傻了。 继续阅读“[数学][计算几何][极角排序][递推] UVA 11529 Strange Tax Calculation”
题目链接 https://cn.vjudge.net/problem/UVA-1543
复习微机原理复习到吐，随便翻了个题写了写缓和一下脑子。。。。
一开始看题目给的信息总想着怎么能用到那个1/2sinα，然后就没什么头绪（后来发现给这公式只是用来计算三角形的）。后来开始想正常的dp套路，也就是以xx为结尾/开头的xx的大小，然后发现这个形状的大小不能只由一边来确定，所以加了一维表示另外一边的位置，最后整出来状态就是dp[i][j][k]表示在i到j之间选k个点能组成的最大的多边形大小 继续阅读“[DP][紫书][计算几何] UVA 1543 Telescope”
讲道理90%的工作都是在做图像处理。。。。opencv各种操作。
一完工赶紧专心复习emmmm
大致步骤：
首先必要的库
import cv2 import numpy as np import matplotlib.pyplot as plt import pytesseract from PIL import Image import os from PyQt5 import QtCore, QtGui, QtWidgets, Qt from PyQt5.QtCore import * from PyQt5.QtWidgets import *
① 预处理（灰度，直方图均衡，滤波）
def stechCr(img):
dst = cv2.equalizeHist(img)
if debug:
cv2.imshow('dst',dst)
cv2.waitKey(0)
cv2.destroyAllWindows()
return dst
gray = cv2.fastNlMeansDenoisingColored(img, None, 10, 3, 3, 3)
gray=cv2.cvtColor(gray,cv2.COLOR_BGR2GRAY)
img,gray=makepic(gray)
② 提取ROI，主要用opencv的findContours找到背景下最大的轮廓，也就是卡面本身。
继续阅读“python小项目——实现校园一卡通图片信息识别”
在尝试了各种操蛋的手机端python ide之后忽然意识到可以在服务器上装jupyter然后手机浏览器打开emmmm
当然电脑端也能用啦，只不过我这台小鸡性能太垃圾所以意义不大
主要参考https://bitmingw.com/2017/07/09/run-jupyter-notebook-server/
不过他的文章中有一点问题就是，设置可以远程访问的时候有一步设置
c.NotebookApp.ip = '*'
，但是其实有时候是不行的（我也不知道为什么），如果不行就改成
c.NotebookApp.ip = '0.0.0.0'
另外，这是我用来跑ss的小鸡所以没有https的操作，直接跳过（反正我也懒得弄
基本上的步骤就是
①在服务器上装jupyter（废话
②生成配置文件 命令：
jupyter notebook --generate-config
③生成密钥 ，见下图
④修改配置文件
c.NotebookApp.ip='0.0.0.0' # 就是设置所有ip皆可访问 c.NotebookApp.password = u'sha:ce...' # 刚才复制的那个hash密钥 c.NotebookApp.open_browser = False # 禁止自动打开浏览器 c.NotebookApp.port =8888 #随便指定一个端口
⑤启动jupyter notebook应用，nohup 设置为断开ssh后继续运行的方式
# 启动 notebook 服务 nohup jupyter notebook > /dev/null 2>&1 &
如果想终止 notebook 应用，请找到含有 jupyter-notebook 的进程，并用 kill杀掉它。
⑥本地浏览器地址栏输入服务器ip:8888 就可以看到登录界面了，输入密码即可
