8 12 考试总结
难度分布不是很合理？ 果然只是我太菜了
T1
原题： [ARC164B] Switching Travel
观察题意：可以发现是找一条黑白相间，两端颜色一致的链拼起来的环。
讲真，当时想的是直接爆搜的，但在设计时遇到了一些问题，导致没写出来。
正解是并查集判环。
若一条边连接的两点颜色不同，则其链接的两点加入同一并查集中，表示为一条链。
最后遍历一遍边，查找是否有相邻的点颜色相同且其在同一并查集中。
AC code：
#include <bits/stdc++.h>
#define seq(q, w, e) for (int q = w; q <= e; q++)
#define ll long long
using namespace std;
const int maxn = 2e5+10;
int n,m,fa[maxn],a[maxn];
struct node{
int u,v;
}e[maxn];
bool cmp;
int find(int x){
if(fa[x]==x) return fa[x];
return fa[x]=find(fa[x]);
}
void join(int x,int y){
fa[find(x)]=find(y);
}
int u,v;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
seq(i,1,m){
cin>>u>>v;
e[i]=(node){u,v};
}
seq(i,1,n){
cin>>a[i];
fa[i]=i; //并查集初始化
}
seq(i,1,m)
if(a[e[i].u]!=a[e[i].v]) join(e[i].u,e[i].v);
//若边连接的两边颜色不同，则表示此边是可走的
seq(i,1,m){
if(a[e[i].u]==a[e[i].v]&&find(e[i].u)==find(e[i].v))
//查找相邻的，且处于同意并查集的点，有即yes
cmp=1;
}
if(cmp){
cout<<"Yes";
}
else{
cout<<"No";
}
return 0;
}
T2
一眼鉴定为线段树。主要是我做过
对标朴素线段树，此题的线段树较为特殊，由于其动态的加入点，于是乎我们省去了建树操作。但线段树复杂的结构导致其维护时不是简单的 \(tree[++tot]=x\) 就可以解决的。
则我们假设每个操作都是加点，则此线段树序列的极限长度为 \(m\) ，如是便可进行操作。
维护一个 \(cnt\) 表示当前序列的末尾。用普通线段树的 单点修改+区间查询 即可。
AC code：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=-114514;
ll m,cnt;
char op[2];
ll data[800005],x,t,p;
ll max(ll a,ll b)
{
return a>b?a:b;
}
void add(ll s,ll k,ll o,ll l,ll r)
{
if(l==r)
{
data[o]=k;
return;
}
ll mid=(l+r)>>1;
if(mid>=s) add(s,k,o<<1,l,mid);
if(mid<s) add(s,k,o<<1|1,mid+1,r);
data[o]=max(data[o<<1],data[o<<1|1])%p;
}
ll ask(ll lc,ll rr,ll o,ll l,ll r)
{
if(lc<=l&&rr>=r) return data[o];
ll mid=(l+r)>>1;
ll a=inf,b=inf;
if(mid>=lc) a=ask(lc,rr,o<<1,l,mid);
if(mid<rr) b=ask(lc,rr,o<<1|1,mid+1,r);
return max(a,b);
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>m>>p;
for(ll i=0;i<m;i++)
{
cin>>op>>x;
if(op[0]=='A')
{
add(cnt+1,(x+t)%p,1,1,m);
cnt++;
}
if(op[0]=='Q')
{
if(x==0) t=0;
else t=ask(cnt-x+1,cnt,1,1,m)%p;
cout<<t<<endl;
}
}
return 0;
}
T3
其实读完题就可以发现，这是单调队列板子( P1886 滑动窗口 /【模板】单调队列 ) ，但考试时忘了单调队列怎么写。所以说，这题也用的线段树。 (讲真 \(2^{22}\) 的数据范围竟然不会爆空间，有点惊讶)
既然是线段树，那么思路十分好想。简单的区间 \(RMQ\) 问题。建完树后， \([1,n]\) 扫一遍，输出query(i-m,i-1) 即可。
注：虽然题干上说数据范围为 \(2e6\) 但线段树开 \(2e6 \times 4\) 会 \(WA\) #2,#7。应开到 \(2^{22}\) ,才不会越界。以及，实测不用快读也能 \(AC\) 。
AC code：
#include<bits/stdc++.h>
#define ll long long
#define seq(q,w,e) for(int q=w;q<=e;q++)
using namespace std;
const int maxn=4194304;
ll tree[maxn<<2];
ll ls(ll p){return p<<1;}
ll rs(ll p){return (p<<1)|1;}
void push_up(ll p){
tree[p]=min(tree[ls(p)],tree[rs(p)]);
}
void build_tree(ll p,ll pl,ll pr){
if(pl==pr){
cin>>tree[p];
return;
}
ll mid=(pl+pr)>>1;
build_tree(ls(p),pl,mid);
build_tree(rs(p),mid+1,pr);
push_up(p);
}
ll query(ll l,ll r,ll p,ll pl,ll pr){
if(l>r) return 0;
if(l<=pl&&r>=pr) return tree[p];
ll mid=(pl+pr)>>1;
ll ans=maxn;
if(l<=mid) ans=min(ans,query(l,r,ls(p),pl,mid));
if(r>mid) ans=min(ans,query(l,r,rs(p),mid+1,pr));
return ans;
}
ll n,m;
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
build_tree(1,1,n);
seq(i,1,n){
int l=i-m,r=i-1;
if(l<=0) l=1;
if(l>r){
cout<<"0"<<"\n";
continue;
}
cout<<query(l,r,1,1,n)<<"\n";
}
return 0;
}
T4
考试时盯着这题看了二十分钟，完全没思路，成功爆0。
直接来看正解吧，由于其保证 \(q_i\) 互不相同，于是饲料并不重要。先计算已有的动物编号，哪些位上至少存在一次，用 \(|\) 操作。
对于每个操作，若 \(p_i\) 存在，则此种饲料一定存在。反之一定没有，即这一位一定不为1。
除去一定不为1的位，剩下 \(t\) 个位可能为1，那总动物数可以达到 \(2^t\) ,减去已有的 \(n\) 种，所以答案是 \(2^t-n\) 。
注：全程要用 unsigned long long ,当 \(t=64\) 时，会爆 ull ,所以特判，输出 \(18446744073709551616\) 即可。
AC code：
#include <bits/stdc++.h>
#define seq(q, w, e) for (int q = w; q <= e; q++)
#define ull unsigned long long
using namespace std;
const int maxn = 1e5+10;
int n,m,c,k;
ull sum,b;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>c>>k;
seq(i,1,n){
ull x;
cin>>x;
sum|=x;
}
while(m--){
int p,op;
cin>>p>>op;
if((sum>>p&1)==0) b|=1ull<<p;
}
ull ans=1;
for (int i=0;i<k;i++){
if((b>>i&1)==0) ans<<=1;
}
if(ans==0&&n==0){
cout<<"18446744073709551616";
return 0;
}
ans-=n;
cout<<ans<<"\n";
return 0;
}