[TOC]
3.16 算法
选择
- CRF模型相对HMM模型的优势
- CNN和MLP哪个可以使用稀疏连接
- L1、L2范数怎么计算
OJ
Q1
输入三个二维坐标，给出第四个坐标，使得四个坐标能构成二维平面里的矩形。
A1
三个x异或起来，三个y异或起来，ok两行ac
Q2
好串是指通过重新排列组合能形成回文串的字符串
现在给定一个字符串，小红要询问若干次，每次询问第l个字符到第r个字符是否是好串。你能帮帮她吗？
输入描述
第一行输入两个正整数n，q，代表字符串长度和询问次数。
第二行输入一个长度为n的仅包含小写字母的字符串。
接下来的q行，每行输入两个正整数，代表一次询问。
1≤ n,q ≤ 10^5
1≤ l,r ≤n
输出描述
输出q行，每行输出一个字符串代表结果。若询问的字符串是好串，则输出”Yes”。否则输出”No”。
示例 1
输入
5 3
aabac
1 3
2 4
3 5
输出
Yes
Yes
No
A2
dp[n]，dp[i]表示从字符串索引0-i的字符数异或和，递推公式：dp[i] = dp[i-1]^(1«(s.charAt(i)-‘a’))
i到j处的字母异或和：int num = dp[j]^dp[i-1];
如果num中1的位数不超过一个，就说明可以构成回文：num &(num -1)==0
Q3
小红有一棵树，树上每条边都有一个权值，小红想知道树上有多少条路径的权值和为偶数。
输入描述
第一行输入一个整数 n（1≤n ≤ 10^5）表示树节点个数。
接下来n-1行，每行输入三个整数:
u,v(1≤u,v≤n)，w(1≤w≤ 10^9)表示树上的边。
输出描述
输出一个整数表示答案。
示例 1
输入
3
1 2 2
2 3 2
输出
3
A3
任意节点开始bfs一遍计算各节点到根节点的距离，会发现到根节点距离同为奇或同为偶的两点之间距离为偶数，统计一下奇偶分别的个数算两个组合数加起来
