狂歡1

• T1：玩游戲 / Game
• • 題目
  • 題解
  • 代碼實現
• T2：函數
• • 題目
  • 題解
  • 代碼實現
• T3：JOIOI王國
• • 題目
  • 題解
  • 代碼實現

T1：玩游戲 / Game

題目

ljcc 和他的學妹在玩游戲，這個游戲共有 n 輪，在第 i 輪獲勝會獲得 i 分，沒有平局。
現在給出 ljcc 和學妹的得分，求是否有一種方案符合當前得分。

輸入格式
從標準輸入讀入數據。
輸入一行輸入兩個數 代表 ljcc 和學妹的得分。
輸出格式
輸出到標準輸出。

若有解，在一行輸出一組合法的解。第一個數代表游戲總共進行了 n 輪，之后若干個數表示 ljcc 在哪些局獲勝了，每兩個數用單個空格隔開，行末不允許有空格。若沒有合法解輸出 No。

樣例
樣例輸入
10 5
樣例輸出
5 1 2 3 4
數據范圍與提示
a,b≤2³¹-1,1≤n≤10⁵

題解

首先No的情況很好想，運用等差數列公式跑一個$O(n)$看一下是否存在$i$滿足$\frac{(1+i)?i}{2}==n$
然后就是運用一點小技巧，我們發現對于一個$[1,n]$的數列，第$i$項與第$n?i+1$的和是一個定值$n+1$
所以仗著是$special$ $judge$我們就可以把$score$一直抽絲剝繭，減肥，讓它瘦到$<n+1$

代碼實現

我寫得比較復雜，用了許多特判，求輕噴，最后只想吐槽一下這個該死的$long$ $long$

#include <cstdio> #define MAXN 100000 #define LL long long LL a, b, sum; int main() {scanf ( "%lld %lld", &a, &b );LL i;bool flag = 0;for ( i = 1;i <= MAXN;i ++ ) {sum = ( i + 1 ) * i / 2;if ( sum == a + b ) {flag = 1;break;}}if ( ! flag )printf ( "No" );else {printf ( "%lld", i );if ( a <= i )printf ( " %lld", a );else if ( a <= i + i - 1 )printf ( " %lld %lld", a - i, i );else if ( b <= i ) {for ( LL j = 1;j <= i;j ++ )if ( j != b )printf ( " %lld", j );}else {LL x = 1, y = i;while ( a >= x + y ) {printf ( " %lld %lld", x, y );x ++;y --;a -= x + y;}if ( ! a )return 0;else {if ( x <= a && a <= y )printf ( " %lld", a );elseprintf ( " %lld %lld", x, a - x );}}}return 0; }

---

T2：函數

題目

wls 有 n 個二次函數 $Fi(x)=a_i?x^2+b_i?x+c_i$ (1 ≤ i ≤ n).
現在他想在${\sum }_{i=1}^n{x}_i=m$ 且 x 為正整數的條件下求${\sum }_{i=1}^{n}Fi(xi)$的最小值。
請求出這個最小值。

Input
第一行兩個正整數 n, m。
下面 n 行，每行三個整數 a, b, c 分別代表二次函數的二次項，一次項，常數項系數。
1 ≤ n ≤ m ≤ 100, 000
1 ≤ a ≤ 1, 000
?1, 000 ≤ b, c ≤ 1, 000
Output
一行一個整數表示答案。

Sample Input
2 3
1 1 1
2 2 2

Sample Output
13

題解

我們考慮對于一個函數$f(x)$的$△$，have a look↓：
$f(x)=a?x?x+b?x+c$
$f(x+1)=a?(x+1)?(x+1)+b?(x+1)+c$
兩式相減可得：$△=f(x+1)?f(x)=2?a+b$

---

首先$n$個函數要保證正整數，即每一個函數的$x$至少為1，接下來我們就要不停移動某一些函數的取值，就是$△$要最小，我們就可以用優先隊列維護每一條函數的$△$，每次取隊列的頭，直到滿足要求的$m$個即可

代碼實現

#include <cstdio> #include <queue> using namespace std; #define MAXN 500005 struct node {int id, val, idx;node () {}node ( int x, int y, int z ) {id = x;val = y;idx = z;}bool operator < ( const node &t ) const {return t.val < val;} }; priority_queue < node > q; int n, m, result; int a[MAXN], b[MAXN], c[MAXN];int main() {scanf ( "%d %d", &n, &m );for ( int i = 1;i <= n;i ++ ) {scanf ( "%d %d %d", &a[i], &b[i], &c[i] );result += a[i] + b[i] + c[i];int t = ( a[i] << 1 ) + a[i] + b[i];q.push( node ( i, t, 2 ) );}m -= n;while ( ! q.empty() && m ) {m --;result += q.top().val;node t = q.top();q.pop();int tmp = ( a[t.id] << 1 ) * t.idx + a[t.id] + b[t.id];q.push( node ( t.id, tmp, t.idx + 1 ) );}printf ( "%d", result );return 0; }

---

T3：JOIOI王國

題目

點擊查看
JOIOI 王國是一個 H 行 W 列的長方形網格，每個 $1\times 1$的子網格都是一個正方形的小區塊。為了提高管理效率，我們決定把整個國家劃分成兩個省 JOIJOI 和 IOIIOI

我們定義，兩個同省的區塊互相連接，意為從一個區塊出發，不用穿過任何一個不同省的區塊，就可以移動到另一個區塊。有公共邊的區塊間可以任意移動。

我們不希望劃分得過于復雜，因此劃分方案需滿足以下條件：
區塊不能被分割為兩半，一半屬 JOIJOI 省，一半屬 IOIIOI 省。
每個省必須包含至少一個區塊，每個區塊也必須屬于且只屬于其中一個省。
同省的任意兩個小區塊互相連接。
對于每一行/列，如果我們將這一行/列單獨取出，這一行/列里同省的任意兩個區塊互相連接。這一行/列內的所有區塊可以全部屬于一個省

現給出所有區塊的海拔，第 i行第 j 列的區塊的海拔為 $A_{i,j}$
設 JOI省內各區塊海拔的極差（最大值減去最小值）為 $R_{JOI}$， IOI省內各區塊海拔的極差為 $R_{IOI}$
在劃分后，省內的交流有望更加活躍。但如果兩個區塊的海拔差太大，兩地間的交通會很不方便。 因此，理想的劃分方案是 $max(R_{JOI},R_{IOI})$盡可能小。

你的任務是求出 $max(R_{JOI},R_{IOI})$ 至少為多大。

輸入格式
第一行，兩個整數 H,W用空格分隔。
在接下來的 H 行中，第 i 行有 W 個整數 $A_{i,1},A_{i,2},?,A_{i,W}$用空格分隔。
輸入的所有數的含義見題目描述。
輸出格式
一行，一個整數，表示 $max(R_{JOI},R_{IOI})$可能的最小值。

數據范圍
對于 $15\%$ 的數據，$H,W?10$
對于另外 $45\%$ 的數據， $H,W?200$
對于所有數據， $2?H,W?2000,A_{i,j}?10^9$

輸入輸出樣例
輸入
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10
輸出
11

J J J I
J J J I
J J I I
J I I I

J J I I
J J J I
J J J I
J I I I
輸入
8 6
23 23 10 11 16 21
15 26 19 28 19 20
25 26 28 16 15 11
11 8 19 11 15 24
14 19 15 14 24 11
10 8 11 7 6 14
23 5 19 23 17 17
18 11 21 14 20 16
輸出
18

題解

首先要想到這個劃分的矩陣一定是成單調性的，只可能如下圖四種情況

如果不是單調的，那么肯定有一列或者一行的J，I區域劃分會被斷掉，不滿足題意，應該很好理解吧，我就不畫圖了

---

接著便是思考算法，答案肯定是在$[0,maxh?minh]$中的，于是我們可以考慮二分這個答案，然后去驗證答案的正確性
那么如何驗證答案的正確性呢？其實區域劃分屬于誰并不重要，我們只在乎是不是屬于同一個省的區域

因此，我們就可以強制要求最高的區域是被劃分在JOI省的，自然而然最低的區域就只能劃分給IOI才能縮小答案
那么對于一個區域如果$max?a[i][j]\le ans$就代表著這個區域劃分給JOI省是可以滿足答案的，不難想到一個區域如果滿足答案肯定是多劃分給JOI省最好，這樣就可以盡量減小剩下屬于IOI省的區域的最大海拔，就可以盡可能地讓IOI省也滿足ans

對于一行假設我們已經找到了屬于JOI的省，那么接下來就要驗證IOI省的區域是否滿足ans，因為最低的海拔區是IOI省的，所以IOI的其它區域都是高于最低海拔區的，那么如果每一個$a[i][j]?min\le x$，ans就是合法的

最后看上圖，我們畫出來有四種劃分的單調情況所以對于每一種情況的答案可能是不一樣的，我們就要比較取最小值，
為此我畫的四種圖就畫得很有技巧，仔細觀察或者拿一張紙旋轉，就可以出現以上四種情況，這暗示我們可以將矩陣旋轉90°，180°，270°，代碼的實現就是從行與列的中間斷開進行交換，實現翻轉

代碼實現

#include <cstdio> #include <iostream> using namespace std; #define MAXN 2005 #define INF 0x7f7f7f7f int h, w, minn = INF, maxx = - INF, result = INF; int a[MAXN][MAXN];bool check ( int x ) {int last = w;for ( int i = 1;i <= h;i ++ ) {int tmp = 0;for ( int j = 1;j <= last;j ++ ) {if ( maxx - a[i][j] <= x )tmp = max ( tmp, j );elsebreak;}last = tmp;for ( int j = tmp + 1;j <= w;j ++ )if ( a[i][j] - minn > x )return 0;}return 1; }void solve ( int l, int r ) {int mid = ( l + r ) >> 1;if ( l > r )return;if ( check ( mid ) ) {result = min ( result, mid );solve ( l, mid - 1 );}elsesolve ( mid + 1, r ); }void reverse_row () {for ( int i = 1;i <= ( h >> 1 );i ++ )for ( int j = 1;j <= w;j ++ )swap ( a[i][j], a[h - i + 1][j] ); }void reverse_col () {for ( int i = 1;i <= h;i ++ )for ( int j = 1;j <= ( w >> 1 );j ++ )swap ( a[i][j], a[i][w - j + 1] ); } int main() {scanf ( "%d %d", &h, &w );for ( int i = 1;i <= h;i ++ )for ( int j = 1;j <= w;j ++ ) {scanf ( "%d", &a[i][j] );minn = min ( minn, a[i][j] );maxx = max ( maxx, a[i][j] );}solve ( 0, maxx - minn );reverse_row ();solve ( 0, maxx - minn );reverse_col ();solve ( 0, maxx - minn );reverse_row ();solve ( 0, maxx - minn );printf ( "%d\n", result );return 0; }

走了byebye有問題歡迎子初

總結

以上是生活随笔為你收集整理的周末狂欢赛1（玩游戏/Game，函数，JOIOI王国）的全部內容，希望文章能夠幫你解決所遇到的問題。

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