【做题笔记】CF Edu Round 132
本人第一次把 Div2. D 切了，开心。
C 不会，寄。 后来在场外想到一种奇怪做法 AC 了。
A. Three Doors
签到题。循环查找手中的钥匙能打开哪扇门然后更新手上钥匙，如果扫完一遍后发现还有门没打开，输出 \(\texttt{NO}\)，否则输出 \(\texttt{YES}\)。
时间复杂度：\(\mathcal O(3)\)。
期望得分：\(100\)。
Code
点击查看代码
/*
Author: TheSky233
Windows 11 Creation. All rights reserved.
*/
#include <bits/stdc++.h>
using namespace std;
#define Multicase() for(int T = read() ; T ; T--)
#define lowbit(x) (x & (-x))
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define l(p) tree[p].l
#define r(p) tree[p].r
#define sum(p) tree[p].sum
#define tag(p) tree[p].tag
#define F(i,a,b) for(int i=(a) ;i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i< (b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define clr(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define endl '\n'
#define ENDL putchar('\n')
#define forGraph(u) for(int i=head[u];i;i=G[i].next)
#define _file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
const int N=5e5+5;
const int M=1e6+5;
const int MN=1e3+5;
const int iinf=INT_MAX;
const double eps=1e-9;
const double pi=acos(-1);
const long long linf=LLONG_MAX;
const long long mod=1000000007,mod2=998244353;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<string,int> msi;
inline int read(){int x(0), f(0); char ch=getchar(); while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();} return f?-x:x;}
template <typename T> void read(T &x){x=0; T f(0); char ch=getchar(); while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();} x=f?-x:x;}
template <typename T,typename ...Arg>void read(T& x,Arg& ...arg){read(x);read(arg...);}
template <typename T> inline void write(T x){static char buf[64]; static int tot(0); if(x<0) putchar('-'),x=-x; do buf[++tot]=(x%10)+48,x/=10; while(x); do putchar(buf[tot--]); while(tot);}
template <typename T> void write(T x,char c){static char buf[64]; static int tot(0); if(x<0) putchar('-'),x=-x; do buf[++tot]=(x%10)+48,x/=10; while(x); do putchar(buf[tot--]); while(tot); putchar(c);}
void judge(bool x){printf(x?"YES\n":"NO\n");}
void Solve();
struct Graph{
int to,w,next;
}G[M<<1];
int head[N],_cnt;
void addEdge(int u,int v,int w){G[++_cnt]=(Graph){v,w,head[u]}; head[u]=_cnt;}
int n,m,q,k,p;
int a[5];
bool vis[10];
vector<int> v;
int main(){
Multicase()
Solve();
}
void Solve(){
memset(vis,0,sizeof(vis));
read(q);
F(i,1,3) read(a[i]);
vis[q]=1;
while(a[q]) vis[a[q]]=1,q=a[q];
F(i,1,3) if(vis[i]==0) return judge(0),void();
judge(1);
} B. Also Try Minecraft
首先，作为一个 MC 玩家和 Terraria 玩家，看到题面还小激动了一会。
进入正题。我们发现如果 \(a_i > a_{i\pm1}\)，那么就会收到 \(a_i - a_{i \pm 1}\) 的伤害，否则无伤。
我们可以 \(\mathcal O(n)\) 预处理出 \(a_{i-1}\) 前往 \(a_{i}\) 时收到的伤害和 \(a_{i+1}\) 前往 \(a_i\) 的伤害，随后将这两个数组分别做前缀和和后缀和，查询时如果 \(l \le r\) ，输出前缀和，否则输出后缀和。
时间复杂度：预处理 \(\mathcal O(n)\)，单次查询 \(\mathcal O(1)\)，总时间复杂度：\(\mathcal O(n+q)\)。
Code
点击查看代码
/*
Author: TheSky233
Windows 11 Creation. All rights reserved.
*/
#include <bits/stdc++.h>
using namespace std;
#define Multicase() for(int T = read() ; T ; T--)
#define lowbit(x) (x & (-x))
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define l(p) tree[p].l
#define r(p) tree[p].r
#define sum(p) tree[p].sum
#define tag(p) tree[p].tag
#define F(i,a,b) for(int i=(a) ;i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i< (b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define clr(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define endl '\n'
#define ENDL putchar('\n')
#define forGraph(u) for(int i=head[u];i;i=G[i].next)
#define _file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
const int N=5e5+5;
const int M=1e6+5;
const int MN=1e3+5;
const int iinf=INT_MAX;
const double eps=1e-9;
const double pi=acos(-1);
const long long linf=LLONG_MAX;
const long long mod=1000000007,mod2=998244353;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<string,int> msi;
inline int read(){int x(0), f(0); char ch=getchar(); while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();} return f?-x:x;}
template <typename T> void read(T &x){x=0; T f(0); char ch=getchar(); while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();} x=f?-x:x;}
template <typename T,typename ...Arg>void read(T& x,Arg& ...arg){read(x);read(arg...);}
template <typename T> inline void write(T x){static char buf[64]; static int tot(0); if(x<0) putchar('-'),x=-x; do buf[++tot]=(x%10)+48,x/=10; while(x); do putchar(buf[tot--]); while(tot);}
template <typename T> void write(T x,char c){static char buf[64]; static int tot(0); if(x<0) putchar('-'),x=-x; do buf[++tot]=(x%10)+48,x/=10; while(x); do putchar(buf[tot--]); while(tot); putchar(c);}
void judge(bool x){printf(x?"YES\n":"NO\n");}
void Solve();
struct Graph{
int to,w,next;
}G[M<<1];
int head[N],_cnt;
void addEdge(int u,int v,int w){G[++_cnt]=(Graph){v,w,head[u]}; head[u]=_cnt;}
int n,m,q,k,p;
ll a[N],b[N],f[N];
ll pre[N],suf[N];
vector<int> v;
int main(){
// Multicase()
Solve();
}
void Solve(){
read(n,q);
F(i,1,n) read(a[i]);
F(i,2,n) if(a[i-1]>a[i]) pre[i]=a[i-1]-a[i];
dF(i,n-1,1) if(a[i+1]>a[i]) suf[i]=a[i+1]-a[i];
F(i,1,n) pre[i]+=pre[i-1];
dF(i,n,1) suf[i]+=suf[i+1];
while(q--){
int x,y;
read(x,y);
if(x<=y) write(pre[y]-pre[x],'\n');
else write(suf[y]-suf[x],'\n');
}
} C. Cover an RBS
A-D 中最难题。
首先，我们先预处理出字符串中 \(\texttt{( ) ?}\) 的个数，记为 \(l,r,q\)，如果 \(|l-r|=q\)，说明所有的问号都得填上某种括号，唯一，输出 \(\texttt{YES}\)。
然后，因为题面保证了是一个 RBS 填上若干个问号，所以必定有一种合法的解。我们贪心：如果当前左括号数量不足字符串长度的一半，就填左括号，否则全填右括号。在填的同时维护一下 最后一个左括号 和 第一个右括号 出现的位置。
然后我们就能得到类似这样一个字符串
\(\texttt{(} \color{red}{\texttt{)}} \texttt{(())} \color{red}{\texttt{(}} \texttt{)}\)。
我们可以发现，交换两个标红的括号，还能保持一个合法括号序列的基本要求（对于 \(\forall 1\ge i \le len\),有前缀和 \(l_i \geq r_i\)），同时，因为我们保存的是最边界的左右括号，也能保证对其它的影响最少。
如果 \(\operatorname{swap}(s_{lastL},s_{firstR})\) 后，还是一个合法的序列，说明不唯一，输出 \(\texttt{NO}\)，否则输出 \(\texttt{YES}\)。（感性理解）
时间复杂度：\(\mathcal O(n)\)
期望得分：\(100\)
Code
点击查看代码
/*
Author: TheSky233
Windows 11 Creation. All rights reserved.
*/
#include <bits/stdc++.h>
using namespace std;
#define Multicase() for(int T = read() ; T ; T--)
#define lowbit(x) (x & (-x))
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define l(p) tree[p].l
#define r(p) tree[p].r
#define sum(p) tree[p].sum
#define tag(p) tree[p].tag
#define F(i,a,b) for(int i=(a) ;i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i< (b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define clr(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define endl '\n'
#define ENDL putchar('\n')
#define forGraph(u) for(int i=head[u];i;i=G[i].next)
#define _file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
const int N=5e5+5;
const int M=1e6+5;
const int MN=1e3+5;
const int iinf=INT_MAX;
const double eps=1e-9;
const double pi=acos(-1);
const long long linf=LLONG_MAX;
const long long mod=1000000007,mod2=998244353;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<string,int> msi;
inline int read(){int x(0), f(0); char ch=getchar(); while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();} return f?-x:x;}
template <typename T> void read(T &x){x=0; T f(0); char ch=getchar(); while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();} x=f?-x:x;}
template <typename T,typename ...Arg>void read(T& x,Arg& ...arg){read(x);read(arg...);}
template <typename T> inline void write(T x){static char buf[64]; static int tot(0); if(x<0) putchar('-'),x=-x; do buf[++tot]=(x%10)+48,x/=10; while(x); do putchar(buf[tot--]); while(tot);}
template <typename T> void write(T x,char c){static char buf[64]; static int tot(0); if(x<0) putchar('-'),x=-x; do buf[++tot]=(x%10)+48,x/=10; while(x); do putchar(buf[tot--]); while(tot); putchar(c);}
void judge(bool x){printf(x?"YES\n":"NO\n");}
void Solve();
struct Graph{
int to,w,next;
}G[M<<1];
int head[N],_cnt;
void addEdge(int u,int v,int w){G[++_cnt]=(Graph){v,w,head[u]}; head[u]=_cnt;}
int n,m,k,p;
int a[N],b[N],f[N];
vector<int> v;
int main(){
Multicase()
Solve();
}
string s;
void Solve(){
int l=0,r=0,q=0;
cin>>s;
int len=s.length();
F2(i,0,len){
if(s[i]=='(') l++;
else if(s[i]==')') r++;
else q++;
}
if(q==abs(l-r)) return judge(1),void();
int tot=len/2;
int lastL=0,firstR=iinf;
F2(i,0,len){
if(s[i]=='?'){
if(l<tot){
l++;
s[i]='(';
lastL=i;
}
else{
r++;
s[i]=')';
firstR=min(firstR,i);
}
}
}
swap(s[lastL],s[firstR]);
int cnt=0;
F2(i,0,len){
if(s[i]=='(') cnt++;
else cnt--;
if(cnt<0) return judge(1),void();
}
judge(0);
} D. Rorororobot
萌萌题。使用 ST-Table 维护区间 \([l,r]\) 中墙的最大高度，显然，如果 \([x_1,x_2]\) 中有墙的高度为 \(n\)，那么无解。
否则，判断他们是否都能走到最高的墙的上面以及 \(|x_1-x_2| \bmod{k}\) 和 \(|y_1-y_2| \bmod{k}\) 是否都为 \(0\)，如果是，输出 \(\texttt{YES}\)，否则 \(\texttt{NO}\)。
时间复杂度：ST 表预处理 \(\mathcal O(m \log m)\)，单次查询 \(\mathcal O(1)\)，总复杂度 \(\mathcal O(n+q)\)。
期望得分：\(100\)。
Code
点击查看代码
/*
Author: TheSky233
Windows 11 Creation. All rights reserved.
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define Multicase() for(int T = read() ; T ; T--)
#define lowbit(x) (x & (-x))
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define l(p) tree[p].l
#define r(p) tree[p].r
#define sum(p) tree[p].sum
#define tag(p) tree[p].tag
#define F(i,a,b) for(int i=(a) ;i<=(b);++i)
#define F2(i,a,b) for(int i=(a);i< (b);++i)
#define dF(i,a,b) for(int i=(a);i>=(b);--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define clr(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define endl '\n'
#define ENDL putchar('\n')
#define forGraph(u) for(int i=head[u];i;i=G[i].next)
#define _file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
const int N=5e5+5;
const int M=1e6+5;
const int MN=1e3+5;
const int iinf=INT_MAX;
const double eps=1e-9;
const double pi=acos(-1);
const long long linf=LLONG_MAX;
const long long mod=1000000007,mod2=998244353;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<string,int> msi;
inline int read(){int x(0), f(0); char ch=getchar(); while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();} return f?-x:x;}
template <typename T> void read(T &x){x=0; T f(0); char ch=getchar(); while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();} x=f?-x:x;}
template <typename T,typename ...Arg>void read(T& x,Arg& ...arg){read(x);read(arg...);}
template <typename T> inline void write(T x){static char buf[64]; static int tot(0); if(x<0) putchar('-'),x=-x; do buf[++tot]=(x%10)+48,x/=10; while(x); do putchar(buf[tot--]); while(tot);}
template <typename T> void write(T x,char c){static char buf[64]; static int tot(0); if(x<0) putchar('-'),x=-x; do buf[++tot]=(x%10)+48,x/=10; while(x); do putchar(buf[tot--]); while(tot); putchar(c);}
void judge(bool x){printf(x?"YES\n":"NO\n");}
void Solve();
struct Graph{
int to,w,next;
}G[M<<1];
int head[N],_cnt;
void addEdge(int u,int v,int w){G[++_cnt]=(Graph){v,w,head[u]}; head[u]=_cnt;}
int n,m,q,k,p;
int a[N],b[N],f[N];
int ST[N][25];
vector<int> v;
signed main(){
// Multicase()
Solve();
}
int query(int l,int r){
int k=__lg(r-l+1);
return max(ST[l][k],ST[r-(1<<k)+1][k]);
}
void Solve(){
read(n,m);
F(i,1,m) read(a[i]);
memset(ST,0,sizeof(ST));
for(int i=1;i<=m;i++) ST[i][0]=a[i];
for(int j=1;j<=21;j++){
for(int i=1;i+(1<<j)-1<=m;i++){
ST[i][j]=max(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
}
}
read(q);
while(q--){
int x,y,xx,yy,k;
read(y,x,yy,xx,k);
if(x>xx) swap(y,yy),swap(x,xx);
if(query(x,xx)==n){
judge(0);
continue;
}
if((xx-x)%k!=0 || (abs(yy-y))%k!=0){
judge(0);
continue;
}
int h=query(x,xx)+1;
int ly=n-y,lyy=n-yy;
int ty=ly/k,tyy=lyy/k;
if(y>=h && yy>=h) judge(1);
else if(y+ty*k>=h || yy+tyy*k>=h) judge(1);
else judge(0);
}
}
/*
0 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0
1 0 0 1 0 0 0 1 1 0
1 0 0 1 0 0 1 1 1 1
1 0 0 1 0 0 1 1 1 1
1 0 0 1 0 0 1 1 1 1
1 0 0 1 0 0 1 1 1 1
1 0 & 1 & 1 1 1 1 1
1 0 0 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 1 1
*/手机扫一扫
移动阅读更方便
你可能感兴趣的文章