#离线 #广度优先搜索 #构造 #优先队列bfs

A

题意

• 求a/r上取整

思路

• 小技巧，求上取整

代码

void solve(){
    int a,l,r;
    cin >> a >> l >> r;
    cout << (a+r-1)/r << endl;
}

B

题意

• 双排列序列，相同的两个数的最远距离

思路

• 开一个桶记录记录位置，同时更新答案
• 直接模拟

代码

void solve(){
    int n;
    cin >> n;
    vector<int> a(n+10);
    int ans=0;
    for(int i=1;i<=2*n;i++){
        int tmp;
        cin >> tmp;
        if(a[tmp]==0) a[tmp]=i;
        else ans=max(ans,i-a[tmp]+1);
    }
    cout << ans << endl;
}

C

• 二分也好久没写了，发病了，二分的右界找错两次

题意

• 长为n的序列，按照如下规则攻击
  • 初始攻击力为1
  • 连续攻击攻击力+1，否则攻击力重置为1
• 要攻击多少次才能使得序列所有值均小于等于0

思路

• 攻击序列是等差数列
• 连续攻击一个元素是最优的
• 对于每一个元素二分攻击次数就行

代码

ll check(ll n){
    ll l=1,r=(ll)sqrt(n*2)+1;
    while(l<=r){
        // if(n==22) cout << l << ' ' << r << endl;
        ll mid=(r+l)/2;
        if(mid*(mid+1)/2>=n){
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    // cout << l << endl;
    return l;
}

void solve(){
    int n;
    cin >> n;
    ll ans=0;
    for(int i=1;i<=n;i++){
        ll tmp;
        cin >> tmp;
        ans+=check(tmp);
    }
    cout << ans << endl;

}

D

题意

• 裸搜索，没啥好记录的

思路

• 纯白给

代码

vector<int> G[202020];
bool sb[202020];
int vis[202020];
vector<int> ans;

void dfs(int x,int fa){
    vis[x]=1;
    ans.push_back(x);
    for(auto i:G[x]){
        if(i==fa||sb[i]||vis[i]) continue;
        dfs(i,x);
    }
}

void solve(){
    int n,m,x;
    cin >> n >> m >> x;
    for(int i=0;i<x;i++){
        int tmp;
        cin >> tmp;
        sb[tmp]=1;
    }
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,-1);
    sort(ans.begin(),ans.end());
    for(auto i:ans){
        cout << i << ' ' ;
    }
    cout << endl;
}

E

• 构造……奇偶判断

题意

• 一次攻击可以将相邻的两个元素-1，构造长为n的序列，使得序列元素的和为a，并且恰好k次最优攻击使得序列所有元素为0

思路

• 任何一次攻击可以使得a-1或者a-2
• 对于已知的k一定可以判断需要几次-1和-2，如果全部-1或-2都超出就直接寄了
• 然后判柱子
• 如果偶数柱子-2平铺，-1放最后一根
• 如果奇数柱子-2平铺前n-1根，-1放最后一根
• 如果平铺不够直接寄
• 最后n=1需要特判

代码

void solve(){
    int n,a,k;
    cin >> n >> a >> k;
    vector<int> ans(n+10);
    if(n==1) cout << (a==k?k:-1) << endl;
    else if(a-k<0||2*k-a<0) cout << -1 << endl;
    else{
        if(n%2){
            if((n-1)/2>a-k) cout << -1 << endl;
            else{
                int bas=2*(a-k)/(n-1);
                int res=2*(a-k)%(n-1);
                for(int i=1;i<=n&&res;i++){
                    ans[i]++;
                    res--;
                }
                for(int i=1;i<=n-1;i++) cout << ans[i]+bas << ' ';
                cout << 2*k-a << endl;
            }
        }else{
            if(n/2>a-k) cout << -1 << endl;
            else{
                int bas=2*(a-k)/n;
                int res=2*(a-k)%n;
                for(int i=1;i<=n&&res;i++){
                    ans[i]++;
                    res--;
                }
                for(int i=1;i<=n;i++) cout << ans[i]+bas+(i==n?2*k-a:0) << ' ';
                cout << endl;
            }            
        }
    }
}

F

题意

• n*m地图，每个点有自己的val
• 在第一行撒伤害为x毒，毒会干掉小于自己的值并向四个方向传播
• 一共q次询问，每次给出初始毒x

思路一

• 观察发现，随着x增大，只会增加一些点被抬走
• 把所有询问存下来，按升序排序
• 然后做一个按血量的优先队列bfs
• 入队是无条件的

代码一

struct ty{
    int x,y,val;
    bool operator<(const ty &a) const {
        return val>a.val;
    } 
};

vector<ty> mp;
vector<pii> qr;
bool vis[550][550];
int a[550][550];
int ans[202020];
int dir[4][2]={0,1,1,0,0,-1,-1,0};

void solve(){
    int n,m,q;
    cin>> n >> m >> q;
    priority_queue<ty> pq;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ty tmp;
            cin >> a[i][j];
            tmp.x=i,tmp.y=j,tmp.val=a[i][j];
            mp.push_back(tmp);
            if(i==1) pq.push(tmp);
        }
    }
    for(int i=1;i<=q;i++){
        ll x;
        cin>>x;
        qr.push_back({x,i});
    }
    sort(qr.begin(),qr.end());
    ll sum=0;
    for(auto [x,id]:qr){
        while(!pq.empty()&&pq.top().val<=x){
            int X=pq.top().x;
            int Y=pq.top().y;
            int v=pq.top().val;
            pq.pop();
            if(vis[X][Y]) continue;
            vis[X][Y]=1;
            sum++;
            for(int i=0;i<4;i++){
                int tx=X+dir[i][0];
                int ty=Y+dir[i][1];
                if(tx<1||ty<1||tx>n||ty>m||vis[tx][ty]) continue;
                pq.push({tx,ty,a[tx][ty]});
            }
        }
        ans[id]=sum;
    }
    for(int i=1;i<=q;i++) cout << ans[i] << endl;    
}

思路二

• 硬搞
• 依然离线，同时把所有点也升序排序
• 然后把所有点依次加入，维护并查集，记录被覆盖的点数
• 同时并查集维护每个集合的size和是否和第一行联通

代码二

ll ans;
vector<pii> mp;
vector<pii> qr;
int fa[550*550];
int siz[550*550];
bool top[550*550];
bool vis[550*550];
int res[202020];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }

void merge(int x,int y){
    int rx=find(x),ry=find(y);
    if(rx==ry) return;
    if(siz[rx]>siz[ry]) swap(rx,ry);
    fa[rx]=ry;
    if(top[rx]&&!top[ry]) ans+=siz[ry];
    if(top[ry]&&!top[rx]) ans+=siz[rx];
    siz[ry]+=siz[rx];
    top[ry]=top[ry]||top[rx];
}

void solve(){
    int n,m,q;
    cin>> n >> m >> q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int id=i*(m+1)+j;
            fa[id]=id;
            siz[id]=1;
            top[id]=(i==1);
            ll val;
            cin>>val;
            mp.push_back({val,id});
        }
    }
    for(int i=1;i<=q;i++){
        ll x;
        cin>>x;
        qr.push_back({x,i});
    }
    sort(mp.begin(),mp.end());
    sort(qr.begin(),qr.end());
    int j=0;
    for(auto [x,id]:qr){
        while(j<mp.size()&&mp[j].first<=x){
            int u=mp[j].second;
            int nx=u/(m+1);
            int ny=u%(m+1);
            vis[u]=1;
            if(nx==1) ans++;
            for(int k=0;k<4;k++){
                int tx=nx+dir[k][0];
                int ty=ny+dir[k][1];
                if(tx<1||tx>n||ty<1||ty>m) continue;
                int v=tx*(m+1)+ty;
                if(vis[v]) merge(u,v);
            }
            j++;
        }
        res[id]=ans;
    }
    for(int i=1;i<=q;i++) cout << res[i] << endl;
}