数学题又一波
标签： 数学
hdu_5795 sg函数应用
题意：
两个人从很多堆中取石子，每次可以从其中任意一堆中取一个或者多个，也可以吧其中任意一堆分成三堆，问先手赢还是后手赢。
题解：
先讲解一下sg函数的意义：sg函数表示的是当前这一堆石子的所有可能的后继状态中第一个没有出现过的状态值，如果在这个题中，如果只考虑拿取石子，不考虑分堆情况的话，可以看到，对于一堆石子个数是x的一堆石子来说，它的sg函数就是x.
所有堆的sg函数异或起来就是整个堆的sg函数，如果等于0是一种状态，不等于0是另外一种状态，根据题意判读即可，但是这个题有分堆的情况，考虑一下要怎么做呢，采用打表找规律的方式，因为枚举每个堆分堆后的后继状态，然后找每一堆对应的sg函数值得规律，我们可以发现当x = 8k+7和x = 8k+8的时候sg分别等于 sg = 8k+8和sg = 8k + 7之外，其他的sg = x；
那么总结一下这种题的思路，对于每一堆枚举它的sg函数值，找到对应每一堆的sg函数值，然后异或起来，得到所有堆的sg函数，然后根据其是否得0来判读状态。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
int ans = 0;
int tm;
int sg;
for(int i= 0; i < n ;i++){
scanf("%d",&tm);
if(tm%8==7) sg = tm+1;
else if(tm%8==0) sg = tm-1;
else sg = tm;
ans = ans^sg;
}
if(ans==0) puts("Second player wins.");
else puts("First player wins.");
}
return 0;
}
hdu_1024 dp经典
题意：
求一个数组的m个不重合子区间的和最大值
题解：
经典的dp，dp[i][j]表示组成了i个集合，用到了前j个元素的时候的子区间最大值。那么有转移方程为，考虑当前这个元素加入到前面这个集合，或者这个元素不加入前面这个集合,而是作为一个新的集合的起点
(dp[i][j] = max(dp[i][j-1]+a[j],max(dp[i-1][k]+a[k]))
注意，这里很明显，要遍历每次(0<k<j)所以如果每次都扫一遍的话肯定会超时，我们可以每次算上一层的时候保存一个上一层到k的最大值，因为空间问题，要使用滚动数组，和其他的dp一样，画一个状态转移的图，然后找规律即可。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int RINF = -1000000009;
const int N = 1000008;
int dp[N];
int mp[N];
int mmax[N];
int main()
{
int n,m;
int tm;
while(~scanf("%d%d",&m,&n))
{
for(int i = 1; i <= n; i++){
scanf("%d",&mp[i]);
}
memset(dp,0,sizeof(dp));
memset(mmax,0,sizeof(mmax));
mmax[0] = 0;
for(int i = 1; i <= m; i++){
tm = RINF;
for(int j = i; j <= n; j++){
dp[j] = max(dp[j-1]+mp[j],mmax[j-1]+mp[j]);
mmax[j-1] = tm;
tm = max(tm,dp[j]);
}
}
printf("%d
",tm);
}
return 0;
}
hdu_5762 暴力+鸽巢原理
题意：
给你很多点，求存不存在两组不同的点对满足其哈密顿距离相同
题解：
考虑到两点的距离的所有可能解为2M，所以如果点数对大于2M的话，肯定存在两个点数对的距离和是相同的的。所以直接暴力可能可以在规定时间内结束循环。那么我们就直接暴力好了，哈哈
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 300004;
int xx[N],yy[N];
int vis[N];
int aabs(int a)
{
if(a>=0) return a;
else return -a;
}
int main()
{
int T,n,m;
scanf("%d",&T);
while(T--)
{
memset(xx,0,sizeof(xx));
memset(yy,0,sizeof(yy));
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&m);
int x,y;
for(int i = 0; i < n; i++){
scanf("%d%d",&xx[i],&yy[i]);
}
bool fl = 0;
for(int i = 0; i <n&&fl==0; i++){
for(int j = i+1; j < n&&fl==0; j++){
int tm = aabs(xx[i]-xx[j])+aabs(yy[i]-yy[j]);
if(vis[tm]) {
fl = 1;
}
else vis[tm] = 1;
}
}
if(fl) puts("YES");
else puts("NO");
}
return 0;
}
hdu_1808 鸽巢原理+前缀和
题意：
求一个数组，存不存在一个子序列的和是c的倍数
题解：
考虑到这个题已知n>c所以对于n个数的前缀和%c一定存在两个相同的值，那么求前n个数的前缀和%c那么如果两个数相同了，那么在这两个数之间的数加起来肯定会和是c的倍数，可以自己验证
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100006;
int sum[N];
int vis[N];
int main()
{
int n,m,tm;
int l,r;
while(~scanf("%d%d",&n,&m))
{
memset(sum,0,sizeof(sum));
memset(vis,0,sizeof(vis));
if(n==0&&m==0) return 0;
bool fl = 0;
for(int i = 1; i <= m; i++){
scanf("%d",&tm);
if(fl==1) continue;
sum[i] = (sum[i-1]+tm)%n;
if(tm%n==0){
fl = 1;
l = r = i;
}
else if(sum[i]%n==0) {
fl = 1;
l = 0;
r = i;
}
else if(vis[sum[i]]!=0){
fl = 1;
l = vis[sum[i]];
r = i;
}
else {
vis[sum[i]] = i;
}
}
for(int i = l+1; i <= r; i++){
printf("%d",i);
if(i!=r) printf(" ");
}
puts("");
}
return 0;
}
hdu_1205 组合数学
题意：
略
题解：
用隔板法考虑，考虑个数最多的糖果如果可以通过隔板法分开，那么其他的糖果就一定可以分割开了，为啥自己想
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1000008;
#define ll long long
ll mp[N];
int main()
{
int T,n;
scanf("%d",&T);
while(T--)
{
ll mmax = 0;
ll sum = 0;
scanf("%d",&n);
for(int i = 0; i < n; i++){
scanf("%lld",&mp[i]);
mmax = max(mmax,mp[i]);
sum+=mp[i];
}
if(sum-mmax+1>=mmax) puts("Yes");
else puts("No");
}
return 0;
}
hdu_2048 组合数学
题意：
以后中文题面的都不介绍题意了
题解：
经典的错排问题。考虑N个人，如果将其中一个人y放在另一个位置x上，那么x这个人就有两种可能，一种是x就去y的位置上，那么剩下的人就有(f(n-2))种可能，另一种情况就是x没有去y的位置，那么就是剩下的n-1个人错排，(f(n-1))
于是有了这样的公式
(f(n) = (n-1)*[f(n-2)+f(n-1)])
当然，也可以套用错排的公式
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
double ans[22];
double dp[22];
void init()
{
for(int i = 0; i < 22; i++){
dp[i] = 0;
ans[i] = 0;
}
ans[1] = 0.0;
ans[2] = 50.0;
dp[1] = 0.0;
dp[2] = 1.0;
double tm;
for(int i = 3; i < 22; i++){
tm = 1;
for(int j = 1; j <= i; j++){
tm = tm*j;
}
dp[i] = ((double)i-1)*(dp[i-1]+dp[i-2]);
// printf("dp = %lf ",dp[i]);
ans[i] = dp[i]/tm*100;
}
}
int main()
{
init();
int T,c;
scanf("%d",&T);
while(T--)
{
scanf("%d",&c);
printf("%.2lf%%
",ans[c]);
}
return 0;
}
poj_2356 鸽巢原理
- 题意:
求一个区间是否存在几个数的的和是n的整数倍
- 题解：
根据鸽巢原理，(x\%n) 最多有n-1种情况，那么如果有n个数的话，所以求完前缀和后对n取模，然后如果结果又两个相同的话，那么一定这两个数之间的数的和是n的倍数，为什么的话，自己推
- 代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10008;
int sum[N];
int vis[N];
int mp[N];
int main()
{
int n;
int l, r;
int tm;
while(~scanf("%d",&n))
{
memset(sum,0,sizeof(sum));
memset(vis,0,sizeof(vis));
for(int i = 1; i <= n; i++)
{
scanf("%d",&tm);
mp[i] = tm;
sum[i] = (sum[i-1]+tm)%n;
if(sum[i]%n==0){
l = 0;
r = i;
}
else if(vis[sum[i]%n]){
l = vis[sum[i]%n];
r = i;
}
else {
vis[sum[i]%n] = i;
}
}
printf("%d
",r-l);
for(int i = l+1; i <= r; i++){
printf("%d
",mp[i]);
}
}
return 0;
}
csu_1320 卡特兰数
- 题解：
和括号的匹配差不多的想法，裸的卡特兰数，直接套用公式下面给出卡特兰数的三个公式
- 迭代式
- 通项公式
- 递推式
- 代码：
#include <cstdio>
typedef long long ll;
const int MAXN = 10000 + 100;
const ll MOD = 1000000007;
ll ans[MAXN];
ll extgcd(ll a, ll b, ll &x, ll &y){
ll d = a;
if(b == 0LL){
x = 1; y = 0;
}else{
d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
}
return d;
}
ll mod_inverse(ll a, ll MOD){
ll x, y;
extgcd(a, MOD, x ,y);
return (x % MOD + MOD) % MOD;
}
void Init(){
ans[0] = ans[1] = 1;
for(int i = 2; i < MAXN; ++i){
ans[i] = (((ans[i - 1] * (4 * i - 2)) % MOD) * mod_inverse(i + 1, MOD)) % MOD;
}
return;
}
int main(int argc, char const *argv[]){
Init();
int x;
while(~scanf("%d", &x)){
printf("%lld
", ans[x]);
}
return 0;
}
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MOD = 1000000007;
const int N = 10008;
#define ll long long
ll f[N];
int n;
void getf()
{
f[0] = 1;
for(int i = 0; i < N; i++){
for(int j = 0; j < i; j++){
f[i] = ((f[j]*f[i-1-j])%MOD+f[i])%MOD;
}
}
}
int main()
{
getf();
while(~scanf("%d",&n))
{
printf("%lld
",f[n]);
}
return 0;
}
uva_10790 组合数学
- 题意：
有两排，上面给出一定的点数，下面也给出一定的点数，然后问你，交点的个数，多条线不能相交于同一个点
- 题解：
上面选择两个点，下面选择两个点一定就有一个交点，所以我们直接$$dbinom{a}{2}*dbinom{b}{2}$$
- 代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20008;
#define ll long long
int main()
{
ll a,b;
ll ans;
int cnt = 1;
while(~scanf("%lld%lld",&a,&b))
{
if(a==0&&b==0) return 0;
ans = a*b*(a-1)*(b-1)/4;
printf("Case %d: %lld
",cnt++,ans);
}
return 0;
}
hdu_1023 卡特兰数+java大数
- 题意：
求火车进站和出栈的顺序的种类数，经典的卡特兰数，但是100的卡特兰数要用大数算。
- 代码：
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static BigInteger f[] = new BigInteger[101];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
f[0] = BigInteger.ONE;
for(int i=1;i<101;i++) {
BigInteger a = BigInteger.valueOf(4*i-2);
BigInteger b = BigInteger.valueOf(i+1);
f[i] = a.multiply(f[i-1]).divide(b);
}
while(scan.hasNext()){
int n = scan.nextInt();
System.out.println(f[n]);
}
}
}