读图机 东莞网站建设,全自动引流推广软件app,淘宝客不建立网站怎么做,北京装饰公司排行 2019Educational Codeforces Round 143 (Rated for Div. 2) D. Triangle Coloring
思路#xff1a;
每个环都需要取最大值#xff0c;那么我们讨论一个环获得最大值选的两条边的可能取法#xff1a; 显然#xff1a;如果三边相等#xff0c;这个环有3种取法。如…Educational Codeforces Round 143 (Rated for Div. 2) D. Triangle Coloring
思路
每个环都需要取最大值那么我们讨论一个环获得最大值选的两条边的可能取法 显然如果三边相等这个环有3种取法。如果有两条小边相等这个环有两种取法。其余情况都只能取一种之后把每个环都看成一个点就是从n个环选n/2个蓝色红色求组合数。所以其实就是考逆元乘法逆元费马小定理拓欧线性dp
#include bits/stdc.h
using namespace std;
#define ll long long
#define int ll
typedef unsigned long long ull;
typedef pairlong long, long long pll;
typedef pairint, int pii;//double 型memset最大127最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF 0x3f3f3f3f; //int型的INF
const ll llINF 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N 2e5 10;
const int mod 998244353;
int a[3];ll fastmi(ll base, ll power)//快速幂求逆元
{ll ans 1;while (power){if (power 1)ans ans * base % mod;base base * base % mod;power 1;}return ans;
}int32_t main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n;cin n;//n从表示一个点转化为表示一个环n / 3;ll ans 1;for (int i 1; i n; i){cin a[0] a[1] a[2];//3点一个环sort(a, a 3);//if (a[0] a[2])ans (ans * 3) % mod;//else if (a[0] a[1])ans (ans * 2) % mod;}ll tmp 1;for (int i 1; i n / 2; i)//求组合数C(n/2,n){ans (ans * (n / 2 i)) % mod;tmp tmp * i % mod;}ans (ans * fastmi(tmp, mod - 2)) % mod;cout ans endl;return 0;
}
E. Explosions?
思路
我们枚举每个点作为爆炸点显然爆炸连续的前提就是左边生命值严格单调增右边严格单调减。由于我们需要消耗的生命值总和是恒定的所以那个点爆炸造成总伤害高显然耗费魔法值更少我们考虑爆炸时左边右边的邻居(j)与爆炸点(x)的大小关系(a[i]表示生命值,l[i]表示i对左边可以造成的伤害和包括炸死自己 会发现如果a[j]a[x]-1,是无法爆炸的不过我们可以用单位魔法把j生命值变为a[x]-1所以无影响所以对于x左边任意点j如果a[j]a[x]-(x-j),我们可以用单位魔法操作到其生命值为a[x]-(x-j)。对于a[j]a[x]-(x-j),那我们下一次爆炸的威力就减少了而且我们发现后续产生的伤害等于l[j]所以我们加上l[j]就不用再往左了因此我们得出每次求l[x]只需要找到第一个点j满足a[j]a[x]-(x-j那么 l[x](x-j)*(a[x](a[x]-(x-j)1)/2l[j]然而每个点都回溯太费时间了我们中间那些不满足a[j]a[x]-(x-j)的点j只要没用一次就一直没用我们能不能舍去他为这个数组减肥呢。观察发现不等式可以表示为a[j]-ja[x]-x,所以我们可以另开一个数组记录这个信息。然后从左往右遍历每次求当前点l[x]只需要把a[j]-ja[x]-x的前面点舍去最后就可以立刻求取答案显然舍去这个功能让我们想到可以开一个栈先进后出爆炸右边也是同理
#include bits/stdc.h
using namespace std;
#define ll long long
#define int ll
typedef unsigned long long ull;
typedef pairlong long, long long pll;
typedef pairint, int pii;//double 型memset最大127最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF 0x3f3f3f3f; //int型的INF
const ll llINF 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N 3e5 10;
int a[N], l[N], r[N], a1[N], n;void cnt(int *f)
{stackints;s.push(0);//放入左边边界外面0for (int i 1; i n; i)a1[i] a[i] - i; //记录比较数组for (int i 1; i n; i){while ((int)s.size() 1 a1[s.top()] a1[i])s.pop(); //从最靠近右边的点堆顶开始比较不满足的点全部舍去后面也没用了int len min(a[i], (ll)i - s.top()); //爆炸可持续范围最长是a[i]伤害不断递减不是直接取遇到满足条件的j点你可能到不了那个点f[i] f[s.top()] len * (2 * a[i] - len 1) / 2;s.push(i);//不断给栈存入新的点}
}int32_t main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin t;while (t--){cin n;ll sum 0;for (int i 1; i n; i)cin a[i], sum a[i];cnt(l);reverse(a 1, a 1 n); //反转一下求右边爆炸cnt(r);reverse(r 1, r 1 n); //r获得的是反转过的要反转回来reverse(a 1, a 1 n);ll ans 0;for (int i 1; i n; i)ans max(ans, l[i] r[i] - 2 * a[i]); //l与r都记录了a[i]造成的伤害然而这个伤害是魔法产生的不是被波及的cout sum - ans endl;}return 0;
}
