codeforces D. Nastya and Scoreboard

标签: codeforces

在这里插入图片描述

题目

题意:

给你nn77位数,然后你可以尽力把木棍关闭的打开来使着nn个数字最大(只能从关闭->打开),问最大是多少。

思路

我们可以直接用dfsdfs先从最大的99开始递归,然后因为无法从把打开的关闭,所以就有(val[i]&a[step])==a[step](val[i] \& a[step]) == a[step],这样可以保证astepa_{step}上的位数在valival_i都存在,就保证了只能打开了,然后dfs(step+1,)dfs(step+1,剩余的数量-此次打开的数量),因为使从最大的开始找的,所以一旦符合条件,那么这个就是答案了,但是数据有点大,所以需要加上剪枝,也就是if(book[step][kk])return;if(book[step][kk]) return ;book[step][kk]=true;book[step][kk] = true;这样的话,因为可能某些数字和某些数字翻转所需的使一样的,这样就会导致重复,因为已经递归过并且无法成功。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <deque>
#include <stack>
using namespace std;
typedef long long ll;
typedef vector<int> veci;
typedef vector<ll> vecl;
typedef pair<int, int> pii;
template <class T>
inline void read(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return ;
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1:1;
    ret = (c == '-') ? 0:(c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return ;
}
inline void out(int x) {
    if (x > 9) out(x / 10);
    putchar(x % 10 + '0');
}
const int maxn = 2010;
int val[20] = {119, 18, 93, 91, 58, 107, 111, 82, 127, 123}, a[maxn], ans[maxn];
int n, k, x;
bool book[maxn][maxn] = {false};
void dfs(int step, int kk) {
    if (kk < 0) return ;
    if (book[step][kk]) return ;
    book[step][kk] = true;
    if (step == n) {
        if (kk == 0) {
            for (int i = 0; i < n; i++) printf("%d", ans[i]);
            exit(0);
        }
        return ;
    }
    for (int i = 9; i >= 0; i--) {
        if ((val[i] & a[step]) == a[step]) {
            ans[step] = i;
            dfs(step + 1, kk - __builtin_popcount(val[i] ^ a[step]));
        }
    }
}
int main() {
    read(n) ,read(k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 7; j++) {
            scanf("%1d", &x);
            a[i] = (a[i] << 1) + x;
        }
    }
    dfs(0, k);
    printf("-1\n");
    return 0;
}

版权声明:本文为weixin_45031646原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45031646/article/details/105751120

智能推荐

循环

与任何程序设计语言一样Java利用条件语句与循环结构确定流程控制,一下总结一下Java中的循环语句: while do while for switch 对于golang来说: switch非常灵活。从第一个expr为true的case开始执行,如果case带有fallthrough,程序会继续执行下一条case,不会再判断下一条case的expr,如果之后的case都有fallthrough,d...

1638 统计只差一个字符的子串数目(动态规划)

1. 问题描述: 给你两个字符串 s 和 t ,请你找出 s 中的非空子串的数目,这些子串满足替换一个不同字符以后,是 t 串的子串。换言之,请你找到 s 和 t 串中恰好只有一个字符不同的子字符串对的数目。比方说, "computer" 和 "computation"...

websocket基本原理

HTTP中一个request只能有一个response。而且这个response也是被动的,不能主动发起 因此过去的服务端推送信息是通过客户端不停的轮询实现的 websocket是双向通信协议,提供了服务端主动推送信息的能力 需要客户端(浏览器)和服务端同时支持 如果经过代理的话,还需要代理支持,否则有些代理在长时间无通信时会自动切断连接 因此WS为了保证连接不被断掉,会发心跳 WebSocket...

mybatis+ehcache二级缓存

导入jar包 mapper.xml文件开启二级缓存 pojo类实现序列化接口 配置ehcache.xml 测试...

python+opencv实现图像拼接

任务 拍摄两张图片去除相同部分,拼接在一起 原图 结果 步骤 读取两张图片 使用sift检测关键点及描述因子 匹配关键点 处理并保存关键点 得到变换矩阵 图像变换并拼接 代码实现 扩展 这里对右边图像进行变换,右边变得模糊,可以修改代码对左边图像变换 这里只有两张图片拼接,可以封装实现多张图片拼接 可以修改代码实现上下图片的拼接...

猜你喜欢

python_sklearn机器学习算法系列之AdaBoost------人脸识别(PCA,决策树)

          注:在读本文之前建议读一下之前的一片文章python_sklearn机器学习算法系列之PCA(主成分分析)------人脸识别(k-NearestNeighbor,KNN)         本文主要目的是通过一个简单的小...

memmove函数与memcpy函数的模拟实现

memmove函数和memcpy函数都是在内存复制任意类型的,但是它俩也有区别。当源区域和目标区域有重复的,memmove函数会复制缓冲区重叠的部分,而memcpy相反,会报出未知错误。 下面给出两个函数的实现 首先,memmove函数。 实现的基本原理如下图。 具体代码如下: memcpy函数的实现很简单,就直接给出源代码了...

SpringFramework核心 - IOC容器的实现 - 总结

1. 概述 把Spring技术内幕第一章和第二章过了一遍,也做了一些笔记, 对IOC容器的实现有了一定皮毛理解,现在跟着源码再过一遍总结一下IOC容器的初始化,Bean的初始化的过程,做一下总结 ① IOC容器和简单工厂模式 在开始之前,先想想我们平时是怎么使用IOC容器为我们管理Bean的,假设我们要把下面的User类交给IOC容器管理 我们不想关心如何创建一个User对象实例的,仅仅在需要他的...

Python和Django的安装

个人博客导航页(点击右侧链接即可打开个人博客):大牛带你入门技术栈  一、下载并安装Python Python 官方下载地址:http://www.python.org/ftp/python/ 我们这里选择的是 Python 2.7.2 。虽然目前最新版是Python 3.2.2, 但是Django目前还不支持 Python 3.2.2。 安装步骤很简单,双击安装包开...