文章目錄

• 素數(shù)
• • solution
  • code
• 精靈
• • solution
  • code
• 農夫約的假期
• • solution
  • code
• 觀察
• • solution
  • solution
  • code

素數(shù)

solution

通過觀察可得一個結論
對于兩個相鄰的質數(shù)$p_1,p_2(p_1<p_2)$
對于$x\in [p_1,p_2)$，都有$u_x=p_2,v_x=p_1$

接著隨隨便便推一下
假設三個相鄰的質數(shù)$p_1,p_2,p_3(p_1<p_2<p_3)$
對于$x_1\in [p_1,p_2)$👉${\sum }_{x_1}=(p_2?p_1)?\frac{1}{p_1?p_2}$
對于$x_2\in [p_2,p_3)$👉${\sum }_{x_2}=(p_3?p_2)?\frac{1}{p_2?p_3}$
將兩式相加👉${\sum }_{x_i\in [p_1,p_3)}\frac{1}{u_{x_i}?v_{x_i}}=\frac{p_3?(p_2?p_1)+p_1?(p_3?p_2)}{p_1?p_2?p_3}=\frac{p_3?p_1}{p_1?p_3}$
按道理下面繼續(xù)相加$p_3,p_4...p_i$都會被消掉，只剩下第一個質數(shù)$2$和最后一個小于等于$n$的質數(shù)
于是就又出來了一個結論
只不過最后那個質數(shù)和$n$之間的數(shù)的貢獻得單獨算，因為它不是一個完整區(qū)間
也很簡單啊， 求出最后一個小于等于$n$的質數(shù)$P_1$和第一個大于$n$的質數(shù)$P_2$
計算方法也是一樣的啊，只不過乘的個數(shù)不一樣罷了👉$\frac{n?P_1+1}{P_1?P_2}$
我們可以感性猜想兩個素數(shù)之間按道理是不會差太多的，也就是說應該能放得過我的暴力尋找
證不來那就感性猜想走一波

code

#include <cstdio> #define ll long long int T, n; ll pre, suf;bool check( ll x ) {for( ll i = 2;i * i <= x;i ++ )if( x % i == 0 ) return 0;return 1; }ll GCD( ll x, ll y ) {if( ! y ) return x;else return GCD( y, x % y ); }ll LCM( ll x, ll y ) {ll d = GCD( x, y );return x / d * y; }int main() {scanf( "%d", &T );while( T -- ) {scanf( "%d", &n ); pre = n, suf = n + 1;while( ! check( pre ) ) pre --;while( ! check( suf ) ) suf ++;ll x1 = pre - 2, y1 = ( pre << 1 ), x2 = n - pre + 1, y2 = pre * suf;ll lcm = LCM( y1, y2 );ll ansx = lcm / y1 * x1 + lcm / y2 * x2;ll ansy = lcm;ll d = GCD( ansx, ansy );printf( "%lld/%lld\n", ansx / d, ansy / d );}return 0; }

精靈

Branimirko 是一個對可愛精靈寶貝十分癡迷的玩家。最近，他閑得沒事組織了一場捉精 靈的游戲。游戲在一條街道上舉行，街道上一側有一排房子，從左到右房子標號由 1 到 n。 剛開始玩家在 k 號房子前。有 m 個精靈，第 i 只精靈在第 A[i]棟房子前，分值是 B[i]， 以及它在 T[i]秒內（含）存在，之后消失。Branimirko 可以選擇移動至相鄰的房子，耗時 1 秒。抓住精靈不需要時間，精靈被抓住后消失。時間從第 1 秒開始。Branimirko 能最多獲得 多少分值和。

輸入格式
輸入的第 1 行為三個正整數(shù) n，k，m。 接下來 m 行描述精靈的信息，分別為 A[i]，B[i]，T[i]。

輸出格式
輸出 Branimirko 能最多獲得多少分值和。

樣例
樣例輸入
10 5 4
1 30 4
3 5 7
7 10 12
9 100 23
115
數(shù)據(jù)范圍與提示
20%的數(shù)據(jù)：𝑚 ≤ 10 40%的數(shù)據(jù)：𝑚 ≤ 20 對于 100%的數(shù)據(jù)：𝑘 ≤ 𝑛 ≤ 1000, 𝑚 ≤ 100, 𝐴[𝑖] ≤ 𝑁, 𝐵[𝑖] ≤ 100, 𝑇[𝑖] ≤ 2000，所有數(shù)為正整數(shù)

solution

這道題好啊，這道題妙啊，這道題頂呱呱啊

首先讀題讀完就應該有了dp的方向，略微思考那么一丟丟（直接就看得出來）肯定是區(qū)間dp沒得跑了，接著去看看數(shù)據(jù)范圍，嗯針不戳確定三四維差不多了
這里精靈只有$m$個，地點的范圍級別是精靈的十倍，所以我們應該是用精靈進行區(qū)間dp
不會有人硬剛n吧，不會吧不會吧

$dp[l][r][t][0/1]$：表示在$t$時刻，已經$?$完了$[l,r]$內所有能艸的精靈，此時是在$l(0)/r(1)$位置上的最大收益
然后就可以暴力四個轉移方程轉移了
$$?\begin{array}{r}f[l][r][t][0]=max\{f[l+1][r][t?(g[l+1].p?g[l].p)][0]+g[l].s\}l+1=>l\\ f[l][r][t][0]=max\{f[l+1][r][t?(g[r].p?g[l].p)][1]+g[l].s\}r=>l\\ f[l][r][t][1]=max\{f[l][r?1][t?(g[r].p?g[r?1].p)][1]+g[r].s\}r?1=>r\\ f[l][r][t][1]=max\{f[l][r?1][t?(g[r].p?g[l].p)][0]+g[r].s\}l=>r\end{array}$$
一般dp左右都會對其造成影響的dp就可以往區(qū)間dp上去思考

code

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define maxt 2005 #define maxm 105 struct node {int p, s, t; }g[maxm]; int n, k, m, maxT; int f[maxm][maxm][maxt][2];bool cmp( node x, node y ) {return x.p < y.p; }int Fabs( int x ) {return ( x < 0 ) ? -x : x; }int main() {memset( f, -0x3f, sizeof( f ) );scanf( "%d %d %d", &n, &k, &m );for( int i = 1;i <= m;i ++ ) {scanf( "%d %d %d", &g[i].p, &g[i].s, &g[i].t );maxT = max( maxT, g[i].t );}sort( g + 1, g + m + 1, cmp );for( int i = 1;i <= m;i ++ )if( Fabs( g[i].p - k ) + 1 > g[i].t ) continue;else f[i][i][Fabs( g[i].p - k ) + 1][0] = f[i][i][Fabs( g[i].p - k ) + 1][1] = g[i].s;for( int len = 2;len <= m;len ++ ) {for( int l = 1;l + len - 1 <= m;l ++ ) {int r = l + len - 1;for( int t = 1;t <= maxT;t ++ ) {if( t - ( g[l + 1].p - g[l].p ) > 0 )f[l][r][t][0] = max( f[l][r][t][0], f[l + 1][r][t - ( g[l + 1].p - g[l].p )][0] );if( t - ( g[l + 1].p - g[l].p ) > 0 && t <= g[l].t )f[l][r][t][0] = max( f[l][r][t][0], f[l + 1][r][t - ( g[l + 1].p - g[l].p )][0] + g[l].s );if( t - ( g[r].p - g[l].p ) > 0 )f[l][r][t][0] = max( f[l][r][t][0], f[l + 1][r][t - ( g[r].p - g[l].p )][1] );if( t - ( g[r].p - g[l].p ) > 0 && t <= g[l].t )f[l][r][t][0] = max( f[l][r][t][0], f[l + 1][r][t - ( g[r].p - g[l].p )][1] + g[l].s );if( t - ( g[r].p - g[r - 1].p ) > 0 )f[l][r][t][1] = max( f[l][r][t][1], f[l][r - 1][t - ( g[r].p - g[r - 1].p )][1] );if( t - ( g[r].p - g[r - 1].p ) > 0 && t <= g[r].t )f[l][r][t][1] = max( f[l][r][t][1], f[l][r - 1][t - ( g[r].p - g[r - 1].p )][1] + g[r].s );if( t - ( g[r].p - g[l].p ) > 0 )f[l][r][t][1] = max( f[l][r][t][1], f[l][r - 1][t - ( g[r].p - g[l].p )][0] );if( t - ( g[r].p - g[l].p ) > 0 && t <= g[r].t )f[l][r][t][1] = max( f[l][r][t][1], f[l][r - 1][t - ( g[r].p - g[l].p )][0] + g[r].s );}}}int ans = 0;for( int l = 1;l <= m;l ++ )for( int r = l;r <= m;r ++ )for( int t = 1;t <= maxT;t ++ )ans = max( ans, max( f[l][r][t][0], f[l][r][t][1] ) );printf( "%d\n", ans );return 0; }

農夫約的假期

在某國有一個叫農夫約的人，他養(yǎng)了很多羊，其中有兩頭名叫 mm 和 hh，他們的歌聲 十分好聽，被當?shù)厝朔Q為“魔音”······ 農夫約也有自己的假期呀！他要去海邊度假，然而 mm 和 hh 不能離開他。沒辦法，他 只好把他們兩個帶上。 到了海邊，農夫約把他的羊放在一個(nn)的矩陣(有 nn 個方格)里。mm 和 hh 十分好 動，他們要走到 m(m<=n*n)個地方，第 i 個地方的坐標為(xi,yi)，每到一個地 方他們會高歌一曲，制造 q[i]點魔音值，因為他們的魔音十分獨特，他們的聲音只能橫著或 豎著傳播。每傳播一格，魔音值會增加 1。(傳播的格子數(shù)取最小的)接下來農夫約要住酒店。 為了方便照顧小羊們，他選的酒店的坐標要在矩陣內。但小羊們的魔音讓他十分頭疼。他想 求出魔音值最小的地方。 他還要享受他的假期，所以他把這個任務交給你了，加油(^_)。

輸入格式
第一行輸入 n、m 和 z。 接下來 m 行，每行 3 個正整數(shù) x[i],y[i]和 q[i]。

輸出格式
第一行一個整數(shù)表示魔音值最小是多少。 接下來一行兩個正整數(shù) zb1 和 zb2，表示魔音值最小的地方的坐標(如果有多個答案， 輸出橫坐標最小的情況下，縱坐標最小的)。

樣例
輸入樣例
3 3 1
1 1 1
1 2 1
1 3 1
輸出樣例
5
1 2
數(shù)據(jù)范圍與提示
10%的數(shù)據(jù)，n<=10. 30%的數(shù)據(jù)，n<=1000. 100%的數(shù)據(jù)，0<n<=100000， 0<m<=100000，0<q[i]<=100.

solution

語文是個好東西，讀題讀了半個小時硬是沒讀懂

樣例解釋你寫了跟沒寫一樣，呵呵呵呵

讀懂過后就發(fā)現(xiàn)比素數(shù)還簡單
這個饒了?山路十八彎的距離說白了的曼哈頓距離，橫坐標差絕對值+縱坐標差絕對值
于是自然而然地
想到了
將$x,y$分開處理，彼此是不影響的
二維就被降成了一維
一個數(shù)軸上一堆點，求它們到一個點的距離最小值
就是中位數(shù)噻 這還反應不過來？？
題目要求有多個答案，先保證$x$最小，再保證$y$最小
根據(jù)計算機除法計算的特別性，管它奇偶，老子直接$>>1$搞定
所以這道題就是兩個sort排序取兩個中位數(shù)$x_{mid},y_{mid}$，然后算$m$個點與該點的曼哈頓距離

code

#include <cstdio> #include <algorithm> using namespace std; #define maxn 100005 struct node {int x, y, q; }s[maxn]; int n, m, z;bool cmp1( node x, node y ) {return x.x < y.x; }bool cmp2( node x, node y ) {return x.y < y.y; }int Fabs( int x ) {return ( x < 0 ) ? -x : x; }int main() {scanf( "%d %d %d", &n, &m, &z );for( int i = 1;i <= m;i ++ )scanf( "%d %d %d", &s[i].x, &s[i].y, &s[i].q );sort( s + 1, s + m + 1, cmp1 );int ansx = s[( m + 1 ) >> 1].x;sort( s + 1, s + m + 1, cmp2 );int ansy = s[( m + 1 ) >> 1].y;long long ans = 0;for( int i = 1;i <= m;i ++ )ans += Fabs( s[i].x - ansx ) + Fabs( s[i].y - ansy ) + s[i].q;printf( "%lld\n%d %d", ans, ansx, ansy );return 0; }

觀察

solution

infleaking 十分愉快地走在路上，因為經過 10⁹9^9 年后，他得到了一個新技能—— 觀察大法。 剛出來的 infleaking 就想要挑戰(zhàn)自我。 為什么 infleaking 會這么自信呢？ 因為 infleaking 做到了可以通過觀察數(shù)據(jù)就就可以得出答案。 但是出題人十分不服，想要將 infleaking 的氣焰打壓下去，于是想到了一道題。 結果被 infleaking 運用他那強大的觀察能力看完數(shù)據(jù)后給出了答案。 怎么能夠讓 infleaking 繼續(xù)下去呢，出題人于是就將數(shù)據(jù)重出并且加密了。 沒有能直接觀察數(shù)據(jù)的 infleaking 十分不服氣，想要解決這道題，但是苦于不能直接使 用他的新技能，所以想要請聰明的你幫 infleaking 解決這個問題。 出題人給出一顆以 1 為根的樹，一開始每個節(jié)點都是一顆棋子，一面白一面黑，白色的 面朝上接下來就 q 次操作，操作分兩種 0 操作 將一個顆棋子翻轉 1 操作 詢問一顆棋子與所有面朝上為黑色的棋子 lca 最深的那個的編號

輸入格式
第 1 行，兩個正整數(shù) n，q 第 2 行，一共 n-1 個正整數(shù)，第 i 個正整數(shù)表示 i+1 號結點的父親 第 3~q+3 每行兩個整數(shù) x ，第|x|個為被操作的棋子，x>0 操作為 0 否則為 1

輸出格式
對于每個 op 為 1 的操作輸出對應的編號，若場上沒有黑棋子輸出 0

樣例
樣例輸入
10 10
6 2 7 9 1 10 5 4 3
-2
1
3
3
-5
8
1
4
-1
-5
樣例輸出
0
1
1
5
數(shù)據(jù)范圍與提示
100%的數(shù)據(jù)，n，q<=800000

solution

有一個結論
好家伙這場是結論專場了吧
一個點肯定跟dfn序離自己最近的兩個點（前后各一個）lca最大
這個結論errrr——，怎么證明呢？？感性理解吧，畢竟虛樹就是在這個結論基礎上做的

于是就可以用一個數(shù)據(jù)結構維護所有黑點的$dfn$序
這里我們選擇既好寫又可愛的 set
小兒子考場用的set，但他不會，半天編譯過不了，于是他生氣了，敲了個treap

但是考后OJ上，被卡了？？？T了——啊這，這波我沒有想到
于是乎手動O(2)，lca用樹鏈剖分去搞，再加上多次提交，最后終于卡過去了一次

code

#pragma GCC optimize(2) #include <set> #include <cstdio> #include <vector> using namespace std; #define maxn 800005 set < int > st; set < int > :: iterator it; vector < int > G[maxn]; int n, Q, cnt; int dfn[maxn], dep[maxn], rnk[maxn], siz[maxn], son[maxn], top[maxn], f[maxn];void dfs1( int u ) {dfn[u] = ++ cnt, rnk[cnt] = u, dep[u] = dep[f[u]] + 1, siz[u] = 1;for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];f[v] = u;dfs1( v );siz[u] += siz[v];if( ! son[u] || siz[v] > siz[son[u]] )son[u] = v;} }void dfs2( int u, int t ) {top[u] = t;if( ! son[u] ) return;dfs2( son[u], t );for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];if( v == son[u] ) continue;else dfs2( v, v );} }int lca( int u, int v ) {while( top[u] ^ top[v] ) {if( dep[top[u]] > dep[top[v]] )u = f[top[u]];elsev = f[top[v]];}return ( dep[u] < dep[v] ) ? u : v; }int main() {scanf( "%d %d", &n, &Q );for( int i = 2, fa;i <= n;i ++ ) {scanf( "%d", &fa );G[fa].push_back( i );}dfs1( 1 );dfs2( 1, 1 );while( Q -- ) {int x;scanf( "%d", &x );if( x < 0 ) {x = -x;if( st.empty() ) printf( "0\n" );else {it = st.upper_bound( dfn[x] );int lca1 = 0, lca2 = 0;if( it != st.end() ) lca2 = lca( x, rnk[*it] );if( it != st.begin() ) it --, lca1 = lca( x, rnk[*it] );if( dep[lca1] > dep[lca2] ) printf( "%d\n", lca1 );else printf( "%d\n", lca2 );}}else {it = st.find( dfn[x] );if( it == st.end() ) st.insert( dfn[x] );else st.erase( it ); }}return 0; }

總結

以上是生活随笔為你收集整理的[2020-11-28 contest]素数（数学），精灵（区间dp），农夫约的假期（结论），观察（树链剖分lca+set）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。