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

news/2024/10/23 5:33:29/

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 与读书的奇妙之旅

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

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

RabbitMQ-整合mqtt

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

Windows 自带环境变量

目录 Windows自带环境变量说明Windows自带环境变量总结 所谓 Windows 环境变量&#xff0c;指的是 Windows 指定操作系统工作环境的一些设置选项或属性参数&#xff0c;比方说指定系统文件夹或临时文件夹的位置等。与常量相比&#xff0c;一个环境变量往往由变量名称和变量值组…
阅读更多...
MySQL全局锁、表级锁、行级锁介绍演示（详细）

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+模型的工业应用流程

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

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

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

一、概述 Android系统启动过程中&#xff0c;会启动一个包管理服务PackageManagerService(PKMS)&#xff0c;这个服务主要负责扫描系统中指定目录&#xff0c;找出里面以apk结尾的文件&#xff0c;通过对这些文件进行解析&#xff0c;得到应用程序的所有信息并完成应用程序的安…
阅读更多...
【AI生产力工具】ChatPDF：将 PDF 文档转化为交互式阅读体验的利器

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

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

【排序】快速排序（递归和非递归）

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

Copyright @ 2022~2023