学习笔记20:牛客周赛32

D

统计子节点中1的个数即可(类似树形dp?)

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<map>

using namespace std;
typedef long long LL;
#define int long long
typedef pair<int,int> PII;
const int N=1000010;
int a[N];
string x;
int dp[N];
std::vector<int> v[N];
void dfs(int u,int fa){
    if(x[u]=='1') dp[u]=1;
    for(auto c:v[u]){
        if(c==fa) continue;
        dfs(c,u);
        dp[u]+=dp[c];
    }
}
void solve(){
    int n;
    cin>>n;
    cin>>x;
    x=","+x;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x); 
    }
    dfs(1,-1);
    for(int i=1;i<=n;i++){
        cout<<dp[i]-(x[i]=='1')<<endl;
    }

}
signed main(){
    
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    } 
}
        

E

我们思考如果当前可以和之前的点重排成一个回文数,那么有两种情况

1.之前出现过的奇偶性质完全相等的(奇-奇=偶 偶-偶=偶)

2.之前出现过的奇偶性质中有一个不同的(奇-偶=奇 偶-奇=奇,这样会有一个值出现次数为奇数,就行  39993 393 ……)

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<map>

using namespace std;
typedef long long LL;
#define int long long
typedef pair<int,int> PII;
const int N=1000010;
int a[N];
void solve(){
    string x;
    cin>>x;
    int ans=0;
    map<vector<int>,int>mp;
    vector<int>sum;
    for(int i=0;i<10;i++) sum.push_back(0);
        mp[sum]++;
    for(int i=0;i<x.size();i++){
        sum[x[i]-'0']^=1;
        ans+=mp[sum];
        for(int i=0;i<10;i++){
            vector<int>tt=sum;
            tt[i]^=1;
            ans+=mp[tt];
        }
        mp[sum]++;
    }
    cout<<ans<<endl;
}
signed main(){
    
    int t=1;
   // cin>>t;
    while(t--){
        solve();
    }
}
        

F

状态压缩dp

变成r对应0

变成e对应1

变成d对应2

可以用三进制模拟

1.首先枚举自己可行的转变的状态j

        也就是,在自己这列中,相邻不相等的状态

2.然后再枚举上一列的状态k

        如果对于j和k,如果不冲突则可以直接转化

最终答案就是min(dp[m-1][k])

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<map>

using namespace std;
typedef long long LL;
#define int long long
typedef pair<int,int> PII;
const int N=1000010;
int a[N];
string str[N];
int tmp[N];
int t[5]={1,3,9,27,81};
int dp[1010][1010];
int n,m;
    
int b[4];
bool check(int num){
    for(int i=0;i<n;i++){
        b[i]=num%3;
        num/=3;
    }
    for(int i=1;i<n;i++) if(b[i]==b[i-1]) return false;
    return true;
}
bool check(int x,int y){
    for(int i=0;i<n;i++){
        if(x%3==y%3) return false;
        x/=3;
        y/=3;
    }
    return true;
}
void solve(){
    
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>str[i];
    int ans=1e18;
    map<char,int>mp;
    mp['r']=0;
    mp['e']=1;
    mp['d']=2;
    memset(dp,0x3f,sizeof dp);
    for(int i=0;i<m;i++){
        for(int j=0;j<t[n];j++){
            int res=0;
            int now=j;
            if(check(j)){
                if(!i){

                    for(int k=0;k<n;k++){
                        if(mp[str[k][i]]!=(now%3))res++;
                        now/=3;
                    }
                    dp[i][j]=min(dp[i][j],res);
                }else{
                    
                    for(int k=0;k<n;k++){
                        if(mp[str[k][i]]!=(now%3))res++;
                        now/=3;
                    }
                    for(int k=0;k<t[n];k++){
                        if(check(j,k)){
                            dp[i][j]=min(dp[i][j],dp[i-1][k]+res);
                        }
                    }
                }
                if(i==m-1){
                    ans=min(dp[i][j],ans);
                }
            }
                
        }
        
     }
    cout<<ans<<endl;
}
signed main(){
    
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}
        

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/388025.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Nvidia 推出了本地版聊天 Chat with RTX;OpenAI联创Karpathy宣布离职专注个人项目

&#x1f989; AI新闻 Nvidia 推出了本地版聊天 Chat with RTX 摘要&#xff1a;英伟达最近发布了名为“Chat with RTX”的Demo版个性化AI聊天机器人&#xff0c;适用于Windows平台&#xff0c;需要Nvidia的30系/40系显卡&#xff0c;显存至少为8GB&#xff0c;系统配置包括1…

【教学类-19-05】20240214《ABAB式-规律黏贴18格-手工纸15*15CM-一页一种图案,A空,横向、边框》(中班)

背景需求 利用15*15CM手工纸制作AB色块手环&#xff08;手工纸自带色彩&#xff09; 素材准备 代码展示 作者&#xff1a;阿夏 时间&#xff1a;2024年2月14日 名称&#xff1a;正方形数字卡片AB图案 _ 华光彩云_CNKI A的位置有图案 18格 一页一种图案&#xff0c;A空&#…

步步深入 k8s 使用 pv pvc sc 在 nfs 基础上共享存储

博客原文 文章目录 前言集群环境nfs 环境搭建pod 挂载 nfs架构图 pvc 方式挂载 nfs架构图 storageclass 方式动态申请 pv架构图 参考 前言 持久化卷&#xff08;Persistent Volume, PV&#xff09;允许用户将外部存储映射到集群&#xff0c;而持久化卷申请&#xff08;Persist…

open ai api 国内配置代理指南(网上最全)

1.配置须知 open ai 作为这一波AI浪潮的推动者&#xff0c;opne ai的gpt 系列产品在使用和体验上绝对是最强大的&#xff0c;现在对于开发者来说要在代码中访问open ai api是不可用的。所以本文就主要解决这个问题。我们要了解open ai 的网站gpt的访问和api的访问收费是分开来…

K8sGPT 的使用

K8sGPT 介绍 k8sgpt 是一个扫描 Kubernetes 集群、诊断和分类问题的工具。它将 SRE 经验编入其分析器中&#xff0c;并帮助提取最相关的信息&#xff0c;通过人工智能来丰富它。它还可以与 OpenAI、Azure、Cohere、Amazon Bedrock 和本地模型结合使用。 K8sGPT Github 地址 …

波奇学Linux:文件系统

磁盘认识 磁盘被访问的基本单元是扇区-512字节。 磁盘可以看成多个同心圆&#xff0c;每个同心圆叫做磁道&#xff0c;多个扇区组成同心圆。 我们可以把磁盘看做由无数个扇区构成的存储介质。 要把数据存到磁盘&#xff0c;先定位扇区&#xff0c;用哪一个磁头&#xff0c;…

【Javascript】内存泄漏

JavaScript 内存泄露指的是在程序中&#xff0c;不再使用的内存没有被正确释放&#xff0c;导致内存占用持续增加&#xff0c;最终引发性能问题甚至崩溃。 通常哪些操作会造成内存泄漏呢&#xff1f; 未使用 var 声明的全局变量&#xff1a;在 JavaScript 中&#xff0c;如果…

Java与JavaScript的区别与联系

Java是目前编程领域使用非常广泛的编程语言&#xff0c;相较于JavaScript&#xff0c;Java更被人们熟知。很多Java程序员想学门脚本语言&#xff0c;一看JavaScript和Java这么像&#xff0c;很有亲切感&#xff0c;那干脆就学它了&#xff0c;这也间接的帮助了JavaScript的发展…

【Py/Java/C++三种语言详解】LeetCode每日一题240215【二叉树BFS】LeetCode107、二叉树的层序遍历II

有LeetCode交流群/华为OD考试扣扣交流群可加&#xff1a;948025485 可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题 绿色聊天软件戳 od1336了解算法冲刺训练 文章目录 题目链接题目描述解题思路DFS和BFS异同用队列维护的BFS 代码PythonJavaC时空复杂度 相关习题华为OD算法/大…

Vue2学习第一天

Vue2 学习第一天 1. 什么是 vue? Vue 是一套用于构建用户界面的渐进式框架。 2. vue 历史 vue 是在 2013 年创建的&#xff0c;vue3 是 2020 出现的&#xff0c;现在主要是用 vue2&#xff0c;创新公司用的是 vue3 vue 的作者是尤雨溪&#xff0c;vue 的搜索热度比 react…

java的面向对象编程(oop)——认识泛型

前言&#xff1a; 打好基础&#xff0c;daydayup! 泛型 1&#xff0c;认识泛型&#xff1a; 定义类&#xff0c;接口&#xff0c;方法时&#xff0c;同时声明了一个或多个类型变量&#xff08;例&#xff1a;<E>&#xff09;,称为泛型&#xff0c;泛型接口&#xff0c;泛…

计算机网络——11EMail

EMail 电子邮件&#xff08;EMail&#xff09; 3个主要组成部分 用户代理邮件服务器简单邮件传输协议&#xff1a;SMTP 用户代理 又名“邮件阅读器”撰写、编辑和阅读邮件输入和输出邮件保存在服务器上 邮件服务器 邮箱中管理和维护发送给用户的邮件输出报文队列保持待发…

###51单片机学习(2)-----如何通过C语言运用延时函数设计LED流水灯

前言&#xff1a;感谢您的关注哦&#xff0c;我会持续更新编程相关知识&#xff0c;愿您在这里有所收获。如果有任何问题&#xff0c;欢迎沟通交流&#xff01;期待与您在学习编程的道路上共同进步。 目录 一. 延时函数的生成 1.通过延时计算器得到延时函数 2.可赋值改变…

2月14日作业

1.请编程实现二维数组的杨慧三角 代码&#xff1a; #include <stdio.h> #include <string.h> #include <stdlib.h> int main(int argc, const char *argv[]) {int n;printf("please enter n:");scanf("%d",&n);int arr[n][n];for(…

算法——数论——快速幂

目录 快速幂 费马小定理 一、试题 算法训练 A的B的C次方次方 快速幂 快速幂是一种用于快速计算幂运算的算法。计算复杂度 O(log n)基本思想是利用指数 n 的二进制展开形式&#xff0c;将 转化为多个 a 的幂的乘积&#xff0c;然后通过迭代快速计算。 快速幂的示例代码&…

Zabbix图形中文乱码问题(显示口口)解决办法

一 切换到zabbix安装目录assets/fonts下&#xff0c;下载字体 这里使用是nginxphp作为zabbix-web展示&#xff0c;使用find 命令查找 进入目录下&#xff0c;将原有字体备份&#xff0c;下载msyh字体 wget https://www.xxshell.com/download/sh/zabbix/ttf/msyh.ttf 二 修改配…

基于FPGA的UDP实现(包含源工程文件)

1、概括 前文通过FPGA实现了ARP和ICMP协议&#xff0c;ARP协议一般用来获取目的IP地址主机的MAC地址&#xff0c;ICMP通过回显请求和回显应答来判断以太网链路是否通畅&#xff0c;这两个协议都不是用来传输用户数据的。如果用户需要向PC端传输大量数据&#xff0c;那么就必须使…

嵌入式培训机构四个月实训课程笔记(完整版)-Linux ARM驱动编程第四天-ARM Linux编程之IIC与uart (物联技术666)

链接&#xff1a;https://pan.baidu.com/s/1V0E9IHSoLbpiWJsncmFgdA?pwd1688 提取码&#xff1a;1688 教学内容&#xff1a; 1、I2C总线&#xff1a; I2C&#xff08;Inter&#xff0d;Integrated Circuit),PHILIPS公司开发的两线式半双工同步串行总线&#xff1b;可以用来连…

RCS系统之:浅谈系统设计与开发

这是我在开发RCS系统中的一些个人感悟与心得&#xff0c;写出来与大家一起分享下。是想到什么写到什么&#xff0c;如果有什么不对的&#xff0c;欢迎大家一起探讨。 有些人喜欢把WMS系统下面的系统统称为RCS系统。 但我不是这么想的&#xff0c;我这里把WMS/ERP系统与AGV之间…

AtCoder Beginner Contest 332 --- E - Lucky bag --- 题解

目录 E - Lucky bag 题目大意&#xff1a; 思路解析&#xff1a; 代码实现&#xff1a; E - Lucky bag 题目大意&#xff1a; 思路解析&#xff1a; 在方差中平均值只与输入有关为定值。看到数据范围为 2 < D < N < 15&#xff0c;想到是否能使用状压dp来进行解答…