| by XianKa | No comments

【二分图匹配-最小边覆盖】mz语考试

Description
jswf夺冠后
cc: tql
gj: tggl
mz:tlrxml
frz: bksjs
wjjj: whnzmqa
......
js: ??? 
js: nmflb

————节选自某次mz语等级测试

mz语等级测试即将到来。然而mz语十分难,用词灵活多变,导致作弊人数众多。而防止考生作弊的一个有效的途径是让考生之间保持一定的距离。

某考场有R(行)*C(列)个座位,坐在(r, c)的考生可能会看到(r,c-1)、(r,c+1)、(r-1,c-1)、(r-1,c+1)(即左、右、左前、右前)4个位置的考生的答案。

为了防止这种情况发生,就要保证一个考生周围的这4个位置中无其他考生。

而由于这个考场年久失修,有一些座位已经损坏,是无法使用的。

现在,fls想知道,在保证无人能看到别人答案的前提下,这个考场最多能安排多少名考生?

Input
多组数据

第一行有一个整数T(T<=30),代表数据组数。

对每组数据,第一行有两个整数R、C(1 <= R, C <= 50),表示考场规模。

接下来R行,每行有一个长度为C的字符串,描述考场内每个位置。'.'表示该位置可用,'x'则表示已损坏。

Output
对每组数据,输出该考场内最多能安排的考生数。

Sample Input
1
2 3
...
.x.
Sample Output
4

相隔两列的人是看不见对方的。所以把有冲突的座位连边即为二分图。

任意两个冲突的位置只能有一个地方坐人,即任意点只能有一条边相连。边数就是能坐下的人。转化为了最小边覆盖问题。

答案就是 点数-最大匹配数

注意link vis这些变量名有可能会与STL冲突

#include<vector>
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<string> 
using namespace std;
int dx[]={-1, 0, 1,-1,0,1};
int dy[]={-1,-1,-1, 1,1,1};
char tsr[55][55];
vector<int> G[3025];
int id[55][55];
int visa[3025]={0};
int linka[3025]={0};
int r,c;
int lig(int 
Read the rest Read More
| by XianKa | No comments

【计算几何-技巧】射击游戏

Description
js在ak了一套cf后,打开了一款新出的射击游戏。

这个射击游戏在一个二维平面进行,js控制的人物处于坐标原点(0,0)。平面上共有n只怪物,每个怪物所在的坐标为(x[i], y[i])。js进行一次射击会把x轴和y轴上(包含坐标原点)的怪物一次性消灭。

而高贵的js是这个游戏的VIP玩家,他拥有两项特权操作:
1、让平面内的所有怪物向任意一个相同的方向移动相同的距离d。
2、让平面内的所有怪物以js为中心旋转相同的角度θ。

js在进行射击前,可以无限次的使用这两项特权操作。js想知道在他射击的时候最多可以同时消灭多少只怪物,请你帮帮伟大的js吧。

Input
输入包括三行。

第一行中有一个正整数n(1 <= n <= 100),表示平面内的怪物数量。

第二行包括n个由空格分隔的整数x[i](-1,000,000 <= x[i] <= 1,000,000),表示每只怪物的横坐标。

第二行包括n个由空格分隔的整数y[i](-1,000,000 <= y[i] <= 1,000,000),表示每只怪物的纵坐标。

Output
输出js一次性最多能消灭的怪物数。

Sample Input
5
0 -1 1 1 -1
0 -1 -1 1 1
Sample Output
5

枚举两个点,连成一条线。每次检查在线上有多少点,不在线上的点往线上作投影,当线上的点+某个投影的坐标的所有点>答案的时候,更新答案。

是否三点一线用向量是否平行,投影也用向量坐标运算。

技巧:投影用map来存储,遍历的时候用map的迭代器进行遍历。重载运算符实现坐标相减得到向量的功能。

答案初始化为1;因为如果没有能构成线点,那么将不运算

#include<bits/stdc++.h>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
struct point{
	ll x, y;
	point(){}
	point(ll x,ll y):x(x),y(y){}
	point operator -(point tp)
	{
		return point(x-tp.x,y-tp.y);
	}
}p[110];
ll dot(point a,point b)
{
	
Read the rest Read More
| by XianKa | No comments

【生成函数】果苣拼盘

Description
果苣是一类高贵的水果的统称。

而果苣拼盘则是使用这些高贵的水果制成的拼盘。制作一份果苣拼盘,需要满足如下限制:
     1. 必须使用特定的n种果苣。
     2. 第i种果苣的数量不能少于li 份,也不能多于ri 份
     3. 果苣的总份数要恰好为m份

果苣想知道,一共有多少种不同的果苣拼盘的制作方案?

Input
多组数据

第一行有一个整数T(T<=20),代表数据组数。

对每组数据,第一行有两个由空格分隔的整数n和m(1<=n<=20, 1<=m<=100),表示果苣的种类和拼盘需要的果苣总份数。

接下来n行,每行有两个由空格分隔的整数li 和ri (0<= li <= ri <= 10),描述第i种果苣数量的限制。

Output
对每组数据,输出满足限制条件的方案数。

Sample Input
2
2 3
1 2
1 2
3 5
0 3
0 3
0 3
Sample Output
2
12
HINT
对于两种方案,当有任意一种水果的份数不同时,则两种方案不同。

每种水果无论取几个都只有一种取法。生成函数,最后[latex]x^n[/latex]的系数就是答案,即多项式的乘法。

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
ll a[220][1100]={0};
ll t,n,m,l[220],r[220];
ll ans[1100],tmp[1100];
int main()
{
	scanf("%lld",&t);
	while(t--)
	{
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		memset(ans,0,sizeof(ans));
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=n;i++)
		{
			scanf("%lld%lld",&l[i],&r[i]);
			m-=l[i];
			
Read the rest Read More
| by XianKa | No comments

【矩阵快速幂】hyper Fibonacci 数列

Description
令F(i)表示斐波那契数列的第i项。
S1(i)表示F数列的前i项和。
S2(i)表示S1数列的前i项和。
S3(i)表示S2数列的前i项和。
S4(i)表示S3数列的前i项和。
S5(i)表示S4数列的前i项和。
S6(i)表示S5数列的前i项和。
S7(i)表示S6数列的前i项和。
S8(i)表示S7数列的前i项和。
求S8(N)。答案可能很大,请对1000000007取模。
斐波那契数列的定义可以查看https://baike.baidu.com/item/斐波那契数列

Input
多组数据。
输入的第一行包括一个整数表示数据组数T(1< =T<=1000)。
每组数据的第一行包括一个整数表示题目所说的N(1<=N<=1000000000000000000)。

Output
每组数据在单独的一行中输出S8(N)。


Sample Input
4
1
2
3
4
Sample Output
1
9
46
175
HINT
F数列前四项:1 1 2 3

S1数列前四项:1 2 4 7

S2数列前四项:1 3 7 14

S3数列前四项:1 4 11 25

S4数列前四项:1 5 16 41

S5数列前四项:1 6 22 63

S6数列前四项:1 7 29 92

S7数列前四项:1 8 37 129

S8数列前四项:1 9 46 175 

由题目给的hint其实已经看出来了[latex]S_n^8=S_{n-1}^{87654321}+F_n[/latex]

其他项也是如此

#include
using namespace std;
typedef long long ll;
ll p=1000000007;
struct Mat{
    ll a[10][10];
    Mat(){
        memset(a,0,sizeof(a));
    }
};
Mat mul(Mat a,Mat b)
{
    Mat res=Mat();
    for(ll i=0;i<10;i++)
    {
        for(ll j=0;j<10;j++)
        {
            for(ll k=0;k<10;k++)
            {
                if(a.a[i][k]&&b.a[k][j])
                res.a[i][j]+=(a.a[i][k]%p)*(b.a[k][j]%p)%p; 
            }   
        }   
    }   
    return res;
} 
Mat ksm(Mat n,ll k)
{
    Mat ans=Mat();
    for(ll i=0;i<10;i++)
    ans.a[i][i]=1;
    while(k)
    {
        if(k&1) ans=mul(n,ans);
        n=mul(n,n);
        k>=1;
    }
    return ans;
}
int main()
{
    ll t;
    ll temp1[10][10]={
        {1,1,1,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,0},
        {0,0,1,1,1,1,1,1,1,0},
        {0,0,0,1,1,1,1,1,1,0},
        {0,0,0,0,1,1,1,1,1,0},
        {0,0,0,0,0,1,1,1,1,0},
        {0,0,0,0,0,0,1,1,1,0},
        {0,0,0,0,0,0,0,1,1,0},
        {0,0,0,0,0,0,0,0,1,1},
        {0,0,0,0,0,0,0,0,1,0}
        };
    ll temp2[10][10]={
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,0,0}
        };
    
Read the rest Read More
| by XianKa | No comments

【欧拉函数||容斥】gcd之和

Description
给出一个数列,求数列中任意一对数的最大公因数之和。
最大公因数的定义可以查看 baike.baidu.com/item/最大公因数 

Input
 多组数据。
输入的第一行包括一个整数表示数据组数T(1< =T<=10)。
每组数据的第一行包括一个整数表示数列的长度N(1<=N<=10000)。
第二行包括N个整数,第i个整数表示数列的第i个数ai(1<=ai<=10000)。

Output
每组数据在单独的一行中输出数列中任意一对数的最大公因数之和。 

Sample Input
3
3
2 1 3
4
4 3 9 6
7
7 7 7 7 7 7 7
Sample Output
3
13
147
HINT
 对于第一组数据:


gcd(2,1)+gcd(2,3)+gcd(1,3)=1+1+1=3

对于第二组数据:

gcd(4,3)+gcd(4,9)+gcd(4,6)+gcd(3,9)+gcd(3,6)+gcd(9,6)=1+1+2+3+3+3=13

对于第三组数据:

gcd(7,7)*(6+5+4+3+2+1)=7*21=147 

关于这题有很多种解法。

1.容斥

假设d为N公因数,那么公因数之和就是所有的d乘上C 2 \choose num(d),其中num(d)指的是d出现的次数。因为任意两个数才有公约数,从有d这个公因数的所有数中选择两个即可。

然而这下算出来的是所有公因数的和,我们需要的是最大公因数的和。所以要除重,可以利用容斥原理。d算出的答案减去d的倍数算出的答案即为最大公约数之和。例如最大公因数为2的,就可以算出公因数为2的,再减去公因数和为4,8,16...的。倒过来容斥就可以了。

代码见 题解 F

2.欧拉函数

首先欧拉函数有个性质:n = \sum\limits_{d|n}φ(d)也就是说n的所有因数的欧拉函数之和等于n本身。

假设gcd(x,y)=n,则x,y小于n的公约数一定是相同的。可以得到:任意两数的gcd等于他们的公因数的欧拉函数值之和。则同样有某个gcd的和为

n*C 2 \choose num(n)

其中2 \choose num(n可以看作是0..num(n)-1的等差求和公式:0+1+2+..+num(n)-1。n则可以写为\sum\limits_{d|n}φ(d)

(0+1+2+..+num(n)-1) * \sum\limits_{d|n}φ(d)

可以看出每个公因数的Φ值乘上自己出现的次数都会对gcd的和做出一定贡献。而且因为每个d都有对应的gcd,所以不存在重复的情况。

那每加入一个数x。可以把答案加上num(k) * \sum\limits_{k|x}φ(k)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+233;
ll phi[maxn+23]={0};
ll a[maxn+23];
vector<ll> d[maxn+23];
void phi_t()
{
    for(ll i=2;i<=maxn;i++) phi[i]=0;
    phi[1]=1;
    for(ll i=2;i<=maxn;i++) 
        if(!phi[i])
        {
            for(ll j=i;j<=maxn;j+=i)
            {
                if(!phi[j]) 
Read the rest Read More
| by XianKa | No comments

【矩阵快速幂-构造】I – Algebraic Problem LightOJ – 1070

Given the value of a+b and ab you will have to find the value of an+bn. a and b not necessarily have to be real numbers.

Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains three non-negative integers, p, q and n. Here p denotes the value of a+b and q denotes the value of ab. Each number in the input file fits in a signed 32-bit integer. There will be 
Read the rest Read More
| by XianKa | No comments

【组合数求模】K – Combinations LightOJ – 1067

Given n different objects, you want to take k of them. How many ways to can do it?

For example, say there are 4 items; you want to take 2 of them. So, you can do it 6 ways.

Take 1, 2

Take 1, 3

Take 1, 4

Take 2, 3

Take 2, 4

Take 3, 4

Input
Input starts with an integer T (≤ 2000), denoting the number of test cases.

Each test case contains two integers n (1 
Read the rest Read More
| by XianKa | No comments

【组合数学】J – Rooks LightOJ – 1005

A rook is a piece used in the game of chess which is played on a board of square grids. A rook can only move vertically or horizontally from its current position and two rooks attack each other if one is on the path of the other. In the following figure, the dark squares represent the reachable locations for rook R1 from its current position. The figure also shows that the rook R1 and R2 are in attacking positions where 
Read the rest Read More
| by XianKa | No comments

【long long 坑】‘早自习打卡’

Description
重庆游戏与电子竞技大学开始使用电子打卡机进行早自习考勤,打卡机记录了每个人到达教室和离开教室的时间。现在辅导员想知道今天有多少同学在7:20之前(包括7:20)到达,7:40之后(包括7:40)离开,且这段时间内没有离开过教室的同学有多少,但是考勤记录被打乱了,于是他把这个任务交给了你。
Input
每个输入包含一个测试用例。 每个测试用例由多行记录组成,每行记录由时间(以h:m的形式,h(1<=h<=24)表示小时,m(0<=m<60)表示分钟)和学号s(s由十位数字组成)组成。 输入保证记录由合法的记录打乱得到,即同一个人时间轴上第一次记录一定是到达记录,相邻两次记录一定是一次到达一次离开。 记录最多有100000行。
Output
输出一个整数,表示在7:20之前(包括7:20)到达,7:40之后(包括7:40)离开,且这段时间内没有离开过教室的同学的数量。
Sample Input
7:19 2015233333
7:40 2015666666
7:20 2015666666
7:39 2015233333
7:00 2015123456
Sample Output
1

把学号离散化,但学号已经超过了1e10,所以要用long long

#include<bits/stdc++.h>
#include<queue>
#include<map>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
map<ll, int> id;
priority_queue<int,vector<int> ,greater<int > > tl[100010];
int ans=0,cnt=0;
int main()
{
	int h,m;
	ll s;
	while(scanf("%d:%d %lld",&h,&m,&s)!=EOF)
	{
		if(id.count(s)==0)
		{
			id[s]=++cnt;
		}
		tl[id[s]].push(h*100+m);
	}
	int a,b;
	for(int i=1;i<=cnt;i++)
	{
		int card=tl[i].size();
		while(card>1)
		{
			a=tl[i].top();tl[i].pop();
			b=tl[i].top();tl[i].pop();
			card-=2;
			if(a<=720&&b>=740)
			{
				ans++;
				break;
			
Read the rest Read More
| by XianKa | No comments

【最大匹配】‘组队难题’

Description
一年一度的保研杯又开始了,重庆游戏与电子竞技大学的同学们都跃跃欲试。今年学校收集了参赛学生的信息,打算统一分配队伍。学校把学生分为端茶、倒水和大佬三种类型,一个队伍由三个学生组成,而且不能同时有多个端茶学生或者多个倒水学生。大佬比较佛系,不会和其他学生起冲突,但是剩下两种学生都是凡人,所以一些学生之间会有矛盾。现在问题来了,在避免矛盾的前提下,最多能组成多少只队伍呢?
Input
每个输入包含一个测试用例。 每个测试的第一行包括两个整数,学生数量N(1<=N<=300)和矛盾数量M(0<=M<=90000)。学生的编号从1到N。 接下来的N行,每行包括一个字符串,第i行的字符串表示i号学生的类型:”DL”表示大佬,”DC”表示端茶,”DS”表示倒水。 接下来的M行,每行包括两个正整数,表示有矛盾的学生的编号。保证矛盾双方编号不同。 数据保证矛盾不会和”DL”类型的同学有关,保证每对同学的矛盾最多只会出现一次。
Output
输出一个整数,表示最多能组成的队伍数量。
Sample Input
4 2
DL
DC
DC
DS
2 4
3 4
Sample Output

虽然一眼就看出来是最大匹配,但是有个坑点没有注意到。

一个队不能有多个端茶送水但是可以有多个大佬…………………………

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;
int dl=0;
int d[303]={0};
vector<int> qds,qdc;
int cp[303][303]={0};
int vis[303]={0};
int mch[303]={0};
int fbfs(int x)
{
	int j;
	for(int k=0;k<qdc.size();k++)
	{
		j=qdc[k];
		if(cp[x][j]==1 && vis[j]==0)
		{
			vis[j]=1;
			if(mch[j]==0 || fbfs(mch[j]))
			{
				mch[j]=x;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		char 
Read the rest Read More