| 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
| by XianKa | No comments

【数位DP-技巧】长度为N的数串每M个和都为质数

Description
经过不懈的努力,你在后山挖出了一个宝箱,旁边还有一张纸条,上面写着两个数字还有一段话:“我是九头龙晗源,想要我的资源吗?如果想要的话,那就到oj.cqupt.edu.cn.cqu.pt去找吧,我全部都放在那里。密码是满足由N位数字组成,且每连续M个数字之和都是质数的数字串的个数。N和M我写在纸上了。”
Input
每个输入包含一个测试用例。 每个测试用例包括两个整数N(1<=N<=12)和M(1<=M<=4)。
Output
输出一个整数,表示密码,即满足由N位数字组成,且每连续M个数字之和都是质数的数字串的个数。 这N位数字每一位可以是0~9,数字串可以有前导0。
Sample Input
2 2
Sample Output
37
HINT
当M>N时,密码为0

无脑滚表虽然过了,但和MZJJ学到了很多数位dp的技巧。

比如如何取位,如何快速加和一个3位数,如何巧妙的避开判断m的大小。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,md;
int pri[55];
int g[10001];
ll dp[55][5555];
void init()
{
	for(int i=1;i<=49;i++) pri[i]=1;
	pri[0]=0;pri[1]=0;
	for(int i=2;i<=7;i++)
	{
		if(pri[i])
		{
			for(int j=i*i;j<=49;j+=i) pri[j]=0;
		}
	}
	for(int i=1;i<=9999;i++) g[i]=g[i/10]+i%10;
}
ll dfs(int pos,int num)
{
	if(pos==0) return 1;
	ll &ans=dp[pos][num];
	if(~ans) return ans;
	ans=0;
	for(int i=0;i<=9;i++)
	{
		if(pos+m-1>n||pri[g[num]+i]==1)
		{
			ans+=dfs(pos-1,(num*10+i)%md);
		}
	}
	return ans;
Read the rest Read More
| by XianKa | No comments

【高斯消元解异或方程组】开关问题


1518: 熄灯的工作
Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 471  Solved: 19
[Submit][Status][Web Board]
Description
重庆游戏与电子竞技大学的熄灯时间是11点半。每天晚上,宿管嬢嬢都是用总开关来关灯的。但是今天总开关坏了,只有一些分开关,每个开关控制一些灯,灯都有可能被多个开关控制。按一次开关,所有它所控制的灯都会切换一次状态,即亮的灯变灭,灭的灯变亮。一开始所有灯都是亮的,宿管嬢嬢想把所有的灯都灭了,但是她面对一堆开关头皮发麻,只好找来了头铁的你来解决这个问题。
Input
每个输入包含一个测试用例。 每个测试的第一行包括两个正整数,表示灯的数量N(1<=N<=100)和开关的数量M(1<=M<=100)。灯的编号从1到N。 接下来M行,每行的开头是一个整数,表示这个开关控制的灯的数量X(0<=X<=N),接下来是X个不相同的数字,表示这个开关控制的灯的编号。
Output
如果可以用这些开关关掉所有灯,输出”YES”。否则,输出”NO”。
Sample Input
3 2
2 1 2
2 1 3
Sample Output
NO

学了一下高斯消元,异或方程还挺有意思的

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[202][202]={0};
void gauss()
{
	for(int i=1;i<=n;i++)
	{
		int j=i;
		while(j<=n&&!a[j][i]) j++;
		if(j>n) continue;
		if(i!=j) for(int k=1;k<=m+1;k++) swap(a[i][k],a[j][k]);
		for(int l=1;l<=n;l++)
			if(l!=i&&a[l][i])
				for(int k=1;k<=m+1;k++) a[l][k]^=a[i][k];
	}
}
int main()
{
	int ans=1;
	scanf("%d%d",&n,&m);
	//a[n][m];
	for(int i=1;i<=n;i++) a[i][m+1]=1;
	
Read the rest Read More
| by XianKa | No comments

Playing with Paper CodeForces – 527A

http://codeforces.com/problemset/problem/527/A

求GCD,答案是每次加上a/b;

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
typedef long long ll;
ll ans=0;
ll gcd(ll a,ll b)
{
	if(b==0) 
	{
		return a;	
	}
	else
	{
		ans+=a/b;
		return gcd(b,a%b);
	}
}
ll aa,bb;
int main()
{
	scanf("%lld%lld",&aa,&bb);
	gcd(aa,bb);
	printf("%lld",ans);
} 

 … Read the rest

Read More
| by XianKa | No comments

LightOJ – 1282 求取数字前三位和后三位

You are given two integers: n and k, your task is to find the most significant three digits, and least significant three digits of nk.

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

Each case starts with a line containing two integers: n (2 ≤ n < 231) and k (1 ≤ k ≤ 107).

Output
For each case, print the case number and the three leading digits (most significant) and three trailing 
Read the rest Read More
| by XianKa | No comments

LightOJ – 1138 Trailing Zeroes (III)

You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N! = 1*2*...*N. For example, 5! = 120, 120 contains one zero on the trail.

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

Each case contains an integer Q (1 ≤ Q ≤ 108) in a line.

Output
For each case, print the case number and N. If 
Read the rest Read More
| by XianKa | No comments

LightOJ – 1045 K进制的位数

Factorial of an integer is defined by the following function

f(0) = 1

f(n) = f(n - 1) * n, if(n > 0)

So, factorial of 5 is 120. But in different bases, the factorial may be different. For example, factorial of 5 in base 8 is 170.

In this problem, you have to find the number of digit(s) of the factorial of an integer in a certain base.

Input
Input starts with an integer T (≤ 50000), denoting the 
Read the rest Read More
| by XianKa | No comments

线性同余方程组的合并

类似于

[latex][/latex]

a_ix\equiv b_i\mod m_i

的方程组就是线性同余方程组
根据同余的可加性,可令

x\equiv B \mod lcm(m_i)

所以答案就转化为了求B和lcm

a_1x \equiv b_1 \mod m1

x\equiv (b_1/\gcd(a_1,m_1))*(a_1^{-1}/gcd(a_1,m_1)) \mod (m_1/gcd(a_1,m_1))

x \equiv B_1 \mod m1

x=B_1+m_1*t 此时的m1*t是未知的

带入第二个方程,并整理

a(B_1+m_1t) \equiv b_2 \mod m_2

am_1t \equiv b_2-aB_1 \mod m_2

解出t

t \equiv (b_2-aB_1)/gcd(am_1,m_2) * (am_1)^{-1}/gcd(am_1,m_2) \mod (m_2)/gcd(am_1,m_2)

把t带入

x=B_1+m_1*t

[latex]此时的x在\mod m1和\mod m2的意义下都是成立的。B1_+m_1*t变成了新的B_2[/latex]

x\equiv B_2 \mod lcm(m_1,m_2)

x=B_2+lcm*t

再带入第三个方程即可向下合并

//返回一个b,m对 
pair<int, int> inner_congruence(const vector<int> &A,const vector<int> &B,const vector<int> &M)
{
	int x=0,m=1;
	for(int i-9;i<A.size();i++)
	{
		int a=A[i]*m,b=B[i]-A[i]*x,d=gcd(a,M[i]);
		if(b%d!=0) return make_pair(0,-1); 
Read the rest Read More
| by XianKa | No comments

【容斥原理】Arrange the Numbers LightOJ – 1095

Consider this sequence {1, 2, 3 ... N}, as an initial sequence of first N natural numbers. You can rearrange this sequence in many ways. There will be a total of N! arrangements. You have to calculate the number of arrangement of first N natural numbers, where in first M positions; exactly K numbers are in their initial position.

For Example, N = 5, M = 3, K = 2

You should count this arrangement {1, 4, 3, 2, 5}, 
Read the rest Read More
| by XianKa | No comments

【矩阵快速幂】nth Term LightOJ – 1096

You have to find the nth term of the following function:

f(n) = a * f(n-1) + b * f(n-3) + c, if(n > 2)

     = 0, if(n ≤ 2)

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

Each case contains four integers n (0 ≤ n ≤ 108), a b c (1 ≤ a, b, c ≤ 10000).

Output
For each case, print the case number and f(n) modulo 10007.

Sample Input
Read the rest Read More