关于ProgrammingComputerVisionwithPython和学习笔记三的问题就给大家分享到这里，感谢你花时间阅读本站内容，更多关于3DComputerVision、ACMInterna

关于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）

概要

原书对于PCA的讲解只有一小节，一笔带过的感觉，但我发现PCA是一个很重要的基础知识点，在机器机视觉、人脸识别以及一些高级图像处理技术时都被经常用到，所以本人自行对PCA进行了更深入的学习。

PCA是什么

PCA（Principal Component Analysis，主成分分析或主元分析）是一种算法，PCA的结果是用尽可能少的特征数据来表达最多的原始图像的本质结构特征。即使它会丢失一部分原始图像的特征表达，但它仍然是很有用的处理技巧，也很常用，特别在计算机视觉和人脸识别方面。

假设我们有一个二维数据集，它在平面上的分布如下图：

如果我们想要用一个一维向量来表达此数据集，就会丢失一部分此数据集的信息，但我们的目标是让求得的这个一维向量可以尽可能多地保留这个数据集的特征信息，那么这个求解过程就是PCA。

通过PCA我们可以找到若干个1维向量，如图：

直观上看出，向量u1是数据集变化的主方向，而u2是次方向，u1比u2保留了更多的数据集的结构特征，所以我们选择u1作为主成分，并把原数据集投影到u1上就可以得出对原数据集的一维近似重构：

以上只是一种直观的示例，把二维数据降为用1维来表示，当然，PCA通常是应用在高维数据集上。

PCA解决什么问题

假设我们有10张100 × 100像素的灰度人脸图，我们目标是要计算这10张图的主成分来作为人脸特征，这样就可以基于这个‘特征脸’进行人脸匹配和识别。但即使一个100 × 100像素的灰度图像维度就达到10,000维，10张图像的线性表示可以达到100,000维，如此高维的数据带来几个问题：

• 对高维数据集进行分析处理的计算量是巨大的，消耗资源太大，时间太长

• 高维数据包含了大量冗余和噪声数据，会降低图像识别率

所以通常对于高维数据集，首先需要对其进行降维运算，以低维向量表达原数据集最多最主要的结构特征。从而将高维图像识别问题转化为低维特征向量的识别问题，大大降低了计算复杂度，同时也减少了冗余信息所造成的识别误差。PCA其实就是最常用的一种降维算法。

PAC也可用于高维数据压缩、高维数据可视化（转二维或三维后就可以画图显示）等方面，也是其它很多图像处理算法的预处理步骤。

PCA的计算

关于PCA，网上一搜还是不少的，但我仔细看了几篇文章之后，发现这些文章讲的跟书上讲的有些地方不一致，甚至连计算时的公式都不一样，这让我产生了很多困惑。所以我想最重要的还是要理解PCA的数学原理，数学原理才是根，掌握了数学原理，再来写代码。恰好找到一篇文章专门讲PCA数学原理，作者的数学功底和逻辑表达能力非常棒，让我很容易看明白。另外，我也找到一篇老外写的文章（见底部参考文章），这两篇文章对PCA的计算描述是一致的，所以我决定在这两篇文章的基础上，结合书上的示例代码进行学习和验证。

本文不是要要把PCA的数学原理及推导写出来，而是通过理解PCA的数学原理，总结PCA的计算步骤，因为计算步骤是代码实现的必备知识。

PCA的计算过程涉及到几个很重要的数学知识点：

• 零均值化

• 矩阵的转置及乘法

• 协方差与协方差矩阵

• 特征值及特征向量

现在来看PCA的计算步骤：
1）将原始数据按列组成d行n列矩阵X
重要说明：d对应的就是数据的字段（或叫变量、特征、维，下称’维‘），而n表示n条记录（或叫样本、观察值，下称’样本‘），即每1列对应1个样本，之所以行和列这样安排，是为了与数学公式保持一致，很多文章对这一点都没有明确的说明，导致计算的方式各有不同，让人产生不必要的困惑
2）将X的每个维（行）进行零均值化，即将行的每个元素减去这一行的均值
3）求出X的协方差矩阵C，即 X 乘 X的转置
4）求出C所有的特征值及对应的特征向量
5）将特征向量按对应特征值大小从上到下按行排列成矩阵，取前k行组成矩阵E
6）Y=EX即为降维到k维后的数据

下面用一个例子来验证一下这个计算过程。

黑白图像的PCA实现

书中的例子是用PCA计算特征脸（人脸识别中的一步），它应用在多张图片上面。为直观起见，我用另外一个例子——对单张黑白图像进行PCA，相当于把二维图像降为一维。

把图像转成二维矩阵
这张图像是原书封面：

下面代码是将图中‘怪鱼’部分截取出来，并转成黑白图像显示：

from PIL import Image
pim = Image.open(''cover.png'').crop((110,360,460,675)).convert(''1'')
pim.show()

效果如图：

之所以截取这部分的图片，是因为我们大概能猜到这幅图像降到一维后，其一维表示的向量应该跟怪鱼的方向大概一致。

使用黑白图像是因为黑点才是我们关心的数据，因为是这些黑点描绘了图像，每个黑点有唯一确定的行和列位置，对应平面上的（x,y）坐标，于是我们就可以得到此图像的 2乘n 矩阵表示：第一行表示x维，第二行表示y维，每一列表示一个点。参考代码：

import numpy as np
import matplotlib.pyplot as plt
from PIL import Image

im = np.array(Image.open(''cover.png'').crop((110,360,460,675)).resize((256,230)).convert(''L''))
n,m = im.shape[0:2]
points = []
for i in range(n):
    for j in range(m):
        if im[i,j] < 128.0:  #把小于128的灰度值当作黑点取出来
            points.append([float(j), float(n) - float(i)]) #坐标转换一下
    
im_X = np.mat(points).T; #转置之后，行表示维度（x和y），每列表示一个点（样本）
print ''im_X='',im_X,''shape='',im_X.shape

现在，我们按上面说明的计算步骤来实现PCA：

def pca(X, k=1): #降为k维
  d,n = X.shape
  mean_X = np.mean(X, axis=1) #axis为0表示计算每列的均值，为1表示计算每行均值
  print ''mean_X='',mean_X
  X = X - mean_X
  #计算不同维度间的协方差，而不是样本间的协方差，方法1：
  #C = np.cov(X, rowvar=1) #计算协方差，rowvar为0则X的行表示样本，列表示特征/维度
  #方法2：
  C = np.dot(X, X.T)
  e,EV = np.linalg.eig(np.mat(C)) #求协方差的特征值和特征向量
  print ''C='',C
  print ''e='',e
  print ''EV='',EV
  e_idx = np.argsort(-e)[:k] #获取前k个最大的特征值对应的下标（注：这里使用对负e排序的技巧，反而让原本最大的排在前面）
  EV_main = EV[:,e_idx]   #获取特征值（下标）对应的特征向量，作为主成分
  print ''e_idx='',e_idx,''EV_main='',EV_main      
  low_X = np.dot(EV_main.T, X)    #这就是我们要的原始数据集在主成分上的投影结果
  return low_X, EV_main, mean_X

OK,现在我们调用此PCA函数，并把原图像和投影到一维向量后的结果也描绘出来：

low_X, EV_main, mean_X = pca(im_X)
print "low_X=",low_X
print "EV_main=",EV_main
recon_X = np.dot(EV_main, low_X) + mean_X  #把投影结果重构为二维表示，以便可以画出来直观的看到
print "recon_X.shape=",recon_X.shape

fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(im_X[0].A[0], im_X[1].A[0],s=1,alpha=0.5)
ax.scatter(recon_X[0].A[0], recon_X[1].A[0],marker=''o'',s=100,c=''blue'',edgecolors=''white'')
plt.show()

画散点图函数pyplot.scatter说明：

matplotlib.pyplot.scatter(x, y, ...)
x: 数组，样本点在X轴上的坐标集
y: 数组，样本点在Y轴上的坐标集
s: 表示画出来的点的缩放大小
c: 表示画出来的点（小圆圈）的内部颜色
edgecolors: 表示小圆圈的边缘颜色

运行以上代码打印：

im_X= [[  23.   24.   25. ...,  215.  216.  217.]
 [ 230.  230.  230. ...,    5.    5.    5.]] shape= (2, 19124)
mean_X= [[ 133.8574566 ]
 [ 123.75941226]]
C= [[ 2951.65745054 -1202.25277635]
 [-1202.25277635  3142.71830026]]
e= [ 1841.14567037  4253.23008043]
EV= [[-0.73457806  0.67852419]
 [-0.67852419 -0.73457806]]
e_idx= [1] EV_main= [[ 0.67852419]
 [-0.73457806]]
low_X= [[-153.26147057 -152.58294638 -151.90442219 ...,  142.29523704
   142.97376123  143.65228541]]
EV_main= [[ 0.67852419]
 [-0.73457806]]
recon_X.shape= (2, 19124)

并显示如下图像：

从图中看出，向量的方向跟位置与我们目测的比较一致。向量上的大量蓝色圆点（白色边缘）表示二维数据在其上的投影。

小结

以上实现的PCA算法，跟我参考的两篇文章所讲的原理一致。但跟书中的PCA计算方法有一定的不同，但也因为使用的例子不一样，对原始数据集的定义不一样导致的，由于避免文章过长，这些放在后面再讲。
至此，通过对PCA的计算过程的学习，了解了一些线性代数知识、numpy和pyplot模块的一些接口的用法，接下来我打算做点更有兴趣的事情——就是使用PCA来实现人脸识别。

参考链接：
PCA的数学原理
A Tutorial on Principal Component Analysis
NumPy函数索引

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:

1. [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.
2. [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.)
3. [1p] Explain what line 382-389 do? What does the “multiply” result means? Why should all the multiply
   values be (close to) zero?
4. [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));
    }
}

View Code

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("");
    }
}

View Code

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");
            }
        }
    }    
}

View Code

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);
        }
    }
}

View Code

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;
}

View Code

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");
    }
}

View Code

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");
        
    }
}

View Code

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);
    }
}

View Code

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");
    }
}

View Code

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);
    }
}

View Code

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");
    }
}

View Code

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]);
    }
}

View Code

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)的相关信息，请在本站查询。