抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

UESTC 2023 Summer Training#4 Div.2暑假集训

发布于：2023年7月14日

字数：2.8k 字

时长：13 分钟

Preface

作为暑假集训的第一篇博客，为什么是#4呢？因为终于写出了免于爆零了 ，感慨良多，虽然在赛场上一直卡G（英语不好读不懂题），但明显感觉到卷子的难度正在适应我的水平，而且几何和字符串专题根本做不动，借着这个契机开始整理笔记（感觉学习曲线过于陡峭了）；

赛后补题只补了六道，留坑记录一下；

A:cf245D 1500 二进制 B:cf1557B 1100 排序 C:cf1338B 1800 构造 D:cf1430E 1900 转换后求逆序对 E:cf915F 2400（虚高） 并查集 F:cf1668C 1300 暴力，贪心 G:cf176D 2100 有些技巧的DP H:cf448D 1800 二分答案

#A. Restoring Table

题源：CF245D

题意：

给定对称矩阵和规模n,满足如下关系，要求还原数组a

思路：

  • 对每个b做二进制拆分不难发现还原a只需要对相应下标做按位且运算即可，而且确实如题目所说答案并不唯一；
  • 本场签到题；

AC code：

#include<bits/stdc++.h>
using namespace std;

int main ()
{
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n;
    const int maxn=105;
    int a[maxn];
    memset(a,0,sizeof(a));
    int b[maxn][maxn];
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>b[i][j];
        }
    }
    for(int j=1;j<=n;j++){
        b[j][j]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i]|=b[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        if(i!=1) cout<<" ";
        cout<<a[i];
    }
    return 0;
}

#B. Moamen and k-subarrays

题源：CF1557B

题意：

询问能否将长度为n的数组分成k块，重新排列得到顺序；

思路：

  • 我们考察可以把原数组的若干个数绑定在一起的块，若能重新排列得到顺序，那么块里的数必然在顺序排列中也是相连的；
  • 如果原数组这样分块后存在（可能不到）k个块，那么把一些好的块打散肯定也是符合题意的；
  • 考虑原地排序还原下标，依次遍历检查相邻两数能否组块，采用pair输入；
  • 也是签到题，但是没看榜后面的时间all in G题了~~（所以这场没有到）~~；

AC code：

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn=300005;
 
int main ()
{
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local
 
    int t;
    std::cin>>t;
    while(t--){
        int n,k;
        std::cin>>n>>k;
        std::vector<pair<int,int> > v(n);
        for(int i=0;i<n;i++){
            std::cin>>v[i].first;
            v[i].second=i;
        }
        std::vector<pair<int,int> > u=v;
        std::sort(v.begin(),v.end());
        int cnt=1;
        for(int i=1;i<n;i++){
            if(v[i-1].second+1!=v[i].second) cnt++;
        }
        if(cnt<=k) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

#C. Edge Weight Assignment

题源：CF1338B

题意：

没读；

思路：

没有；

#D. String Reversal

题源：CF1430E

题意：

将字符串对换成其反串最少的操作次数；

思路：

  • 开始陷入误区尝试证明最少的次数是正串和反串逆序对差的绝对值，结果样例都跑不过，换思路；
  • 直接模拟对换过程，猜想不做故意浪费的操作换回来又换回去即为最小次数；
  • 建立一个目标数组，即每个字符最终应该到达的下标位置，考虑到有重复字符要做到某种意义的最优应使得对于正串某个字符第i个目标是反串相同字符的第i个；
  • 对目标数组最终变为自然排列，因而最少的次数就是这个字符串的逆序对个数，归并排序即可；
  • 这个转化初见，有些巧妙的，留坑归并排序、树状数组的模板整理于此（做这个题时也没学过归并排序，线段树写不下去了思路还是错的就摘了个板子过来还没仔细看看）；
  • 复杂度 O（n logn) ;

AC code：

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=200006;
ll ans=0;
void msort(int* tar,int* tmp,int l,int r){
    if(l==r) return ;
    int mid=l+((r-l)>>1);
    msort(tar,tmp,l,mid);
    msort(tar,tmp,mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(tar[i]<=tar[j]) tmp[k++]=tar[i++];
        else tmp[k++]=tar[j++],ans+=mid-i+1;
    }
    while(i<=mid) tmp[k++]=tar[i++];
    while(j<=r) tmp[k++]=tar[j++];
    for(int p=l;p<=r;p++){
        tar[p]=tmp[p];
    }
    return ;
}
int star[maxn],stemp[maxn],ttar[maxn],ttemp[maxn];
int main ()
{
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n;
    cin>>n;
    string s;
    cin>>s;
    //string t=string(s.rbegin(),s.rend());
    memset(star,0,sizeof(star));
    memset(stemp,0,sizeof(stemp));
    stack<int> buc[26];
    for(int i=0;i<n;i++){
        int x=s[i]-'a';
        buc[x].push(n-1-i);
    }
    for(int i=0;i<n;i++){
        int x=s[i]-'a';
        star[i]=buc[x].top();
        buc[x].pop();
    }
    msort(star,stemp,0,n-1);
    cout<<ans<<endl;
    return 0;
}

#E. Imbalance Value of a Tree

题源：CF915F

题意：

给定树T以及树上结点赋点权a[i]，定义I（i，j）为i与j之间的路径经过点最大值与最小值之差，计算

思路：

  • 开始采用树上倍增找到lca的做法，但是MLE了，毕竟确实开了很大的数组，而且也感觉会跑不过；

  • 但还是见的少了，本题是DSU模板题；

  • 首先观察到在树上路径操作，并且经过的边显然只取决于它的端点，考虑将点权转化为边权（常见套路），在考虑最大值问题时为两端点最大值，反之亦然；

  • 转化表达式，维护各个最大值和最小值贡献的次数，考虑最大值这一边的问腿，

  • p1(e)可以看作由e的权值决定这样路径i~j的条数，很明显权值越小能够能决定的路径数越少；

  • 将权值原地排序，用DSU维护边全局信息，两边相连则加入DSU中，对树做路径压缩的DSU总会转化为星状图，所以每次更新将贡献次数传递给父亲并更新DSU的状态就好了，并且开始做的点权转化使得每条边至少可以控制自己两个端点之间的路径（就是自己），所以初始化为1；

  • 要加上输入优化，不知道为什么跑出来差别那么大看起来真的输入了很多很多数来卡人，复杂度应该是略大于O(n)，这是由于路径压缩的DSU复杂度是近似常数，所以数据膨胀的飞起；

AC code:

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=1000006;
ll a[maxn],f[maxn],p[maxn];
int n;
ll ans=0;
class Edge{
    public:
    ll x,y,w;
}e[maxn];
bool cmp1(Edge&a,Edge&b){
    return a.w<b.w;
}
bool cmp0(Edge&a,Edge&b){
    return a.w>b.w;
}
ll find(ll x){
    return (f[x]==x)?x:f[x]=find(f[x]);//路径压缩
}
void init(bool op){
    for(int i=1;i<=n;i++){
        f[i]=i;
        p[i]=1;
    }
    
    for(int i=1;i<=n-1;i++){
        e[i].w=(op)?max(a[e[i].x],a[e[i].y]):min(a[e[i].x],a[e[i].y]);
    }
    sort(e+1,e+n,op?cmp1:cmp0);
    return ;
}
int main ()
{
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
    }
    for(int i=1;i<=n-1;i++){
        scanf("%lld%lld",&e[i].x,&e[i].y);
    }
    init(1);
    for(int i=1;i<=n-1;i++){
        ll ex=find(e[i].x);//通过并查集等效出去的两端
        ll ey=find(e[i].y);
        ans+=e[i].w*(p[ex]*p[ey]);
        f[ey]=ex;
        p[ex]+=p[ey];
    }
    init(0);
    for(int i=1;i<=n-1;i++){
        ll ex=find(e[i].x);
        ll ey=find(e[i].y);
        ans-=e[i].w*(p[ex]*p[ey]);
        f[ey]=ex;
        p[ex]+=p[ey];
    }
    cout<<ans<<endl;
    return 0;
}

p.s.

看的出来对并查集也不是很熟悉，留个坑整理一下；

#F. Make it Increasing

题源：CF1668C

题意：

给定数组a，零初始化b,找到a[i]b[i]严格递增的数组b，最小化

思路：

  • 想法是活用负数，暴力找到一点置为0，左边为负数右边为正数；
  • 于是brute force枚举置零的位置，只需要比较当前最优方案即可；
  • 最优方案是贪心的使得b[i]a[i]从0位置开始看变化的缓慢一点，至少保证能递增的最低限度；
  • 试图优化了但直接WA了一发，因为找不到确切的i，枚举变化陡峭的点也是在O(n)的，比如1 1 4 5 1 4 重复；
  • 复杂度 O(n^2)

AC code:

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=5005;
int main ()
{
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n;
    cin>>n;
    vector<ll>a(n+1);
    vector<double>k(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    // int cnt=0;
    // double km=0;
    // for(int i=2;i<=n;i++){
    //     k[i]=(a[i]+0.0)/a[i-1];
    //     km=std::max(k[i],km);
    // }
    vector<ll> id;
    for(int i=1;i<=n;i++){
        //if(k[i]==km) 
        id.push_back(i); 
    }
    int num=id.size();
    ll best=0;
    for(int j=0;j<num;j++){
        int pos=id[j];
        ll sum=0;
        vector<ll> b(n+1);
        for(int i=pos+1;i<=n;i++){
            b[i]=ceil((1.0+b[i-1]*a[i-1])/a[i]);
            sum+=b[i];
        }
        for(int i=pos-1;i>=1;i--){
            b[i]=-ceil((1.0-b[i+1]*a[i+1])/a[i]);
            sum-=b[i];
        }
        best=(j==0)?sum:std::min(best,sum);
    }
    cout<<best<<endl;
    return 0;
}

#G. Hyper String

题源：CF176D

题意：

没看

思路：

没有

#H. Multiplication Table

题源：CF448D

题意：

找到m·n的乘法表中非去重非递减第k大的数；

思路：

  • 比赛的时候感觉html彻底崩了，读了好几遍题目没有读懂里面几个单词的意思，一直以为是要去重的所以连样例也没读懂但好多人都过了也不懂，反正当时就懵逼的一批这也是掉大分的罪魁祸首（）；
  • 感觉去重的话可能是个超级大容斥加筛法；
  • 赛后发题源秒懂这就是二分的签到题（）；
  • 对每次折半询问一个数，在表里算出不大于它的数的个数；
  • 复杂度O(nlogmn),让我们一起学习二分吧；

AC code：

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
int main(){
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif

    ll n,m,k;
    cin>>n>>m>>k;
    if(n<m) swap(n,m);
    ll l=1,r=m*n;
    while(l<r){
        ll tmp=0;
        ll x=l+(r-l)/2;
        for(int i=1;i<=n;i++){
            tmp+=min(m,x/i);
        }
        if(tmp<k) l=x+1;
        else r=x;
    }
    cout<<l<<endl;
    return 0;
}

Remark

  • 大概率是过不了线了感觉学的东西已经应付不过来了，如果没有进入的话正好留点时间给自己整理一下；
  • 没爆零就是win；

评论




博客内容遵循 [署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh)
本站使用 Volantis 作为主题
[Copyright © since 2023. All rights reserved](/)
字数统计：318.5k
<