做网站的市场有那么大吗,如何做网站ppt,动画专业大学排名,小x导航正品A - Line Trip 题意#xff1a;有一条路#xff0c;可以用一条数线来表示。你位于数线上的点 0 #xff0c;你想从点 0 到点 x #xff0c;再回到点 0。你乘汽车旅行#xff0c;每行驶 1个单位的距离要花费 1 升汽油。当您从点 0出发时#xff0c;汽车已加满油(油箱中的…A - Line Trip 题意有一条路可以用一条数线来表示。你位于数线上的点 0 你想从点 0 到点 x 再回到点 0。你乘汽车旅行每行驶 1个单位的距离要花费 1 升汽油。当您从点 0出发时汽车已加满油(油箱中的油量已达到最大值)。在 a1,a2,…,an点有 n 个加油站。到达加油站后为汽车加满油。注意只能在加油站加油 0 和 x点没有加油站。你必须计算出你的汽车油箱的最小容积(以升为单位)这样你才能从点 0行驶到点 x 并返回到点 0 。 思路求一下相邻加油站的距离最大值即可注意最后一个加油站要先到点x再回来。 // Problem: A. Line Trip
// Contest: Codeforces - Educational Codeforces Round 158 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1901/problem/0
// 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 N1e0510;
const LL mod1e097;
typedef pairint,intpl;
priority_queueLL , vectorLL, greaterLL t;
priority_queueLL q;
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;}
}
void solve()
{cin n m;for(int i 1 ; i n ; i ){cin a[i];} int maxx (m - a[n]) * 2;for(int i 1 ; i n ;i ){maxx max(maxx , a[i] - a[i - 1]);}cout maxx 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;
}B - Chip and Ribbon 题意有一条带子被分成 n 个单元格从左到右编号为 1 到 n 。最初每个单元格中都写有一个整数 0。Monocarp在玩芯片游戏。游戏由几个回合组成。在第一轮中Monocarp 将芯片放入色带的 第一单元格。除了第一轮之外在每一轮中魔卡都会做以下两个动作中的恰好一个
将芯片移动到下一个单元格(例如如果芯片在 i 单元格则将其移动到 i1单元格)。如果芯片在上一格则无法进行此操作
选择任意一个 x单元格将芯片传送到该单元格。可以选择芯片当前所在的单元格。
每回合结束时写入芯片所在单元格的整数会增加 1。
Monocarp的目标是在某些回合中使第一个单元格中等于整数 c1 第二个单元格中等于整数 c2 ....第n个单元格中等于整数 cn。他希望尽可能少地传送芯片。
请帮助 Monocarp 计算他传送芯片的最少次数。 思路:对于一个连续的序列来说无需传送就能全部1因此此题变成了每轮操作能将[l ,r]单元格内的数加一求最小操作数。此题类似于Problem - C - Codeforces 可以发现所有左侧标红的即为选择的区间因此最小操作数就是统计标红的数量即。具体解析可以看该题题解。 // Problem: B. Chip and Ribbon
// Contest: Codeforces - Educational Codeforces Round 158 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1901/problem/B
// 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 N2e0510;
const LL mod1e097;
typedef pairint,intpl;
priority_queueLL , vectorLL, greaterLL t;
priority_queueLL q;
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;}
}
void solve()
{int n;cin n;for(int i 1 ; i n ; i ){cin a[i];} LL ans 0;for(int i 1 ; i n ; i ){if(a[i] a[i - 1]){ans a[i] - a[i - 1];}}cout ans - 1 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;
}C - Add, Divide and Floor 题意给你一个整数数组 a1,a2,…,an ( )。在一次操作中你可以选择一个整数 x ( )并用 ⌊⌋ 替换 ai ( ⌊y⌋ 表示将 y 舍入为最接近的整数)。 ⌊y⌋ 表示将 y 舍入为最接近的整数来替换从 1 到 n 的所有 i。请注意每次操作都会影响数组中的所有元素。打印使数组中所有元素相等所需的最小操作数。如果操作次数小于或等于 n则打印每次操作所选择的 x 。如果有多个答案则打印任意一个。 思路若最小的数通过操作等于最大的数那么其他数必然也相等。因此只需要看最小的和最大的即可。再考虑如何去操作观察可以发现其实x的大小没有用x的奇偶性可能会改变答案因此我们x的取值只设为0 1。如果最大值是偶数那么1不会使得结果更大否则可能会使得结果更大。 // Problem: C. Add, Divide and Floor
// Contest: Codeforces - Educational Codeforces Round 158 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1901/problem/C
// 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 N2e0510;
const LL mod1e097;
typedef pairint,intpl;
priority_queueLL , vectorLL, greaterLL t;
priority_queueLL q;
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;}
}
void solve()
{cin n;int maxx -1 , minn 1.5e9;for(int i 0 ; i n ; i ){cin a[i];maxx max(a[i] , maxx);minn min(minn , a[i]);}vectorint ans;while (minn ! maxx) {if (minn % 2 maxx % 2) {ans.push_back(0);} else if (maxx % 2 0) {ans.push_back(1);minn;maxx;} else {ans.push_back(0);}minn / 2;maxx / 2;}cout ans.size() \n;if ((int)ans.size() n) {for (int x : ans) {cout x ;}cout \n;}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t1;cint;while(t--){solve();}return 0;
}D - Yet Another Monster Fight 题意现有n头怪兽每个怪兽有的血量你需要发动一次魔法将所有怪兽打败。魔法规则如下第一轮将打中你选择的那头怪兽并扣除x的血量接下来每一轮魔法的伤害值减一并且打中那些未被打中的处于已被打中的怪兽的相邻怪兽。要求你可以选择任意第一轮打中的怪兽的情况下魔法的初始伤害的最小值。 思路首先考虑已知第一轮打中第 只怪兽的情况下魔法初始伤害的最小值。对于的第只怪兽而言其最晚被打中的轮次为右边所有怪兽的数量所以初始伤害值需要,我们将其定义为。而对于的第只怪兽而言则相反其最晚被打中的轮次为初始伤害值需要 我们将其定义为。因此魔法初始伤害的最小值为。考虑完这个以后我们可以通过前缀最大值和后缀最大值来维护数组。然后再遍历每只怪兽假设其为第一轮攻击的怪兽求魔法初始伤害的最小值即可。 // Problem: D. Yet Another Monster Fight
// Contest: Codeforces - Educational Codeforces Round 158 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1901/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 N3e0510;
const LL mod1e097;
typedef pairint,intpl;
priority_queueLL , vectorLL, greaterLL t;
priority_queueLL q;
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];
LL r[N] , l[N];
void init(int n){for(int i 0 ; i n ; i ){a[i] 0;}
}
void solve()
{int n;cin n;for(int i 1 ; i n ; i )cin a[i];for(int i 1 ; i n ; i ){l[i] a[i] (i - 1);r[i] a[i] (n - i);}for(int i 1 ; i n ; i){r[i] max(r[i - 1] , r[i]);}for(int i n; i 1 ; i --){l[i] max(l[i 1] , l[i]);}LL ans 1e18;for(int i 1 ; i n ; i ){ans min(ans , max(a[i] , max(r[i - 1] ,l[i 1])));}cout ans ;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t1;
// cint;while(t--){solve();}return 0;
}E - Compressed Tree 树形DP 题意给你一棵由 n 个顶点组成的树。每个顶点上都写有一个数字顶点 i 上的数字等于 ai 。 您可以执行以下任意次数的操作(可能为零)选择一个最多有1条边的顶点并将该顶点从树中删除。请注意您可以删除所有顶点。 完成所有操作后就可以压缩树了。压缩过程如下。当树中有一个顶点恰好有2条边时执行以下操作删除该顶点用一条边连接其邻居。 可以看出如果在压缩过程中有多种选择删除顶点的方法那么得到的树还是一样的。 你们的任务是计算在任意次数的上述操作后求出压缩完树以后的所有顶点的权值之和最大。 思路对于一个顶点来说最终压缩完树以后有4种情况
1、只保留了自己一个顶点。
2、保留了自己和自己邻边上一个顶点。
3、保留了邻边上的两个顶点。
4、保留了自己和邻边上面2个以上的顶点。这样在压缩的时候就不会把自己删了
因此用dp[n][4]来分别表示这四种状态。接下来考虑如何从子顶点上转移若顶点只有一个子顶点那么就只有1、2两种情况。如果顶点有两个子顶点那么就会出现1、2、3三种情况。如果子顶点大于2个的话那么就需要对子顶点的值进行排序了肯定是越大的越好。对于情况4并不是所有的子顶点都需要选择若子顶点的值小于0那么就代表这子顶点是无需保留的删除即可。 接下来考虑子树的值如何选择对于情况1和情况4直接继承。对于情况2在压缩的过程中会把子树结点给压缩掉所以需要减去子顶点的值。对于情况3原本是不保留子顶点的但是由于需要连到父亲上所以子顶点需要保留因此需要增加子顶点的值。因此一个子顶点的值即为。 接下来走任意一点开始走一遍DFS时刻记录最大值。只有一条链或者两个点的情况下特殊处理一下即可
// Problem: E. Compressed Tree
// Contest: Codeforces - Educational Codeforces Round 158 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1901/problem/E
// 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 N5e0510;
const LL mod1e097;
const LL inf 1e18;
typedef pairint,intpl;
priority_queueLL , vectorLL, greaterLL t;
priority_queueLL q;
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];
int deg[N];
vectorinte[N];
LL dp[N][4];
void init(int n){for(int i 0 ; i n ; i ){a[i] 0 , deg[i] 0 , e[i].clear();}
}
LL cmp(LL a , LL b){return a b;
}
LL ans 0;
void dfs(int cur , int fa){dp[cur][0] a[cur] , dp[cur][1] -inf , dp[cur][2] -inf , dp[cur][3] -inf;vectorLLch;for(auto v : e[cur]){if(v fa)continue;dfs(v , cur);ch.pb(max(dp[v][0], max(dp[v][1] - a[v], max(dp[v][2] a[v], dp[v][3]))));}sort(ch.begin() , ch.end() , cmp);if(ch.size() 1){dp[cur][1] a[cur] ch[0];}if(ch.size() 2){dp[cur][2] ch[0] ch[1];}if(ch.size() 3){dp[cur][3] a[cur] ch[0] ch[1] ch[2];for(int i 3 ; i (int)ch.size() ; i ){if(ch[i] 0){break;}dp[cur][3] ch[i];}}ans max(ans , max(dp[cur][0], max(dp[cur][1], max(dp[cur][2], dp[cur][3]))));
}
void solve()
{cin n;for(int i 1 ; i n ; i )cin a[i];int max_deg 1;for(int i 1 ; i n ; i ){int x , y;cin x y;e[x].pb(y);e[y].pb(x);deg[x] ;deg[y] ;max_deg max(max_deg , max(deg[x] , deg[y]));}if(max_deg 1){if(a[1] 0){cout max(1LL * 0 , a[2]) endl;}else{cout max(a[1] , a[1] a[2]) endl;}}else if(max_deg 2){sort(a 1, a 1 n , cmp);if(a[1] 0){cout max(1LL * 0 , a[2]) endl;}else{cout max(a[1] , a[1] a[2]) endl;}}else{ans 0;dfs(1 , 0);cout ans endl;}init(n);
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t1;cint;while(t--){solve();}return 0;
}
