T1 奇怪的教室

題目背景

LSU 的老師有個(gè)奇怪的教室，同學(xué)們會(huì)從左到右坐成一個(gè)橫排，并且同一個(gè)位置可以坐多個(gè)同學(xué)。這天，入學(xué)考試的成績下來了。同學(xué)們想根據(jù)入學(xué)考試的成績，找出班里學(xué)霸扎堆的區(qū)域“學(xué)霸區(qū)”。

題目描述

共有 $N$ 個(gè)同學(xué)。給定每個(gè)同學(xué)的座位號 $X_i$，以及入學(xué)考試的分?jǐn)?shù) $S_i$。多個(gè)同學(xué)的座位號可能相同?，F(xiàn)在給定“學(xué)霸區(qū)”長度 $L$，請找出所有長度為 $L$ 的座位號區(qū)間，考試分?jǐn)?shù)之和的最大值。

輸入格式

第一行兩個(gè)整數(shù) $N,L$，表示學(xué)生數(shù)量和“學(xué)霸區(qū)”長度。

接下來 $N$ 行，每行兩個(gè)整數(shù) $X_i$ 和 $S_i$，表示學(xué)生座位號和分?jǐn)?shù)。

輸出格式

一個(gè)數(shù)，表示所有長度為 $L$ 的座位號區(qū)間，考試分?jǐn)?shù)之和的最大值。

樣例 #1

樣例輸入 #1

6 3
1 2
2 4
3 8
4 4
5 2
1000 1

樣例輸出 #1

16

提示

樣例說明：

選擇長度為 $3$ 的座位號區(qū)間 $[2,4]$，則包含 $3$ 位同學(xué)，其座位號和分?jǐn)?shù)分別為：

2 4
3 8
4 4

分?jǐn)?shù)之和為 $4+8+4=16$，最大。

數(shù)據(jù)范圍說明：

對于 $10\%$ 的數(shù)據(jù)，$L=0$（沒有邊緣）；

對于 $40\%$ 的數(shù)據(jù)，$L\le 1000$；

對于 $100\%$ 的數(shù)據(jù)，$1\le N\le 10^5$，$0\le L\le 10^5$，$1\le X_i\le 10^5$，$1\le S_i\le 100$。

除 $L=0$ 的情況外，$L$ 均為 $\ge 3$ 的奇數(shù)。

坑點(diǎn) & 正解

坑點(diǎn)：同一個(gè)座位上能做很多人，就能“疊高高”。例如這個(gè)樣例：

5 1
1 100
1 100
1 100
1 100
2 100

選 $1$ 這個(gè)座位能拿 $400$ 分。

正解：前綴和。

時(shí)間復(fù)雜度：$O(\max (X_i))$。

#include <bits/stdc++.h>
//#define int long long
using namespace std;int n,m;
int mx;const int N = 100010;
int a[N],b[N]; int ans;void solve()
{scanf("%d%d",&n,&m);for (int i = 1;i <= n;i++){int x,y;scanf("%d%d",&x,&y);a[x] += y;mx = max(mx,x); //最大的座位號 }//前綴和 for (int i = 1;i <= mx;i++)b[i] = b[i-1] + a[i];for (int i = 1;i <= mx-m+1;i++)ans = max(ans,b[i+m-1]-b[i-1]);cout << ans; 
}signed main()
{int TTT;
//	cin >> TTT;TTT = 1;while (TTT--) solve();return 0;
}

T2 安排班級

題目背景

新學(xué)期開始了，LSU 的老師迎來了若干個(gè)學(xué)生。現(xiàn)在老師要給大家分配班級。

題目描述

只考慮分配給每個(gè)班的學(xué)生人數(shù)。把總共 $M$ 個(gè)同學(xué)分配到總共 $N$ 個(gè)班里，可以有 $0$ 個(gè)同學(xué)的班。請問，一共有多少種不同的分配方案？

注意：假設(shè)有 $4$ 個(gè)學(xué)生，$3$ 個(gè)班。$[1,1,2]$，$[1,2,1]$ 和 $[2,1,1]$ 均視為相同的分配方案。$[0,2,2]$ 和 $[2,1,1]$ 視為不同的分配方案。

輸入格式

包含多組測試數(shù)據(jù)。

第一行為一個(gè)整數(shù)，表示測試數(shù)據(jù)的數(shù)目 $T$。

接下來$T$行，每行均包括二個(gè)整數(shù) $M$ 和 $N$。

輸出格式

共 $T$ 行，為對每組測試數(shù)據(jù)的結(jié)果。

樣例 #1

樣例輸入 #1

1
7 3

樣例輸出 #1

8

樣例 #2

樣例輸入 #2

3
3 2
4 3
2 7

樣例輸出 #2

2
4
2

提示

樣例1說明：
$8$ 種方案分別為：$[0,0,7],[0,1,6],[0,2,5],[0,3,4],[1,1,5],[1,2,4],[1,3,3],[2,2,3]$。

數(shù)據(jù)范圍：
對于所有數(shù)據(jù)，保證：$1\le M,N\le 10$，$0\le T\le 20$。

坑點(diǎn) & 正解

坑點(diǎn)：可以有 $0$ 個(gè)同學(xué)的班！

正解：一看數(shù)據(jù)范圍就知道是 DFS 暴搜。注意，因?yàn)椴荒芊窒嗤姆峙浞桨?#xff0c;所以需要非嚴(yán)格遞增去安排人數(shù)。

時(shí)間復(fù)雜度：$O(N!)$。

老師的正解：打表。

時(shí)間復(fù)雜度：$O(1)$，完美過關(guān)！

賽時(shí)正解：

#include <bits/stdc++.h>
#define int long long
using namespace std;int sum;
int a[30];
int m,n;void dfs(int s,int dep,int last)
{if (dep == n-1){sum++;return ;}for (int i = last;i <= s/(n-dep);i++){a[dep] = i;dfs(s-i,dep+1,i);}
}void solve()
{scanf("%lld%lld",&m,&n);dfs(m,0,0);printf("%lld\n",sum);sum = 0;
}signed main()
{int TTT;scanf("%lld",&TTT);
//	TTT = 1;while (TTT--) solve();return 0;
}

我做的：

#include <bits/stdc++.h>
//#define int long long
using namespace std;void solve()
{int m,n;cin >> m >> n;if (m == 1){if (n == 1) cout << 1;if (n == 2) cout << 1;if (n == 3) cout << 1;if (n == 4) cout << 1;if (n == 5) cout << 1;if (n == 6) cout << 1;if (n == 7) cout << 1;if (n == 8) cout << 1;if (n == 9) cout << 1;if (n == 10) cout << 1;}if (m == 2){if (n == 1) cout << 1;if (n == 2) cout << 2;if (n == 3) cout << 2;if (n == 4) cout << 2;if (n == 5) cout << 2;if (n == 6) cout << 2;if (n == 7) cout << 2;if (n == 8) cout << 2;if (n == 9) cout << 2;if (n == 10) cout << 2;}if (m == 3){if (n == 1) cout << 1;if (n == 2) cout << 2;if (n == 3) cout << 3;if (n == 4) cout << 3;if (n == 5) cout << 3;if (n == 6) cout << 3;if (n == 7) cout << 3;if (n == 8) cout << 3;if (n == 9) cout << 3;if (n == 10) cout << 3;}if (m == 4){if (n == 1) cout << 1;if (n == 2) cout << 3;if (n == 3) cout << 4;if (n == 4) cout << 5;if (n == 5) cout << 5;if (n == 6) cout << 5;if (n == 7) cout << 5;if (n == 8) cout << 5;if (n == 9) cout << 5;if (n == 10) cout << 5;}if (m == 5){if (n == 1) cout << 1;if (n == 2) cout << 3;if (n == 3) cout << 5;if (n == 4) cout << 6;if (n == 5) cout << 7;if (n == 6) cout << 7;if (n == 7) cout << 7;if (n == 8) cout << 7;if (n == 9) cout << 7;if (n == 10) cout << 7;}if (m == 6){if (n == 1) cout << 1;if (n == 2) cout << 4;if (n == 3) cout << 7;if (n == 4) cout << 9;if (n == 5) cout << 10;if (n == 6) cout << 11;if (n == 7) cout << 11;if (n == 8) cout << 11;if (n == 9) cout << 11;if (n == 10) cout << 11;}if (m == 7){if (n == 1) cout << 1;if (n == 2) cout << 4;if (n == 3) cout << 8;if (n == 4) cout << 11;if (n == 5) cout << 13;if (n == 6) cout << 14;if (n == 7) cout << 15;if (n == 8) cout << 15;if (n == 9) cout << 15;if (n == 10) cout << 15;}if (m == 8){if (n == 1) cout << 1;if (n == 2) cout << 5;if (n == 3) cout << 10;if (n == 4) cout << 15;if (n == 5) cout << 18;if (n == 6) cout << 20;if (n == 7) cout << 21;if (n == 8) cout << 22;if (n == 9) cout << 22;if (n == 10) cout << 22;}if (m == 9){if (n == 1) cout << 1;if (n == 2) cout << 5;if (n == 3) cout << 12;if (n == 4) cout << 18;if (n == 5) cout << 23;if (n == 6) cout << 26;if (n == 7) cout << 28;if (n == 8) cout << 29;if (n == 9) cout << 30;if (n == 10) cout << 30;}if (m == 10){if (n == 1) cout << 1;if (n == 2) cout << 6;if (n == 3) cout << 14;if (n == 4) cout << 23;if (n == 5) cout << 30;if (n == 6) cout << 35;if (n == 7) cout << 38;if (n == 8) cout << 40;if (n == 9) cout << 41;if (n == 10) cout << 42;}cout << '\n';
}signed main()
{int TTT;cin >> TTT;while (TTT--) solve();return 0;
}

同學(xué)評論：

帥爆了！

二維數(shù)組打表：

#include <bits/stdc++.h>
//#define int long long
using namespace std;int a[20][20] = {{1,1,1,1,1,1,1,1,1,1},{1,2,2,2,2,2,2,2,2,2},{1,2,3,3,3,3,3,3,3,3},{1,3,4,5,5,5,5,5,5,5},{1,3,5,6,7,7,7,7,7,7},{1,4,7,9,10,11,11,11,11,11},{1,4,8,11,13,14,15,15,15,15},{1,5,10,15,18,20,21,22,22,22},{1,5,12,18,23,26,28,29,30,30},{1,6,14,23,30,35,38,40,41,42}};void solve()
{int m,n;cin >> m >> n;cout << a[m-1][n-1] << '\n';
}signed main()
{int TTT;cin >> TTT;while (TTT--) solve();return 0;
}

T3 名牌

題目背景

LSU 的學(xué)校要舉行撕名牌大賽，每個(gè)同學(xué)在比賽前可以自己選擇一個(gè)字符串作為自己的名牌。

題目描述

LSU 想根據(jù)自己好朋友 CBJ 的名牌 $A$，來決定自己的名牌 $B$。

規(guī)則如下：

1. LSU 將 CBJ 的名牌 $A$ 復(fù)制一份放在末尾，得到字符串 $A+A$；

2. 在上一步得到的字符串中，LSU 任選一個(gè)位置，插入一個(gè)任意字符，得到自己的名牌 $B$。

現(xiàn)在給定 LSU 的名牌 $B$，你能找出 CBJ 的名牌 $A$ 嗎？

輸入格式

第一行一個(gè)整數(shù) $N$ 代表 LSU 的名牌 $B$ 的長度。
第二行一個(gè)長度為 $N$ 的字符串 $B$。

輸出格式

• 如果能從 $B$ 得到多種可行的 $A$ ，輸出 NOT UNIQUE。
• 如果能從 $B$ 得到唯一可行的 $A$ ，輸出該唯一解字符串。
• 如果不能從 $B$ 得到至少一種可行的 $A$ ，輸出 NOT POSSIBLE。

樣例 #1

樣例輸入 #1

9
ABABABABA

樣例輸出 #1

NOT UNIQUE

樣例 #2

樣例輸入 #2

7
CBXACBA

樣例輸出 #2

CBA

樣例 #3

樣例輸入 #3

3
XYZ

樣例輸出 #3

NOT POSSIBLE

提示

數(shù)據(jù)規(guī)模與約定

本題采用捆綁測試。

• 子任務(wù) 1（$35$ 分）：$N\le 2001$。
• 子任務(wù) 2（$65$ 分）：$2\le N\le 2\times 10^6+1$。

數(shù)據(jù)保證 $B$ 中只包含大寫字母。

坑點(diǎn) & 部分分 & 正解

坑點(diǎn)：字符串長度可能為偶數(shù)！

部分分就是暴力做法：

• 枚舉任意字符串的下標(biāo) $i$
• $B$ 字符串去掉這個(gè)任意字符
• 拆成左右兩部分
• 判斷左右是否相等

正解：哈希+前綴和。

• 將時(shí)間復(fù)雜度從 $O(N^2)\to O(N)$。

1. 特判字符串 $S$ 長為偶數(shù)，不可能
2. 計(jì)算哈希前綴和數(shù)組 $h$，$h_i$ 表示 $s_1,s_2,s_3\dots s_i$ 的哈希值
3. 預(yù)處理出哈希乘數(shù) $base$ 的 $i$ 次方，$pr{e}_i=pr{e}_{i?1}\times base$
4. 枚舉插入字符的位置，比較剩下的字符串中，左右兩部分的哈希值是否相等。$[l,r]$ 的哈希值是 $h_r?h_{l?1}\times pr{e}_{r?l+1}$。
5. 若左右兩部分哈希值相等，sum++記錄答案。
6. 若 $sum\ge 2$，輸出 NOT UNIQUE
7. 若 $sum=1$，輸出唯一解
8. 若 $sum=0$，輸出 NOT POSSIBLE

正解：

#include <bits/stdc++.h>
#define int long long
using namespace std;int n,mid;
char s[2000010];int base = 22783;
int la,lb;int pre[2000010],h[2000010];
string a,b,c,d;int _hash(int l,int r) {return h[r]-h[l-1]*pre[r-l+1];}
int __hash(int l,int r,int k) {return _hash(l,k-1)*pre[r-k]+_hash(k+1,r);}int sum;void solve()
{cin >> n >> s+1;mid = (n+1) / 2; if (n % 2 == 0){cout << "NOT POSSIBLE";return ;}pre[0] = 1;for (int i = 1;i <= n;i++){pre[i] = pre[i-1] * base;h[i] = h[i-1] * base + (s[i] - 'A' + 1);}la = _hash(mid+1,n);for (int i = mid+1;i <= n;i++) a.push_back(s[i]);for (int i = 1;i <= mid;i++){lb = __hash(1,mid,i);if (la == lb){sum++;c = a;break;}}lb = _hash(1,mid-1);for (int i = 1;i < mid;i++) b.push_back(s[i]);for (int i = mid;i <= n;i++){la = __hash(mid,n,i);if (la == lb){sum++;d = b;break;}}if (!sum) cout << "NOT POSSIBLE";else if (sum == 1 || c == d) cout << (c.size() ? c : d);else cout << "NOT UNIQUE";
}signed main()
{int TTT = 1;
//	cin >> TTT;while (TTT--) solve();return 0;
}

T4 奇怪的商店

題目描述

有一家奇怪的商店，店里的商品不是想買就能買，而是需要先積攢足夠的積分和威望。

商店里有 $N$ 件商品。想購買第 $i$ 件商品，需要買家有至少 $a_i$ 的積分和 $b_i$ 的威望，且購買后可以為買家提升 $c_i$ 的積分和 $d_i$ 的威望。

LSU 很喜歡這家商店，并且想購買店里所有的商品。LSU 可以以任意的順序進(jìn)行購買。

現(xiàn)在，LSU 希望你幫忙計(jì)算出，要購買所有商品，LSU 的初始積分最小值是多少？在初始積分為這個(gè)最小值的前提下，LSU 的初始威望最小值應(yīng)該是多少？

輸入格式

第一行一個(gè)整數(shù) $T$，表示該測試點(diǎn)所在的子任務(wù)編號。
第二行一個(gè)整數(shù) $N$，表示商店內(nèi)的商品總數(shù)。
接下來 $N$ 行，每行四個(gè)整數(shù)，依次表示第 $i$ 件商品的 $a_i,b_i,c_i,d_i$。

輸出格式

輸出一行兩個(gè)整數(shù)，用空格隔開。分別表示初始積分最小值，及在初始積分最小前提下的初始威望最小值。

樣例 #1

樣例輸入 #1

0
2
1 5 0 2
1 2 3 4

樣例輸出 #1

1 2

樣例 #2

樣例輸入 #2

3
6
33 33 97 64
27 10 18 2
10 51 43 79
36 98 61 93
56 3 50 77
63 77 19 45

樣例輸出 #2

10 51

樣例 #3

樣例輸入 #3

7
6
24457404 0 786147346 0
35269648 0 385597498 0
986729974 0 674254286 0
967571555 0 945921862 0
112950075 0 738686121 0
101290103 0 425579434 0

樣例輸出 #3

24457404 0

提示

樣例 1 解釋：

當(dāng)童童的初始積分為 $1$，威望為 $2$ 時(shí)，剛好可購買第 $2$ 件商品。

購買后，童童的積分為 $4$，威望為 $6$，可購買第 $1$ 件商品，從而完成購買商店內(nèi)所有商品。

【數(shù)據(jù)范圍說明】：

本題采用多測試點(diǎn)捆綁測試。

• 子任務(wù) $1$（$5$ 分）：保證 $N=0$。
• 子任務(wù) $2$（$5$ 分）：保證 $N=1$。
• 子任務(wù) $3$（$20$ 分）：保證 $a_i,b_i\le 100$，$N\le 6$。
• 子任務(wù) $4$（$10$ 分）：保證 $a_i,b_i\le 10^5$，$N\le 6$。
• 子任務(wù) $5$（$10$ 分）：保證 $a_i,b_i\le 10$。
• 子任務(wù) $6$（$10$ 分）：保證 $a_i,b_i\le 100$。
• 子任務(wù) $7$（$10$ 分）：保證 $b_i=0$，$N\le 6$。
• 子任務(wù) $8$（$10$ 分）：保證 $b_i=0$。
• 子任務(wù) $9$（$10$ 分）：保證 $N\le 6$。
• 子任務(wù) $10$（$10$ 分）：無特殊約定。

對于全部的測試點(diǎn)，保證 $0\le N\le 10^5$，$0\le a_i,b_i,c_i,d_i\le 10^9$。

正解

1. 先求初始積分的最小值：
   將問題轉(zhuǎn)化為有 $n$ 個(gè)商品，購買需要 $a_i$ 積分，買完后增加 $c_i$ 積分，求初始積分的最小值。
   簡單貪心：按照 $a_i$ 進(jìn)行從小到大排序，每次嘗試購買積分需求最少的商品，買不了就增加初始積分。
2. 再按照威望的要求為第一關(guān)鍵字從小到大，威望的加成為第二關(guān)鍵字從大到小排序。

#include <bits/stdc++.h>
#define int long long
using namespace std;int T;int n,ansa,ansb;
struct node //按照威望 
{int a,b,c,d;bool operator < (const node &x) const{return b != x.b ? b > x.b : d != x.d ? d < x.d : a != x.a ? a > x.a : c < x.c;}
}a[100010];
priority_queue <node> q;bool cmp(node a,node b) //按照積分 
{return a.a != b.a ? a.a < b.a : a.c != b.c ? a.c > b.c : a.b != b.b ? a.b < b.b : a.d > b.d;
}void solve()
{cin >> T >> n;for (int i = 1;i <= n;i++) cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;sort(a+1,a+n+1,cmp);for (int i = 1,aa = 0;i <= n;i++) //積分先貪心 {if (aa < a[i].a) ansa += a[i].a - aa,aa = a[i].a;aa += a[i].c;}cout << ansa << ' '; //先輸出積分最小值for (int i = 1,b = 0;i <= n;i++) //再算威望{while (a[i].a > ansa){if (b < q.top().b) ansb += q.top().b - b,b = q.top().b;b += q.top().d;ansa += q.top().c;q.pop(); }if (a[i].a <= ansa) q.push(a[i]);if (i == n)while (!q.empty()){if (b < q.top().b) ansb += q.top().b - b,b = q.top().b;b += q.top().d;q.pop();}}cout << ansb; //最后輸出威望最小值 
}signed main()
{int TTT;
//	cin >> TTT;TTT = 1;while (TTT--) solve();return 0;
}