题目VJ链接:https://vjudge.net/problem/UVA-11426
题目大意:
求这个
G=0;
for(i=1;i<N;i++)
for(j=i+1;j<=N;j++)
{
G+=gcd(i,j);
}
\(1<N<4000001\)
题目VJ链接:https://vjudge.net/problem/UVA-11426
求这个
G=0;
for(i=1;i<N;i++)
for(j=i+1;j<=N;j++)
{
G+=gcd(i,j);
}
\(1<N<4000001\)
VJ题目链接:https://vjudge.net/problem/LightOJ-1282
给你两个数\(n,k\),\(\left( 2\leq n\leq 2^{31}\right)\),\(\left( 1\leq k\leq 10^{7}\right) \)
让你求\(n^{k}\)的前三位数和后三位数
二分图的定义:一个图中的点可以分成两个不相交的集合\(A,B\),并且图中所有的边都是从一个集合连向另一个集合,即同一个集合中的点之间没有边,如图1就是一个二分图
匹配:图论中,一个「匹配」(matching)是一个边的集合,其中任意两条边都没有公共顶点,如图2中红色的边就是一个匹配
题目大意:
给你1-n的n个数,给出一个序列,序列由这n个数组成,然后给m对数u,v,一对数u,v代表在序列中如果u和v相邻,且u在v的左边,则可以交换这两个数,现在问你序列中的最后一个数最多可以向左移动几次
思路:设序列中最后一个数为x,考虑哪些数在x的左边时可以将x向左移动,将这些数用一个集合V记录下来。
用一个指针pos指向最后一个数,然后看pos左边的数是不是这些记录下来的数中的一个,如果是的话就交换这两个数,并且将左边这个数从集合V中删除,然后pos-1,ans++,如果不是,则看pos左边这个数y,看可以将y向左移动的数有哪些,将这些数与V求交集然后更新V,因为X只能与V中的数交换,所以能与y交换的数若不在V中就不能使得X左移,然后让pos指向y,重复上面的过程,直到V为空集或者指着走到最左边
给你一个数字N,问将N分解成若干个数字的和有几种方法,每个数字都是正数且不超过N
如:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
题目大意:有N个车站围成一个圆,火车按顺时针走,车站编号1-N,然后车站可能有人要去往某个车站,每次列车在一个车站只能带一个人,问你火车分别以1-N的车站为起点,最少需要多少时间把所有人带到目的地,火车花费一单位的时间从一个车站到另一个。
链接:https://ac.nowcoder.com/acm/contest/317/G
来源:牛客网
小a的排列
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld
小a有一个长度为n的排列。定义一段区间是”萌”的,当且仅当把区间中各个数排序后相邻元素的差为1
现在他想知道包含数x,y的长度最小的”萌”区间的左右端点
也就是说,我们需要找到长度最小的区间[l,r],满足区间[l,r]是萌的,且同时包含数x和数y
如果有多个合法的区间,输出左端点最靠左的方案。
链接:https://ac.nowcoder.com/acm/contest/327/H
来源:牛客网
处女座的测验(一)
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
Special Judge, 64bit IO Format: %lld
处女座进行了一场c语言的考试,要求很简单,输出2000个正整数,并且满足以下条件:
1.任意两个数互质
2.任意两个数x,y,满足T(x*y)>10,其中为T(n)的因子的个数
举例:6的因子有1,2,3,6,所以T(6)=4
dinic算法是网络流中的一种算法,这里拿来求最大流
所谓最大流就是一个网络中的最大流量,如下面这个图片
其中A称作源点,B称为汇点,边上的数字代表这条边最多能容纳多大的流量,所以上图的最大流量为12
dinic算法就是求最大流算法的一种
AC自动机的目的是实现多模式串的匹配,即在一个主串中查询多个模式串
AC自动机是在trie(字典树)树的基础上实现的
对于一个主串,将这个各个模式串插入字典树,然后进行fail指针的生成fail指针的生成是AC自动机的关键
fail指针顾名思义就是在匹配失败时使用的,在匹配失败时下一步就是去fail指针指向的结点,避免了多次匹配造成的时间浪费