一次性寫(xiě)兩道題

• T1：一個(gè)簡(jiǎn)單的詢(xún)問(wèn)
• • 題目
  • 題解
  • 代碼實(shí)現(xiàn)
• T2：憤怒的小鳥(niǎo)
• • 題目
  • 暴搜題解
  • 暴搜代碼實(shí)現(xiàn)
  • 狀壓DP題解
  • 狀壓DP代碼實(shí)現(xiàn)

T1：一個(gè)簡(jiǎn)單的詢(xún)問(wèn)

題目

給你一個(gè)長(zhǎng)度為 N 的序列 ai ,1≤i≤N，和 q 組詢(xún)問(wèn)，每組詢(xún)問(wèn)讀入 l1,r1,l2,r2，需輸出
$\infty$
$\sum get(l1,r1,x)?get(l2,r2,x)$
$x=0$
get(l,r,x) 表示計(jì)算區(qū)間 [l,r] 中，數(shù)字 x 出現(xiàn)了多少次。

輸入格式
第一行，一個(gè)數(shù)字 N，表示序列長(zhǎng)度。
第二行，N 個(gè)數(shù)字，表示 a1～aN
第三行，一個(gè)數(shù)字 Q，表示詢(xún)問(wèn)個(gè)數(shù)。
第 4～Q+3 行，每行四個(gè)數(shù)字 l1,r1,l2,r2，表示詢(xún)問(wèn)。
輸出格式
對(duì)于每組詢(xún)問(wèn)，輸出一行一個(gè)數(shù)字，表示答案。

輸入輸出樣例
輸入
5
1 1 1 1 1
2
1 2 3 4
1 1 4 4
輸出
4
1
說(shuō)明/提示
對(duì)于20% 的數(shù)據(jù)，1≤N,Q≤1000；
對(duì)于另外 30% 的數(shù)據(jù)，1≤ai≤50；
對(duì)于 100% 的數(shù)據(jù)，N,Q≤50000，1≤ai≤N，1≤l1≤r1≤N，1≤l2≤r2≤N

答案有可能超過(guò) int 的最大值

題解

首先對(duì)于一個(gè)區(qū)間，我們考慮對(duì)它進(jìn)行轉(zhuǎn)化，使用差分
$get(l,r,x)=get(1,r,x)?get(1,l?1,x)$
那么答案也就可以轉(zhuǎn)化為
$$\sum _{x=0}^{\infty }get(l1,r1,x)?get(l2,r2,x)$$
$$?$$
$$\sum _{x=0}^{\infty }[get(1,r1,x)?get(1,l1?1,x)]?[get(1,r2,x)?get(1,l2?1,x)]$$
$$?$$
$$\sum _{x=0}^{\infty }get(1,r1,x)?get(1,r2,x)?get(1,r1,x)?get(1,l2?1,x)$$
$$?get(1,l1?1,x)?get(1,r2,x)+get(1,l1?1,x)?get(1,l2?1,x)$$

---

之后我們把它拆成四個(gè)詢(xún)問(wèn)塊，再用一個(gè)sign記錄前面的符號(hào)±
1.$get(1,r1,x)?get(1,r2,x)(+)$
2.$get(1,r1,x)?get(1,l2?1,x)(?)$
3.$get(1,l1?1,x)?get(1,r2,x)(?)$
4.$get(1,l1?1,x)?get(1,l2?1,x)(+)$

---

最后我們來(lái)考慮算法以及轉(zhuǎn)移過(guò)程
因?yàn)檫@個(gè)并沒(méi)有要求強(qiáng)制在線(xiàn)，其次它只有多個(gè)區(qū)間查詢(xún)，并沒(méi)有涉及到更新
所以莫隊(duì)就相較于線(xiàn)段樹(shù)更加適合，線(xiàn)段樹(shù)有點(diǎn)大材小用了
$$get(1,r,x)?get(1,l+1,x)=get(1,l,x)?get(1,r,x)+sum$$
sum表示a[l]在[1,r]區(qū)間出現(xiàn)的次數(shù)
為森么是這樣的呢？？
我們思考除開(kāi)a[l]，其它值出現(xiàn)次數(shù)并未發(fā)生改變，所以對(duì)答案的影響也并沒(méi)有改變
當(dāng)l+1，就意味著多加了一個(gè)get(1,r,x)，即
$$get(1,r,x)?get(1,l+1,x)=[get(1,l,x)+get(l+1,l+1,x)]?get(1,r,x)$$
那么同理r進(jìn)行移動(dòng)的時(shí)候，就要加減a[r]在[1,l]區(qū)間內(nèi)出現(xiàn)的次數(shù)

故，我們用兩個(gè)cntl[i]，cntr[i]分別表示i在[1,l]出現(xiàn)的次數(shù)和i在[1,r]出現(xiàn)的次數(shù)

---

這里用的莫隊(duì)算法，跟平常不太一樣，平時(shí)是用于維護(hù)[l,r]區(qū)間，
而這里我們維護(hù)是是[1,l]和[1,r]

代碼實(shí)現(xiàn)

#include <cmath> #include <cstdio> #include <algorithm> using namespace std; #define MAXN 50005 struct node {int id, l, r, sign, num; }query[MAXN << 2]; int n, q, tot, sum; int a[MAXN], cntl[MAXN], cntr[MAXN]; int result[MAXN];bool cmp ( node x, node y ) {return x.num == y.num ? x.r < y.r : x.num < y.num; }int main() {scanf ( "%d", &n );for ( int i = 1;i <= n;i ++ )scanf ( "%d", &a[i] );scanf ( "%d", &q );int T = ( int ) sqrt ( double ( n ) );for ( int i = 1;i <= q;i ++ ) {int l1, r1, l2, r2;scanf ( "%d %d %d %d", &l1, &r1, &l2, &r2 );query[++ tot] = ( node ) { i, r1, r2, 1, r1 / T };query[++ tot] = ( node ) { i, l1 - 1, r2, -1, ( l1 - 1 ) / T };query[++ tot] = ( node ) { i, l2 - 1, r1, -1, ( l2 - 1 ) / T };query[++ tot] = ( node ) { i, l1 - 1, l2 - 1, 1, ( l1 - 1 ) / T };}sort ( query + 1, query + tot + 1, cmp );int curl = 0, curr = 0;for ( int i = 1;i <= tot;i ++ ) {int l = query[i].l, r = query[i].r;while ( l < curl ) {cntl[a[curl]] --;sum -= cntr[a[curl]];curl --;}while ( l > curl ) {curl ++;cntl[a[curl]] ++;sum += cntr[a[curl]];}while ( r < curr ) {cntr[a[curr]] --;sum -= cntl[a[curr]];curr --;}while ( curr < r ) {curr ++;cntr[a[curr]] ++;sum += cntl[a[curr]];}result[query[i].id] += sum * query[i].sign;}for ( int i = 1;i <= q;i ++ )printf ( "%d\n", result[i] );return 0; }

T2：憤怒的小鳥(niǎo)

題目

Kiana 最近沉迷于一款神奇的游戲無(wú)法自拔。
簡(jiǎn)單來(lái)說(shuō)，這款游戲是在一個(gè)平面上進(jìn)行的。
有一架彈弓位于 (0,0) 處，每次 Kiana 可以用它向第一象限發(fā)射一只紅色的小鳥(niǎo)，小鳥(niǎo)們的飛行軌跡均為形如 y=ax^2+bx的曲線(xiàn)，其中 a,b是Kiana 指定的參數(shù)，且必須滿(mǎn)足 a < 0,a,b 都是實(shí)數(shù)。
當(dāng)小鳥(niǎo)落回地面（即 x 軸）時(shí)，它就會(huì)瞬間消失。

在游戲的某個(gè)關(guān)卡里，平面的第一象限中有 n 只綠色的小豬，其中第 i 只小豬所在的坐標(biāo)為(xi,yi)
如果某只小鳥(niǎo)的飛行軌跡經(jīng)過(guò)了(xi,yi)，那么第 i 只小豬就會(huì)被消滅掉，同時(shí)小鳥(niǎo)將會(huì)沿著原先的軌跡繼續(xù)飛行；
如果一只小鳥(niǎo)的飛行軌跡沒(méi)有經(jīng)過(guò) (xi,yi)，那么這只小鳥(niǎo)飛行的全過(guò)程就不會(huì)對(duì)第 i 只小豬產(chǎn)生任何影響。
例如，若兩只小豬分別位于 (1,3)和 (3,3)，Kiana 可以選擇發(fā)射一只飛行軌跡為 y=-x^2+4x的小鳥(niǎo)，這樣兩只小豬就會(huì)被這只小鳥(niǎo)一起消滅。
而這個(gè)游戲的目的，就是通過(guò)發(fā)射小鳥(niǎo)消滅所有的小豬。

這款神奇游戲的每個(gè)關(guān)卡對(duì) Kiana來(lái)說(shuō)都很難，所以Kiana還輸入了一些神秘的指令，使得自己能更輕松地完成這個(gè)游戲。這些指令將在【輸入格式】中詳述。
假設(shè)這款游戲一共有 TT 個(gè)關(guān)卡，現(xiàn)在 Kiana想知道，對(duì)于每一個(gè)關(guān)卡，至少需要發(fā)射多少只小鳥(niǎo)才能消滅所有的小豬。由于她不會(huì)算，所以希望由你告訴她。

輸入格式
第一行包含一個(gè)正整數(shù) T，表示游戲的關(guān)卡總數(shù)。
下面依次輸入這 T 個(gè)關(guān)卡的信息。每個(gè)關(guān)卡第一行包含兩個(gè)非負(fù)整數(shù) n,m，分別表示該關(guān)卡中的小豬數(shù)量和 Kiana 輸入的神秘指令類(lèi)型。接下來(lái)的 n 行中，第 i行包含兩個(gè)正實(shí)數(shù)xi,yi表示第 i 只小豬坐標(biāo)為 (xi,yi)數(shù)據(jù)保證同一個(gè)關(guān)卡中不存在兩只坐標(biāo)完全相同的小豬。

如果 m=0，表示Kiana輸入了一個(gè)沒(méi)有任何作用的指令。
如果 m=1，則這個(gè)關(guān)卡將會(huì)滿(mǎn)足：至多用?n/3+1? 只小鳥(niǎo)即可消滅所有小豬。
如果 m=2，則這個(gè)關(guān)卡將會(huì)滿(mǎn)足：一定存在一種最優(yōu)解，其中有一只小鳥(niǎo)消滅了至少?n/3? 只小豬。
保證1≤n≤18，0≤m≤2，0 <xi,yi < 100輸入中的實(shí)數(shù)均保留到小數(shù)點(diǎn)后兩位。

上文中，符號(hào)?c? 和?c? 分別表示對(duì) c 向上取整和向下取整，例如：?2.1?=?2.9?=?3.0?=?3.0?=?3.1?=?3.9?=3。
輸出格式
對(duì)每個(gè)關(guān)卡依次輸出一行答案。
輸出的每一行包含一個(gè)正整數(shù)，表示相應(yīng)的關(guān)卡中，消滅所有小豬最少需要的小鳥(niǎo)數(shù)量。

輸入輸出樣例
輸入
2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00
輸出
1
1

輸入
3
2 0
1.41 2.00
1.73 3.00
3 0
1.11 1.41
2.34 1.79
2.98 1.49
5 0
2.72 2.72
2.72 3.14
3.14 2.72
3.14 3.14
5.00 5.00
輸出
2
2
3

輸入
1
10 0
7.16 6.28
2.02 0.38
8.33 7.78
7.68 2.09
7.46 7.86
5.77 7.44
8.24 6.72
4.42 5.11
5.42 7.79
8.15 4.99
輸出
6

說(shuō)明/提示
【樣例解釋1】
這組數(shù)據(jù)中一共有兩個(gè)關(guān)卡。
第一個(gè)關(guān)卡與【問(wèn)題描述】中的情形相同，2只小豬分別位于(1.00,3.00)和 (3.00,3.00)，只需發(fā)射一只飛行軌跡為y = -x^2 + 4x的小鳥(niǎo)即可消滅它們。
第二個(gè)關(guān)卡中有5只小豬，但經(jīng)過(guò)觀(guān)察我們可以發(fā)現(xiàn)它們的坐標(biāo)都在拋物線(xiàn) y = -x^2 + 6x上，故Kiana只需要發(fā)射一只小鳥(niǎo)即可消滅所有小豬。

【數(shù)據(jù)范圍】

暴搜題解

首先就是計(jì)算兩個(gè)點(diǎn)的拋物線(xiàn)解析式（在狀壓題解中我就不再闡釋）
y1=a1*x²+ b1*x
y2=a2*x²+b2*x
可以先把a(bǔ)算出來(lái)，也就得把b1，b2消掉，那么方程式分別乘上另一個(gè)方程式b的系數(shù)
再兩式一減，把x移過(guò)去就可以了，即
b2*y1=a1*b2*x²+ b1*b2*x
b1*y2=a2*b1*x²+b1*b2*x

---

暴力的思路就是遍歷每一只豬，在當(dāng)前狀態(tài)下已經(jīng)用了多少只鳥(niǎo)（拋物線(xiàn)）
有多少只豬豬是一只豬孤單的死去
那么答案就是用的鳥(niǎo)的個(gè)數(shù)加上單獨(dú)的豬的個(gè)數(shù)
1.豬豬可以多個(gè)匹配被一只鳥(niǎo)一次性殺死
2.豬太特殊了，只能單獨(dú)找一鳥(niǎo)抵著它殺

那我們就枚舉每一個(gè)豬豬的狀態(tài)，單獨(dú)被殺，或者和前后面的某些豬一起被殺

---

部分闡釋在代碼中有呈現(xiàn)

暴搜代碼實(shí)現(xiàn)

#include <cmath> #include <cstdio> #define MAXN 20 int T, n, m, result; double x[MAXN], y[MAXN]; double tx[MAXN], ty[MAXN]; double pwxa[MAXN], pwxb[MAXN];bool check ( double a, double b ) {return fabs ( a - b ) < 1e-7; }void dfs ( int pig, int used, int alone ) {if ( used + alone >= result )//最優(yōu)性剪枝，因?yàn)樵谶@樣下去//1.拋物線(xiàn)的個(gè)數(shù)+1，少了一只單獨(dú)的豬-1，并不會(huì)使答案變小//2.豬仔之前與別的豬一起被一條拋物線(xiàn)經(jīng)過(guò)了，就掠過(guò)它，答案也沒(méi)有變//3.豬單獨(dú)被一條拋物線(xiàn)經(jīng)過(guò)+1，答案反而大了//所以這種時(shí)候往下搜索最多就是保持不變，一定大于當(dāng)前最佳答案，就沒(méi)有必要搜索了return;if ( pig > n ) {result = used + alone;return;}bool flag = 0;for ( int i = 1;i <= used;i ++ ) {//判斷之前構(gòu)造的拋物線(xiàn)有沒(méi)有一條經(jīng)過(guò)了這只豬if ( check ( pwxa[i] * x[pig] * x[pig] + pwxb[i] * x[pig], y[pig] ) ) {dfs ( pig + 1, used, alone );flag = 1;break;}}if ( ! flag ) {//看能不能把這只豬和單身的豬組個(gè)隊(duì)一起死for ( int i = 1;i <= alone;i ++ ) {//特殊判斷，如果x相同意味著，這是一條常函數(shù)，是不可能一起死的if ( check ( tx[i], x[pig] ) )continue;double a = ( y[pig] * tx[i] - ty[i] * x[pig] ) / ( x[pig] * x[pig] * tx[i] - tx[i] * tx[i] * x[pig] );double b = ( y[pig] - x[pig] * x[pig] * a ) / x[pig];if ( a < 0 ) {//要小于零才是匹配的組隊(duì)pwxa[used + 1] = a;pwxb[used + 1] = b;double Ai = tx[i], Bi = ty[i];//這只豬已經(jīng)和本層循環(huán)的豬配對(duì)了，就要把它踢出單身狗群體for ( int j = i;j < alone;j ++ ) {tx[j] = tx[j + 1];ty[j] = ty[j + 1];}dfs ( pig + 1, used + 1, alone - 1 );//回溯后，這只豬重獲單身for ( int j = alone;j > i;j -- ) {ty[j] = ty[j - 1];tx[j] = tx[j - 1];}tx[i] = Ai;ty[i] = Bi;}}//本層循環(huán)的豬也加入單身行列tx[alone + 1] = x[pig];ty[alone + 1] = y[pig];dfs ( pig + 1, used, alone + 1 );} }int main() {scanf ( "%d", &T );while ( T -- ) {result = 0x7f7f7f7f;scanf ( "%d %d", &n, &m );for ( int i = 1;i <= n;i ++ )scanf ( "%lf %lf", &x[i], &y[i] );dfs ( 1, 0, 0 );printf ( "%d\n", result );}return 0; }

狀壓DP題解

n≤18，在暴搜基礎(chǔ)上我們就可以考慮狀壓DP
0表示這只豬還活著，1表示這只豬仔已經(jīng)被鳥(niǎo)干死了

---

首先我們還是暴力跑個(gè)n²，去求出以任意兩只豬構(gòu)造一條拋物線(xiàn)，一次性能殺死多少豬
接著就是常規(guī)的狀態(tài)轉(zhuǎn)移了$DP[s]$表示當(dāng)狀態(tài)為s時(shí)，所用的最少拋物線(xiàn)個(gè)數(shù)
當(dāng)s狀態(tài)時(shí)枚舉每一條拋物線(xiàn)與s進(jìn)行或運(yùn)算，有可能開(kāi)始s就已經(jīng)殺了某只豬
而這條拋物線(xiàn)讓豬豬重復(fù)死亡了罷了
$$DP[s|pwx[i][j]]=min(DP[s|pwx[i][j],DP[s]+1)$$

---

此處還可以有一個(gè)優(yōu)化
我們想一想如果pwx能打1，2，4，7，它會(huì)傻著先把后面的4,7殺了再跑回來(lái)搞1,4？
肯定是一路上不走回頭路，不打回頭豬啊！
所以我們就開(kāi)一個(gè)數(shù)組記錄當(dāng)狀態(tài)為s時(shí)最先打到的豬仔是誰(shuí)

狀壓DP代碼實(shí)現(xiàn)

#include <cmath> #include <cstdio> #include <cstring> #include <iostream> using namespace std; #define eps 1e-7 #define MAXN 20 int n, m, T; double x[MAXN], y[MAXN]; int pwx[MAXN][MAXN], dp[1 << MAXN]; int lowcount[1<< MAXN];bool check ( double u, double v ) {return fabs ( u - v ) < eps; }void count ( double &a, double &b, double x1, double y1, double x2, double y2 ) {a = ( y1 * x2 - y2 * x1 ) / ( x1 * x1 * x2 - x2 * x2 * x1 );b = ( y1 - x1 * x1 * a ) / x1; }int main() {for ( int i = 0;i < ( 1 << 18 );i ++ ) {int j = 1;while ( ( i & ( 1 << ( j - 1 ) ) ) && j <= 18 )j ++;lowcount[i] = j;}scanf ( "%d", &T );while ( T -- ) {scanf ( "%d %d", &n, &m );for ( int i = 1;i <= n;i ++ )scanf ( "%lf %lf", &x[i], &y[i] );memset ( dp, 0x7f, sizeof ( dp ) );memset ( pwx, 0, sizeof ( pwx ) );dp[0] = 0; for ( int i = 1;i <= n;i ++ ) {for ( int j = 1;j <= n;j ++ ) {if ( x[i] == x[j] )continue;double a, b;count ( a, b, x[i], y[i], x[j], y[j] );if ( a >= 0 ) continue;for ( int k = 1;k <= n;k ++ )if ( check ( a * x[k] * x[k] + b * x[k], y[k] ) ) pwx[i][j] |= ( 1 << ( k - 1 ) );}}for ( int i = 0;i < ( 1 << n );i ++ ) {int j = lowcount[i];dp[i | ( 1 << ( j - 1 ) )] = min ( dp[i | ( 1 << ( j - 1 ) )], dp[i] + 1 );for ( int k = 1;k <= n;k ++ )dp[i | pwx[j][k]] = min ( dp[i | pwx[j][k]], dp[i] + 1 );}printf ( "%d\n", dp[( 1 << n ) - 1] );} return 0; }

走了，如有疑問(wèn)歡迎評(píng)論，歡迎指出錯(cuò)誤

總結(jié)

以上是生活随笔為你收集整理的[ NOIP提高组 2016]愤怒的小鸟（暴搜 + 状压DP）// [SNOI2017]一个简单的询问（莫队）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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