做财务还是网站运营,旅社网站怎么建立,织梦做的网站有哪些,西安建网页文章目录problemsolution(10pts)code(10pts)solution(30pts)code(30pts)solution(60pts)code(60pts)solution(100pts)code(100pts)problem
luogu-P6619
一场比赛即将开始。
每位战士有两个属性#xff1a;温度和能量。
有两派战士#xff1a;
冰系战士的技能会对周围造成…
文章目录problemsolution(10pts)code(10pts)solution(30pts)code(30pts)solution(60pts)code(60pts)solution(100pts)code(100pts)problem
luogu-P6619
一场比赛即将开始。
每位战士有两个属性温度和能量。
有两派战士
冰系战士的技能会对周围造成降温冰冻伤害因而要求场地温度不低于他的自身温度才能参赛火系战士的技能会对周围造成升温灼烧伤害因而要求场地温度不高于他的自身温度才能参赛。
当场地温度确定时双方能够参赛的战士分别排成一队。
冰系战士按自身温度从低到高排序火系战士按自身温度从高到低排序温度相同时能量大的战士排在前面。
首先双方的第一位战士之间展开战斗两位战士消耗相同的能量能量少的战士将耗尽能量退出比赛而能量有剩余的战士将继续和对方的下一位战士战斗能量都耗尽则双方下一位战士之间展开战斗。
如此循环直至某方战士队列为空比赛结束。
你需要寻找最佳场地温度使冰火双方消耗总能量最高的温度的最高值。
现在比赛还处于报名阶段目前还没有任何战士报名接下来你将不断地收到报名信息和撤回信息。
其中报名信息包含报名战士的派系和两个属性撤回信息包含要撤回的报名信息的序号。
每当报名情况发生变化即收到一条信息时你需要立即报出当前局面下的最佳场地温度以及该场地温度下双方消耗的总能量之和是多少。
若当前局面下无论何种温度都无法开展比赛某一方没有战士能参赛则只要输出 Peace。
solution(10pts)
Q≤100,x≤103Q\le 100,x\le 10^3Q≤100,x≤103。
枚举整个信息读入过程O(Q)O(Q)O(Q)。
然后枚举答案温度O(T)O(T)O(T)。
再计算当前温度下报名的且可以参赛的冰系战士/火系战士的总能量O(Q)O(Q)O(Q)。
取所有温度下二者的较小值的最大值输出其的两倍及记录的温度。
时间复杂度 O(Q2T)O(Q^2T)O(Q2T) 其中 TTT 是所有战士的温度最大值。
可以获得 10′1010′ 的普通成绩。
code(10pts)
namespace subtask1 {bool vis[105];void solve() {for( int i 1, op, k, x, y;i Q;i ) {scanf( %d %d, op, k );if( op 1 ) {scanf( %d %d, x, y );g[i] { k, x, y };vis[i] 1;}else vis[k] -1;int ans 0, ti;for( int T 1;T 1e3;T ) {int ice 0, fire 0;for( int j 1;j i;j )if( vis[j] 1 ) {if( g[j].k 0 and g[j].x T ) ice g[j].y;if( g[j].k 1 and g[j].x T ) fire g[j].y;}if( ans min( ice, fire ) ) ans min( ice, fire ), ti T;else if( ans min( ice, fire ) ) ti max( ti, T );}if( ! ans ) puts( Peace );else printf( %d %d\n, ti, ans 1 );}}
}solution(30pts)
Q≤104,x≤5000Q\le 10^4,x\le 5000Q≤104,x≤5000不存在撤回信息且输入的 xxx 按顺序不降。
每次枚举温度再枚举战士计算的原始暴力就不可行了。
关注特殊的两个性质 不存在撤回信息。 我们原始暴力为什么要枚举战士不仅仅是为了计算战士的能量、温度更重要的是我们不知道当时某个战士是否已经撤回了报名信息。 如果不撤回我们就期望能找到一个数据结构或者什么工具来维护这些战士的能量和。 输入的 xxx 按顺序不降。 已知冰系战士的温度从小到大排序火系战士的温度从大到小排序。 所以每次加入战士如果是冰系就排在冰系队伍的最后面如果是火系就排在火系队伍的最前面。 我们可以用两个数组来模拟这个过程用指针移动即可。 且当两个战士同派系且温度一样的话就没有什么区别了所以直接合并成一个战士。
最后考虑计算答案。
从高到低枚举参与比赛的温度最低的火系战士即当时的场地温度。证明见满分题解
则冰系战士能参与比赛的一定对应的是其队伍的一段前缀。
而随着枚举的火系战士温度降低冰系战士能参加比赛的数量也在减少。
所有可以用指针枚举能参与比赛的温度最高的冰系战士。
时间复杂度 O(Q2)O(Q^2)O(Q2)。结合前一档可以获得 30′3030′ 的不错成绩。
code(30pts)
namespace subtask1 {}
namespace subtask2 {pair int, int ice[10005], fire[10005];void solve() {int p0 0, p1 Q 1, sum_ice 0;for( int i 1, op, k, x, y;i Q;i ) {scanf( %d %d %d %d, op, k, x, y );if( k 0 ) {sum_ice y;if( p0 and ice[p0].first x ) ice[p0].second y;else ice[ p0] make_pair( x, y );}else {if( p1 Q and fire[p1].first x ) fire[p1].second y;else fire[-- p1] make_pair( x, y );}int p p0, Sice sum_ice, Sfire 0, ans 0, ti;for( int j p1;j Q;j ) {int T fire[j].first; Sfire fire[j].second;while( T ice[p].first ) Sice - ice[p --].second;if( ans min( Sice, Sfire ) ) ans min( Sice, Sfire ), ti T;if( ans min( Sice, Sfire ) ) ti max( ti, T );}if( ! ans ) puts(Peace);else printf( %d %d\n, ti, ans 1 );}}
}solution(60pts)
Q≤2e5,x≤2e5Q\le 2e5,x\le 2e5Q≤2e5,x≤2e5。
再次注意到冰系战士是按温度从低到高火系战士是按温度从高到低。
即冰系战士不降火系战士不升。
而冰系战士参加比赛人数越多前缀取得越多火系战士就越少反之火系越多冰系越少。
所以我们大胆猜测可以三分快速求前缀能量和利用树状数组/线段树均可。
实测写了后很遗憾消耗总能量最高都求不对。输出中间三分点发现存在平台。
仔细想想确实很容易就出现平台因为战士的温度是离散的。
平台三分不行。我们考虑二分。
如果火系战士的总能量更大就再升高一下场次温度反之降温。这其实是正解的做差后的二分思想了
写了后又哭又笑消耗总能量最高求对了。但是场次温度并不是最大值。
同样是因为温度的离散问题。
但是我们肯定温度一定是某个战士的自身温度。
所以直接暴力一点去找比记录温度高的战士温度然后计算答案是否和总能量一样一样就记录这个温度为场地温度继续找知道总能量消耗小于答案为止。
所以还要用个 set\text{set}set 来记录所有报名的战士的温度。
时间复杂度 O(Qlog2T)O(Q\log^2 T)O(Qlog2T)因为那个暴力也跳不了多少次复杂度前面最多乘个几的常数。
结合前两档的部分可以获得 60′6060′ 的优秀成绩。
code(60pts)
namespace subtask1 {}
namespace subtask2 {}
namespace subtask3 {#define maxn 200005#define lson now 1#define rson now 1 | 1#define mid (l r 1)set pair int, int val;namespace ice {int sum[maxn 2];void modify( int p, int x, int now 1, int l 1, int r 2e5 ) {if( l r ) { sum[now] x; return; }if( p mid ) modify( p, x, lson, l, mid );else modify( p, x, rson, mid 1, r );sum[now] sum[lson] sum[rson];}int query( int L, int R, int now 1, int l 1, int r 2e5 ) {if( R l or r L ) return 0;if( L l and r R ) return sum[now];return query( L, R, lson, l, mid ) query( L, R, rson, mid 1, r );}}namespace fire {int sum[maxn 2];void modify( int p, int x, int now 1, int l 1, int r 2e5 ) {if( l r ) { sum[now] x; return; }if( p mid ) modify( p, x, lson, l, mid );else modify( p, x, rson, mid 1, r );sum[now] sum[lson] sum[rson];}int query( int L, int R, int now 1, int l 1, int r 2e5 ) {if( R l or r L ) return 0;if( L l and r R ) return sum[now];return query( L, R, lson, l, mid ) query( L, R, rson, mid 1, r );}}int find( int x, int ans ) {while( 1 ) {auto it val.upper_bound( make_pair( x, Q ) );if( it val.end() ) return x;int sum1 fire :: query( it-first, 2e5 );int sum2 ice :: query( 1, it-first );if( ans min( sum1, sum2 ) ) return x;else x it-first;}}void solve() {int Min 1e9, Max -1e9;for( int i 1, op, k, x, y;i Q;i ) {scanf( %d %d, op, k );if( op 1 ) {scanf( %d %d, x, y );val.insert( make_pair( x, i ) );Min min( Min, x );Max max( Max, x );g[i] { k, x, y };if( k 0 ) ice :: modify( x, y );else fire :: modify( x, y );}else {val.erase( make_pair( g[k].x, k ) );if( g[k].k 0 ) ice :: modify( g[k].x, - g[k].y );else fire :: modify( g[k].x, - g[k].y );}int l 1, r 2e5;int ans 0, ti;while( l r ) {int sum1 fire :: query( mid, 2e5 );int sum2 ice :: query( 1, mid );if( ans min( sum1, sum2 ) ) ans min( sum1, sum2 ), ti mid;else if( ans min( sum1, sum2 ) ) ti mid;if( sum1 sum2 ) l mid 1;else r mid - 1;}if( ! ans ) puts(Peace);else printf( %d %d\n, find( ti, ans ), ans 1 );}}
}solution(100pts)
Q≤2e6,1≤x≤2e9Q\le 2e6,1\le x\le 2e9Q≤2e6,1≤x≤2e9。
observation1:\text{observation1}:observation1: 冰系战士排列后温度成不降函数火系战士排列后温度成不升函数。
observation2:\text{observation2}:observation2: 最后的场地温度一定是某个战士的体温。 证明显然。感性感知一下。 如果最后的场地温度不是某个战士的温度。 那么这个场地温度一定 参与比赛的火系战士的最低温度 参与比赛的冰系战士的最高温度。 这个场地温度就可以被调整为 参与比赛的火系战士的最低温度。 这样火系和冰系战士原本能参与比赛的没有变化说不定还可以新增几名参与比赛的冰系战士。 温度拉高总消耗也没有变劣。
基于这个结论我们可以将战士的温度离散化成和 QQQ 同量级。
假设场地温度为 TTT能参加比赛的冰系战士的能量和为 I(T)\text{I}(T)I(T)能参加比赛的火系战士的能量和为 F(T)\text{F}(T)F(T)。
勾勒成函数后一个单增火一个单减冰。答案肯定是在交点处。 而我们真正要二分的应该两函数合并取较小值的函数。 更详细地我们记 Ice(i):\text{Ice}(i):Ice(i): 自身温度 ≤i\le i≤i 的冰系战士的能量和记 Fire(i):\text{Fire}(i):Fire(i): 自身温度 ≤i\le i≤i 的火系战士的能量和记当前报名的所有火系战士的能量和为 sumsumsum。
则当场地温度为 TTT 的时候答案即为 min(Ice(T),sum−Fire(T−1))\min\Big(\text{Ice}(T),sum-\text{Fire}(T-1)\Big)min(Ice(T),sum−Fire(T−1)) 再乘 222。
我们二分的函数应该是两个前缀和函数做差G(T)Ice(T)−(sum−Fire(T−1))G(T)\text{Ice}(T)-(sum-\text{Fire}(T-1))G(T)Ice(T)−(sum−Fire(T−1))。与上图不太一样反转了火系函数
因为 Ice(T)\text{Ice}(T)Ice(T) 函数不降sum−(Fire(T−1))sum-(\text{Fire}(T-1))sum−(Fire(T−1)) 函数不升所以 G(T)G(T)G(T) 函数非严格不降。
那么交点必定在最后一个 ≤0\le 0≤0 和第一个 000 的位置之间。
所以我们二分最后一个使得 G(T)≤0G(T)\le 0G(T)≤0 的位置 ttt答案必定在 t/t1t/t1t/t1 处取得。
如果在 ttt 处答案更大则温度自然就是 ttt
否则还要在函数平台处二分出最大的温度 t0t_0t0满足 Ice(t1)−(sum−Fire(t))Ice(t0)−(sum−Fire(t0−1))⇒Fire(t)≥Fire(t0−1)\text{Ice}(t1)-(sum-\text{Fire}(t))\text{Ice}(t_0)-(sum-\text{Fire}(t_0-1))\Rightarrow \text{Fire}(t)\ge \text{Fire}(t_0-1)Ice(t1)−(sum−Fire(t))Ice(t0)−(sum−Fire(t0−1))⇒Fire(t)≥Fire(t0−1)。
但肯定不能二分后树状数组查询这样跟 60′6060′ 的做法是一样的。推导过程严谨了一些而已但谁管这个呢》》
这里我们要用到 树状数组上二分与线段树上二分类似是 O(nlogn)O(n\log n)O(nlogn) 的。
为什么不用线段树二分是因为这位虽然看似一个 log\loglog 但是跑出来因为常数问题跟二分后树状数组差不多。
树状数组二分。
这需要改写一下上面函数的形式
记 fire(i):fire(i):fire(i): 温度为 iii 的火系战士的能量和。 Ice(T)−(sum−Fire(T−1))≤0⇒Ice(T)Fire(T)−fire(T)≤sum\text{Ice}(T)-(sum-\text{Fire}(T-1))\le 0\Rightarrow \text{Ice(T)}\text{Fire}(T)-fire(T)\le sumIce(T)−(sum−Fire(T−1))≤0⇒Ice(T)Fire(T)−fire(T)≤sum。 这样下标只有 TTT 且具有单调性可以树状数组二分了。 Fire(T)−fire(T)≤sum−ans\text{Fire}(T)-fire(T)\le sum-ansFire(T)−fire(T)≤sum−ans。
时间复杂度 O(QlogQ)O(Q\log Q)O(QlogQ)可以获得 100′100100′ 的好成绩。
code(100pts)
#include bits/stdc.h
using namespace std;
#define maxn 2000005
int val[maxn], fire[maxn];
int Q, n, cnt_fire, sum_fire, cnt_ice;
struct node { int op, k, x, y; }q[maxn];
struct BIT {int sum[maxn];void modify( int i, int x ) {for( ;i n;i i -i ) sum[i] x;}int query( int i ) {int ans 0;for( ;i;i - i -i ) ans sum[i];return ans;}
}Fire, Ice;int calc( int x ) {return min( Ice.query( x ), sum_fire - Fire.query( x - 1 ) );
}int main() {scanf( %d, Q );for( int i 1;i Q;i ) {scanf( %d %d, q[i].op, q[i].k );if( q[i].op 1 ) scanf( %d %d, q[i].x, q[i].y ), val[ n] q[i].x;}sort( val 1, val n 1 );n unique( val 1, val n 1 ) - val - 1;for( int i 1;i Q;i )if( q[i].op 1 ) q[i].x lower_bound( val 1, val n 1, q[i].x ) - val;for( int t 1;t Q;t ) {int k q[t].k, x, y;if( q[t].op 1 ) {x q[t].x, y q[t].y;if( k 0 ) Ice.modify( x, y ), cnt_ice ;else Fire.modify( x, y ), cnt_fire , sum_fire y, fire[x] y; }else {x q[k].x, y q[k].y;if( q[k].k 0 ) Ice.modify( x, -y ), cnt_ice --;else Fire.modify( x, -y ), cnt_fire --, sum_fire - y, fire[x] - y;}int p 0, ans 0;for( int i 20;~ i;i -- ) {k p | (1 i);if( k n and ans Ice.sum[k] Fire.sum[k] - fire[k] sum_fire )p | (1 i), ans Ice.sum[k] Fire.sum[k];}int ans1 calc( p ), ans2 calc( p 1 );if( max( ans1, ans2 ) 0 ) { puts(Peace); continue; }if( ans1 ans2 ) { printf( %d %d\n, val[p], ans1 1 ); continue; }p 0, ans 0;for( int i 20;~ i;i -- ) {k p | (1 i);if( k n and ans Fire.sum[k] - fire[k] sum_fire - ans2 )p | (1 i), ans Fire.sum[k];/*ans2说明火系战士的能量和更小二分平台上的最大温度t0在前缀和Fire数组中以T为自变量呈一个平台满足 Fire(t)Fire(t0-1)即 sum-Fire(t)sum-Fire(t0-1)*/}printf( %d %d\n, val[p], ans2 1 );}return 0;
}
