【组合数求模】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

【组合数学】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

【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

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

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

【数位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

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


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

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

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

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

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