Preparing Olympiad---cf550B(DFS或者状态压缩模板)
2024-08-20 22:24:13
比赛链接:http://codeforces.com/problemset/problem/550/B
给你n个数,选出来只是2个然后求他们的和在L和R的区间内,并且选出来的数中最大值和最小值的差不得小于x,求共有多少种选法
下面是dfs搜出来的;
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define met(a, b) memset(a, b, sizeof(a))
using namespace std;
#define N 110
#define INF 0x3f3f3f3f int n, l, r, x, ans, a[N];
///sum是当前的和,cnt是选了几个数了, s是起始位置,e是终止位置;
void dfs(int sum, int cnt, int s, int e)
{
if(sum > r)return ; if(sum<=r && sum>=l && a[e]-a[s]>=x && cnt>= )ans++; for(int i = e+; i<=n; i++) dfs(sum + a[i], cnt+, s, i);
} int main()
{
while(scanf("%d %d %d %d", &n, &l, &r, &x)!=EOF)
{
ans = ;
for(int i=; i<=n; i++)
scanf("%d", &a[i]); sort(a+, a+n+); for(int i=; i<=n; i++)
dfs(a[i], , i, i); printf("%d\n", ans);
}
return ;
}
暴力枚举所有情况,判断是否符合条件即可; 第一次写状态压缩的题
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define met(a, b) memset(a, b, sizeof(a))
using namespace std;
#define N 15
#define INF 0x3f3f3f3f int main()
{
int n, L, R, x, a[N]; while(scanf("%d %d %d %d", &n, &L, &R, &x) !=EOF )
{
met(a, ); for(int i=; i<n; i++)
scanf("%d", &a[i]); int cnt = (<<n)-, ans = ; for(int i=; i <= cnt; i++)
{
int Min = INF, Max = -INF, num, sum = ; for(int j=; j<n; j++)
{
if( i & (<<j) )
{
sum += a[j];
Min = min(Min, a[j]);
Max = max(Max, a[j]);
num ++;
}
}
if(sum >= L && sum <= R && Max - Min >= x && num >= )
ans++;
}
printf("%d\n", ans); }
return ;
}
最新文章
- 水题 Codeforces Round #296 (Div. 2) A. Playing with Paper
- data-属性
- [转载] Linux下高并发socket最大连接数所受的各种限制
- java script 闭包
- 玩转Android之手摸手教你DIY一个抢红包神器!
- Android 开机自启动应用
- php开启curl和openssl
- Git之路——Git的使用
- JAVA中List与Array之间互换
- Laravel Cache 使用
- Server 2008 R2多用户远程桌面连接授权,解决120天过期问题
- 《图解Java多线程设计模式》读书笔记
- # 2019-2020-4 《Java 程序设计》第六周总结
- C语言 指针基础篇 数组,函数与指针的运用 2 14
- Mysql 8.0修改密码
- Android 软件管理工具类Utils
- mysql之select语法
- 【转】单KEY业务,数据库水平切分架构实践
- Shiro-Base64加密解密,Md5加密
- PHP开发微信公众号(二)消息接受与推送