最近很多小伙伴都在问ProgrammingComputerVisionwithPython和学习笔记一这两个问题，那么本篇文章就来给大家详细解答一下，同时本文还将给你拓展3DComputerVisio
最近很多小伙伴都在问Programming Computer Vision with Python 和学习笔记一这两个问题，那么本篇文章就来给大家详细解答一下，同时本文还将给你拓展3D Computer Vision、ACM International Collegiate Programming Contest, Damascus University Collegiate Programming Cont...、ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2...、ACM International Collegiate Programming Contest, JUST Collegiate Programming Contest (2018)等相关知识，下面开始了哦！
本文目录一览：- Programming Computer Vision with Python （学习笔记一）（learn programming with python in 100 steps）
- 3D Computer Vision
- ACM International Collegiate Programming Contest, Damascus University Collegiate Programming Cont...
- ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2...
- ACM International Collegiate Programming Contest, JUST Collegiate Programming Contest (2018)
Programming Computer Vision with Python （学习笔记一）（learn programming with python in 100 steps）
介绍
《Programming Computer Vision with Python》是一本介绍计算机视觉底层基本理论和算法的入门书，通过这本收可以学到有关对象识别、基于内容的图像搜索、光学字符识别、光流法、跟踪、三维重建、立体成像、增强现实、姿态估计、全景创建、图像分割、降噪、图像分组等技术的实现原理。
英文版PDF下载：https://it-ebooks.info/book/836/
中文版介绍：http://book.douban.com/subject/25906843/
Python图像处理
先介绍基本的图像处理，包括图像的读取、转换、缩放、导数计算、画图和保存，这些知识将为后面内容的学习打下基础。
作者选择Python编写例子，并使用一个叫PIL(Python Imaging Library)的第三方图像处理库。这里特别指出的是：PIL库开发不活跃，并且很久没更新了，所以有人基于它fork了另一个分支叫Pillow，Pillow保持与PIL相似的使用接口，解决了许多Bug，并同时兼容Python2和Python3，目前开发状态活跃。接下来的学习笔记本人都将使用Pillow来代替PIL。
安装Pillow
以Ubuntu系统为例：
#安装python开发工具及包管理工具
sudo apt-get install python-dev python-pip
#安装一些需要支持的图像格式开发包
sudo apt-get install libjpeg-dev libpng-dev libtiff-dev
#安装Pillow图像处理库
sudo pip install pillow Pillow一瞥
Pillow主要包含了对各种图像模式、图像格式、颜色、过滤器的数据结构（对象）表示，实现了对图像模式转换、格式转换、过滤器应用、常规图像处理操作、图像数据算术运算、2D画图等功能，以模块、类对外提供。
首先，先了解一下Pillow库使用的一些基本概念：
Bands（图像通道）
图像的通道即图像像素的组成部分，跟Channel应该是同一个概念。比如RGB图像有3个通道分别为红、绿、蓝。二值图像和灰度图像只有1个通道。PNG图像有4个通道分别为R、G、B和alpha。库中提供的很多图像操作都是分别作用于某个通道的数据。
Modes（图像模式）
图像模式定义了像素的类型和位深，Pillow支持以下模式：
1 (1-bit pixels, black and white, stored with one pixel per byte)
L (8-bit pixels, black and white)
P (8-bit pixels, mapped to any other mode using a color palette)
RGB (3x8-bit pixels, true color)
RGBA (4x8-bit pixels, true color with transparency mask)
CMYK (4x8-bit pixels, color separation)
YCbCr (3x8-bit pixels, color video format)
LAB (3x8-bit pixels, the Lab color space)
HSV (3x8-bit pixels, Hue, Saturation, Value color space)
I (32-bit signed integer pixels)
F (32-bit floating point pixels)
模块概览
Pillow的功能划分为许多模块，我们简单过一下这些模块的功能，以便在看到作者的示例代码时，可以快速知道这些代码功能在Pillow哪些模块中提供。因为作者使用的PIL库已经过时，我们得用新的Pillow库来重写和改进代码。
-
Image模块
提供了一个叫Image的类来表示图像，以下提到的PIL图像指的就是此类的对象。Image对象可以使用Image.new、Image.fromarray、Image.frombytes、Image.frombuffer等方法来构造，也可以open一张图片来构造。Image类提供了一些对图像进行简单处理的方法（如：convert、copy、crop、filter、resize、rotate、save、show、transform等）和图像的基本属性/信息。以下代码示例打开一张图片，旋转45度后显示出来：from PIL import Image im = Image.open("bride.jpg") im.rotate(45).show() ImageChops模块
提供了一些对图像颜色通道的算术运算，Chops为Channel Operations的缩写，这些运算通常是对两幅图像进行的，并返回一幅处理后的图像，大部分操作目前只支持8-bit通道。-
ImageColor模块
包含一个颜色表和一个从CSS3表示的颜色到RGB颜色的转换器，主要用于方便构造Image对象，即PIL.Image.new(mode, size, color=0)的color参数支持以下形式：16进制的颜色表示，如#rgb, #rrggbb
rgb函数，如rgb(255,0,0), rgb(100%, 0%, 100%)
HSL（色相、饱和、亮度）函数，如hsl(0,100%,100%），色相取值为0到360，饱和度和亮度取值为0%到100%
常规的HTML颜色名字，如red, Red
ImageCms模块
提供对LittleCMS2色彩管理引擎的支持。Little CMS是最流行的开源色彩管理库之一。ImageDraw模块
提供简单的2D画图功能，比如画点、画线、画矩形、多边形、文本、弧形、椭圆等，支持字体设置。ImageEnhance模块
提供一些类用于图像增强操作，比如边缘锐化、色彩平衡、对比度和亮度调节等。ImageFile模块
提供图像文件的打开和保存，另外，还提供了一个Parser类，用于支持对图片边读边解码（比如图片边从网络上下载边解码的情景）。-
ImageFilter模块
预定义了一些过滤器，可以在Image.filter(filter)中作为参数使用：BLUR（模糊效果）
CONTOUR（轮廓）
DETAIL（细节）
EDGE_ENHANCE（边缘加强）
EDGE_ENHANCE_MORE（边缘加强）
EMBOSS（浮雕效果）
FIND_EDGES（查找边缘）
SMOOTH（使光滑）
SMOOTH_MORE（使光滑）
SHARPEN（锐化）
ImageFont模块
定义了类ImageFont表示位图字体（点阵字体），字体对象可以作为参数传给ImageDraw.Draw.text(xy, text, fill=None, font=None, anchor=None)以指定的字体画文本。
PIL使用自有格式存储位图字体，从1.1.4开始，支持TrueType和OpenType字体。ImageGrab模块
从屏幕截图或从剪贴板获取图像，得到Image对象。目前只支持OSX（在3.0增加）和Windows。ImageMath模块
只提供了一个函数ImageMath.eval用于对图像表达式（image expressions）进行求值，这些表达式可以是对图像数据每个bit的位运算（&、|、^、~），也可以是内置的一些运算，比如对图像的每个像素求绝对值、转换图像模式、转float或int等。ImageMorph模块
提供图像形态操作。ImageOp模块
提供一些可直接使用的图像处理操作，如自动调节对比度、自动裁边等。ImagePalette模块
提供调色板类，其中的方法都被标记为experimental，文档不详。ImagePath模块
用于存储和操作2维向量数据。Path对象可传入ImageDraw模块的相关方法。ImageQt模块
支持从PIL图像对象创建PyQt4或PyQt5的QImage对象，方便被Qt使用和显示。ImageSequence模块
支持枚举出一个image sequence（图像系统，如fli动画文件）的所有帧。ImageStat模块
对图像或指定区域的每个通道进行统计，包括count、sum、min/max等。ImageTk模块
支持从PIL图像对象创建Tkinter（Python的GUI库）的BitmapImage和PhotoImage对象。ImageWin模块
支持在Windows平台上创建和显示图像，可与PythonWin和其它UI库一起使用，为这些工具库提供Windows设备上下文或windows句柄的访问。
最后给出一个简单的示例，把书的彩色封面图像转为灰度图像并显示出来：
from PIL import Image
pil_im = Image.open(''cover.png'').convert(''L'')
pil_im.show()效果如下：
小结
下一个笔记将介绍另外几个图像处理相关的库。
3D Computer Vision
3D Computer Vision
Programming Assignment 2 – Epipolar Geometry
You will upload your codes and a short report (PDF) in a zip file to the NewE3 system. Grading will be done
at demo time (face-to-face or Skype).
A C++ Visual Studio project is provided. To build the code, install VS 2019 (Community). When open the
solution file (project2.sln), be sure NOT to upgrade the Windows SDK Version nor the Platform Toolset:
The project should be buildable and runnable on a Windows system. Your tasks are:
- [2p] For the test stereo images (pictures/stereo1_left.png , stereo1_right.png), find 8 matching pairs of
2D points. List them as g_matching_left and g_matching_right. Note: x and y are in [-1,1] range. You
can define the matching manually or
[Bonus: +1~2p to mid-term] use off-the-shelf matching methods (such as OpenGL feature matching or
others). The bonus amount depends on how well you understood and explains your matching method. - [5p] Implement the normalized eight-point method in EpipolarGeometry() to calculate the fundamental
matrix (same as essential matrix). Remember to fill your result in g_epipolar_E To verify your result, the
eight “*multiply:” stdout should output values very close to zero (around e-6 ~ e-7). The rendering
should look like:
(Here the 8 matching are the 8 vertices of the “cube”. But your matching can be anything.) - [1p] Explain what line 382-389 do? What does the “multiply” result means? Why should all the multiply
values be (close to) zero? - [3p] Download the OpenCV sfm module source code at https://github.com/opencv/ope... Go
to \modules\sfm\src\libmv_light\libmv\multiview. Explain the following functions:
FundamentalFromEssential () in fundamental.cc [1p].
MotionFromEssential() in fundamental.cc [1p].
P_From_KRt () in projection.cc [1p].
Note: “HZ” means the textbook “Multiple View Geometry in Computer Vision” by Richard Hartley and
Andrew Zisserman and a pdf is provided for your reference.
WX：codehelp
ACM International Collegiate Programming Contest, Damascus University Collegiate Programming Cont...
签到题
A
4min 1Y
C
45min 3Y
题意
给两个串，要把第一个串变成第二个串。每次选择一个半径r，然后以第一个串的中心为中心，r为半径，左右翻转。问最少几次操作？
题解
细节有点多。
- 先是输出
-1的情况。这个很好考虑 - 然后遍历s1串，对于位置
i，如果需要翻转(s1[i]=s2[n+1-i])，则打上标记1，不需要翻转(s1[i]=s2[i]).则打上标记0，如果翻不翻转都可以(s1[i]=s1[n+1-i])，打上标记2。 - 遍历
[1,n/2]，对于打上标记2的位置，我们要决定是翻还是不翻，根据贪心，我们可以怠惰一点！对于打上标记2的位置，和前一个位置保持一致即可。
F
25min 1Y
题解
统计一下每个数字出现了多少次，出现了x次，对答案的贡献则为x!，相乘即为答案。
J
42min 2Y
题解
按题意模拟。
冷静分析一下开局
- 开场看了C觉得很基本，然后过了A，开始写C。
- C细节没考虑清楚，用了
10min，WA on test 2!
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 100000 + 10;
int T;
char s1[N], s2[N], s3[N];
bool ok[N];
int main() {
scanf("%d", &T);
while (T --) {
scanf("%s %s", s1+1, s2+1);
int n = strlen(s1+1);
int mid = (n+1)/2;
if (s1[mid] != s2[mid]) {
printf("-1\n"); continue;
}
bool gg = 0;
for (int i=1;i<mid;i++) {
if (s1[i]==s2[i] && s1[n-i+1]==s2[n-i+1])
ok[i] = 1;
else if (s1[i]==s2[n-i+1] && s1[n-i+1]==s2[i])
ok[i] = 0;
else
gg = 1;
}
if (gg) {
printf("-1\n"); continue;
}
int ans = 0;
ok[0] = 1;
for(int i=1;i<mid;i++) {
if (ok[i] != ok[i-1])
ans ++;
}
printf("%d\n", ans);
}
}
完全没有考虑s1[i]=s1[n+1-i]的情况。
用了6分钟fix了一下。s1[i]=s1[n+1-i]
int ans = 0;
ok[0] = 1;
for(int i=1;i<mid;i++) {
if (ok[i] != ok[i-1] && ok[i] != 2)
ans ++;
}
printf("%d\n", ans);
然后喵了个呜，又一次WA2
- 我逃跑，用了5min时间过了F
- 用了10min的时间J题
WA2 - 用了5min的时间fix了一下，人调换方向那个地方写得意识有点模糊。
- 用了2min时间fix了一下C，很沙比的错误，比如说
n = 7,前3位，标记为0 2 0的情况就智障掉了。
前期比较容易细节没考虑清楚就上去写代码。C,J这两个模拟题都是这个原因吧。开始写代码之间，大概是抱着“随便搞搞就好”的想法。这种态度很沙比的啊。
- 我在求什么？
- 在模拟的过程，变量会如何变化？
这两个问题都考虑得不清楚吧！
中档题
B
Hash的做法很容易看出。然后就unlimited WA TLE MLE
搞Hash的经验严重不足？
边的种数不会超过n种，因此我们放n个桶。每个桶记录这种边出现的次数。
然后就是对一个XXX进制下，n位数的hash了【双hash保平安】
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int N = 10000008;
const LL MOD1 = 100000007;
const LL MOD2 = 923439347;
int T;
int n, x, y;
int val[N]; vector<int> v;
LL k1[N], k2[N];
unordered_map< LL, int > mp;
int main() {
scanf("%d", &T);
k1[0] = k2[0] = 1;
for(int i=1;i<N;i++) {
k1[i]=k1[i-1]*10007LL%MOD1;
k2[i]=k2[i-1]*20007LL%MOD2;
}
while (T --) {
scanf("%d", &n);
v.clear();
for (int i = 1; i <= n; i ++) {
scanf("%d %d", &x, &y);
if (x > y) swap(x, y);
val[i] = (2*n+1)*x + y;
v.push_back(val[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(int i=1;i<=n;i++) {
val[i] = lower_bound(v.begin(), v.end(), val[i])-v.begin()+1;
}
mp.clear();
LL sum1, sum2;
LL ans=0;
for (int i=1;i<=n;i++) {
sum1 = 0, sum2 = 0;
for(int j=1;j<=n;j++) {
sum1 += k1[val[j]];
sum1 %= MOD1;
sum2 += k2[val[j]];
sum2 %= MOD2;
}
mp[sum1*MOD2 + sum2] ++;
for(int j=i+1;j<=n;j++) {
sum1 += k1[val[j]]-k1[val[j-i]];
sum1 = (sum1%MOD1+MOD1)%MOD1;
sum2 += k2[val[j]]-k2[val[j-i]];
sum2 = (sum2%MOD2+MOD2)%MOD2;
mp[sum1*MOD2+sum2] ++;
}
for (auto x: mp) {
LL v = x.second;
ans += v * (v - 1) / 2;
}
mp.clear();
}
printf("%lld\n", ans);
}
}
G
题意
修改最少的元素，使得序列的GCD为x，LCM为y。
题解
先判-1(一番激烈的讨论)
如果a[i]%x!=0 or y%a[i]!=0，那么i就是个卜。
直觉告诉我们把一个数字变成x,另一个数字变成y，只要其它的数字不卜，生活就有保障了。
- 如果卜的个数>=2,那么答案就是卜的个数了。
- 否则答案可能是1，可能是2，可能是0
- 答案是0，很简单。
- 答案是1，很不简单。我们枚举一下每个数字，看他是否能力挽狂澜，我们把枚举的数字放逐掉，求出其它数字的GCD&LCM(先预处理前缀后缀GCD&LCM)，然后看一看世界末日前怎么办？来得及拯救吗？【具体怎么做，留给读者思考。】
- 答案是2，很简单，加个else
I
题意
n堆石头，两种操作，两人轮流操作。
- 可以从一堆石头中拿走一个石头。
- 如果每堆石子都至少有1个，可以从每堆石头中拿走一个石头。
先手胜？后手胜？
题解
冷静分析一下
- n%2=1. 易证，留给读者思考【读者似乎就我一个人。】
- n%2=0. 这个得冷静分析一下。
- min=1, 先手可以把后手气死。类似于chomp Game的模型。
- min=2, 第一种操作肯定不可以施展的！不然会被气死。既然只能施展第二种操作，胜负显而易见了吧。
- min=3, 先手可以把后手气死。类似于chomp Game的模型。
- min=4, .......
博弈在模型的直觉很重要的吖！这题意识到了chomp Game就很简单了吧。
K
题意
n个点，n条边，多组查询，求两点间最短路。
题解
先去掉一条边edge，那么这个图就是一颗树了。
枚举，u到v是否要经过edge即可。
冷静分析一下中期
- 先用了10min施展G，施展了一大半，然后咕咕咕了。
- 先用了10min施展B题。没考虑清楚自己在hash什么东西，耽误了一段时间，然后
WA11。 - 用了13min过了K。
- 用了3min过了G的样例，
WA2 - 开始unlimited Fix G，中间用了很长一段时间次饭去了。但调G的时间至少有1小时。
- Bug1：没读完就输出结果，WA
- Bug2：复杂度
nsqrt(n).【不错，有创意】 - Bug3：
n=1的特判不到位，搞得后面越界了。一大波RE。
- 用了一个小时Fix B题的Hash，好不容易开始双hash然后MLE。枚举长度后清空，解决了问题。
- 用了半个小时搞I
emmmm....大部分时间都在Fix辣鸡。。。
考虑清楚再写啊······
羊肉粉丝汤弱鸡啊。
感觉30min 4题，2h30min8题是比较合理的。
ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2...
A.Arcade Game（康拓展开）
题意：
给出一个每个数位都不同的数n，进行一场游戏。每次游戏将n个数的每个数位重组。如果重组后的数比原来的数大则继续游戏，否则算输。如果重组后的数是最大的数则算赢，问赢的概率。
题解：
用康拓展开求出n是第几大的数，然后递推后面的概率。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
char s[15];
double ans;
int fac[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
double cal(char *s) {
int res = 0;
int k = strlen(s);
for(int i = 0; i < k; i++) {
int cnt = 0;
for(int j = i+1; j < k; j++) if(s[j]<s[i]) cnt++;
res += fac[k-i-1]*cnt;
}
if(res==fac[k]-1) return 0;
double ans = 1.0/fac[k];
for(int i = res; i < fac[k]-2; i++) ans += ans/fac[k];
return ans;
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%s", s);
printf("%.9lf\n", cal(s));
}
}
B.Unlucky Teacher（模拟）
题意：
Q个题目和M个学生的判卷，求出每道题的答案。如果求不出则输出？。
题解：
模拟即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int q, m;
int num[105], state[105];
char ans[105];
char s1[2], s2[2];
int main() {
scanf("%d", &t);
while(t--) {
memset(state, 0, sizeof(state));
memset(num, 0, sizeof(num));
scanf("%d%d", &q, &m);
while(m--) {
for(int i = 1; i <= q; i++) {
scanf("%s%s", s1, s2);
if(s2[0]==''T'') num[i] = -1, ans[i] = s1[0];
else {
if((num[i]==-1)||((state[i]&(1<<s1[0]-''A''))>0)) continue;
state[i] |= 1<<s1[0]-''A'';
num[i]++;
if(num[i]==3) {
for(int j = 0; j < 4; j++)
if(!(state[i]&(1<<j))) {
ans[i] = ''A''+j;
break;
}
num[i] = -1;
}
}
}
}
for(int i = 1; i <= q; i++) {
if(num[i]>-1) printf("?");
else printf("%c", ans[i]);
if(i < q) printf(" ");
}
puts("");
}
}
C.Connecting Graph（并查集+二分）
题意：
初始有n个点，m次操作。每次操作加一条边或者询问两个点第一次连通的时刻（若不连通输出-1）。
题解：
GYM - 100814 C.Connecting Graph
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int t;
int n, m;
int u, v, k;
int f[N], num[N];
vector<pair<int, int> > g[N];
vector<int> c[N];
bool check(int x) {
int l = 0, r = g[u].size()-1;
while(l <= r) {
int mid = l+r>>1;
if(g[u][mid].first <= x) l = mid+1;
else r = mid-1;
}
int p1 = g[u][r].second;
l = 0, r = g[v].size()-1;
while(l <= r) {
int mid = l+r>>1;
if(g[v][mid].first <= x) l = mid+1;
else r = mid-1;
}
int p2 = g[v][r].second;
if(p1==p2) return 1;
return 0;
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
num[i] = 1;
f[i] = i;
c[i].clear();
g[i].clear();
c[i].push_back(i);
g[i].push_back(make_pair(0, i));
}
for(int i = 1; i <= m; i++) {
scanf("%d%d%d", &k, &u, &v);
if(k&1) {
u = f[u]; v = f[v];
if(u!=v) {
if(num[u]>num[v]) swap(u, v);
for(int j = 0; j < num[u]; j++) {
c[v].push_back(c[u][j]);
f[c[u][j]] = v;
g[c[u][j]].push_back(make_pair(i, v));
}
num[v] += num[u];
num[u] = 0;
c[u].clear();
}
}
else {
int l = 0, r = i-1;
while(l<=r) {
int mid = l+r>>1;
if(check(mid)) r = mid-1;
else l = mid+1;
}
if(check(r+1)) printf("%d\n", r+1);
else puts("-1");
}
}
}
}
D.Frozen Rivers
题意：
一棵n个节点的树，每条边代表一条河。从点1开始边以每秒1个单位开始融化。每个点连的边（不包括连向父亲的）有一条融化完时剩下的该点连的边融化速度降为0.5。q次询问，每次询问某个时刻融化到叶子节点的数量。
题解：
设minn[u]代表节点u的边中权值最小的那个，将点u所有边的权值加上他们与minn[u]的差值。即每条边的权值翻倍再减去minn[u]。
这样处理完之后就省去了0.5的限制。问题变成了求叶子节点到根节点的距离。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
int t;
int n, q, p, c;
int tot;
int head[N], to[N], nxt[N], w[N], minn[N];
int cnt;
ll tim, num[N];
void dfs(int u, ll val) {
if(minn[u]==inf) {
num[++cnt] = val;
return ;
}
for(int i = head[u]; ~i; i = nxt[i]) {
w[i] = 2*w[i]-minn[u];
dfs(to[i], val+w[i]);
}
}
int main() {
scanf("%d", &t);
while(t--) {
tot = cnt = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++) head[i] = -1, minn[i] = inf;
for(int i = 2; i <= n; i++) {
scanf("%d%d", &p, &c);
to[++tot] = i; nxt[tot] = head[p]; head[p] = tot, w[tot] = c;
minn[p] = min(minn[p], c);
}
dfs(1, 0);
sort(num+1, num+cnt+1);
scanf("%d", &q);
while(q--) {
scanf("%lld", &tim);
int ans = upper_bound(num+1, num+cnt+1, tim)-num-1;
printf("%d\n", ans);
}
}
}
E.Palmyra（dp）
题意：
给出n*m的矩阵。从点（1，1）出发，可以向右或者向下移动，最后走到（n，m）。将路途上的点值乘起来，问最后的值拿6进制表示末尾最多有几个0。
题解：
题意可以理解为，使最后2的因子数和3的因子数中的最小值最大。
dp[i][j][k]表示走到（i，j），3的因子数为k时2的因子数最多是多少。
#include <bits/stdc++.h>
using namespace std;
int t;
int n, m;
int q[105][105][3];
int dp[105][105][1505];
int main() {
scanf("%d", &t);
while(t--) {
memset(q, 0, sizeof(q));
memset(dp, -1, sizeof(dp));
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
scanf("%d", &q[i][j][0]);
int t = q[i][j][0];
while(t%2 == 0) {
q[i][j][1]++;
t /= 2;
}
while(t%3 == 0) {
q[i][j][2]++;
t /= 3;
}
}
}
dp[1][1][q[1][1][2]] = q[1][1][1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int n2 = q[i][j][1];
int n3 = q[i][j][2];
for(int k = 0; k + n3 <= 1500; k++) {
if(dp[i][j-1][k] != -1)
dp[i][j][k+n3] = max(dp[i][j][k+n3], dp[i][j-1][k]+n2);
if(dp[i-1][j][k] != -1)
dp[i][j][k+n3] = max(dp[i][j][k+n3], dp[i-1][j][k]+n2);
}
}
}
int ans = 0;
for(int i = 1; i <= 1500; i++) {
int nn = min(dp[n][m][i], i);
ans = max(ans, nn);
}
printf("%d\n", ans);
}
return 0;
}
F.Geometry
题意：
给出长和宽，判断时正方形还是矩形。
题解：
判断w是否等于h。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int w, h;
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &w, &h);
if(w==h) puts("Square");
else puts("Rectangle");
}
}
G.It is all about wisdom（最短路+二分）
题意：
给出一个图，图中的每条边有使用的最低限制值和花费。问从1走到n在总花费小于k的前提下的最小限制值是多少。
题解：
标准的二分套最短路的题型。二分最小的限制值即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
int t;
int n, m, k;
int u, v, c, l, r;
int vis[N], dis[N];
struct node {
int to, v, lim;
node(int a, int b, int c) {
to = a; v = b; lim = c;
}
};
vector<node> g[N];
bool check(int x) {
queue<int> q;
for(int i = 1; i <= n; i++) vis[i] = 0, dis[i] = inf;
q.push(1);
vis[1] = 1;
dis[1] = 0;
while(!q.empty()) {
int v = q.front();
q.pop();
vis[v] = 0;
int len = g[v].size();
for(int i = 0; i < len; i++) {
if(g[v][i].lim > x) continue;
if(g[v][i].v+dis[v] < dis[g[v][i].to]) {
dis[g[v][i].to] = g[v][i].v+dis[v];
if(!vis[g[v][i].to]) {
q.push(g[v][i].to);
vis[g[v][i].to] = 1;
}
}
}
}
if(dis[n] < k) return 1;
return 0;
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d%d", &n, &m, &k);
r = 0;
for(int i = 1; i <= n; i++) g[i].clear();
while(m--) {
scanf("%d%d%d%d", &u, &v, &c, &l);
g[u].push_back(node(v, c, l));
g[v].push_back(node(u, c, l));
r = max(r, l);
}
l = 1;
while(l<=r) {
int mid = l+r>>1;
if(check(mid)) r = mid-1;
else l = mid+1;
}
if(check(r+1)) printf("%d\n", r+1);
else puts("-1");
}
}
I.Salem
题意：
给出n个数，求数对中最大的hamming距离。
题解：
每两个数求一下异或之后二进制下1个数量即可，输出最大值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, n;
int a[105];
int main() {
scanf("%d", &t);
while(t--) {
int ans = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
for(int j = 1; j < i; j++) {
int p = a[i]^a[j], cnt = 0;
for(int k = 20; k >= 0; k--) {
if(p&(1<<k)) cnt++;
}
ans = max(ans, cnt);
}
}
printf("%d\n", ans);
}
}
J.Game
题意：
给出合并规则表。两个人轮流进行操作，每次选择从最左面或者最右面开始每两个合并成一个。如果最后剩的是元音字符，就是Salah获胜。否则Marzo获胜。
题解：
暴力维护每一种情况。用1表示S获胜，0表示M获胜。
当S操作时，若两种情况存在1，则当前为1。
当M操作时，若两种情况存在0，则当前为0。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4+10;
int t;
int tot;
int len[N];
char s[N][N];
char g[30][30];
char cmp[5] = {''a'', ''e'', ''i'', ''o'', ''u''};
bool dfs(int num, int k) {
if(len[num] < 3) {
char c;
if(len[num]==1) c = s[num][0];
else c = g[s[num][0]-''a''][s[num][1]-''a''];
for(int i = 0; i < 5; i++) if(c==cmp[i]) return true;
return false;
}
++tot;
for(int i = 0; i < len[num]; i+=2) {
if(i==len[num]-1) s[tot][i/2] = s[num][i];
else s[tot][i/2] = g[s[num][i]-''a''][s[num][i+1]-''a''];
}
len[tot] = (len[num]+1)/2;
bool res = dfs(tot, k^1);
if(len[num]&1) {
++tot;
s[tot][0] = s[num][0];
for(int i = 1; i < len[num]; i+=2) {
s[tot][i/2+1] = g[s[num][i]-''a''][s[num][i+1]-''a''];
}
len[tot] = (len[num]+1)/2;
if(k) res &= dfs(tot, k^1);
else res |= dfs(tot, k^1);
}
return res;
}
int main() {
scanf("%d", &t);
while(t--) {
tot = 0;
for(int i = 0; i < 26; i++) scanf("%s", g[i]);
scanf("%s", s[0]);
len[0] = strlen(s[0]);
if(dfs(0, 0)) puts("Salah");
else puts("Marzo");
}
}
K.PhD math
题意：
给出a，b，n，p（a<b）。求a/b的前n位数中有多少字串整除p。
题解：
从1扫到n。维护每一位新增的余数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int t;
ll a, b;
int n, p;
int bit[N];
int v1[205], v2[205];
ll ans;
int main() {
scanf("%d", &t);
while(t--) {
ans = 0;
memset(v1, 0, sizeof(v1));
memset(v2, 0, sizeof(v2));
scanf("%lld%lld%d%d", &a, &b, &n, &p);
for(int i = 1; i <= n; i++) {
a *= 10;
bit[i] = a/b;
a = a%b;
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j < p; j++) {
if(i&1) v1[j] = 0;
else v2[j] = 0;
}
for(int j = 0; j < p; j++) {
if(i&1) v1[(j*10+bit[i])%p] += v2[j];
else v2[(j*10+bit[i])%p] += v1[j];
}
if(i&1) v1[bit[i]%p]++, ans += v1[0];
else v2[bit[i]%p]++, ans += v2[0];
}
printf("%lld\n", ans);
}
}
L.Candy Jars（博弈）
题意：
N个罐子，每个罐子有一定数量的糖。两个人轮流操作，每次选定一罐，把其他罐中的糖都扔掉。然后把选定罐中的糖任意分配给每个罐，但要保证每个罐中都有糖。不能操作者判输。
题解：
只要有一个罐子糖数必胜则操作者必胜。
当所有罐子糖数小于N时无法给所有罐子分配糖，必输。
当存在罐子糖数在[N，N(N-1)]时，可以把糖分成必输态，即分成所有罐子糖数小于N的状态，这时必胜。
然后举例发现N(N-1)是一个循环节，取模就可以了。
#include <bits/stdc++.h>
using namespace std;
int t, n;
int k;
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int ans = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &k);
k %= n*(n-1);
if(k==0 || k > n-1) ans = 1;
}
if(ans) puts("Alice");
else puts("Bob");
}
}
M.Building Force Fields（dp）
题意：
按x升序给出n个点的二维坐标，并保证没有两个点x坐标相同。可以在任意两个点之间连边，最后要保证每个点都在连边之下（或在连边上）。问最小的连边总长。
题解：
dp[i]表示第i个点结尾的最小总连边长。
转移是枚举i向第j（1<=j<i）个点连边，要保证连边上方无点。即第i和第j个点的斜率比第i个点和（j，i）范围内的点的斜率都小。最后取最小值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, n;
double dp[1005];
struct node {
ll x, y;
}a[1005];
double dis(int n1, int n2) {
return sqrt((a[n1].x-a[n2].x)*(a[n1].x-a[n2].x)+(a[n1].y-a[n2].y)*(a[n1].y-a[n2].y));
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%lld%lld", &a[i].x, &a[i].y);
dp[1] = dis(1, 2);
for(int i = 2; i <= n; i++) {
int pos = i-1;
dp[i] = min(dp[i-2], dp[i-1])+dis(i, i-1);
for(int j = i-2; j >= 1; j--) {
if((a[i].y-a[pos].y)*(a[i].x-a[j].x) >= (a[i].y-a[j].y)*(a[i].x-a[pos].x)) {
dp[i] = min(dp[i], min(dp[j-1], dp[j])+dis(i, j));
pos = j;
}
}
}
printf("%.6lf\n", dp[n]);
}
}
ACM International Collegiate Programming Contest, JUST Collegiate Programming Contest (2018)
ACM International Collegiate Programming Contest, JUST Collegiate Programming Contest (2018)
B. New Assignment
- 有 n 个人 (1 ≤ n ≤ 104)，有男有女，每个人都有一个 id，现在这 n 个人分成学习互助小组，有三种组队模式，一个男人一组，一个女人一组，一男一女一组，如果要一男一女一组，那么这两人 id 的 gcd 要 > 1。保证任意三个人的 gcd=1。求小组的组数最少是多少？
- 看起来是一个很裸的二分匹配，当两个人性别为男女，并且 gcd>1 时，连边。可是这里的连边的时候复杂度很高。直接暴力连边为 5000 × 5000×log 级别的。所以，需要换一个角度考虑。
- 可以发现，由于任意三个数的 gcd=1 的性质，可以保证任何一个质因子最多有两个被除数。当且仅当这两个被除数的性别不同连边。
#include"stdio.h"
#include"string.h"
#include"queue"
#include"vector"
#include"algorithm"
#include"iostream"
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=100010;//点数
const int maxm=400010;//边数
struct node{
int v,next,cap,flow;
}edge[maxm];
int cnt;
int head[maxn];
int cur[maxn],d[maxn];// 当前弧下标 结点到汇点弧长
int p[maxn],gap[maxn];////可增广路上的上一条弧 gap优化
int ss[maxn];//保存路径
void init(){
cnt=-1;
memset(head,-1,sizeof(head));
}
void debug(int k){
int i,j;
printf("\n");
for (i=0;i<=k;i++)
for (j=head[i];j!=-1;j=edge[j].next)
printf("%d %d %d\n",i,edge[j].v,edge[j].flow);
}
void add(int u,int v,int w,int rw=0){
cnt++;
edge[cnt].v=v;
edge[cnt].next=head[u];
edge[cnt].cap=w;
edge[cnt].flow=0;
head[u]=cnt;
cnt++;
edge[cnt].v=u;
edge[cnt].next=head[v];
edge[cnt].cap=rw;
edge[cnt].flow=0;
head[v]=cnt;
}
void bfs(int k){
int v,i;
int u;
memset(gap,0,sizeof(gap));
memset(d,-1,sizeof(d));
d[k]=0;
gap[0]++;
queue<int> q;
q.push(k);
while(q.empty()==false){
u=q.front();q.pop();
for (i=head[u];i!=-1;i=edge[i].next){
v=edge[i].v;
if (d[v]==-1) {
d[v]=d[u]+1;
gap[d[v]]++;
q.push(v);
}
}
}
}
int sap(int s,int t,int N){
int i;
bfs(t);
memcpy(cur,head,sizeof(head));
int top=0;
int u=s;
int ans=0;
while(d[s]<N){
if (u==t){
int min=inf;
int inser;
for (i=0;i<top;i++){
if (min>=edge[ss[i]].cap-edge[ss[i]].flow){
min=edge[ss[i]].cap-edge[ss[i]].flow;
inser=i;//这跟管子是满流了
}
}
for (i=0;i<top;i++){
edge[ss[i]].flow+=min;
edge[ss[i]^1].flow-=min;
}
ans+=min;
top=inser;
u=edge[ss[top]^1].v;//u为满流的那个结点 也就是那根管子的倒管子的终点
continue;
}
bool ok=false;
int v;
for (i=cur[u];i!=-1;i=edge[i].next){
v=edge[i].v;
if (edge[i].cap-edge[i].flow>0&&d[v]+1==d[u]){
ok=true;
cur[u]=i;
break;
}//u后 添加了一条下标为i的弧
}
if(ok==true){
ss[top]=cur[u];
top++;
u=v;
continue;
}
//如果这条路已经走不通了，那么撤退
int min=N;
for (i=head[u];i!=-1;i=edge[i].next)
if (edge[i].cap-edge[i].flow>0&&d[edge[i].v]<min){
min=d[edge[i].v];
cur[u]=i;
}
gap[d[u]]--;
if (gap[d[u]]==0) return ans;
d[u]=min+1;
gap[d[u]]++;
if (u!=s) {
top--;
u=edge[ss[top]^1].v;
}
}
return ans;
}
int gcd(int a,int b){
if (a%b==0) return b;
return gcd(b,a%b);
}
int prime[600000]={0},numprime=0;
bool isNotPrime[1000010]={1,1};
void sushu(int N){
long long int i;
for (i=2;i<=N;i++) {
if(! isNotPrime[i])
prime[numprime ++]=i;
for(long j = 0 ; j < numprime && i * prime[j] < N ; j ++)
{
isNotPrime[i * prime[j]] = 1;
if( !(i % prime[j] ) )
break;
}
}
}
int a[10500];
char s[10];
vector<int > v[1000005];
int vis[1000005];
int main(){
int e,t,i,j,x,y,cap,now;
int n,m;
sushu(1000000);
scanf("%d",&t);
for (e=1;e<=t;e++){
memset(vis,0,sizeof(vis));
for (i=0;i<numprime;i++) v[prime[i]].clear();
init();
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (j=1;j<=n;j++) {
scanf("%s",s);
if (s[0]==''M'') {
now=a[j];
for (i=0;i<numprime&&prime[i]<=1000;i++) {
// printf("%d\n",now);
if (now%prime[i]==0) v[prime[i]].push_back(j);
while (now%prime[i]==0) now=now/prime[i];
if (now==1||isNotPrime[now]==0) break;
}
if (isNotPrime[now]==0) v[now].push_back(j);
} else {
now=a[j];
for (i=0;i<numprime&&prime[i]<=1000;i++) {
if (now%prime[i]==0) v[prime[i]].push_back(-j);
while (now%prime[i]==0) now=now/prime[i];
if (now==1||isNotPrime[now]==0) break;
}
if (isNotPrime[now]==0) v[now].push_back(-j);
}
}
// printf("%d %d %d\n",prime[0],v[prime[0]][0],v[prime[0]][1]);
for (i=0;i<numprime;i++)
if (v[prime[i]].size()==2&&v[prime[i]][0]*v[prime[i]][1]<0) {
if (v[prime[i]][0]>0) {
if (vis[v[prime[i]][0]]==0) {add(0,v[prime[i]][0],1);vis[v[prime[i]][0]]=1;}
if (vis[-v[prime[i]][1]]==0) {add(-v[prime[i]][1],n+1,1);vis[-v[prime[i]][1]]=1;}
add(v[prime[i]][0],-v[prime[i]][1],inf);
// printf("%d %d\n",v[prime[i]][0],-v[prime[i]][1]);
}
else {
if (vis[v[prime[i]][1]]==0) {add(0,v[prime[i]][1],1);vis[v[prime[i]][1]]=1;}
if (vis[-v[prime[i]][0]]==0) {add(-v[prime[i]][0],n+1,1);vis[-v[prime[i]][0]]=1;}
add(v[prime[i]][1],-v[prime[i]][0],inf);
// printf("%d %d\n",v[prime[i]][1],-v[prime[i]][0]);
}
}
int ans=sap(0,n+1,n+2);
printf("%d\n",n-ans);
}
}E. Maximum Sum
- 取数问题。16*16 的矩阵，如果你取了这个数，那么周围 8 个格子的数都不能取。求取的数和最大。
- dp 瞎搞。事先筛选出行内任意两个相邻位置不同的状态，大约有 3000 种不到。
- dp [i][j] 代表第 i 行，这一行的取数方案为 j 时，前 i 行的最大和。由于第 i-1 行无法去影响 i+1 行，故可以这样设置状态。
- 考虑转移， 设上一行的状态为 k, 当前行的状态为 j，如果 j and k==0 并且 j<<1 and k ==0 并且 j and k<<1 ==0 那么表示可以转移。
- 尽管算下来是超高的复杂度，不过千万不要低估银河评测机的实力。
#include"stdio.h"
#include"string.h"
#include"vector"
#include"algorithm"
using namespace std;
vector<int> v;
int d[20];
int a[50][50];
int dp[17][2600];
int main(){
int i,j,k,l;
int e,t,n;
int ans,x;
int tmp;
d[0]=1;
v.clear();
for (i=1;i<=17;i++) d[i]=d[i-1]*2;
for (i=0;i<=d[16]-1;i++) {
int sign=0;
for (j=0;j<=14;j++)
if ((i&d[j])>0&&(i&d[j+1])>0) {sign=1;break;}
if (sign==0) v.push_back(i);
}
l=v.size();
scanf("%d",&t);
for (e=1;e<=t;e++) {
scanf("%d",&n);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) scanf("%d",&a[i][j]);
memset(dp,0,sizeof(dp));
for (i=0;i<l&&v[i]<=d[n]-1;i++) {
for (j=1;j<=n;j++) if ((v[i]&d[j-1])>0) dp[1][i]+=a[1][j];
// printf("%d :%d\n",i,dp[1][v[i]]);
}
for (k=2;k<=n;k++) {
for (i=0;i<l&&v[i]<=d[n]-1;i++) {
int tmp=0;
for (x=1;x<=n;x++) if ((v[i]&d[x-1])>0) tmp+=a[k][x];
for (j=0;j<l&&v[j]<=d[n]-1;j++)
if ((v[i]&v[j])==0&&((v[i]<<1)&v[j])==0&&(v[i]&(v[j]<<1))==0) {
dp[k][i]=max(dp[k][i],tmp+dp[k-1][j]);
// printf("%d :%d :%d\n",k,v[i],dp[k][v[i]]);
}
}
}
ans=0;
for (i=0;i<l&&v[i]<=d[n]-1;i++) ans=max(dp[n][i],ans);
printf("%d\n",ans);
}
}今天的关于Programming Computer Vision with Python 和学习笔记一的分享已经结束，谢谢您的关注，如果想了解更多关于3D Computer Vision、ACM International Collegiate Programming Contest, Damascus University Collegiate Programming Cont...、ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2...、ACM International Collegiate Programming Contest, JUST Collegiate Programming Contest (2018)的相关知识，请在本站进行查询。
本文标签：
