cf1552F. Telepanting

題意：

在一個坐標(biāo)軸上，有n個傳送門，格式為：xi,yi,si,可以從xi傳送到y(tǒng)i，si表示狀態(tài)，如果si為0，到位置xi時不會傳送，si變?yōu)?.如果到達(dá)xi時si為1，則觸發(fā)傳送，si變?yōu)?.
問到達(dá)xn+1需要走的距離是多少？

題解：

我一開始就是模擬做，但是必然會超時，所以需要我們?nèi)ふ移渌男再|(zhì)
當(dāng)我們到達(dá)一個xi時，在此之前的所有傳送位置(不含xi)必然都是激活狀態(tài)(即si=1)

為什么？如果之前有個傳送位置pos不是激活，說明你在經(jīng)過pos之前，pos是激活狀態(tài)，那你經(jīng)過pos就要被傳送到前面，pos變?yōu)槲醇せ?#xff0c;然后經(jīng)過他又變成激活。

.這說明在yi到xi這段區(qū)間內(nèi)的所有傳送位置我們都是要經(jīng)歷一遍。
我們設(shè)q[i]:表示觸發(fā)了第i個傳送，又回到位置x[i]所走的路徑
sum[i]:表示觸發(fā)前i個傳送所要走的路徑,即q[i]的前綴和
q[i]如何求？
q[i]就是從y[i]走到x[i]這段路徑，再加上這段路程上的所有q[pos],pos為這段區(qū)間的傳送門，這個可以用sum來表示
最后統(tǒng)計答案時，先計算基本路程x[n]+1，以及每個激活的傳送門的路程

代碼：

// Problem: F. Telepanting // Contest: Codeforces - Codeforces Global Round 15 // URL: https://codeforces.com/contest/1552/problem/F // Memory Limit: 256 MB // Time Limit: 2000 ms // By Jozky#include <bits/stdc++.h> #include <unordered_map> #define debug( a, b ) printf ( "%s = %d\n", a, b ); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; // Fe~Jozky const ll INF_ll = 1e18; const int INF_int = 0x3f3f3f3f; void read (){}; template <typename _Tp, typename... _Tps> void read ( _Tp &x, _Tps &...Ar ) {x = 0;char c = getchar ();bool flag = 0;while ( c < '0' || c > '9' )flag |= ( c == '-' ), c = getchar ();while ( c >= '0' && c <= '9' )x = ( x << 3 ) + ( x << 1 ) + ( c ^ 48 ), c = getchar ();if ( flag )x = -x;read ( Ar... ); } template <typename T> inline void write ( T x ) {if ( x < 0 ){x = ~( x - 1 );putchar ( '-' );}if ( x > 9 )write ( x / 10 );putchar ( x % 10 + '0' ); } void rd_test () { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen ( "in.txt", "r", stdin ); #endif } void Time_test () { #ifdef ONLINE_JUDGE #elseendTime = clock ();printf ( "\nRun Time:%lfs\n",(double)( endTime - startTime ) / CLOCKS_PER_SEC ); #endif } const int maxn = 3e5 + 9;const int mod = 998244353; ll sum[maxn]; ll q[maxn]; ll x[maxn]; ll y[maxn]; ll s[maxn]; int main () {// rd_test();int n;cin >> n;int maxx = 0;for ( int i = 1; i <= n; i++ ){read ( x[i], y[i], s[i] );// read ( a[i], a[i].y, a[i].s );int pos = lower_bound ( x + 1, x + 1 + i, y[i] ) - x;// cout << "pos=" << pos << endl;q[i] = ( x[i] - y[i] + sum[i - 1] - sum[pos - 1] + mod ) % mod;sum[i] = ( sum[i - 1] + q[i] ) % mod;}ll ans = ( x[n] + 1 ); //必走的路for ( int i = 1; i <= n; i++ ){if ( s[i] )ans = ( ans + q[i] + mod ) % mod;}printf ( "%lld", ( ans % mod + mod ) % mod );return 0;// Time_test(); }

總結(jié)

以上是生活随笔為你收集整理的cf1552F. Telepanting的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。