问题引入： 添加链接描述 给定N和M和D，求满足1<=x<=N,1<=y<=M且gcd(x,y)=D的点对(x,y)的个数 1<=N,M<=1000000 莫比乌斯函数 μ μ(n) = 1 , n=1 μ(n) = (-1)k, n=p1 * p2 * … * Pk （x有奇数个质因子时为-1，x有偶数个质因子时为1） μ(n) = 0 其他情况（x存在平方因子） 莫比乌斯线性筛： int prime[MAXN],prime_tot; bool prime_tag[MAXN]; int mu[MAXN]; void pre_calc(int lim) { ...

题意： 有n个人会在某时间段来洗衣服，但是只有一台洗衣机，当洗衣机被用时其他人只能手洗，手洗时间为y（题目给定），洗衣机的时间为x，x∈[1,y]，问当x分别为[1,y]时，最短的洗衣时间是多少？ 题解： 据我所知有两个方法： 1.李超树 2.贪心 李超树我还不是很清楚，等学会了再更新。。 贪心的话其实就是想办法优化，以为按照原题数据肯定是不可能暴力的， 根据题意：y肯定大于x 那我们就像最省时间的方法就是在y的时间内来洗衣机，因为一个人一旦手洗就不能再机洗，我们就看手洗时间等于多好啊机洗时间 记录最大数为pos，也就是从pos到最后一个人，这期间是小于一次手洗时间，也就是都可以手洗 然后i从...

又和同学肝了半个上午（主要是一二节有课），完成了天气图像识别的第二期练习 一开始几个题不难，挺简单的，到后面出现HOG特征拟合svm模型，HOG提取特征，又是现学内容 HOG特征的维数用cv2.HOGDescriptor()来做 最后用shape来反应维数 import cv2 import matplotlib.pyplot as plt img=cv2.imread('/home/kesci/input/weather_image1552/训练集/100.jpg',0) plt.imshow(img) hg=cv2.HOGDescriptor() winSreide=(64,64) pad...

ABB 题意： 长度为n的字符串，问最少添加多少字符可以使其构成回文字符串 题解： 最长回文字符串我的第一反应是manacher马拉车算法，那我们直接马拉车找到已有最长回文串，然后总长度减去不就是答案吗？非也 ~ ~ 。注意是让我们构造最长回文字符串，我们会发现，如果我们用马拉车找到的最长回文串的最右端不是字符串最右端，那此情况就相当于作废 比如： murderforajarofz 我们可以找到最长回文串forajarof，但是最后一位z并不在里面，那你无论怎么构造也用不到forajarof这个回文串，也就是我们要找最长的带最后一个字符的回文字符串 我们直接在manacher的基础上改就可以，...

Bob in Wonderland 题意： 一棵树，问最少移动多少次边可以使其变成一个链？ 移动是指：从原位置拆下并连到新位置，这样算一次 题解： 错误思路 我一开始在想既然求最少移动次数，那我们就尽可能在原本的就存在的链的基础上进行修改，也就是先找树中最长的链（即树的直径），然后看这条链上有多少子链相连，拆下来再连上即可，所以先跑两边dfs，求出最长直径，并记录直径上的点，然后依次查看直径上的点的度数是否大于2，如果大于2就说明除了前后两个点，还有其他点相连，注意如果7连在6上，然后6连在直径上，那6和7是算一个整体的，所以只需要查看直径点的度数即可 正确思路 但是。。代码就是wa。。。感觉...

Zeldain Garden 题意： 问[L,R]内所有数的因子的数量和 题解： 如果传统暴力做肯定不行 我们来找找规律： 数字： 因子数目 1~n的因子数和 1 1 1 2 2 3=2+1/ 3 2 5=3+1+1 4 3 8=4+2+1+1 5 2 10=5+2+1+1+1 6 4 14= 7 2 16= 8 4 20= 9 3 23=9+4+3+2+1+1+1+1+1  有发现什么规律？ 可以推出：1—n的因子数和 =∑ (int)n/i （i是从1到n） 问我咋推出来的？ 额。。“直觉”算能力吗？我在纸上把因子数和进行拆分就发现这样的规律 但是注意题目中的数据是1e12，感觉直接做还是...

VIRUS OUTBREAK   文章目录    题目描述 输入描述: 输出描述: 题解： 代码：    题目描述 The State Veterinary Services Department recently reported an outbreak of a newly found cow disease. All cows found to have affected by the disease have since euthanized because of the risk to the industry. Number of affected cows increased t...

来源：牛客网： 题目描述 1st Academy is an international leadership training academy based in Kuala Lumpur. Every year, the company trains thousands of people to be supplied to companies around the world. To be fair amongst all the trainees, the company will do the selection process using numbering system. The ...

MATRIX MULTIPLICATION CALCULATOR 题意： 求两矩阵相乘 题解： 应该都学过把。。。矩阵相乘 矩阵相乘的前提是两个矩阵的列等于另一个矩阵的行 也就是cij=∑aik*bkj 原理很简单注意格式，但是我遇到一个玄学问题。。。 就是卡格式了。。我人都傻了   为啥我这case都是最后输出？？？ 如果是输出undefined就是正常的 人傻了。。 代码： 格式错误代码： #include<bits/stdc++.h> using namespace std; const int maxn=2000; int pos[maxn]; int a[40][40];...

最小公倍数之和 题目描述： 对于A1，A2…AN，求 ∑ i=1N∑ j=1Nlcm(Ai,Aj) 题解： 莫比乌斯反演，直接强推一波  推导过程我也是一知半解，大体如图 然后预处理f(T)即可 代码： #include<bits/stdc++.h> using namespace std; #define ll long long #define maxn 50005 #define rgt register int N, M, cnt[maxn], mu[maxn], p[maxn], tot, v[maxn]; ll s[maxn]; ll ans=0; int main()...

Points 题目描述 Jack and Rose are playing games after working out so many difficult problems. They together drew a “Haizi” tree to show their collaboration. “Haizi” tree is the same as the tree defined in graph theory. Now Jack would like to count the number of vertices whose degree is one in this tree....

Leftbest 链接：https://ac.nowcoder.com/acm/contest/7830/A 来源：牛客网 题目描述 Jack is worried about being single for his whole life, so he begins to use a famous dating app. In this app, the user is shown single men/women’s photos one by one, and the user may choose between “yes” and “no”. Choosing “yes” means...

Flowers 题目描述 Recently Jack becomes much more romantic. He would like to prepare several bunches of flowers. Each bunch of flowers must have exactly M flowers. As Jack does not want to be boring, he hopes that flowers in the same bunch are all different species. Now there are {N}N species of flowers ...

Digits Are Not Just Characters 题意： 比较大小，如果比目标字符串大输出“+”，相等也输出“+”，小则输出“-”： 比较规则： 字母大于数字 两个字母比较按照ASCII码 当被解释为十进制数时，两个数字项按其值排序。 Number items come before letter items. Two letter items are ordered by their ASCII codes. Two number items are ordered by their values when interpreted as decimal numbers.  题解：...