2023年广东省程序设计大赛

devtools/2024/9/22 18:32:21/

C

双指针,排序

买便宜的,用最贵的卖出

#include<bits/stdc++.h>using namespace std;
#define int long long
const int N = 2e5 + 10;
int n,m;
int re[2]={1,4};
int bl[4]={2,3,5,6};
int f;
struct node
{int x,y;
}a[N];
bool cmp(node W,node Q)
{return W.x<Q.x;
}
void solve()
{cin>>n;for(int i=1;i<=n;i++){
//		cin>>a[i].x>>a[i].y;scanf("%d%d",&a[i].x,&a[i].y);}sort(a+1,a+n+1,cmp);int ans=0;int l=1,r=n;while(l<r){int k=min(a[l].y,a[r].y);ans+=k*(a[r].x-a[l].x);a[r].y-=k;a[l].y-=k;if(a[r].y==0) r--;if(a[l].y==0) l++;}cout<<ans<<endl;
}
signed main()
{int T;cin>>T;while(T--)solve();return 0;
} 

K

爆搜+回溯 

#include<bits/stdc++.h>using namespace std;
#define int long long
const int N = 2e5 + 10;
int n,m,k;
int a[30][30];
int f[][2]={{0,2},{0,-2},{2,0},{-2,0}};
int ff[][2]={{0,1},{0,-1},{1,0},{-1,0}};
int minn=6;
void dfs(int c)
{minn=min(minn,c);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]){for(int k=0;k<4;k++){int dx=i+f[k][0],dy=j+f[k][1];int tx=i+ff[k][0],ty=j+ff[k][1];if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&a[tx][ty]==1&&a[dx][dy]==0){a[i][j]=0;a[dx][dy]=1;a[tx][ty]=0;dfs(c-1);a[i][j]=1;a[dx][dy]=0;a[tx][ty]=1;						}}}}}
}
void solve()
{memset(a,0,sizeof a);minn=6;cin>>n>>m>>k;for(int i=1;i<=k;i++)	{int x,y;cin>>x>>y;a[x][y]=1;}dfs(k);cout<<minn<<endl;
}
signed main()
{int T;cin>>T;while(T--)solve();return 0;
} 

注意python中global的运用 

f = [[0, 2], [0, -2], [2, 0], [-2, 0]]
ff = [[0, 1], [0, -1], [1, 0], [-1, 0]]def dfs(c):global minn  # 声明使用全局变量minn = min(minn, c)for i in range(1, n + 1):for j in range(1, m + 1):if a[i][j] == 1:for k in range(4):dx, dy = i + f[k][0], j + f[k][1]tx, ty = i + ff[k][0], j + ff[k][1]if dx >= 1 and dx <= n and dy >= 1 and dy <= m and a[tx][ty] == 1 and a[dx][dy] == 0:a[i][j] = 0a[dx][dy] = 1a[tx][ty] = 0dfs(c - 1)a[i][j] = 1a[dx][dy] = 0a[tx][ty] = 1T = int(input())while T:T -= 1n, m, k = map(int, input().split())a = [[0 for _ in range(m + 1)] for _ in range(n + 1)]global minnminn = 6  # 重置 min 值for _ in range(k):x, y = map(int, input().split())a[x][y] = 1dfs(k)print(minn)

枚举所有邻居的数量和不是邻居的数量

假设有k个邻居,那么剩余的n-k个邻居需要2*(n-k),所以房子的个数需要大于等于2*(n-k)+k

没有只有1个邻居的可能,还有一种可能就是所有人都没有邻居,那么需要的房子数量是2*n-1

所有可能取最大值

#include<bits/stdc++.h>using namespace std;#define int long long
const int N = 5e5 + 10;
int n,m,k;
struct  node
{int x,y;
}a[N];
int sum[N];
bool cmp(node W,node E)
{return W.x-W.y>E.x-E.y;
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i].y;int ans=a[1].x;int res=0;for(int i=2;i<=n;i++){ans+=a[i].x;if(2*n-i<=m){res=max(res,ans+sum[n]-sum[i]);}}if(2*n-1<=m){res=max(res,sum[n]);}cout<<res<<endl;
}
signed main()
{int T;cin>>T;while(T--)solve();return 0;
} 

I

二分答案

对于不需要在图上操作的,尤其是,n*m数组太大的情况,可以使用i*m+j来存储每个点的值,

check(x)

只需要看整个图中比x小的数的坐标,只要这些小的数构成的路径满足题意(只能往右往下走)

(怎么样判断是否满足,一行一行遍历,并记录上一个点的列坐标,如果当前点的纵坐标小于上一个点的列坐标,则不满足题意,因为,当小于上一个点的列坐标,从上一个点走向当前点,上一个点只能往左走,才能走到当前点)

对于路径上其他大于x的点,不管怎么排列,x一定可以满足是这条路径最大的mex(x)

#include<bits/stdc++.h>using namespace std;#define int long long
const int N = 2e6 + 10;
int n,m,k;
int a[N];
int check(int x)
{int last=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i*m+j]<x){if(j<last) return 0;last=j;}}}return 1;
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int x;cin>>x;a[i*m+j]=x;} }int l=0,r=n*m;while(l<r){int mid=(l+r+1)>>1;if(check(mid)) l=mid;elser=mid-1;} cout<<r<<endl;
}
signed main()
{int T;cin>>T;while(T--)solve();return 0;
} 


http://www.ppmy.cn/devtools/43278.html

相关文章

TCP 连接排故:使用 BPF BCC工具包进行网络跟踪

写在前面 博文内容为 BCC 进行网络跟踪常见工具介绍tcpconnect:主动的 TCP 连接跟踪tcpaccept:被动的 TCP 连接跟踪tcpretrans:重传的 TCP 连接跟踪tcptracer:已建立的 TCP 连接跟踪tcpconnlat:测量出站 TCP 连接的延迟tcpdrop:被内核丢弃的 TCP 数据包跟踪tcplife: TCP 会话追…

单片机的内存映射和重映射

内存映射 在单片机内&#xff0c;不管是RAM还是ROM还是寄存器&#xff0c;他们都是真实存在的物理存储器&#xff0c;为了方便操作&#xff0c;单片机会给每一个存储单元分配地址&#xff0c;这就叫做内存映射。 单片机的内存映射是指将外部设备或外部存储器映射到单片…

数据赋能(101)——概念:数据治理、数据管理

此文为本人学习与提高能力的笔记。 数据治理与数据管理这两个术语&#xff0c;尽管在数据管理的领域中经常相伴出现&#xff0c;且在某些情境下可能被视为具有相似的语义范畴&#xff0c;但为了确保术语使用的精准度和专业性&#xff0c;我们必须对它们有更为深入的认知。我们…

【sass插值语句 #{}简介以及使用方法】

Sass 中的插值&#xff08;Interpolation&#xff09;是一种强大的特性&#xff0c;它允许你在 Sass 代码中嵌入变量、选择器、属性名或任何其他 Sass 表达式&#xff0c;并动态地生成 CSS 代码。插值通过 #{} 语法来实现。 Sass 插值简介 Sass 插值允许你创建可动态生成内容…

URI 和URL以及URN的区别

URI 和URL以及URN的区别 URL&#xff0c;URI&#xff0c;URN的关系 URN和URL都是URI中的一种 URI 统一资源标识符 URL 统一资源定位符 URN 统一资源名称 URL 统一资源标识符 用于表示某一互联网资源名称的字符串&#xff0c;该种标识允许用户对任何的资源通过特定的协议进…

C++基础——vector的详解与运用

vector的介绍 文档介绍 vector是表示可变大小数组的序列容器。就像数组一样&#xff0c;vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问&#xff0c;和数组一样高效。但是又不像数组&#xff0c;它的大小是可以动态改变的&#xff0c;…

电路仿真软件:点亮教学新篇章,十大便利助力高效学习

在信息化时代的浪潮中&#xff0c;电路仿真软件以其独特的优势&#xff0c;逐渐在教学领域崭露头角。它不仅能够帮助学生更好地理解电路知识&#xff0c;还能提升教师的教学效果。接下来&#xff0c;让我们一起探讨电路仿真软件对教学带来的十大便利。 一、直观展示电路原理 电…

使用 Effect 同步-09

有些组件需要与外部系统同步。例如&#xff0c;你可能希望根据 React state 控制非 React 组件、设置服务器连接或在组件出现在屏幕上时发送分析日志。Effects 会在渲染后运行一些代码&#xff0c;以便可以将组件与 React 之外的某些系统同步。 简单理解&#xff0c;就是需要操…