The 1st Universal Cup Stage 12: ̄Ookayama, April 15-16, 2023 题解

news/2024/5/19 22:03:02/

A XOR Tree Path

给一颗树,树上点有黑白两色,每次可以选一个叶子节点,翻转其到根路径上所有点的颜色,问最大黑色点数。
树dp

#include<bits/stdc++.h> 
using namespace std;
#define MAXN (100000+10)
#define ll long long
#define F (100000000)
#define Rep(i,n) for(int i=0;i<n;i++)
#define next Next
int n,edge[MAXN*2],pre[MAXN],next[MAXN*2],Size=0;
int f[MAXN][2];
int a[MAXN];
int g[2];
void addedge(int u,int v)
{edge[++Size]=v;next[Size]=pre[u];pre[u]=Size;
}
void dfs(int x,int father)
{bool lef=1;int g[2];for (int p=pre[x];p;p=next[p]){int &v=edge[p];if (v!=father){dfs(v,x);if(lef) {f[x][0]=g[0]=f[v][0];f[x][1]=g[1]=f[v][1];lef=0;}else {f[x][0]=max(g[0]+f[v][0],g[1]+f[v][1]);f[x][1]=max(g[1]+f[v][0],g[0]+f[v][1]);g[0]=f[x][0],g[1]=f[x][1];}}}	if(lef) f[x][0]=a[x],f[x][1]=a[x]^1;else f[x][0]+=a[x],f[x][1]+=a[x]^1;
}
int main()
{
//	freopen("a.in","r",stdin);scanf("%d",&n);memset(pre,0,sizeof(pre));memset(next,0,sizeof(next));for(int i=1;i<=n;i++) cin>>a[i];for (int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}dfs(1,0);	cout<<max(f[1][0],f[1][1]);return 0;
}

B Magical Wallet

You have a magical wallet with X yen in it. (Yen is the currency of Japan.)
Using the magic on this wallet, you can rearrange the amount of money in the wallet as a decimal string
in any order you like. For example, if you have a magical wallet with 120 yen, you can use magic to change
the amount of money in the wallet to any of the following: 12 yen, 21 yen, 102 yen, 120 yen, 201 yen, or
210 yen (leading zeros are ignored).
You will now visit N shops with the magical wallet in order. At the i-th shop (1 ≤ i ≤ N ), a product
costing Ai yen is sold, and if the magical wallet contains at least Ai yen, you can pay Ai yen from the
magical wallet to buy the product.
You can use magic as much as you like whenever you want. How many products can you buy at most?

直接暴力模拟过程

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
vi get(int x) {stringstream ss;ss<<x;char s[6];ss>>s;int m=strlen(s);vi v;sort(s,s+m);do{stringstream ss;ss<<s;int p;ss>>p;v.pb(p);
//		cout<<p<<" ";}while(next_permutation(s,s+m));return v;
}
#define MAXX (10000+10)
int f[101][MAXX];
vi v[MAXX];
int main()
{
//	freopen("B.in","r",stdin);
//	freopen(".out","w",stdout);int n,x;Rep(i,1e4) {v[i]=get(i);}
//	Rep(i,20) {
//		for(int j:v[i]) cout<<j<<' ';cout<<endl;
//	}cin>>n>>x;get(x);MEMi(f)for(int i:v[x])f[0][i]=0;Rep(i,n) {int cx=read();Rep(j,10000)gmax(f[i+1][j],f[i][j])Rep(j,10000) {if(f[i][j]>=0 && j>=cx) {for(int k:v[j-cx])gmax(f[i+1][k],f[i][j]+1)}}} int t=0;Rep(j,10000) gmax(t,f[n][j])cout<<t<<endl;	return 0;
}

E Five Med Sum

在这里插入图片描述
枚举中位数,注意可以事先给A-E数组定个顺序,以防算重。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (998244353)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \For(j,m-1) cout<<a[i][j]<<' ';\cout<<a[i][m]<<endl; \} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f;
} 
//class node{
//	int x,t;
//	bool friend operator<(node a,node b) {
//		if(a.x<b.x)
//	}
//};
vector<pair<int,int > > v[5];
int main()
{
//	freopen("E.in","r",stdin);
//	freopen(".out","w",stdout);int n=read();Rep(j,5) {For(i,n) v[j].pb(mp(read(),j) );sort(ALL(v[j]));}ll ans=0;Rep(j,5) {Rep(i,n) {int p=v[j][i].fi;vi L,R;Rep(k,5) if(k^j) {int l=lower_bound(ALL(v[k]),v[j][i])-v[k].begin();int r=v[k].end()-lower_bound(ALL(v[k]),v[j][i]);L.pb(l),R.pb(r);}Rep(p1,3) Fork(p2,p1+1,3) {ll c=mul(L[p1],L[p2]);Rep(t,4) if(t!=p1 && t!=p2) c=mul(c,R[t]);upd(ans,mul(c,p));}}}cout<<ans;return 0;
}

http://www.ppmy.cn/news/46942.html

相关文章

【社区图书馆】启迪后人——GPT 与读书的奇妙之旅

随着科技的发展和人工智能的不断进步&#xff0c;我们的阅读方式也在逐渐改变。作为一个热爱读书的人&#xff0c;我深感好奇与惊讶地发现&#xff0c;GPT&#xff08;即生成预训练 Transformer&#xff09;正以前所未有的方式拓展我们的阅读视野。在这篇博客中&#xff0c;我将…

RabbitMQ-整合mqtt

用 springboot rabbitmq可以搭建物联网&#xff08;IOT&#xff09;平台&#xff0c;rabbitmq 不是消息队列吗&#xff0c;原来rabbitmq有两种协议&#xff0c;消息队列是用的AMQP协议&#xff0c;而用在智能硬件中的是MQTT协议。 一、rabbitmq是什么&#xff1f; RabbitMQ就…

Windows 自带环境变量

目录 Windows自带环境变量说明Windows自带环境变量总结 所谓 Windows 环境变量&#xff0c;指的是 Windows 指定操作系统工作环境的一些设置选项或属性参数&#xff0c;比方说指定系统文件夹或临时文件夹的位置等。与常量相比&#xff0c;一个环境变量往往由变量名称和变量值组…

MySQL全局锁、表级锁、行级锁介绍演示(详细)

目录 介绍 分类 1、全局锁 1.1介绍 1.2场景 1.3语法 1.4演示 2、表级锁 2.1介绍 2.2分类 2.3语法 2.4演示 3、行级锁 3.1介绍 3.2分类 3.3场景 介绍 锁是计算机协调多个进程或线程并发访问某一资源的机制。在数据库中&#xff0c;除传统的计算资源&#xff08;…

详解语义分割deeplabv3+模型的工业应用流程

来源&#xff1a;投稿 作者&#xff1a;某一个名字 编辑&#xff1a;学姐 导语 在工业视觉应用中&#xff0c;目标检测算法常用于特征的粗定位&#xff0c;而语义分割则在特征的精定位方面有着突出的表现。使用较多的语义分割模型主要有FCN、deeplab系列、unet等&#xff0c;根…

android framework-PackageManagerService(PKMS)包管理服务

一、概述 Android系统启动过程中&#xff0c;会启动一个包管理服务PackageManagerService(PKMS)&#xff0c;这个服务主要负责扫描系统中指定目录&#xff0c;找出里面以apk结尾的文件&#xff0c;通过对这些文件进行解析&#xff0c;得到应用程序的所有信息并完成应用程序的安…

【AI生产力工具】ChatPDF:将 PDF 文档转化为交互式阅读体验的利器

文章目录 简介一、ChatPDF 是什么&#xff1f;二、ChatPDF 的优势三、ChatPDF 的应用场景四、如何使用 ChatPDF&#xff1f;五、结语 简介 随着数字化时代的发展&#xff0c;PDF 文件已经成为了日常工作和学习中不可或缺的一部分。然而&#xff0c;仅仅将 PDF 文件上传或下载并…

【排序】快速排序(递归和非递归)

快速排序 前言图解大致思路对于hoare版本对于挖坑法对于前后指针法 实现方法递归非递归 快排的优化&#xff08;基于递归的优化&#xff09;三数取中法小区间优化 时间复杂度和空间复杂度 前言 快速排序&#xff0c;听名字就比较霸道&#xff0c;效率根名字一样&#xff0c;非…

理解C语言中的空指针和野指针

在C语言中&#xff0c;指针是一个非常重要的概念&#xff0c;可以用于操作变量和数据结构。但是&#xff0c;指针也是很容易出错的地方。其中包括两种可能的错误&#xff1a;空指针和野指针。 空指针 空指针指代无效的地址&#xff0c;表示指针不指向内存中的任何一个合法对象…

深入剖析:如何优化Android应用的性能和内存管理

深入剖析&#xff1a;如何优化Android应用的性能和内存管理 性能和内存管理的重要性 在今天的移动应用开发中&#xff0c;用户对于应用的性能和体验要求越来越高。一款性能卓越的Android应用能够提供流畅的操作体验、快速的响应速度以及较低的资源消耗&#xff0c;从而提高用户…

Android 11.0 设置默认DNS

1.前言 在11.0的系统rom产品定制化开发中,由于是wifi产品的定制,需要对wifi功能要求比较高,所以在wifi需求方面要求设置默认的dns功能,这就需要分析网络通讯 流程,然后在联网之后,设置默认的dns,来实现功能要求 2.设置默认DNS的核心类 frameworks\base\core\java\andr…

深入探索 Qt6 web模块 WebEngineCore:从基础原理到高级应用与技巧

深入探索 Qt WebEngineCore&#xff1a;从基础原理到高级应用与技巧 Diving into Qt WebEngineCore: From Basic Principles to Advanced Applications and Techniques 一、Qt WebEngineCore 模块简介及原理 (Introduction and Principles of Qt WebEngineCore Module)Qt WebEn…

使用layui组件库制作进度条

使用layui组件库制作进度条 html代码 <!DOCTYPE html> <html> <head><meta charset"UTF-8"><title>Example</title><!-- 引入 layui 的 CSS 文件 --><link rel"stylesheet" href"https://cdn.staticfil…

WordPress图片水印插件 Easy Watermark

1、概述 WordPress图片水印插件Easy Watermark 是一款实现上传图片自动添加水印LOGO功能的高效插件。当我们在WordPress网站后台上传图片文件到媒体库时&#xff0c;或者在发布文章上传图片时&#xff0c;Easy Watermark 都能为图片自动添加水印&#xff0c;同时&#xff0c;还…

查询练习:连接查询

准备用于测试连接查询的数据&#xff1a; CREATE DATABASE testJoin;CREATE TABLE person (id INT,name VARCHAR(20),cardId INT );CREATE TABLE card (id INT,name VARCHAR(20) );INSERT INTO card VALUES (1, 饭卡), (2, 建行卡), (3, 农行卡), (4, 工商卡), (5, 邮政卡); S…

杨志丰:一文详解,什么是单机分布式一体化?

欢迎访问 OceanBase 官网获取更多信息&#xff1a;https://www.oceanbase.com/ 3 月 25 日&#xff0c;第一届 OceanBase 开发者大会在北京举行&#xff0c;OceanBase 首席架构师杨志丰&#xff08;花名&#xff1a;竹翁&#xff09;带来了 《OceanBase 的单机分布式一体化》 的…

IPSEC VPN动态配置(示例)

用的锐捷设备。 ipsec加密图用于对外接口上。 IPsec 使用IPSec对本部到各分部的数据流进行加密。要求使用动态隧道主模式&#xff0c;安全协议采用esp协议&#xff0c;加密算法采用3des&#xff0c;认证算法采用md5&#xff0c;以IKE方式建立IPsec SA。在R1上配置ipsec加密转…

神器集合!这12个免费工具可以让您的工作更高效

好的工具&#xff0c;能够帮助我们更高效地完成工作&#xff0c;节省时间和精力; 节省出更多的摸鱼时间&#xff01; 本文将介绍 12 款绝佳的免费效率工具&#xff0c;这些工具可以让你事半功倍&#xff0c;提高工作效率。无论你是一名程序员、设计师、学生还是白领&#xff0c…

插件化换肤原理—— 布局加载过程、View创建流程、Resources 浅析

作者&#xff1a;孙先森Blog 本文主要分析了 Android 布局加载流程 分析 一般的换肤功能大概是这样的&#xff1a;在 App 的皮肤商城内下载“皮肤包”&#xff0c;下载完成后点击更换界面上的 View 相关资源&#xff08;颜色、样式、图片、背景等&#xff09;发生改变&#xf…

2023年全国最新道路运输从业人员精选真题及答案59

百分百题库提供道路运输安全员考试试题、道路运输从业人员考试预测题、道路安全员考试真题、道路运输从业人员证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 79.道路交通事故自发生之日起&#xff08;&#xff09;日内&…