月刊可以用什么网站做,简单介绍家乡网页html代码,运城网站制作路90,自适应网站建设选哪家1900C - Anjis Binary Tree 题意#xff1a;
凯克西奇一直被安吉冷落。通过一个共同的朋友#xff0c;他发现安吉非常喜欢二叉树#xff0c;于是决定解决她的问题#xff0c;以引起她的注意。Anji 给了 Keksic 一棵有 n个顶点的二叉树。顶点 1 是根#xff…1900C - Anjis Binary Tree 题意
凯克西奇一直被安吉冷落。通过一个共同的朋友他发现安吉非常喜欢二叉树于是决定解决她的问题以引起她的注意。Anji 给了 Keksic 一棵有 n个顶点的二叉树。顶点 1 是根没有父顶点。所有其他顶点都有一个父顶点。每个顶点最多可以有 2个子顶点、一个左子顶点和一个右子顶点。对于每个顶点安吉都会告诉凯西奇它的左子和右子的索引或者告诉他它们不存在。
此外每个顶点上都有一个字母 即 U、L 或 R。
克克西奇从根开始下棋他的每一步都是这样走的
如果当前顶点上的字母是 U他就移动到它的父顶点。如果它不存在他就什么也不做。如果当前顶点上的字母是 L则移动到其左侧子顶点。如果它不存在则他什么也不做。如果当前顶点上的字母是 R则移动到其右边的子顶点。如果它不存在则他什么也不做。
在移动之前他可以执行以下操作选择任意一个节点并用另一个节点替换写在上面的字母。
我们想知道的是当他开始旅行时他将在某一点到达一片叶子那么他在旅行前需要做的操作的最小数目。叶子是一个没有子顶点的顶点。他到达哪片叶子并不重要。需要注意的是他是否会停留在叶子上并不重要他只需要移动到叶子上。此外他需要移动多少次才能到达一片叶子也无关紧要。
帮助 Keksic 解开安吉的树这样他就能赢得她的芳心让她来到恰恰克。 思路转化为到叶子结点最短路若顶点字母是‘L’则到达左孩子路径长度为0若顶点是‘R’则到达右边孩子长度为0否则都是1代表了需要修改求到达叶子结点路径最小值。 // Problem: C. Anjis Binary Tree
// Contest: Codeforces - Codeforces Round 911 (Div. 2)
// URL: https://codeforces.com/contest/1900/problem/C
// Memory Limit: 256 MB
// Time Limit: 2500 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl \n
const LL maxn 4e057;
const LL N 5e0510;
const LL mod 1e097;
const int inf 0x3f3f3f;
const LL llinf 5e18;
typedef pairint,intpl;
priority_queueLL , vectorLL, greaterLL mi;//小根堆
priority_queueLL ma;//大根堆
LL gcd(LL a, LL b){return b 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){for(int i 0 ; i n ; i ){a[i] 0;}
}
struct Node{int l , r;
}e[N];
void solve()
{cin n;string s;cin s;s s;
// cout s[1]endl;for(int i 1 ; i n ; i ){cin e[i].l e[i].r; }int ans inf;queue pairint,intq;q.push({1 , 0});while(!q.empty()){auto tmp q.front();q.pop();int id tmp.x , dis tmp.y;
// cout id dis endl;if(e[id].l ! 0){int nex e[id].l;if(s[id] ! L){q.push({nex , dis 1});}else{q.push({nex , dis});}}if(e[id].r ! 0){int nex e[id].r;if(s[id] ! R){q.push({nex , dis 1});}else{q.push({nex , dis});} }if(e[id].l 0 e[id].r 0){ans min(ans , dis);}}cout ans endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t1;cint;while(t--){solve();}return 0;
}1900D - Small GCD
太菜了导致坐牢一个半小时没想到能够预处理因子的价值下次不会再犯了 题意设 a 、 b 和 c 为整数。函数 f(a,b,c) 的定义如下将数字 a 、 b 、 c 排序为 a≤b≤c 。然后返回 gcd(a,b) 其中 gcd(a,b) 表示整数 a 和 b 的 最大公约数 (GCD)。给你一个由 n 个元素组成的数组 a 。计算每个 i 、 j 、 k 的 f(ai,aj,ak) 和使得 1≤ijk≤n 。更正式地说计算
。 思路当对a数组进行排序以后会发现原式子的k变成了一个无效的东西因为。原式子变为
再转化一下得到.。对于这种所有区间求和问题考虑右端点递增然后思考如何去维护左侧所有区间的信息。首先我们如果单纯的两两求gcd肯定是不行的观察数据后发现a数组的数据很小也就是说a的因子个数很小。而两个数的gcd也就是他们的最大公共因子。因此可以考虑统计区间内所有因子的个数然后对于每个右端点而言遍历其所有因子区间之和就是右端点的因子大小 * 区间内该因子的个数的总和。但是仔细想想之后发现是有重复的假如当前因子是2用2 * 区间内2的因子个数是不正确的因为有2这个因子也必然会有1这个因子。gcd是两个数的最大公共因子所以统计因子2时会把1这个因子给撤销掉后面任意因子也是同理。也就是说2这个因子的实际价值不是2而是1。3也是同理3的实际价值需要减去1的实际价值 而6的实际价值需要减去1、2、3实际价值。因此对于任意一个因子而言其实际价值需要需要减去其所有不为他本身的因子的实际价值。 对于每个数的因子每个因子的实际价值都是可以预处理出来的。做的时候只需要过一下公式即可。 // Problem: D. Small GCD
// Contest: Codeforces - Codeforces Round 911 (Div. 2)
// URL: https://codeforces.com/contest/1900/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl \n
const LL maxn 4e057;
const LL N 1e0510;
const LL mod 1e097;
const int inf 0x3f3f;
const LL llinf 5e18;
typedef pairint,intpl;
priority_queueLL , vectorLL, greaterLL mi;//小根堆
priority_queueLL ma;//大根堆
LL gcd(LL a, LL b){return b 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){for(int i 0 ; i n ; i ){a[i] 0;}
}
int cnt[N];
vectorintyinzi[100010];
int val[N];
void solve()
{memset(cnt , 0 , sizeof cnt);cin n;for(int i 0 ; i n ; i )cin a[i];sort(a , a n);LL ans 0;for(int i 0 ; i n - 1; i ){LL sum 0;for(auto it : yinzi[a[i]])sum 1LL * val[it] * cnt[it];ans sum * (n - i - 1);for(auto it : yinzi[a[i]]){cnt[it];} }cout ans endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t1;int maxx -1;auto cmp [](int x , int y){return x y;};for(int i 1 ; i 100000 ; i ){val[i] i;yinzi[i].pb(i);}for(int i 1 ; i 100000; i ){for(int j i * 2; j 100000 ; j i){yinzi[j].pb(i);val[j] - val[i];}}cint;while(t--){solve();}return 0;
}E - Transitive Graph 补的时候发现就是个SCC缩点 DAG图上DP问题 题意给你一个有向图 G 其中有 n 个顶点和 m条边。
最初图 H与图 G相同。然后您决定执行以下操作
如果存在由顶点 a 、 b 、 c 和 H 组成的三重顶点且存在一条从 a 到 b 的边和一条从 b 到 c 的边但没有从 a 到 c 的边则添加一条从 a 到 c的边。只要存在这样的三边形就重复上一步。
注意执行上述操作后 H中的边的数量最多可达 。
您还在图 H的顶点上写了一些值。更确切地说在顶点 i 上写入了 ai的值。
考虑一条由 k个顶点组成的简单路径。索引为 v1,v2,…,vk 的个不同顶点组成的简单路径。这条路径的长度为 k 。该路径的值定义为 。
如果图中没有其他更长的简单路径那么这条简单路径就是最长的。
在 H中所有最长的简单路径中找出数值最小的一条。 思路观察题目中的操作其实就是把有向图中一条路径上的点全部两两相连其实这样操作在求最长简单路径时没有任何意义因为a到c增加的边在求最长路径时必然会被a到bb到c这两条边代替。这么做保证了能从一个强连通分量上的任意一点连到其他强连通分量上的任意一点。因此本题就变成了给定一个有向图求最长简单路径中权值最小的那一条。直接强连通分量缩点 图上DP就行用tarjan求出scc然后按照逆拓扑序dp就行。 // Problem: E. Transitive Graph
// Contest: Codeforces - Codeforces Round 911 (Div. 2)
// URL: https://codeforces.com/contest/1900/problem/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl \n
const LL maxn 4e057;
const LL N 5e0510;
const LL mod 1e097;
const int inf 0x3f3f;
const LL llinf 5e18;
typedef pairint,intpl;
priority_queueLL , vectorLL, greaterLL mi;//小根堆
priority_queueLL ma;//大根堆
LL gcd(LL a, LL b){return b 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
LL a[N];
vectorinte[N];
int dfn[N] , low[N] , ins[N] , idx 0 , cnt 0, bel[N];//dfn : dfs的时间戳 low : 子树能跳到的最上方的点 bel : 结点位于哪块强连通分量上
stackintstk;
int out[N];
int x[N] , y[N] , ty[N] , ans 0;
pairLL,LLdp[N];
void init(int n){idx cnt 0;for(int i 0 ; i n ; i ){a[i] 0 , low[i] 0 , ins[i] 0 , bel[i] 0 , dfn[i] 0 , e[i].clear();}
}
void tarjan(int u , int fa){//无向图需要fa ! udfn[u] low[u] idx;//dfs序中的顺序ins[u] true;//是否在栈当中stk.push(u);//未被切掉的点for(auto v : e[u]){if(!dfn[v]){tarjan(v , u);low[u] min(low[u] , low[v]);}else{//被访问过了if(ins[v]){low[u] min(low[u] , dfn[v]);} }}if(dfn[u] low[u]){cnt ;int sz 0;LL ch 0;LL sum 0;dp[cnt] {0 , 0};while(true){int v stk.top();bel[v] cnt;ch ;sum a[v];ins[v] false;for(int w : e[v]){if(bel[w] ! cnt bel[w] ! 0){if(dp[bel[w]].x dp[cnt].x){dp[cnt] dp[bel[w]];}else if(dp[bel[w]].x dp[cnt].x dp[bel[w]].y dp[cnt].y){dp[cnt] dp[bel[w]];}}}stk.pop();if(v u){break;}}dp[cnt].x ch;dp[cnt].y sum;}
}
void solve()
{cin n m;mappairint,int,intmp;for(int i 1 ; i n ; i )cin a[i];for(int i 0 ; i m ; i ){int x , y;cin x y;if(mp.count({x , y}) || x y){continue;}else{e[x].pb(y);mp[{x,y}] 1;}}for(int i 1 ; i n ; i){if(!dfn[i]) tarjan(i , 0);}
/* for(int i 1 ; i n ; i ){cout bel[i] endl;}*/pairLL,LLans {0 , 0};for(int i 1 ; i cnt ; i ){if(dp[i].x ans.x){ans dp[i];}else if(dp[i].x ans.x dp[i].y ans.y){ans dp[i];}}init(n);cout ans.x ans.y endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t1;cint;while(t--){solve();}return 0;
}
