[紫书][DP][计算几何] UVA1634 The Picnic
题目链接 https://cn.vjudge.net/problem/UVA-1634
最近有把紫书dp这一章的习题搞完的打算。。。这个题本来看vjudge上就不到20个人做想放弃的，强迫症导致开了题就得ac。
其实和之前的那个极角排序的题目感觉很像，只不过如果还是按照那个思维来的话会遇到一个问题无法解决，就是不能在保证为凸多边形的情况下满足无后效性。。。这个光从样例就可以试出来，所以就卡了半小时没有头绪。索性直接搜了。。。但是没想到这个搜题解讲的也很迷而且做的人很少，就直接去vjudge看了代码，看到dp是二维的和转移方程顿时懂了，和之前那个题一样都是枚举左下角的点，但是这个要求dp的时候考虑两维，也就是dp[i][j]表示当前左下角点对应的以i为顺时针倒数第一个点（也就是紧挨着枚举点s的点）且以就j为顺时针倒数第二个点的最大多边形面积。 继续阅读“[紫书][DP][计算几何] UVA1634 The Picnic”
[蓝书][图论][最短路][坑] UVALive 4080 Walfare And Logistics
题目链接 https://cn.vjudge.net/problem/UVALive-4080
最短路基础题，有意思的部分在于最短路树这个东西的应用，还有对复杂度的正确估算（莽
看题目意思，基本上能确定枚举那条要去除的边然后算每种情况的c，但是如果直接这样的话复杂度会是n*m²*logn,就题目数据量而言基本上不可能过的。所以就要找其他方法来降低复杂度，考虑到，去掉一条边也许不会对以某些点为原点的到每个点的单源最短路产生影响（也就是不在这些点的最短路树上的边），可以试着预处理出来初始状态下每个边的影响到的点的集合，在枚举到这条边的时候只需要重新计算这些点的最短路而不用每次都计算所有点的最短路，这样的话可以把复杂度降低到n²mlogn。不得不吐槽一下这个解法，说实话感觉并没有降低多少就卡过了时限，数据刻意友好么。。。。比赛的话就算能想到这个也不一定敢写吧emmm
坑点是有重边，果然做图论最重要的是搞清楚图的类型。。。重边啊自环啊什么的真的烦,还有一开始小根堆写成大根堆了，又是wa又是t的 继续阅读“[蓝书][图论][最短路][坑] UVALive 4080 Walfare And Logistics”
[数学][计算几何][极角排序][递推] UVA 11529 Strange Tax Calculation
题目链接 https://cn.vjudge.net/problem/UVA-11529
（复习期末期间日常的小题
想到了考虑每个点被多少个三角形包围，但是没想到怎么算。。。主要还是计算几何太萎le，完全没有想到可以极角排序处理emmm。
具体的就是，考虑每一个点被多少个三角形包含，但是直接考虑也不好计算，可以考虑反向计算出不被多少个三角形包含，这个计算就要用到极角排序了。。。循环遍历每个点，在每个xi点，都对所有的其他点（姑且称为角点吧）相对于这个xi点的极角做一个排序，然后利用三角形的性质，选一个方向（顺时针或者逆时针都行），依次考虑“以每个角点为最小极角与之角度差小于pi的最大角度点之间有多少个点“，可能难以理解，画个图就好了，算出来点的数量p（p包含最大的那个点）之后C(p,2)就是“包含当前最小角点的所有的不覆盖xi点的三角形数量”，依次累加就好了。。。
另外，画个图就会发现，还需要考虑圆周转一圈的情况，所以要把排序后的极角数组复制一遍，而且复制出来的这个数组每个元素还要加2pi！（这个自己试试就知道了）
然后就是找最大点的步骤要小心，很容易写错。。莫名其妙，也可能是我最近复习微机原理复习傻了。 继续阅读“[数学][计算几何][极角排序][递推] UVA 11529 Strange Tax Calculation”
[DP][紫书][计算几何] UVA 1543 Telescope
题目链接 https://cn.vjudge.net/problem/UVA-1543
复习微机原理复习到吐，随便翻了个题写了写缓和一下脑子。。。。
一开始看题目给的信息总想着怎么能用到那个1/2sinα，然后就没什么头绪（后来发现给这公式只是用来计算三角形的）。后来开始想正常的dp套路，也就是以xx为结尾/开头的xx的大小，然后发现这个形状的大小不能只由一边来确定，所以加了一维表示另外一边的位置，最后整出来状态就是dp[i][j][k]表示在i到j之间选k个点能组成的最大的多边形大小 继续阅读“[DP][紫书][计算几何] UVA 1543 Telescope”
python小项目——实现校园一卡通图片信息识别
讲道理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小项目——实现校园一卡通图片信息识别”