做鼻翼整形整形的网站,买虚机送网站建设,做外账要登什么网站,wordpress红黑主题Tree Queries - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:LCA好题#xff0c;也有看见用时间戳写的#xff0c;不是很明白. 用LCA非常好写。
要想到,给出k个节点#xff0c;要确定一条路径#xff0c;使得给出的k个点要么在路径上#xff0c;要么和路径中某点的…Tree Queries - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:LCA好题也有看见用时间戳写的不是很明白. 用LCA非常好写。
要想到,给出k个节点要确定一条路径使得给出的k个点要么在路径上要么和路径中某点的距离为1。那么这个路径的尽头肯定是选k个点中最深的点x。因为只要达到了最深的点x再多选点也没有意义了。确定了最深点之后那么k个点和最深点x的LCA必然在路径上。这个时候只需要判点u和LCA(u,x)的距离即可.
int n,q;
vectorint vct[200005];
int dep[200005];
int fa[200005][19]; (118)2.6e5 足够
void dfs(int u,int father){ o(nlogn)dep[u]dep[father]1;fa[u][0]father;跳一半再跳另一半for(int i1;i18;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 i18;i0;i--) if(dep[fa[u][i]]dep[v]) ufa[u][i];if(uv) return v;u,v一起往上跳到LCA下一层for(int i18;i0;i--) if(fa[u][i]!fa[v][i]) ufa[u][i],vfa[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.cinnq;for(int i1;in-1;i){ 双向建边int u,v; cinuv;vct[u].emplace_back(v);vct[v].emplace_back(u);}dfs(1,0);while(q--){int k,maxn-1;vectorint ask;cink;for(int i1;ik;i){int x; cinx;if(maxn-1||dep[x]dep[maxn]) maxnx;ask.emplace_back(x);}bool checktrue;//for(auto v:ask) if(dist(v,lca(maxn,v))1) checkfalse; 这种方法更通用这里这样判距离是因为,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,checkfalseint lca0lca(maxn,v);if(lca0!vlca0!fa[v][0]) checkfalse;if(!check) break;}if(check) coutYESendl;else coutNOendl;}
}
[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 p998244353;
int n;
pairint,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 排序背包dpcinn;for(int i1;in;i) cinarr[i].first;for(int i1;in;i) cinarr[i].second;sort(arr1,arrn1);int ans0;dp[0]1;for(int i1;in;i){int xarr[i].second;for(int j5000;jarr[i].second;j--){if(dp[j-x]) {(dp[j]dp[j-x])%p;if(jarr[i].first) (ansdp[j-x])%p; ans加的是dp[j-x],而不是dp[j]!}}}coutans;
}
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 x11,yy11,x21,y22;
bool check1true,check2true;
void process1(){if(check1){cout1 x1 yy1endl;cout.flush();if(yy12n) yy12;else if(x11n) x11,x11?yy11:yy12;else check1false;}else{cout3 x2 y2endl;cout.flush();if(y22n) y22;else x21,x21?y22:y21;}
}
void process2(){if(check2){cout2 x2 y2endl;cout.flush();if(y22n) y22;else if(x21n) x21,x21?y22:y21;else check2false;}else{cout3 x1 yy1endl;cout.flush();if(yy12n) yy12;else x11,x11?yy11:yy12;}
}
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--互动题-构造思维cinn;int kn*n;while(k--){int ban; cinban;if(ban1) process2();else if(ban2) process1();else if(ban3) process3();}
}
Walk on Matrix - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:构造题。赛时没想到怎么做。
题意:现在给出解决该问题的一个错误dp算法(见题面图片)
请构造一组数据,hack掉这个算法,使得正确答案比错误的输出恰好大k。
这个错误的dp算法认为,dp[i][j]的取值是越大越好的,这是不对的
当现在是dpmax(1000,0111)1000但下一个是0111---那么100001110011101110111,这就hack了,算法取了更大的1000,但是在此处0111是更优的.
按照这个思路,可以思考构造一个大数字X,并且Xk就不会发生进位. k X 3e5
那么可以取X1171.3e5在二进制下加k是不会进位的,那么Xk为10000..k,且Xk3e5
Xk X 0k Xk k
这样构造的话dp[2][2]max(k,X)X, dp[2][3]Xk0;---利用了hack的点.
答案应该是dp[2][2]k, dp[2][3]kkk
题意:现在给出解决该问题的一个错误dp算法(见题面图片)
请构造一组数据,hack掉这个算法,使得正确答案比错误的输出恰好大k。
Walk on Matrix
https://www.luogu.com.cn/problem/CF1332D
这个错误的dp算法认为,dp[i][j]的取值是越大越好的,这是不对的
当现在是dpmax(1000,0111)1000但下一个是0111---那么100001110011101110111,这就hack了
按照这个思路,可以思考构造一个大数字X,并且Xk就不会发生进位. k X 3e5
那么可以取X1171.3e5在二进制下加k是不会进位的,那么Xk为10000..k,且Xk3e5
Xk X 0k Xk k
这样构造的话dp[2][2]max(k,X)X, dp[2][3]Xk0;---利用了hack的点.
但答案是dp[2][2]k, dp[2][3]kkk
void solve(){ B how??cout(1ll17); 1.3e5int k; cink;cout2 3endl;cout(1ll17)k (1ll17) 0endl;coutk (1ll17)k kendl;
}
[ARC134B] Reserve or Reverse - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:把字符和下标都存到pq中并且按字符升序排序,下标降序排序.并且维护一个front和backfront就是iback是交换过的点的最近那个。因为题目的实质是可以进行多次交换但是交换的区间是缩小的.
int n;
string str;
typedef struct myp{char first;int second;bool operator (const myp x) const{if(x.first!first) return firstx.first;return secondx.second;}
}myp;
priority_queuemyp pq;
[ARC134B] Reserve or Reverse
https://www.luogu.com.cn/problem/AT_arc134_b
void solve(){ D ....顺序处理..cinnstr;int backn-1;for(int i0;in;i) pq.emplace((myp){str[i],i});for(int i0;in;i){if(backi) break;while(pq.size()(pq.top().secondback||pq.top().secondi)) pq.pop();if(pq.size()str[i]str[pq.top().second]){swap(str[i],str[pq.top().second]);backpq.top().second,pq.pop();}}coutstr;
}
还没补出来的题
[ABC344F] Earn to Advance - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)--四维dp
Chemical table - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)--构造并查集
