牛客周赛77文字版题解
A.时间表
把所有时间存在字符串数组中,输出对应的下标。
时间复杂度:
void solve(){
vector<string>a{
"20250121",
"20250123",
"20250126",
"20250206",
"20250208",
"20250211"
};
int x;cin>>x;
cout<<a[x-1];
}
B.数独数组
对于此类数独,一定存在连续的周期使得每个数字的出现次数相同,然后最后存在一段连续的数字都恰好出现一次。
故只要判断数字的最少次数和最多次数差距不大于 即可。
时间复杂度:
void solve(){
int n;
cin>>n;
vector<int>a(n+1);
vector<int>cnt(10);
for(int i=1;i<=n;i++){
cin>>a[i];
cnt[a[i]]++;
}
for(int i=1;i<=9;i++){
for(int j=i+1;j<=9;j++){
if(abs(cnt[i]-cnt[j])>1){
cout<<"NO\n";
return ;
}
}
}
cout<<"YES\n";
}
C. 小红走网格
对于行列移动本质上是分离的。
考虑行移动,每次能向上移动 个单位或向下移动
,那么对于
的倍数都可以达到,所以只需要判断
是否是
的倍数即可。
对于列移动同理。
时间复杂度:,其中
是移动的距离。
void solve(){
i64 a,b,c,d,x,y;
cin>>x>>y>>a>>b>>c>>d;
i64 g1=gcd(c,d);
i64 g2=gcd(a,b);
if(x%g1==0&&y%g2==0){
cout<<"YES\n";
}else{
cout<<"NO\n";
}
}
D.隐匿社交网络
假设两个数字在二进制位上存在某位都是 ,那么其必然满足
。
我们可以按位分成 个类,若一个数在对应位上是
,则把它放进对应的容器里。
那么就可以考虑按位并查集,先把可以合并的位合并,然后合并对应容器里的数字,再归纳去重即可。
最后比较容器里的数字个数,最多的便是答案。
时间复杂度:
void solve(){
int n;
cin>>n;
vector<i64>a(n+1);
vector<int>p(64);
iota(p.begin(),p.end(),0);
auto find=[&](auto &&self,int x)->int {
if(p[x]==x) return x;
p[x]=self(self,p[x]);
return p[x];
};
vector<vector<int>>vv(64);
for(int i=1;i<=n;i++){
cin>>a[i];
vector<int>v;
for(int j=0;j<=63;j++){
if(a[i]>>j&1){
v.push_back(j);
}
}
vv[v[0]].push_back(i);
for(int j=1;j<v.size();j++){
vv[v[j]].push_back(i);
int f1=find(find,p[v[j]]);
int f2=find(find,p[v[j-1]]);
if(f1!=f2){
p[f1]=p[f2];
}
}
}
vector<vector<int>>ans(64);
for(int i=0;i<=63;i++){
int fa=find(find,i);
for(auto t:vv[i]){
ans[fa].push_back(t);
}
}
int res=0;
for(int i=0;i<=63;i++){
sort(ans[i].begin(),ans[i].end());
ans[i].erase(unique(ans[i].begin(),ans[i].end()),ans[i].end());
res=max(res,(int)ans[i].size());
}
cout<<res<<"\n";
}
E.1or0
题意转化为求询问区间有多少个子区间包含 。
那么我们可以转化为询问区间的子区间个数减去区间中不包含 的区间个数。
先使用前缀和统计到 时全是
的子区间个数。
再用序列自动机预处理对于任意 其前缀和后缀中最远的
的位置,使得
到该位置的字符全是
。
对于 ,如果
, 那么说明答案便可以直接用
,因为该区间是不会存在
和前面的位置产生新的全
区间。
如果 ,说明我们多减去了如果红色乘以蓝色的区间个数,再加上即可,当然蓝色区间可能超过
,所以还要对
取一下较小值。
时间复杂度:
void solve(){
int n;
string s;
cin>>n>>s;
s=" "+s;
vector<i64>ans(n+2);
int idx=-1;
vector<int>pre(n+5,-1);
vector<int>suf(n+5,-1);
for(int i=1;i<=n;i++){
ans[i]=ans[i-1];
pre[i]=pre[i-1];
if(s[i]=='0'){
if(idx==-1){
ans[i]+=1;
}else{
ans[i]+=(i-idx+1);
}
if(idx==-1) idx=i;
}else{
idx=-1;
}
if(s[i]=='0'&&(s[i-1]=='1'||i-1==0)){
pre[i]=i;
}
}
suf[n]=(s[n]=='0'?n:-1);
for(int i=n-1;i>=1;i--){
suf[i]=suf[i+1];
if(s[i]=='0'&&s[i+1]=='1'){
suf[i]=i;
}
}
int q;
cin>>q;
while(q--){
int l=-1,r=-1;
cin>>l>>r;
i64 len=r-l+1;
i64 sum=(1+len)*len/2;
sum-=ans[r]-ans[l-1];
if(s[l]=='0'){
int right=min(suf[l],r);
int left=pre[l];
sum+=1LL*(right-l+1)*(l-left);
}
cout<<sum<<"\n";
}
}
F.计树
首先我们先记录哪些结点为给定的目标结点,接着对每个结点 考虑它作为目标结点
的次数。
同时记录对于第 个结点的子树下的目标结点数量为
。
对于任意一个 的子结点
,我们考虑对于已经遍历的
的兄弟结点的子树下的目标结点数量为
,那么此时
作为
新增的次数就是
。
特别地,若该结点是目标结点,可作为自身的 。
时间复杂度:
void solve(){
int n;
cin>>n;
vector<vector<int>>e(n+1);
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
int k;
cin>>k;
vector<bool>ok(n+1,false);
for(int i=1;i<=k;i++){
int s;
cin>>s;
ok[s]=true;
}
vector<i64>ans(n+1);
vector<i64>num(n+1);
auto dfs=[&](auto &&self,int u,int fa)->void {
i64 temp=0;
if(ok[u]) temp++;
for(auto v:e[u]){
if(v==fa) continue;
self(self,v,u);
ans[u]+=num[v]*temp*2;
temp+=num[v];
num[u]+=num[v];
}
if(ok[u]) num[u]++;
if(ok[u]) ans[u]++;
};
dfs(dfs,1,-1);
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
}