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=falseint 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  排序+背包dpcin>>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;
}

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   0k  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   0k  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.3e5int 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

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