2021杭电多校4补题记录

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

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

总结

lls不在的第一天，想他
数学我** 你个 **

1001 题意

fx是一个由c，cx，c/x,csinx,ccosx,c/sinx,c/cosx,c^x由加号拼接的函数，对他求前缀和一样的东西得到sx，给你fx，问sx是否收敛

1001 思路

高数下练习题
sx收敛，则fx趋0，由高数知识知这些都不趋0，只有常数C均为0时才成立。

1001 代码
#include<stack>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<deque>
#include<vector>
#include<iostream>
#include<map>
#include<set>
#include<iomanip>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
using namespace std;
ll GCD(ll a,ll b){while(b^=a^=b^=a%=b);return a;}
const int inf=0x3f3f3f3f;
string s;
int T;
bool boo;
signed main() 
{#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out.txt","w",stdout);clock_t start, end;start = clock();#endifIOScin>>T;while (T--){cin>>s;boo=false;for (int i=0;i<s.length();i++)if (s[i]>'0'&&s[i]<='9') boo=true;if (boo) cout<<"NO"<<endl;else cout<<"YES"<<endl;}#ifndef ONLINE_JUDGEend = clock();cout << endl << "Runtime: " << (double)(end - start) / CLOCKS_PER_SEC << "s\n";#endif
}
1002 题意

一颗树，点带权，aij代表i到j路径上不同点权数，需输出所有aij和一个奇怪东西的乘积加和

1002 思路

可以n²跑，暴力就完事了。

1002 代码
#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=2505;const int inf=0x3f3f3f3f;const int mod1=1e9+7;const int mod2=1e9+9;int pow_1[maxn],pow_2[maxn];ll pow_m(ll a,ll k,ll p) {ll ans=1;ll tmp=a%p;while(k) {if(k&1)ans=ans*tmp%p;tmp=tmp*tmp%p;k>>=1;}return ans;}int n,m,k;vector<int>e[maxn];int val[maxn];unordered_map<int,int>mp;int ans1,ans2;void dfs(int x,int fa){mp[val[x]]++;//cout<<"x:"<<x<<"mp:"<<mp.size()<<endl;ans1+=(mp.size()*pow_1[x-1])%mod1;ans1%=mod1;ans2+=(mp.size()*pow_2[x-1])%mod2;ans2%=mod2;for(auto y:e[x]){if(y==fa)	continue;dfs(y,x);}int t=mp[val[x]]-1;mp.erase(val[x]);if(t)mp[val[x]]=t;}void solve(){cin>>n;for(int i=1;i<=n;i++)	e[i].clear();for(int i=2;i<=n;i++){int t;cin>>t;e[t].push_back(i);e[i].push_back(t);}for(int i=1;i<=n;i++){cin>>val[i];}for(int i=1;i<=n;i++){ans1=ans2=0;mp.clear();//cout<<"i:"<<i<<"------------"<<endl;dfs(i,0);//cout<<"------------------"<<endl;cout<<ans1<<' '<<ans2<<endl;}}signed main(){IOS#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out.txt","w",stdout);#endifint tn=1;cin>>tn;for(int i=0;i<2005;i++){pow_1[i]=pow_m(19560929,i,mod1);pow_2[i]=pow_m(19560929,i,mod2);}while(tn--){solve();}}
1008 题意

11走到nn，只能右走或下走，一些点被挡住了过不去，问有多少点到不了

1008 思路

光球层上的黑子 14:02:49
我们按行看，首先一个性质，一行里能到达的点和不能到达的点是一个交替排列的若干连续段。比如我们用0表示可达，1表示不可达，那么某行的可达情况应当是00001110000这种类型

光球层上的黑子 14:05:40
我们考虑行的转移，在这一行上初始不可达点是输入中的点，对于这样的点，它会阻挡人从左方走过来，对于他右侧的点，只有从上方可达转移下来的点才能到，如果这个点右侧的某个点x上方也是不可达的，那么这个点x一定也不可达。也就是说初始不可达点可以向右“染色”，就是找到右方最远的pos，使得pos上方为1也就是不可达。之后将这一段全部染为1.

光球层上的黑子 14:08:19
染色操作和找操作应当都可以使用数据结构优化成log，至于答案就是每一行1的个数，区间查询就行。空间受限肯定不可能开O（n)棵树，显然当前这一行答案只与上一行答案有关，所以我们开两颗树，类似01背包的空间优化那样滚动着用应该就可以了。

以上为和carry嘴的做法，结果最后嘴完也是我自己写，那没事了…

注意特判一个情况，我们在一开始需要独立找一下上一行最左的0位置，在这个位置左边是到不了的，这也是一直的wa点。

1008 代码
#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=200505;const int inf=0x3f3f3f3f;int n,m,k;vector<int>point[maxn];struct tree{int l,r;ll sum;int add;}t1[maxn<<2],t2[maxn<<2];ll ans;inline void build(int root,int l,int r,tree *t){t[root].l=l,t[root].r=r;t[root].add=-1;if(l==r){t[root].sum=0;return ;}int mid=l+r>>1;build(root<<1,l,mid,t);build(root<<1|1,mid+1,r,t);t[root].sum=0;}inline void pushdown(int root,tree *t){if(~t[root].add){t[root<<1].sum=(t[root<<1].r-t[root<<1].l+1)*t[root].add;t[root<<1|1].sum=(t[root<<1|1].r-t[root<<1|1].l+1)*t[root].add;t[root<<1].add=t[root].add;t[root<<1|1].add=t[root].add;t[root].add=-1;}}void update(int root,int l,int r,int x,tree *t){if(l<=t[root].l&&r>=t[root].r){t[root].sum=x*(t[root].r-t[root].l+1);t[root].add=x;return ;}pushdown(root,t);int mid=t[root].l+t[root].r>>1;if(mid>=l)   update(root<<1,l,r,x,t);if(mid<r)   update(root<<1|1,l,r,x,t);t[root].sum=t[root<<1].sum+t[root<<1|1].sum;}int query(int root,int l,int r,tree *t){if(l<=t[root].l&&r>=t[root].r){return t[root].sum;}pushdown(root,t);int mid=t[root].l+t[root].r>>1;int ans=0;if (l<=mid)	ans+=query(root<<1,l,r,t);if (r>mid)	ans+=query(root<<1|1,l,r,t);return ans;}int q_pos(int root,int x,tree *t){if(x>m) return m+1;if(t[root].sum==t[root].r-t[root].l+1)return inf;if(t[root].l==t[root].r){if(t[root].sum==0)  return t[root].l;return inf;}pushdown(root,t);int mid=t[root].l+t[root].r>>1;int ans=inf;if (x<=mid)	ans=min(ans,q_pos(root<<1,x,t));if(ans==inf)ans=min(ans,q_pos(root<<1|1,x,t));return ans;}inline void change(int last,int now){if(now&1){update(1,1,m,0,t2);if(now>1){int p=q_pos(1,1,t1);p=min(p-1,m);update(1,1,p,1,t2);}for(auto x:point[now]){int pos=q_pos(1,x+1,t1);pos=min(pos-1,m);update(1,x,pos,1,t2);}ans-=query(1,1,m,t2);}else{update(1,1,m,0,t1);int p=q_pos(1,1,t2);p=min(p-1,m);update(1,1,p,1,t1);for(auto x:point[now]){int pos=q_pos(1,x+1,t2);pos=min(pos-1,m);update(1,x,pos,1,t1);}ans-=query(1,1,m,t1);}}void solve(){scanf("%d%d%d",&n,&m,&k);ans=1ll*n*m;for(int i=1;i<=n;i++)   point[i].clear();while(k--){int a,b;scanf("%d%d",&a,&b);point[a].emplace_back(b);}build(1,1,m,t1),build(1,1,m,t2);update(1,1,m,1,t1);for(int i=1;i<=n;i++){change(i-1,i);}printf("%lld\n",ans);/* for(int i=1;i<=m;i++)cout<<query(1,i,i,t1)<<' ';cout<<endl;update(1,5,8,1,t1);update(1,11,12,1,t1);for(int i=1;i<=m;i++)cout<<query(1,i,i,t1)<<' ';cout<<endl;cout<<q_sum(1,1,12,t1)<<endl;for(int i=1;i<=m;i++)cout<<q_pos(1,i,t1)<<' ';cout<<endl;  */}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();}}
1009 题意

给30*100图，里面6个点阵画，让你输出他们的左右边界。

1009 思路

模拟题，我们二维投影到一维，右侧五个点阵画保证连续，扫一下就行，左侧汉字不一定连续，所以先右扫，再左扫。

1009 代码
#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;int a[105];void solve(){memset(a,0,sizeof a);for(int i=1;i<=30;i++){for(int j=1;j<=100;j++){char ch;cin>>ch;if(ch=='#')a[j]++;}}vector<pair<int,int> >v;int l,r;bool bl=0;int p=100;while(p&&v.size()<6){if(a[p]){if(!bl){bl=1;r=p;}}else{if(bl){bl=0;l=p;v.push_back({l+1,r});}bl=0;}p--;}for(int i=1;i<=p;i++){if(a[i]){l=i;break;}}for(int i=p;i;i--){if(a[i]){r=i;break;}}v.push_back({l,r});reverse(v.begin(),v.end());for(auto p:v)cout<<p.first<<' '<<p.second<<endl;}signed main(){IOS#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out.txt","w",stdout);#endifint tn=1;cin>>tn;for(int i=1;i<=tn;i++){cout<<"Case #"<<i<<":"<<endl;solve();}}

未完待续

E 题意
E 思路
E 代码
在这里插入代码片

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


http://www.chinasem.cn/article/858166。

相关文章

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