2024 暑假友谊赛 2

Tree Queries - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:LCA好题，也有看见用时间戳写的，不是很明白. 用LCA非常好写。

要想到,给出k个节点，要确定一条路径，使得给出的k个点要么在路径上，要么和路径中某点的距离为1。那么这个路径的尽头肯定是选k个点中最深的点x。因为只要达到了最深的点x，再多选点也没有意义了。确定了最深点之后，那么k个点和最深点x的LCA必然在路径上。这个时候只需要判点u和LCA(u,x)的距离即可.

int n,q;
vector<int> vct[200005];
int dep[200005];
int fa[200005][19];     (1<<18)=2.6e5 足够
void dfs(int u,int father){         o(nlogn)
    dep[u]=dep[father]+1;
    fa[u][0]=father;
    跳一半，再跳另一半
    for(int i=1;i<=18;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(auto v:vct[u]) if(v!=father) dfs(v,u);
}
int lca(int u,int v){               o(logn)
    if(dep[v]>dep[u]) swap(u,v);
    跳到同一层
    for(int i=18;i>=0;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return v;
    u,v一起往上跳到LCA下一层
    for(int i=18;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
求树中任意两点的距离. o(logn)--美妙
int dist(int u,int v){ return dep[u]+dep[v]-2*dep[lca(u,v)]; }
Tree Queries
https://www.luogu.com.cn/problem/CF1328E
void solve(){       补H--先学LCA.
    cin>>n>>q;
    for(int i=1;i<=n-1;i++){    双向建边
        int u,v; cin>>u>>v;
        vct[u].emplace_back(v);
        vct[v].emplace_back(u);
    }
    dfs(1,0);
    while(q--){
        int k,maxn=-1;
        vector<int> ask;
        cin>>k;
        for(int i=1;i<=k;i++){
            int x; cin>>x;
            if(maxn==-1||dep[x]>dep[maxn]) maxn=x;
            ask.emplace_back(x);
        }
        bool check=true;
        //for(auto v:ask) if(dist(v,lca(maxn,v))>1) check=false;  这种方法更通用
        这里这样判距离是因为,1到u的那条路径中的u必然是选最深的点maxn.
        那么点ask[i]和maxn的LCA必然在这条路径上,如果ask[i]和lca(maxn,ask[i])的距离<=1都是满足条件的
        for(auto v:ask){         另一种不用dist的判法,如果lca(maxn,v)不是v也不是v的fa,check=false
            int lca0=lca(maxn,v);
            if(lca0!=v&&lca0!=fa[v][0]) check=false;
            if(!check) break;
        }
        if(check) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

[ABC216F] Max Sum Counting - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:按a从小到大排序,这样依次遍历的最大值必定是当前ai,那么意味着前面的数字bi可以任意取(注意当前bi是必取的) 这个时候只需要考虑在<=i以前的b数组能组出多少个小于等于ai的数字.注意加的是dp[j-x],而不是dp[j],因为dp[j-x]才是当前满足条件的个数,dp[j]可能在之前就组合出来过，并不是当前合法的.

int p=998244353;
int n;
pair<int,int> arr[5005];
int dp[5005];    虽然sumb比较大,但是a最大只有5000,太大就不用考虑了.
题意:给出两个有n个元素的序列a,b。在{1,2,3,...,n}的非空子集中,有多少个子集满足max(i∈S)ai ≥ (i∈S)∑bi
[ABC216F] Max Sum Counting
https://www.luogu.com.cn/problem/AT_abc216_f
思路: 按a从小到大排序,这样依次遍历的最大值必定是当前ai,那么意味着前面的数字bi可以任意取(注意当前bi是必取的)
这个时候只需要考虑在<=i以前的b数组能组出多少个小于等于ai的数字.
注意加的是dp[j-x],而不是dp[j],因为dp[j-x]才是当前满足条件的个数,dp[j]可能在之前就组合出来过，并不是当前合法的.
void solve(){           补F  排序+背包dp
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i].first;
    for(int i=1;i<=n;i++) cin>>arr[i].second;
    sort(arr+1,arr+n+1);
    int ans=0;
    dp[0]=1;
    for(int i=1;i<=n;i++){
        int x=arr[i].second;
        for(int j=5000;j>=arr[i].second;j--){
            if(dp[j-x]) {
                (dp[j]+=dp[j-x])%=p;
                if(j<=arr[i].first) (ans+=dp[j-x])%=p;  ans加的是dp[j-x],而不是dp[j]!
            }
        }
    }
    cout<<ans;
}

[ABC344F] Earn to Advance - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:主要是难点在①dp数组的定义,②对mx,my的理解,③步数小优先否则剩钱多优先.

①定义dp[i][j][x][y]为,走到点(i,j)时,并且路径上p最大的坐标为(x,y),停下最少的次数

  定义g[i][j][x][y]为,走到点(i,j)时,并且路径上p最大的坐标为(x,y),剩下最多的钱数

②dp定义中路径上p最大的坐标(x,y)是严格遵守的,下一个要更新的点(i+1,j) or (i,j+1)也是在路径上的，也需要把他们考虑上，更新的时候更新mx和my!!不然枚举到(i+1,j) or (i,j+1)的时候(i,jx,y)的状态会少了，因为(x,y)是枚举到当前(i,j)的。

③步数少肯定是优先的，因为在每一步剩余的钱不会超过p[x][y]。就算步数少了一步，钱剩0，也是更优的，因为只要花1步必然可以把少了的钱补回来。

P8612 [蓝桥杯 2014 省 AB] 地宫取宝 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)--四维dp

int n;
int p[85][85];
int r[85][85],d[85][85];
int dp[85][85][85][85]; 定义dp[i][j][x][y]为,走到点(i,j)时,并且路径上p最大的坐标为(x,y),停下最少的次数
int g[85][85][85][85]; 定义g[i][j][x][y]为,走到点(i,j)时,并且路径上p最大的坐标为(x,y),剩下最多的钱数
[ABC344F] Earn to Advance
https://www.luogu.com.cn/problem/AT_abc344_f
https://atcoder.jp/contests/abc344/submissions/55754142
https://www.luogu.com.cn/problem/P8612--四维dp
void solve(){           补I    四维dp
    cin>>n;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>p[i][j];
    for(int i=1;i<=n;i++) for(int j=1;j<=n-1;j++) cin>>r[i][j];
    for(int i=1;i<=n-1;i++) for(int j=1;j<=n;j++) cin>>d[i][j];
    memset(dp,0x3f3f3f3f,sizeof(dp));
    //for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int x=1;x<=i;x++) for(int y=1;y<=j;y++) dp[i][j][x][y]=LONG_LONG_MAX/2;
    dp[1][1][1][1]=0;
    int ans=LONG_LONG_MAX;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int x=1;x<=i;x++){
                for(int y=1;y<=j;y++){
                    if(i<n){  往下走
                        int mx=x,my=y;
                        if(p[i+1][j]>p[mx][my]) mx=i+1,my=j; key!
                        int t,left;
                        g[i][j][x][y]>=d[i][j]?t=0:t=(d[i][j]-g[i][j][x][y]-1)/p[x][y]+1;
                        g[i][j][x][y]>=d[i][j]?left=g[i][j][x][y]-d[i][j]:left=t*p[x][y]+g[i][j][x][y]-d[i][j];
                        t+=dp[i][j][x][y];
                        if(t<dp[i+1][j][mx][my] || t==dp[i+1][j][mx][my]&&left>g[i+1][j][mx][my]) dp[i+1][j][mx][my]=t,g[i+1][j][mx][my]=left;
                    }
                    if(j<n){ 往右走
                        int mx=x,my=y;
                        if(p[i][j+1]>p[mx][my]) mx=i,my=j+1;  key!
                        int t,left;
                        g[i][j][x][y]>=r[i][j]?t=0:t=(r[i][j]-g[i][j][x][y]-1)/p[x][y]+1;
                        g[i][j][x][y]>=r[i][j]?left=g[i][j][x][y]-r[i][j]:left=t*p[x][y]+g[i][j][x][y]-r[i][j];
                        t+=dp[i][j][x][y];
                        if(t<dp[i][j+1][mx][my] || t==dp[i][j+1][mx][my]&&left>g[i][j+1][mx][my]) dp[i][j+1][mx][my]=t,g[i][j+1][mx][my]=left;
                    }
                    if(i==n&&j==n) ans=min(ans,dp[i][j][x][y]);
                }
            }
        }
    }
    cout<<ans+2*n-2;
}

3-Coloring - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:想到了就不难的交互题.

因为有三种颜色,ban其中一种,那么可以交替使用1,2颜色,因为1,2其中一个总是能选到的
那么可以构造出
1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1
这种相隔的网格,如果1多次被ban,那2填完之后,剩下的位置填1,3都是无所谓的
并且1,2其中一个总会先填完，剩下的格子除了填2,都是合法的.

int n;
int x1=1,yy1=1,x2=1,y2=2;
bool check1=true,check2=true;
void process1(){
    if(check1){
        cout<<1<<" "<<x1<<" "<<yy1<<endl;
        cout.flush();
        if(yy1+2<=n) yy1+=2;
        else if(x1+1<=n) x1+=1,x1&1?yy1=1:yy1=2;
        else check1=false;
    }
    else{
        cout<<3<<" "<<x2<<" "<<y2<<endl;
        cout.flush();
        if(y2+2<=n) y2+=2;
        else x2+=1,x2&1?y2=2:y2=1;
    }
}
void process2(){
    if(check2){
        cout<<2<<" "<<x2<<" "<<y2<<endl;
        cout.flush();
        if(y2+2<=n) y2+=2;
        else if(x2+1<=n) x2+=1,x2&1?y2=2:y2=1;
        else check2=false;
    }
    else{
        cout<<3<<" "<<x1<<" "<<yy1<<endl;
        cout.flush();
        if(yy1+2<=n) yy1+=2;
        else x1+=1,x1&1?yy1=1:yy1=2;
    }
}
void process3(){
    if(check1) process1();
    else process2();
}
3-Coloring
https://www.luogu.com.cn/problem/CF1503B
因为有三种颜色,ban其中一种,那么可以交替使用1,2颜色,因为1,2其中一个总是能选到的
那么可以构造出
1212
2121
1212
2121
这种相隔的网格,如果1多次被ban,那2填完之后,剩下的位置填1,3都是无所谓的
并且1,2其中一个总会先填完，剩下的格子除了填2,都是合法的.  有意思..
void solve(){           补C--互动题-构造思维
    cin>>n;
    int k=n*n;
    while(k--){
        int ban; cin>>ban;
        if(ban==1) process2();
        else if(ban==2) process1();
        else if(ban==3) process3();
    }
}

Walk on Matrix - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:构造题。赛时没想到怎么做。

题意:现在给出解决该问题的一个错误dp算法(见题面图片)，
请构造一组数据,hack掉这个算法,使得正确答案比错误的输出恰好大k。
这个错误的dp算法认为,dp[i][j]的取值是越大越好的,这是不对的
当现在是dp=max(1000,0111)=1000但下一个是0111---那么1000&0111=0，0111&0111=0111,这就hack了,算法取了更大的1000,但是在此处0111是更优的.
按照这个思路,可以思考构造一个大数字X,并且X+k就不会发生进位.   k< X <3e5
那么可以取X=1<<17=1.3e5，在二进制下加k是不会进位的,那么X+k为10000..k,且X+k<3e5
X+k  X   0
 k  X+k  k
这样构造的话，dp[2][2]=max(k,X)=X, dp[2][3]=X&k=0;---利用了hack的点.
答案应该是dp[2][2]=k, dp[2][3]=k&k=k

题意:现在给出解决该问题的一个错误dp算法(见题面图片)，
请构造一组数据,hack掉这个算法,使得正确答案比错误的输出恰好大k。
Walk on Matrix
https://www.luogu.com.cn/problem/CF1332D
这个错误的dp算法认为,dp[i][j]的取值是越大越好的,这是不对的
当现在是dp=max(1000,0111)=1000但下一个是0111---那么1000&0111=0，0111&0111=0111,这就hack了
按照这个思路,可以思考构造一个大数字X,并且X+k就不会发生进位.   k< X <3e5
那么可以取X=1<<17=1.3e5，在二进制下加k是不会进位的,那么X+k为10000..k,且X+k<3e5
X+k  X   0
 k  X+k  k
这样构造的话，dp[2][2]=max(k,X)=X, dp[2][3]=X&k=0;---利用了hack的点.
但答案是dp[2][2]=k, dp[2][3]=k&k=k
void solve(){           B  how??
    cout<<(1ll<<17);  1.3e5
    int k; cin>>k;
    cout<<2<<" "<<3<<endl;
    cout<<(1ll<<17)+k<<" "<<(1ll<<17)<<" "<<0<<endl;
    cout<<k<<" "<<(1ll<<17)+k<<" "<<k<<endl;
}

[ARC134B] Reserve or Reverse - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:把字符和下标都存到pq中，并且按字符升序排序,下标降序排序.并且维护一个front和back，front就是i，back是交换过的点的最近那个。因为题目的实质是可以进行多次交换，但是交换的区间是缩小的.

int n;
string str;
typedef struct myp{
    char first;
    int second;
    bool operator <(const myp &x) const{
        if(x.first!=first) return first>x.first;
        return second<x.second;
    }
}myp;
priority_queue<myp> pq;
[ARC134B] Reserve or Reverse
https://www.luogu.com.cn/problem/AT_arc134_b
void solve(){       D           ....顺序处理..
    cin>>n>>str;
    int back=n-1;
    for(int i=0;i<n;i++) pq.emplace((myp){str[i],i});
    for(int i=0;i<n;i++){
        if(back<i) break;
        while(pq.size()&&(pq.top().second>back||pq.top().second<i)) pq.pop();
        if(pq.size()&&str[i]>str[pq.top().second]){
            swap(str[i],str[pq.top().second]);
            back=pq.top().second,pq.pop();
        }
    }
    cout<<str;
}

还没补出来的题：

[ABC344F] Earn to Advance - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)--四维dp---done

Chemical table - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)--构造，并查集