2021杭电多校3补题记录

2024-03-29 08:58
文章标签 记录 2021 补题 杭电多校

本文主要是介绍2021杭电多校3补题记录，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

总结

签到太慢太慢太慢
记忆化搜索写炸了，1h半龟速签到。
一个裸的前缀和写好久，全队缺乏数据结构知识
一个思维倒推想不到，麻了

1004 题意

有好多条线段，alice选k条，之后bob画一条，有几个交点扣几分。alice想最大化，bob想最小化，给出线段，输出k为1到n时分数

1004 思路

k=n时，alice全选，那么bob的扣分就是n-出现次数最多的斜率出现数。之后考虑倒推，显然alice要不画当前斜率出现最多的一条边最优，所以统计线段斜率，用个优先队列倒着推就行，nlogn。

1004 代码
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define online_judge
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, x, y) for (auto i = (x); i != (y + 1); ++i)
#define dep(i, x, y) for (auto i = (x); i != (y - 1); --i)
#define debug(x) cout << "debug: " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;double func(int x0, int y0, int x1, int y1) {if (x0 == x1) return inf;return 1.0 * (y1 - y0) / (x1 - x0);
}
unordered_map<double, int> mp;
void test_case() {int n;cin >> n;mp.clear();for (int i = 1; i <= n; ++i) {int x0, y0, x1, y1;cin >> x0 >> y0 >> x1 >> y1;++mp[func(x0, y0, x1, y1)];//   cout<<func(x0, y0, x1, y1)<<endl;}//cout<<"----------"<<endl;vector<int>ans;priority_queue<int>q;for(auto p:mp){q.push(p.second);}for(int i=n;i;i--){int t=q.top();q.pop();ans.push_back(i-t);q.push(t-1);}reverse(ans.begin(),ans.end());for(int i=0;i<n;i++)cout<<ans[i]<<endl;
}signed main() {ios::sync_with_stdio(false), cin.tie(0);
#ifndef online_judgefreopen("IO\\in.txt", "r", stdin);freopen("IO\\out.txt", "w", stdout);clock_t start, end;start = clock();
#endifint _;cin >> _;for (int i = 1; i <= _; ++i) test_case();
#ifndef online_judgeend = clock();cout << endl<< "Runtime: " << (double)(end - start) / CLOCKS_PER_SEC << "s\n";
#endifreturn 0;
}
1007 题意

n个颜色，有自己的颜色混合类型和rgb三个值，每次问lr区间颜色混合最后结果。类型为1代表覆盖，新颜色会覆盖旧颜色，2代表加和，新颜色的rgb是两个颜色的和与255取min。

1007 思路

对于lr，我们至于要找出区间内最靠右的1型位置pos，之后求一下pos到r的区间合，之后与255取min输出即可。
找出pos可以On预处理，这里用了st表，属于大材小用了。之后区间和是前缀和处理的。

1007 代码
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=400505;const int inf=0x3f3f3f3f;int sum[maxn][3];int ST[maxn][20];int arr[maxn];int logn[maxn];int n,m;string s;int ver[maxn];int r[maxn],g[maxn],b[maxn];inline char tran(int c){if (c==10) return 'A';if (c==11) return 'B';if (c==12) return 'C';if (c==13) return 'D';if (c==14) return 'E';if (c==15) return 'F';return c+'0';}inline void print(int x){if (x>255) x=255;int u=x/16,v=x%16;cout<<tran(u)<<tran(v);}inline int trans(int c){if (c=='A') return 10;if (c=='B') return 11;if (c=='C') return 12;if (c=='D') return 13;if (c=='E') return 14;if (c=='F') return 15;return c-'0';}void preST(int len){      for(int i=1;i<=len;i++)ST[i][0]=arr[i];int t=logn[len]+1;for(int j=1;j<t;j++)for(int i=1;i<=len-(1<<j)+1;i++)ST[i][j]=max(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);}int query(int l,int r){int k=logn[r-l+1];return max(ST[l][k],ST[r-(1<<k)+1][k]);}void solve(){cin>>n>>m;sum[0][0]=sum[0][1]=sum[0][2]=0;for (int i=1;i<=n;i++){cin>>ver[i];cin>>s;r[i]=trans(s[0])*16+trans(s[1]);g[i]=trans(s[2])*16+trans(s[3]);b[i]=trans(s[4])*16+trans(s[5]);sum[i][0]=sum[i-1][0]+r[i];sum[i][1]=sum[i-1][1]+g[i];sum[i][2]=sum[i-1][2]+b[i];}for(int i=1;i<=n;i++){if(ver[i]==1)   arr[i]=i;else            arr[i]=0;}preST(n);for(int i=1;i<=m;i++){int l,r;cin>>l>>r;int p=max(query(l,r),l);print(sum[r][0]-sum[p-1][0]);print(sum[r][1]-sum[p-1][1]);print(sum[r][2]-sum[p-1][2]);cout<<endl;}//cout<<"-----------------------"<<endl;}signed main(){IOS#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out.txt","w",stdout);#endifint tn=1;cin>>tn;logn[1]=0;for(int i=2;i<maxn;i++)logn[i]=logn[i/2]+1;while(tn--){solve();}}
1010 题意

一张图，每条边有原价和折扣价。输出使用1,2,3,4.。。条折扣边的最小生成树

1010 思路

拆边成黑白二色，变成了选择k条黑色边的最小生成树。这个刚写了博客了，是二分。现在要输出全部1-n的答案，考虑枚举所有边权预处理，之后每个去扫就行了。这里注意要提前跑一下纯黑边和纯白边的生成树，非树边直接舍弃，这个不知道是怎么证的，就这样吧…

1010 代码
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=400505;const int inf=0x3f3f3f3f;int n,m,k;struct Edge{int u,v,w;}e1[maxn],e2[maxn];int cost[maxn],need[maxn];bool cmp(Edge a,Edge b){return a.w<b.w;}int fa[maxn];int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}bool unite(int x,int y){x=find(x),y=find(y);if(x==y)    return 0;fa[x]=y;return 1;} void reduce(Edge *e){sort(e+1,e+1+m,cmp);for(int i=0;i<=n;i++)   fa[i]=i;int c=0;for(int i=1;i<=m;i++){if(unite(e[i].u,e[i].v)){e[++c]=e[i];}}//for(int i=1;i<=c;i++)//    cout<<e[i].u<<' '<<e[i].v<<' '<<e[i].w<<endl;}int out(int x){for(int i=0;i<=2000;i++){if(need[i]<=x)return cost[i]-x*(i-1000);}}void solve(){cin>>n>>m;for(int i=1;i<=m;i++){cin>>e1[i].u>>e1[i].v>>e1[i].w>>e2[i].w;e2[i].u=e1[i].u,e2[i].v=e1[i].v;}reduce(e1),reduce(e2);for(int i=-1000;i<=1000;i++){for(int j=1;j<=n;j++)   fa[j]=j;int A=1,B=1,sum=0,cnt=0;while(A<n&&B<n){if(e1[A].w<=e2[B].w+i){if(unite(e1[A].u,e1[A].v))sum+=e1[A].w;A++;}else{if(unite(e2[B].u,e2[B].v))sum+=e2[B].w+i,cnt++;B++;}}while(A<n){if(unite(e1[A].u,e1[A].v))sum+=e1[A].w;A++;}while(B<n){if(unite(e2[B].u,e2[B].v))sum+=e2[B].w+i,cnt++;B++;}need[i+1000]=cnt;cost[i+1000]=sum;}for(int i=0;i<n;i++)cout<<out(i)<<endl;}signed main(){IOS#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out1.txt","w",stdout);#endifint tn=1;cin>>tn;while(tn--){solve();}}
1011 题意

给出n，k求1-n的线段树，在节点比k小时不再分裂，共要开多少个点

1011 思路

记忆化搜索

1011 代码
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=400505;const int inf=0x3f3f3f3f;int n,m,k;map<int,int>mp;int fun(int len){if(len<=k)  return 1;if(mp[len]) return mp[len];int rec=0;if(len&1)rec+=fun(len/2)+fun(len/2+1);elserec+=2*fun(len/2);return mp[len]=rec+1;}void solve(){cin>>n>>k;mp.clear();cout<<fun(n)<<endl;}signed main(){IOS#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out.txt","w",stdout);#endifint tn=1;cin>>tn;while(tn--){solve();}}
1009 题意

n*n方格左上走到右下，每个格子都可获得新钻石并永久提升所有钻石价格，终点卖出所有宝石，数据随机，问最大收益

E 思路

我们用dpijk代表i，j位置拿了k个宝石的最大收益。显然如果ij确定后，我们可以比较两个状态的优劣。如果状态a的k和收益全大于状态b的k和收益，那么a一定优于b。所以我们开一个三维数组dp，每个dpij对应一个存pair<int,int>的vector，就是维护一个位置的不同k和收益的列表。我们考虑合并，只有ij都大于1时涉及合并，合并时我们保存有效状态即可。因为是随机数据，所以状态不会特别多。

E 代码
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=105;const int inf=0x3f3f3f3f;int n,m,k;int mp1[maxn][maxn],mp2[maxn][maxn];vector<pair<int,int>>dp[maxn][maxn];pair<int,int>buf[2000005];int cnt;void inse(pair<int,int> p){while(cnt&&buf[cnt].second<=p.second)    cnt--;// if(!m||buf[cnt].first>p.first)buf[++cnt]=p;}void unite(vector<pair<int,int>> &to,const vector<pair<int,int>> &f1,const vector<pair<int,int>>&f2){int s1=f1.size(),s2=f2.size();int p1=0,p2=0;cnt=0;while(p1<s1&&p2<s2){if(f1[p1].first<f2[p2].first){inse(f1[p1++]);}else{inse(f2[p2++]);}}while(p1<s1){inse(f1[p1++]);}while(p2<s2){inse(f2[p2++]);}for(int i=1;i<=cnt;i++)to.emplace_back(buf[i]);//to.resize(cnt);//for(int i=1;i<=cnt;i++)//  to[i-1]=buf[i];}void solve(){cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&mp1[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&mp2[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)   dp[i][j].clear();dp[1][1].resize(1);dp[1][1][0]={mp1[1][1],mp2[1][1]};for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==1&&j==1)  continue;if(i==1){dp[i][j]=dp[i][j-1];}else if(j==1){dp[i][j]=dp[i-1][j];}else{unite(dp[i][j],dp[i-1][j],dp[i][j-1]);}for(auto &p:dp[i][j]){p.first+=mp1[i][j];p.second+=mp2[i][j];}}}ll ans=0;for(auto p:dp[n][n])ans=max(ans,1ll*p.first*p.second);printf("%lld\n",ans);}signed main(){#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out.txt","w",stdout);#endifint tn=1;scanf("%d",&tn);while(tn--){solve();}}

未完待续

这篇关于2021杭电多校3补题记录的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/858165。

相关文章

Python获取中国节假日数据记录入JSON文件

Python获取中国节假日数据记录入JSON文件

《Python获取中国节假日数据记录入JSON文件》项目系统内置的日历应用为了提升用户体验,特别设置了在调休日期显示“休”的UI图标功能,那么问题是这些调休数据从哪里来呢？我尝试一种更为智能的方法：P... 目录节假日数据获取存入jsON文件节假日数据读取封装完整代码项目系统内置的日历应用为了提升用户体验，
阅读更多...
Spring Boot 配置文件之类型、加载顺序与最佳实践记录

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio
阅读更多...
MySQL INSERT语句实现当记录不存在时插入的几种方法

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面：本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE
阅读更多...
Python 中的异步与同步深度解析(实践记录)

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步：深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步
阅读更多...
Python Dash框架在数据可视化仪表板中的应用与实践记录

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash？1.1
阅读更多...
Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

《SpringBoot中定时任务Cron表达式的终极指南最佳实践记录》本文详细介绍了SpringBoot中定时任务的实现方法,特别是Cron表达式的使用技巧和高级用法,从基础语法到复杂场景,从快速启... 目录一、Cron表达式基础1.1 Cron表达式结构1.2 核心语法规则二、Spring Boot中定
阅读更多...
国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)

国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)

《国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)》本文给大家利用deepseek模型搭建私有知识问答库的详细步骤和遇到的问题及解决办法,感兴趣的朋友一起看看吧... 目录1. 第1步大家在安装完ollama后，需要到系统环境变量中添加两个变量2. 第3步 “在cmd中
阅读更多...
Spring Retry 实现乐观锁重试实践记录

Spring Retry 实现乐观锁重试实践记录

《SpringRetry实现乐观锁重试实践记录》本文介绍了在秒杀商品SKU表中使用乐观锁和MybatisPlus配置乐观锁的方法,并分析了测试环境和生产环境的隔离级别对乐观锁的影响,通过简单验证,... 目录一、场景分析 二、简单验证 2.1、可重复读 2.2、读已提交 三、最佳实践 3.1、配置重试模板
阅读更多...
在 Spring Boot 中使用异步线程时的 HttpServletRequest 复用问题记录

在 Spring Boot 中使用异步线程时的 HttpServletRequest 复用问题记录

《在SpringBoot中使用异步线程时的HttpServletRequest复用问题记录》文章讨论了在SpringBoot中使用异步线程时,由于HttpServletRequest复用导致... 目录一、问题描述：异步线程操作导致请求复用时 Cookie 解析失败1. 场景背景2. 问题根源二、问题详细分
阅读更多...
关于Spring @Bean 相同加载顺序不同结果不同的问题记录

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2