Codeforces Round 914 (Div. 2)（A-D全是思维+数据结构优化）

2023-12-11 01:04
文章标签 优化 数据结构 codeforces round div 思维 全是 914

本文主要是介绍Codeforces Round 914 (Div. 2)（A-D全是思维+数据结构优化），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A - Forked!

求他们相交的地方，直接枚举两个点走日字型的相交的点，

然后如果a=b，会重复，从8个格子变成4个格子

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;void solve()
{int a,b;cin>>a>>b;int dx[8]={-a,-a,-b,-b,a,a,b,b},dy[8]={b,-b,a,-a,b,-b,a,-a};int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;int res=0;for(int i=0;i<8;i++){for(int j=0;j<8;j++){if(x1+dx[i]==x2+dx[j]&&y1+dy[i]==y2+dy[j])res++;}}if(a==b) res/=4;cout<<res<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

B - Collecting Game

直接排序，双指针

排序完后，如果当前要求的是i点，那么直接求i点能往右到达的最右的点即可

因为排序后是递增，所以是满足单调性的

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
PII a[N];
int res[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i].first;a[i].second=i;}sort(a+1,a+1+n);int now=0;vector<int> s(n+10);for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i].first;int idx=0;for(int i=1;i<=n;i++){while(idx<=i){now+=a[idx].first;idx++;}while(idx<=n&&now>=a[idx].first){now+=a[idx].first;idx++;}res[a[i].second]=max(0ll,idx-2);}for(int i=1;i<=n;i++) cout<<res[i]<<" \n"[i==n];   
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

C - Array Game

C：分类讨论
k>=3:随便选两个不同的 i,j 然后第三次直接自己剪掉自己就行了
abs(3-9) abs(3-9) 0
k=1:min(数组的最小值,当前数组的绝对值最小值)
k=2::min(数组的最小值,当前数组的绝对值最小值)
当前数组的绝对值最小值和数组里面的数产生新的绝对值

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];
int res[N];
void solve()
{cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];if(k>=3){cout<<0<<"\n";return ;}sort(a+1,a+1+n);int mn=*min_element(a+1,a+1+n);for(int i=2;i<=n;i++)mn=min(mn,a[i]-a[i-1]);if(k==1){cout<<mn<<"\n";return ;}set<int> st;for(int i=1;i<=n;i++) st.insert(a[i]);// cout<<mn<<"\n";for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){int x=abs(a[i]-a[j]);auto it=st.lower_bound(x);mn=min(mn,abs(*it-x));if(it==st.begin()) continue;it--;mn=min(mn,abs(*it-x));//cout<<i<<" "<<j<<" "<<mn<<"\n";}}cout<<mn<<"\n";}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

D1 - Set To Max (Easy Version)


枚举每个数能不能改变的
假设当前枚举 i=3
当前下标往左的第一个a[j]==b[i]的数或者 当前下标往右第一个a[j]==b[i]的数
有两种情况是走不到的
k属于 [j+1:i-1]
就如果 中间b[k]<b[i]或者就是中间a[k]>b[i]
中间b[k]>b[i]:[j+1:i-1]这个区间的b[k]>=b[i] --->这个区间的b的最小值要大于b[i]
中间a[k]>b[i]:[j+1:i-1]这个区间的所有数的a[k]<=b[i] --->这个区间的a最大值不能大于b[i]

a[i]>b[i] 直接 no

第一个是easy版本

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N],b[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int j=1;j<=n;j++) cin>>b[j];for(int i=1;i<=n;i++){if(a[i]==b[i]) continue;if(a[i]>b[i]){cout<<"NO\n";return ;}bool ok=false;for(int j=i-1;j>=1;j--){if(b[j]<b[i]||a[j]>b[i]){break;    }if(a[j]==b[i]){ok=true;break;}}for(int j=i+1;j<=n;j++){if(b[j]<b[i]||a[j]>b[i]){break;    }if(a[j]==b[i]){ok=true;break;}}if(!ok){cout<<"NO\n";return ;}}cout<<"YES\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

优化版本就是用个st表求区间最值

拿个set二分左边第一个当前的数和右边第一个当前的数

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N],b[N];
int f[N][25],g[N][20];
void init(){for (int j = 0; j < 20; j ++ )for (int i = 1; i + (1 << j)-1<=n; i ++ )if (!j) f[i][j] = a[i],g[i][j]=b[i];else {f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);g[i][j] = min(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);}
}
int querya(int l,int r){int len=r-l+1;int k=log(len)/log(2);return max(f[l][k],f[r-(1<<k)+1][k]);
}
int queryb(int l,int r){int len=r-l+1;int k=log(len)/log(2);return min(g[l][k],g[r-(1<<k)+1][k]);
}
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int j=1;j<=n;j++) cin>>b[j];init();map<int,set<int>> mp;for(int i=1;i<=n;i++){mp[a[i]].insert(-2e9);mp[a[i]].insert(2e9);mp[a[i]].insert(i);}for(int i=1;i<=n;i++){if(a[i]==b[i]) continue;if(a[i]>b[i]||!mp.count(b[i])){cout<<"NO\n";return ;}auto it=mp[b[i]].lower_bound(i);bool ok=false;if(*it!=2e9){int x=*it;if(queryb(i+1,x)>=b[i]&&querya(i+1,x)<=b[i])ok=true;}it--;if(*it!=-2e9){int x=*it;if(queryb(x,i-1)>=b[i]&&querya(x,i-1)<=b[i])ok=true;}if(!ok){cout<<"NO\n";return ;}// bool ok=false;//   for(int j=i-1;j>=1;j--){//       if(b[j]<b[i]||a[j]>b[i])//       {//             break;    //       }//       if(a[j]==b[i])//       {//           ok=true;break;//       }//   }//     for(int j=i+1;j<=n;j++){//         if(b[j]<b[i]||a[j]>b[i])//       {//             break;    //       }//       if(a[j]==b[i]){//           ok=true;break;//       }//   }//   if(!ok){//       cout<<"NO\n";return ;//   }}cout<<"YES\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

这篇关于Codeforces Round 914 (Div. 2)（A-D全是思维+数据结构优化）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

《Oracle查询优化之高效实现仅查询前10条记录的方法与实践》：本文主要介绍Oracle查询优化之高效实现仅查询前10条记录的相关资料,包括使用ROWNUM、ROW_NUMBER()函数、FET... 目录1. 使用 ROWNUM 查询2. 使用 ROW_NUMBER() 函数3. 使用 FETCH FI
阅读更多...
C#使用HttpClient进行Post请求出现超时问题的解决及优化

C#使用HttpClient进行Post请求出现超时问题的解决及优化

《C#使用HttpClient进行Post请求出现超时问题的解决及优化》最近我的控制台程序发现有时候总是出现请求超时等问题,通常好几分钟最多只有3-4个请求,在使用apipost发现并发10个5分钟也... 目录优化结论单例HttpClient连接池耗尽和并发并发异步最终优化后优化结论我直接上优化结论吧，
阅读更多...
Java内存泄漏问题的排查、优化与最佳实践

Java内存泄漏问题的排查、优化与最佳实践

《Java内存泄漏问题的排查、优化与最佳实践》在Java开发中,内存泄漏是一个常见且令人头疼的问题,内存泄漏指的是程序在运行过程中,已经不再使用的对象没有被及时释放,从而导致内存占用不断增加,最终... 目录引言1. 什么是内存泄漏？常见的内存泄漏情况2. 如何排查 Java 中的内存泄漏？2.1 使用 J
阅读更多...
MySQL不使用子查询的原因及优化案例

MySQL不使用子查询的原因及优化案例

《MySQL不使用子查询的原因及优化案例》对于mysql,不推荐使用子查询,效率太差,执行子查询时,MYSQL需要创建临时表,查询完毕后再删除这些临时表,所以,子查询的速度会受到一定的影响,本文给大家... 目录不推荐使用子查询和JOIN的原因解决方案优化案例案例1：查询所有有库存的商品信息案例2：使用EX
阅读更多...
MySQL中my.ini文件的基础配置和优化配置方式

MySQL中my.ini文件的基础配置和优化配置方式

《MySQL中my.ini文件的基础配置和优化配置方式》文章讨论了数据库异步同步的优化思路,包括三个主要方面：幂等性、时序和延迟,作者还分享了MySQL配置文件的优化经验,并鼓励读者提供支持... 目录mysql my.ini文件的配置和优化配置优化思路MySQL配置文件优化总结MySQL my.ini文件
阅读更多...
正则表达式高级应用与性能优化记录

正则表达式高级应用与性能优化记录

《正则表达式高级应用与性能优化记录》本文介绍了正则表达式的高级应用和性能优化技巧,包括文本拆分、合并、XML/HTML解析、数据分析、以及性能优化方法,通过这些技巧,可以更高效地利用正则表达式进行复杂... 目录第6章：正则表达式的高级应用6.1 模式匹配与文本处理6.1.1 文本拆分6.1.2 文本合并6
阅读更多...
Vue3 的 shallowRef 和 shallowReactive：优化性能

Vue3 的 shallowRef 和 shallowReactive：优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉，那么对 shallowRef 和 shallowReactive 是否了解呢？ 在编程和数据结构中，“shallow”（浅层）通常指对数据结构的最外层进行操作，而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素，而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层（Shallow） 定义
阅读更多...
HDFS—存储优化（纠删码）

HDFS—存储优化（纠删码）

纠删码原理 HDFS 默认情况下，一个文件有3个副本，这样提高了数据的可靠性，但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码，采用计算的方式，可以节省约50％左右的存储空间。 此种方式节约了空间，但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件，都会执行此策略。 默认只开启对 RS-6-3-1024k
阅读更多...
使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2