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。

相关文章

Node.js学习记录（二）

Node.js学习记录（二）

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件
阅读更多...
记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪（un-tracking）文件重新跟踪（re-tracking）文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法，现在我们已经有了一个仓库，并从这个仓
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
perl的学习记录——仿真regression

perl的学习记录——仿真regression

1 记录的背景 之前只知道有这个强大语言的存在，但一直侥幸自己应该不会用到它，所以一直没有开始学习。然而人生这么长，怎就确定自己不会用到呢？ 这次要搭建一个可以自动跑完所有case并且打印每个case的pass信息到指定的文件中。从而减轻手动跑仿真，手动查看log信息的重复无效低质量的操作。下面简单记录下自己的思路并贴出自己的代码，方便自己以后使用和修正。 2 思路整理 作为一个IC d
阅读更多...
GPU 计算 CMPS224 2021 学习笔记 02

GPU 计算 CMPS224 2021 学习笔记 02

并行类型 （1）任务并行 （2）数据并行 CPU & GPU CPU和GPU拥有相互独立的内存空间，需要在两者之间相互传输数据。 （1）分配GPU内存 （2）将CPU上的数据复制到GPU上 （3）在GPU上对数据进行计算操作 （4）将计算结果从GPU复制到CPU上 （5）释放GPU内存 CUDA内存管理API （1）分配内存 cudaErro
阅读更多...
SSM项目使用AOP技术进行日志记录

SSM项目使用AOP技术进行日志记录

本步骤只记录完成切面所需的必要代码 本人开发中遇到的问题： 切面一直切不进去，最后发现需要在springMVC的核心配置文件中中开启注解驱动才可以，只在spring的核心配置文件中开启是不会在web项目中生效的。 之后按照下面的代码进行配置，然后前端在访问controller层中的路径时即可观察到日志已经被正常记录到数据库，代码中有部分注释，看不懂的可以参照注释。接下来进入正题 1、导入m
阅读更多...
flume系列之：记录一次flume agent进程被异常oom kill -9的原因定位

flume系列之：记录一次flume agent进程被异常oom kill -9的原因定位

flume系列之：记录一次flume agent进程被异常oom kill -9的原因定位 一、背景二、定位问题三、解决方法 一、背景 flume系列之：定位flume没有关闭某个时间点生成的tmp文件的原因，并制定解决方案在博主上面这篇文章的基础上，在机器内存、cpu资源、flume agent资源都足够的情况下，flume agent又出现了tmp文件无法关闭的情况 二、
阅读更多...
2021-8-14 react笔记-2 创建组件 基本用法

2021-8-14 react笔记-2 创建组件 基本用法

1、目录解析 public中的index.html为入口文件 src目录中文件很乱，先整理文件夹。 新建components 放组件 新建assets放资源   ->/images      ->/css 把乱的文件放进去  修改App.js 根组件和index.js入口文件中的引入路径 2、新建组件 在components文件夹中新建[Name].js文件 //组件名首字母大写
阅读更多...
2021-08-14 react笔记-1 安装、环境搭建、创建项目

2021-08-14 react笔记-1 安装、环境搭建、创建项目

1、环境 1、安装nodejs 2.安装react脚手架工具 //  cnpm install -g create-react-app 全局安装 2、创建项目 create-react-app [项目名称] 3、运行项目 npm strat  //cd到项目文件夹    进入这个页面  代表运行成功  4、打包 npm run build
阅读更多...
Linux常用工具与命令日常记录（长期更新）

Linux常用工具与命令日常记录（长期更新）

Linux常用工具与命令日常记录（长期更新） 目录 1.本地复制到远程2.Linux压缩拆包与解压3.生成随机密码4.ubuntu默认Python版本设置5.计算当前文件夹中文件数量6.windows中编写shell脚本，在Linux运行出错7.history 历史命令显示时间用户8.Ubuntu18.04设置源、网卡9.Ubuntu18.04设置网卡10.Ubuntu：自定义开
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2