组队赛4解题报告(组合数学+禁位排列+容斥原理+精度进位+贪心背包+矩阵快速幂)

本文主要是介绍组队赛4解题报告(组合数学+禁位排列+容斥原理+精度进位+贪心背包+矩阵快速幂),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

B题:ZOJ 3687  链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4970

题意:在d天看不了c章,问复习的方案有多少种?

思路:这题比赛的时候看出是组合数组和容斥原理了,不过不会做,所以一直托到现在了才做。而且自己又看别人的解题报告理解了一下午才理解明白……笨了……

我在百度文库上已经知道错排和禁位排列是什么回事了,而且计算公式里面都有,不过这里的禁位有点特别,禁位的条件给出来了,所以不能直接用百度文库里面的计算,因为如d相同,或者c相同的时候它们是不能组合在一组里面的。所以别人的解题报告里面有了很好的解决办法就是dfs搜索禁位的情况……我把dfs里面的每一种情况都输出来了才知道是这么回事……哈哈,不过好在理解了……

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 10000005
#define Max 2
#define INF 55566677
#define eps 1e-7
using namespace std;
typedef long long ll;
int cal[53],n,m,res,a[53][2],v[53][53],vi[53],vis[53];
void init()
{cal[0]=1;for(int i=1;i<=50;i++)cal[i]=((ll)cal[i-1]*i)%INF; //cal[i-1]*i会超出int
}
void dfs(int i,int num) //i表示第i个条件,num是禁位条件数
{if(i>m){//当禁位条件数目为num时,其排列数有(n-num)!,//因为这num个禁位是固定的,所以让不固定的排列就是(n-num)!if(num&1) res=(res-cal[n-num])%INF;else res=(res+cal[n-num])%INF;//cout<<i<<' '<<num<<endl;return ;}dfs(i+1,num);if(!vi[a[i][0]]&&!vis[a[i][1]]){vi[a[i][0]]=vis[a[i][1]]=1;dfs(i+1,num+1);vi[a[i][0]]=vis[a[i][1]]=0;}
}
int main()
{init();while(~scanf("%d%d",&n,&m)){mem(v,0),mem(vi,0),mem(vis,0);for(int i=1;i<=m;i++){scanf("%d%d",&a[i][0],&a[i][1]);if(!v[a[i][0]][a[i][1]]) v[a[i][0]][a[i][1]]=1;else m--,i--;}res=0;dfs(1,0);pri((res%INF+INF)%INF);//puts("");}return 0;
}

C题:ZOJ 3688 链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4971

这题太神了,根本理解不了……

分析网址:http://blog.csdn.net/a_siscon/article/details/8874207

或者:http://blog.csdn.net/zu_xu/article/details/8762847

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 10000005
#define Max 2
#define INF 55566677
#define eps 1e-7
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
int a[100005];
int r[100005];
int main()
{a[1]=a[2]=0;r[1]=a[3]=1;for(int i=4; i<100005; i++){int x=i-2;r[x]=r[MOD%x]*ll(MOD-MOD/x)%MOD;int aa=(i-2ll)*i%MOD*a[i-1]%MOD;int bb=(a[i-2]*ll(i)+(i&1?4:MOD-4))%MOD;a[i]=ll(aa+bb)*r[x]%MOD;}for(int n; scanf("%d",&n)==1; printf("%d\n",a[n]));
}

H题:ZOJ 3693  链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3693

题意:有n个参赛人员,加上教练2个共有n+2个人去吃饭,每k个人能免费一个人的钱,问教练这两个人付款的时候平分要付款多少,精确到分(0.0.1)。

思路:这题真有点坑,两个人因为要精确到分,所以如果只要超过0.01,即小数点第三位之后只要大于0,就得进位,所以……加下0.004999999999就可以了。

#include <iostream>
#include <cstdio>
#include <cstring>
#define eps 1e-7
using namespace std;
int main()
{int n,k,ans;double w,c,d;while(~scanf("%d%lf%d",&n,&w,&k)){ans=(n+2)/k,c=w*(n+2-ans),d=c/2;printf("%.2lf\n",d+0.00499999);}
}

D题 ZOJ 3689 链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3689

题意:给出n个工作量,T个总工作时间,然后每个工作ti,si表示做这个工作花费ti时间,可以得到 (T-ti)*si 的金子,(T-ti)表示的是剩余的时间。问工人能得到最多的金子是多少。

思路:刚开始看起来是01背包,然后大帝敲了样例都没得出来……然后又想了想,觉得是贪心,大帝又想出了排序的方案,我们验证了下,觉得很可行,然后又敲了贪心。不过交了还是WA,然后本来我已经没心思看这题了,木想到OE大帝加了个01背包就行了,哈哈,太神了……所以这题就是贪心+01背包。

贪心就是以:t1*s2<t2*s1 || (t1*s2==t2*s1&&t1<t2) 来排序贪心的,可以举几个例子就可以知道这个贪心的方法了。

本来我们已经觉得贪心已经足够把大部分的数据给过了,但是可能贪心的排序方法还有点不足吧,可能有的例子没过,所以加了01背包的优化之后就过了……呵呵,神!!!

总结:背包中的容量与价值顺序不同,得到的最优结果就会不一样,可以根据背包DP的选择最优情况可知,因为01背包是在前一状态最优的情况取得的,又因为本题与剩余的时候有关系,所以如果排序情况不同,那么剩余的时间就会不一样,所以用的背包最优结果也就不一样,又学到了这一点,哈哈……

解法一:下面第一个代码因为是根据上面的贪心方法做的,所以01背包就得就得从大的往小的取,先取得金子大的,然后下一次是小的在大的基础上取最优:

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 10005
#define MN 3005
#define INF 10000007
#define eps 1e-6
using namespace std;
typedef long long ll;
int dp[MM];
struct node
{int t,s;
} e[MN];
bool cmp(node a,node b)
{return (a.t*b.s<a.s*b.t||(a.t*b.s==a.s*b.t&&a.t<b.t));
}
int main()
{int n,t;while(~scanf("%d%d",&n,&t)){int i,j,ans=-INF;mem(dp,0);for(i=0; i<n; i++)scanf("%d%d",&e[i].t,&e[i].s);sort(e,e+n,cmp);for(i=0; i<n; i++)for(j=0; j<=t-e[i].t; j++){dp[j]=max(dp[j],dp[j+e[i].t]+(j+e[i].t)*e[i].s);ans=max(ans,dp[j]);}pri(ans);}
}
解法二:这个也是背包,不过是我经常用的写法,也是那时学长教的那种写法,第二个for循环是逆序的,刚才那个是顺序的,有点难懂。因为逆序,所以贪心方法相反,是从得金子少的到大的排序的:

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 10005
#define MN 3005
#define INF 10000007
#define eps 1e-6
using namespace std;
typedef long long ll;
int dp[MM];
struct node
{int t,s;
} e[MN];
bool cmp(node a,node b)
{return (a.t*b.s>a.s*b.t||(a.t*b.s==a.s*b.t&&a.t>b.t));
}
int main()
{int n,t;while(~scanf("%d%d",&n,&t)){int i,j,ans=-INF;mem(dp,0);for(i=0; i<n; i++)scanf("%d%d",&e[i].t,&e[i].s);sort(e,e+n,cmp);for(i=0; i<n; i++)for(j=t; j>=e[i].t; j--){dp[j]=max(dp[j],dp[j-e[i].t]+j*e[i].s);ans=max(ans,dp[j]);}pri(ans);}
}

E题:ZOJ 3690 链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4973

f[i],表示前i-1个人的选择,且第i个人选择大于k的值
g[i], 表示前i-1个人的选择,且第i个人选择小于k的值
可得到递推式
f[i]=(m-k)*f[i-1]+(m-k)*g[i-1]
g[i]=k*f[i-1]+(k-1)*g[i-1]
可得到矩阵:
|f[i] g[i]|=|f[i-1] g[i-1]|*|m-k k  |
                            |m-k k-1|
 
   |f[n] g[n]|=|f[1] g[1]|* |m-k k  |^(n-1)
                            |m-k k-1|
ans=f[n]+g[n];

这个题刚开始我都不知道怎么递推,是队友递推出来我才知道的。然后dp 超时,宝哥就想到了快速幂矩阵,唉……今晚学了好久咦……

不过自己对着别人的代码终于整理出自己的快速幂矩阵的模板了……

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 10000005
#define MN 3005
#define INF 1000000007
#define eps 1e-7
using namespace std;
typedef long long ll;
#define Max 3
struct Matrix //快速幂模板
{ll m[Max][Max];Matrix() {}friend Matrix operator*(Matrix &m1,Matrix &m2){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++){temp.m[i][j]=0;for(k=0;k<Max;k++)temp.m[i][j]+=(m1.m[i][k]*m2.m[k][j])%INF;temp.m[i][j]%=INF;}return temp;}friend Matrix quickpow(Matrix &M,ll n){int i,j,k;Matrix temp;for(i=0;i<Max;i++)for(j=0;j<Max;j++) //单位矩阵if(i==j) temp.m[i][j]=1;else temp.m[i][j]=0;while(n){if(n&1) temp=temp*M;n>>=1;M=M*M;}return temp;}
}res;
int main()
{ll n,m,k;while(~scanf("%lld%lld%lld",&n,&m,&k)){res.m[1][1]=res.m[2][1]=m-k;res.m[1][2]=k;res.m[2][2]=k-1;res=quickpow(res,n-1);ll a=((res.m[2][1]*k)%INF+res.m[1][1]*(m-k)%INF)%INF;ll b=((res.m[2][2]*k)%INF+res.m[1][2]*(m-k)%INF)%INF;printf("%lld\n",(a+b)%INF);}return 0;
}



这篇关于组队赛4解题报告(组合数学+禁位排列+容斥原理+精度进位+贪心背包+矩阵快速幂)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1043657

相关文章

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三

C#中async await异步关键字用法和异步的底层原理全解析

《C#中asyncawait异步关键字用法和异步的底层原理全解析》:本文主要介绍C#中asyncawait异步关键字用法和异步的底层原理全解析,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录C#异步编程一、异步编程基础二、异步方法的工作原理三、代码示例四、编译后的底层实现五、总结C#异步编程

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道(channel)操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1:监听多个通道示例 2:带

鸿蒙中@State的原理使用详解(HarmonyOS 5)

《鸿蒙中@State的原理使用详解(HarmonyOS5)》@State是HarmonyOSArkTS框架中用于管理组件状态的核心装饰器,其核心作用是实现数据驱动UI的响应式编程模式,本文给大家介绍... 目录一、@State在鸿蒙中是做什么的?二、@Spythontate的基本原理1. 依赖关系的收集2.

利用Python快速搭建Markdown笔记发布系统

《利用Python快速搭建Markdown笔记发布系统》这篇文章主要为大家详细介绍了使用Python生态的成熟工具,在30分钟内搭建一个支持Markdown渲染、分类标签、全文搜索的私有化知识发布系统... 目录引言:为什么要自建知识博客一、技术选型:极简主义开发栈二、系统架构设计三、核心代码实现(分步解析

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2