為上個世紀的題寫個題解吧。。。
題面因為本人開始做題習慣從1開始標號，所以在\(t = 2\)的情況下的數字大小其實是離散化後的大小，要得到\(a[i]\)直接--就好了。
當\(t = 1\)時很好做，直接用樹狀陣列求一個順序對即可。
對於求順序對其實可以直接反著打逆序對。
即是在迴圈\(a[i]\)時，先輸出\(query(a[i])\)，再在\(a[i]\)的後面\(update(a[i], 1)\)就好了。
這個就有點難想了。
已知這個數的大小應該是在他前面且比他小的數與在他後面比他小的數的和。可是樹狀陣列只能維護字首和。
那麼現在就可以從後往前迴圈。
對於最後一位，它的大小肯定就是給出的\(b[i] + 1\)，那麼倒數第二位數可以分類討論：
#include #include #include using namespace std;
const int maxn = 1e6 + 5;
int t, n, a[maxn], b[maxn];
int bit[maxn], add;
int lowbit(int x)
void update(int x, int k)
int query(int x)
int main()
for (int i = 1; i <= n; i++)
} else
for (int i = n; i >= 1; i--) else r = mid;
}a[i] = r;
update(r, -1);
} for (int i = 1; i <= n; i++)
} return 0;
}
NOIP 編碼問題
設有一個陣列 a array 0.n 1 of integer 陣列中存放的元素為0 n 1之間的整數，且a i a j 當i j時 例如 n 6時，有 a 4,3,0,5,1,2 此時，陣列a的編碼定義如下 a 0 的編碼為0 a i 的編碼為 在a 0 a 1 a i 1 中比a i 的值小的個...
noip 1995 編碼問題
題目描述 設有一個陣列 a array 0 n 1 of integer 陣列中存放的元素為0 n 1之間的整數，且a i a j 當i j時 例如 n 6時，有 a 4,3,0,5,1,2 此時，陣列a的編碼定義如下 a 0 的編碼為0 a i 的編碼為 在a 0 a 1 a i 1 中比a i ...
NOIP2010普及組題解
三國遊戲 題目內容不放了 由於電腦總是會拆掉最大的組合，所以玩家最多隻能得到數值第二大的組合 那麼找出第二大的組合就行了 1 include2 include3 include4 include5 using namespace std 6int d 510 510 7int n 8int fst,...
NOIP2017普及組題解
老年tg選手來發普及組題解啦！新blog版本連結 題面傳送門 直接模擬，不多說了，官方也沒有卡精度，考察你會不會程式設計 include include include include include include define rep i,a,b for int i a i b i define...
NOIP2015 普及組 Junior 解題報告
國王將金幣作為工資，發放給忠誠的騎士。第一天，騎士收到一枚金幣 之後兩天 第二天和第三天 每天收到兩枚金幣 之後三天 第 四 五 六天 每天收到三枚金幣 之後四天 第 七 八 九 十天 每天收到四枚金幣 這種工資發放模式會一直這樣延續下去 當連續 n 天每天收到 n 枚金幣後，騎士會在之後的連續 n...
NOIP2005年普及組題解
這是第一題 這道題嘛，陶陶能夠到的高度是固定的，所以可以列舉每個蘋果，與陶陶能夠到的高度比較，然後再把計數器加1就行了。include include using namespace std int a 15 hei,ans int main 這是第二題 這道題，用的是一個簡簡單單的線段樹，也就沒有...
10NOIP普及組 接水問題
題目描述 學校裡有一個水房，水房裡一共裝有m 個龍頭可供同學們開啟水，每個龍頭每秒鐘的供水量相等，均為1。現在有n 名同學準備接水，他們的初始接水順序已經確定。將這些同學按接水順序從1到n 編號，i 號同學的接水量為wi。接水開始時，1 到m 號同學各佔一個水龍頭，並同時開啟水龍頭接水。當其中某名同...
NOIP2016 提高組 題解
模擬一下，記錄一個位置，如果左移則減，右移則加，再取個模。o n 首先，把u v拆成u lca和lca v兩條路徑。在u lca路徑上，若點j能觀察到該次行動，則應滿足等式 d u d j w j 移項 d u w j d j 其中,d v 表示v的深度，w v 表示v點出現觀察員的時間，再用len...
NOIP2006提高組題解
考察知識 區間型動態規劃 演算法難度 實現難度 xx 分析 只要分析出狀態轉移方程就不難實現了 根據題意，我們可以把項鍊看作矩陣，項鍊的合併就是矩陣乘法 所以我們定義兩個陣列x,y，x,y分別存矩陣的行列數 首先我們怎麼把項鍊轉化為矩陣呢 for int i 1 i n i scanf d a i ...
NOIP2010提高組題解
考察知識 佇列，模擬 演算法難度 x 實現難度 x 分析 真的很簡單，直接按照題意模擬即可 includeint n,m,que 1005 l,r,cnt 0,k int main printf d n cnt return 0 考察知識 動態規劃演算法難度 實現難度 xx 分析 如果想出了狀態轉移...