本文主要是介绍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全是思维+数据结构优化）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
