「HNOI 2013」比赛
2024-10-18 04:12:00
题目链接
\(Solution\)
这道题观察数据范围发现很小,再看看题目可以发现是搜索.
这题纯搜索会\(T\)所以要加入适当剪枝
- 如果一个人后面的比赛都赢却依旧到不了目标分数,则直接\(return\)
- 限制每个人的分数,使他的分数不超过目标分数
- 我们用\(fx\)当做分出胜负的场次,\(fy\)当做平的场,ans当做总分数.则可以列出如下方程:
\[ \left\{
\begin{array}
fx+fy=n*(n-1)/2\\
3*fx+2*fy=ans \
\end{array}
\right.
\]
\begin{array}
fx+fy=n*(n-1)/2\\
3*fx+2*fy=ans \
\end{array}
\right.
\]
上面明显是一个二元一次方程组,可以将\(fx\)和\(fy\)解出来,这样子就可以用\(fx\)和\(fy\)限制胜负的场次和平的场次
- 利用的是人数为\(X\),分数集合为\(A\)的比赛方案数一定,与某人详细的得分是没有关系的.所以可以用记搜.把最后几个人剩余的分数的方案数存下就好了
\(Code\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
map<int,int> hah;
int aim[20],now[20],fx,fy,ans,b[11],n,m,js;
int dfs(int x,int y){
if(x==n) return 1;
if((n-y+1)*3<aim[x]-now[x]) return 0;
if(y==n+1){
for(int i=x+1;i<=n;i++)
b[i]=aim[i]-now[i];
sort(b+x+1,b+1+n),ans=0;
for(int i=x+1;i<=n;i++)
ans=ans*28+b[i];
if(hah.find(ans)!=hah.end()) return hah[ans];
else return hah[ans]=dfs(x+1,x+2);
}
int res=0;
if(now[x]+2<aim[x]&&fx)
now[x]+=3,fx--,res+=dfs(x,y+1),now[x]-=3,fx++;
if(now[x]<aim[x]&&now[y]<aim[y]&&fy)
now[x]++,now[y]++,fy--,res+=dfs(x,y+1),now[x]--,now[y]--,fy++;
if(now[y]+2<aim[y]&&fx)
now[y]+=3,fx--,res+=dfs(x,y+1),now[y]-=3,fx++;
return res%mod;
}
main(){
n=read(),m=n*(n-1);
for(int i=1;i<=n;i++)
aim[i]=read(),js+=aim[i];
sort(aim+1,aim+1+n);
fx=js-m,fy=(m-2*fx)>>1;
printf("%lld",dfs(1,2)%mod);
}
最新文章
- ready与onload的性能
- Swift的排序算法总结
- Nunit在VS2010加载不了程序集的解决办法
- php字符串处理总结
- unix 文件属性
- 更改css element.style
- 前端跨域方案-跨域请求代理(node服务)
- org.apache.hadoop.security.AccessControlException: Permission denied: user=?, access=WRITE, inode=";/";:hadoop:supergroup:drwxr-xr-x 异常解决
- Win7 系统记事本乱码及cmd闪退解决办法
- sed和awk用法
- 百度网盘免VIP全速下载!
- 动态规划-LIS1
- Linux服务部署--Java(一)
- Unity2017灯光烘焙知识点
- Navicat permium工具连接Oracle的配置
- 解题:HEOI 2012 朋友圈
- ubuntu10.04 交叉编译 aria2 总结
- 「CodePlus 2017 11 月赛」大吉大利,晚上吃鸡!(dij+bitset)
- IE中Ext的comboBox跑到页面左上角
- 利用iWARP/RDMA解决以太网高延迟
热门文章
- ubuntu16.04挂载windows NTFS磁盘方法
- 【原】Coursera—Andrew Ng机器学习—Week 7 习题—支持向量机SVM
- 浅谈Job&;JobDetail
- Android基础之sqlite 数据库简单操作
- HashMap、HashTable的区别
- swarmkit
- Core 第三组 结对作业——四则运算 Part1. Core代码编写
- python的 pep8 规范(看完你会感谢我的!!!)
- 34. Search for a Range (Array; Divide-and-Conquer)
- ios学习杂记