文章目錄
- 第一次演算法作業
- Problem A. 思維之花-方程
- Problem C. 擺三角形（列舉）
- 第二次演算法作業
- Problem A. 立方質數（列舉）
- Problem B. 開燈（模擬）
- Problem C. 鍵盤打字（模擬）
- Problem D. 約翰的母牛（列舉）
- Problem E. 整數變換（位運算）
- 第三次演算法作業
- Problem A. 切割木棍（二分）
- Problem B. 移除石頭（二分）
- Problem C. 上臺階（動態規劃）
- Problem D. 包裹快遞（二分）
- Problem E. 移動圓盤
- 第四次演算法作業
- Problem A. 采藥（動規）
- Problem B. 裝箱問題（動規）
- Problem C. 合唱隊形（動規）
- Problem D. 馬攔過河卒（動規）
- Problem E. 傳球游戲（動規）
- 第五次演算法作業
- Problem A. 單行最大子矩陣和問題（動規）
- Problem B. 多行最大子矩陣和問題（動規）
- Problem C. 小明的打工計劃 （動規）
- Problem D. 郵票面值設計（動規）
- Problem E. 導彈攔截（動規）
- 第六次演算法作業
- Problem A. 合并果子(貪心)
- Problem B. 最小差距(貪心)
- Problem C. 上帝的愛好(貪心)
- Problem D. 任務調度問題(貪心)
- Problem E. sqy 的錫紙燙(貪心)
- 第七次演算法作業
- Problem A. 海戰（dfs）
- Problem B. 礦床個數（dfs）
- Problem C. 8皇后（dfs）
- Problem D. 無向圖的連通性（dfs）
- Problem E. 24點游戲(dfs)
- 期中測驗
- Problem B. 等價運算式
- Problem C. 求解多元一次方程組
- Problem E. 最佳課題選擇(動規)
- Problem F. 逆序對的個數()
第一次演算法作業
Problem A. 思維之花-方程
時間限制 1000 ms
記憶體限制 128 MB
題目描述
有形如：ax^3+bx^2+cx+d=0 這樣的一個一元三次方程，給出該方程中各項的系數(a，b，c，d 均為實數)，并約定該方程存在三個不同實根(根的范圍在-100至100之間)，且根與根之差的絕對值> =1，要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，并精確到小數點后2位，
提示：記方程f(x)=0，若存在2個數x1和x2，且x1< x2，f(x1)*(x2)< 0，則在(x1，x2)之間一定有一個根，
輸入資料
輸入該方程中各項的系數 (a,b,c,d (a,b,c,d 均為實數)，
輸出資料
由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，并精確到小數點后 22 位，
樣例輸入
1 -5 -4 20
樣例輸出
-2.00 2.00 5.00
#include <iostream>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
double a, b, c, d;
#define f(x) (a*(x)*(x)*(x)+b*(x)*(x)+c*(x)+d)
void ef(double s, double e)
{
if (f(s) * f(e) <= 0)
{
double mid = (s + e) / 2.0;
if (fabs(f(mid)) <= 1e-8)
{
cout<<setiosflags(ios::fixed) << setprecision(2) << mid << " ";
return;
}
if (f(mid) * f(s) < 0)
ef(s, mid);
else
ef(mid, e);
}
}
int main()
{
cin >> a >> b >> c >> d;
for (double s = -101; s <= 101; s += 1)
{
ef(s, s + 1);
}
return 0;
}
Problem C. 擺三角形（列舉）
時間限制 1000 ms
記憶體限制 64 MB
題目描述
有n根小木棒，任選三根木棒組成一個三角形，問三角形周長最大是多少，（保證至少存在一種選法能組成三角形）
輸入資料
第一行為一個正整數n，3=<n<=100 第二行為n個正整數，代表小木棒長度，不超過100.
輸出資料
三角形周長的最大值
樣例輸入
5
1 2 3 4 5
樣例輸出
12
解法1：
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX_N = 105;
int cmp(const void* a, const void* b)
{
return *(int*)a - *(int*)b;
}
void solve(int n, int* a)
{
qsort(a, n, sizeof(a[0]), cmp);
int sum = 0;
for (int i = n - 1; i > 1; --i)
{
if (a[i] + a[i - 1] > a[i - 2])
if (a[i] + a[i - 2] > a[i - 1])
if (a[i - 1] + a[i - 2] > a[i])
{
sum = a[i] + a[i - 1] + a[i - 2]; break;
}
}
cout << sum;
}
int main()
{
int n, a[MAX_N];
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
solve(n, a);
return 0;
}
第二次演算法作業
Problem A. 立方質數（列舉）
時間限制 1000 ms
記憶體限制 64 MB
題目描述
如果一個質數能被表示為三個不同的質數的和的形式，那么我們稱它為立方質數，現在給你一個數n，判斷它是不是立方質數，
輸入資料
正整數n，n<=1000
輸出資料
Yes或者No
樣例輸入
19
樣例輸出
Yes
解法1
#include <iostream>
#include <cmath>
using namespace std;
//判斷是否為質數
bool isPrime(int num) {
if (num <= 3) {
return num > 1;
}
// 不在6的倍數兩側的一定不是質數
if (num % 6 != 1 && num % 6 != 5) {
return false;
}
for (int i = 5; i <= sqrt(num); i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
int main() {
int n;
cin >> n;
bool flag = false;
if (!isPrime(n)) {
cout << "No" << endl;
}
else {
for (int i = 1; i <= n; i++) {
if (isPrime(i)) {
for (int j = i + 1; j <= n; j++) {
if (isPrime(j) && isPrime(n - i - j) && (n - i - j) != i && (n - i - j) != j) {
flag = true;
}
}
}
}
if (flag) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
Problem B. 開燈（模擬）
時間限制 1000 ms
記憶體限制 64 MB
題目描述
有n盞燈，編號都是1-n，初始燈都是關著的，有n個人，第1個人會打開所有的燈，第2個人會按下所有編號為2的倍數的燈的開關（這些燈將被關掉），第3個人會按下所有編號為3的倍數的開關，以此類推，第n個人會按下所有編號為n的倍數的開關，問最后有幾盞燈是亮著的，
輸入資料
一個正整數n，n<100000
輸出資料
亮著的燈的數量
樣例輸入
5
樣例輸出
2
解法1：
#include <iostream>
using namespace std;
int check(int x) {
int cnt = 0;
int i;
for (i = 1; i * i < x; ++i) {
if (!(x % i)) {
cnt += 2;
}
}
if (i * i == x) {
++cnt;
}
return cnt;
}
int main() {
int n;
cin >> n;
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (check(i) % 2) {
++cnt;
}
}
cout << cnt << endl;
return 0;
}
解法2：
# include "iostream"
# include "vector"
# include "numeric"
using namespace std;
#define MAX_SIZE 100000
int main(){
int n;
cin >>n;
vector<int> p(n+1, 1);
for(int i = 2; i <= n; i++){
for(int j = 1; j*i <= n; j++){
if(p[j*i] == 1)
p[j*i] = 0;
else
p[j*i] = 1;
}
}
p[0] = 0;
cout << accumulate(p.begin(), p.end(), 0) << endl; // 累加范圍，和累加初值
return 0;
}
解法3：
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
int i = 1;
for(; i * i <= n; i++){}
cout << i - 1 << endl;
return 0;
}
Problem C. 鍵盤打字（模擬）
時間限制 1000 ms
記憶體限制 64 MB
題目描述
小明剛買了一個機械鍵盤，但他在用機械鍵盤打字的時候發現鍵盤的Home鍵和End鍵壞掉了，于是他在打字的時候游標有時會突然跑到行首，有時又會突然跑到行尾，現在給你鍵盤的輸入，求最后螢屏上的字串，
輸入資料
輸入資料為一行字串，字串只包含小寫英文字母,’[‘符號以及’]‘符號，’['代表按下了Home鍵，‘]’代表按下了End鍵，字串長度不超過100000，
輸出資料
輸出最后螢屏上的字串，
樣例輸入
xiechengxuz[henhao]wan
樣例輸出
henhaoxiechengxuzwan
樣例說明
可能出現多個’[‘和’]’，也可能沒有’[‘和’]’
解法1：
# include <iostream>
# include <string>
# include <queue>
using namespace std;
deque<string> q;
string buf;
void fun(int flag, string& buf) {
if (flag)
q.push_back(buf);
else
q.push_front(buf);
buf.clear();
}
int main() {
string s;
cin >> s;
int flag = 0;// flag=0,放在前面； flag =1, 放在后面
for (int i = 0; i < s.length(); i++)
{
if (s[i] != '[' && s[i] != ']') {
buf += s[i];
}else if (s[i] == '[') {
fun(flag, buf);
flag = 0;
}
else {
fun(flag, buf);
flag = 1;
}
}
fun(flag, buf);
for (auto i : q)
cout << i;
}
Problem D. 約翰的母牛（列舉）
時間限制 1000 ms
記憶體限制 128 MB
題目描述
農民約翰的母牛總是生產出最好的肋骨，你能通過農民約翰和美國農業部標記在每根肋骨上的數字認出它們，
農民約翰確定他賣給買方的是真正的質數肋骨,是因為從右邊開始切下肋骨,每次還剩下的肋骨上的數字都組成一個質數,舉例來說:
7 3 3 1
全部肋骨上的數字 7331是質數;三根肋骨 733是質數;二根肋骨 73 是質數;當然,最后一根肋骨 7 也是質數，
7331 被叫做長度 4 的特殊質數，
寫一個程式對給定的肋骨的數目 N (1< =N< =8),求出所有的特殊質數，數字1不被看作一個質數，
輸入資料
單獨的一行包含 N ，
輸出資料
按順序輸出長度為 N 的特殊質數,每行一個，
并按大小順序排列(從小到大).
樣例輸入
4
樣例輸出
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393
解法1：
#include<iostream>
#include<cmath>
#include <queue>
using namespace std;
bool isPrime(int num) { //判斷是否為質數
if (num <= 3) {
return num > 1;
}
if (num % 6 != 1 && num % 6 != 5) { // 不在6的倍數兩側的一定不是質數
return false;
}
for (int i = 5; i <= sqrt(num); i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
int main() {
queue <int> q;
int n, m = 4;
int a[] = { 2,3,5,7 }; // 單獨一個數是質數
int b[] = { 1,3,7,9 }; //一這些數字為結尾的，可能是質數
cin >> n;
for (int i = 0; i < 4; i++) q.push(a[i]);
for (int i = 2; i <= n; i++) {
int l = m;
m = 0;
for (int j = 0; j < l; j++) {
for (int k = 0; k < 4; k++) //選擇列舉b[k]
if (isPrime(q.front() * 10 + b[k]))
q.push(q.front() * 10 + b[k]), m++;
q.pop();
}
}
while (!q.empty()) {
cout << q.front() << endl;
q.pop();
}
return 0;
}
解法2
#include <iostream>
#include <vector>
using namespace std;
int mn = 1, mx = 1;
vector<int> bones;
bool isprime(int x) {
if (x == 2) {
return true;
}
if (x == 1 || !(x % 2)) {
return false;
}
for (int i = 3; i * i <= x; i += 2) {
if (!(x % i)) {
return false;
}
}
return true;
}
void dfs(int x) {
if (x >= mn && x < mx) {
bones.push_back(x);
return;
}
x *= 10;
for(int i = 1; i < 10; ++i) {
if (isprime(x + i)) {
dfs(x + i);
}
}
}
int main() {
int n;
cin >> n;
while (--n) {
mn *= 10;
mx = mn;
}
mx *= 10;
dfs(0);
for (int i : bones) {
cout << i << endl;
}
return 0;
}
Problem E. 整數變換（位運算）
時間限制 1000 ms
記憶體限制 128 MB
題目描述
給出一個小于2^32的正整數，這個數可以用一個32位的二進制數表示（不足32位用0補足），我們稱這個二進制數的前16位為“高位”，后16位為“低位”，將它的高低位交換，我們可以得到一個新的數，試問這個新的數是多少（用十進制表示），
例如，數1314520用二進制表示為0000 0000 0001 0100 0000 1110 1101 1000（添加了11個前導0補足為32位），其中前16位為高位，即0000 0000 0001 0100；后16位為低位，即0000 1110 1101 1000，將它的高低位進行交換，我們得到了一個新的二進制數0000 1110 1101 1000 0000 0000 0001 0100，它即是十進制的249036820，
輸入資料
一個小于 232232 的正整數
輸出資料
將新的數輸出
樣例輸入
1314520
樣例輸出
249036820
解法1：
#include<iostream>
using namespace std;
int main()
{
unsigned long long x;
cin >> x;
cout << ((x & 0x0000ffff) << 16 | (x & 0xffff0000) >> 16) << endl;
}
第三次演算法作業
Problem A. 切割木棍（二分）
時間限制 1000 ms
記憶體限制 64 MB
題目描述
我們有n根的木棍，現在從這些木棍中切割出來m條長度相同的木棍，問這m根木棍最長有多長？
輸入資料
第一行輸入兩個數字，n(1<=n<=1000)為木棍數目，m(1<=m<=1000)為需要切割出的相同長度的木棍數目 隨后n個正整數，表示原始木棍的長度(<=10000)
輸出資料
每組輸出一行結果，表示切割后繩子的最長長度(保留兩位小數)
樣例輸入
4 5
5 6 7 8
樣例輸出
4.00
解法1
#include <iostream>
using namespace std;
#include <vector>
#include <iomanip>
#include <cmath>
int main()
{
int n,m;
cin >>n>> m;
vector<int> v;
double max=0;
for (int i = 0; i < n; i++) {
int t;
cin >> t;
v.push_back(t);
if (t > max)
max = t;
}
double s = 0, e = max;
double mid;
while (s + 0.01 < e) {
int cnt = 0;
mid = round(((s + e) / 2.00) * 100) / 100.00; //四舍五入
for (int i = 0; i < n; i++)
cnt += (double)(v[i] / mid);
if (cnt >= m) s = mid;
else e = mid;
}
cout << setiosflags(ios::fixed) << setprecision(2) << s ;
}
Problem B. 移除石頭（二分）
時間限制 1000 ms
記憶體限制 64 MB
題目描述
有一條河，河中間有一些石頭，已知石頭的數量和相鄰兩塊石頭之間的距離，現在可以移除一些石頭，問最多移除m塊石頭后（首尾兩塊石頭不可以移除），相鄰兩塊石頭之間的距離的最小值最大是多少，
輸入資料
第一行輸入兩個數字，n（2<=n<=1000）為石頭的個數，m（0<=m<=n-2）為可移除的石頭數目 隨后n-1個數字，表示順序和相鄰兩塊石頭的距離d（d<=1000）
輸出資料
輸出最小距離的最大值
樣例輸入
4 1
1 2 3
樣例輸出
3
解法1：
#include <stdio.h>
int n, m,ans;
int d[1005];
int l[1005] = { 0 };
int main() {
scanf("%d%d", &n, &m);
for (int i = 2; i <= n; i++) {
scanf("%d", &d[i]);
l[i] = d[i] + l[i - 1];
}
int left=0,right=l[n];
while(left<=right)
{
int now=0,mid=(left+right)>>1,s=0;
for(int i=2;i<=n;++i)
{
if(l[i]-l[now]<mid) ++s;
else now=i;
}
if(s>m) right=mid-1;
else
{
ans=mid;
left=mid+1;
}
}
printf("%d",ans);
return 0;
}
Problem C. 上臺階（動態規劃）
時間限制 1000 ms
記憶體限制 64 MB
題目描述
樓梯有n階，可以一步上一階、兩階或三階，問有多少種不同的走法
由于答案很大，mod(1e9+7)輸出
輸入資料
一個正整數n，代表樓梯的階數，n<=1000000
輸出資料
方案數
樣例輸入
3
樣例輸出
4
解法1
# include <iostream>
# include <cmath>
# include <vector>
using namespace std;
int main() {
long n;
cin >> n;
long long f[3];
f[0] = 1;
f[1] = 2;
f[2] = 4;
int mod = (1e9 + 7);
long long ans;
if (n < 3) {
ans = f[n - 1];
}
else {
for (long i = 3; i < n; i++)
{
long long t;
t = f[0];
f[0] = f[1];
f[1] = f[2];
f[2] = (t + f[0] + f[1]) % mod;
}
ans = f[2];
}
cout << ans;
}
Problem D. 包裹快遞（二分）
時間限制 1000 ms
記憶體限制 128 MB
題目描述
一個快遞公司要將n個包裹分別送到n個地方，并分配給郵遞員小K一個事先設定好的路線，小K需要開車按照路線給的地點順序相繼送達，且不能遺漏一個地點，小K得到每個地方可以簽收的時間段，并且也知道路線中一個地方到下一個地方的距離，若到達某一個地方的時間早于可以簽收的時間段，則必須在這個地方停留至可以簽收，但不能晚于簽收的時間段，可以認為簽收的程序是瞬間完成的，
為了節省燃料，小K希望在全部送達的情況下，車的最大速度越小越好，就找到了你給他設計一種方案，并求出車的最大速度最小是多少，
輸入資料
第 11 行為一個正整數 n (n<2×104)，n (n<2×104)， 表示需要運送包裹的地點數，
下面 nn 行，第 i+1i+1 行有 33 個正整數 xi,yi,si，xi,yi,si， 表示按路線順序給出第 ii 個地點簽收包裹的時間段為 [xi,yi]，[xi,yi]， 即最早為距出發時刻 xi，xi， 最晚為距出發時刻 yi，yi， 從前一個地點到達第 ii 個地點距離為 si，si， 且保證路線中 xixi 遞增，
可以認為 s1s1 為出發的地方到第 11 個地點的距離，且出發時刻為 00 ，
輸出資料
僅包括一個整數，為車的最大速度最小值，結果保留兩位小數，
樣例輸入
3
1 2 2
6 6 2
7 8 4
樣例輸出
2.00
樣例說明
第一段用1的速度在時間2到達第1個地點，第二段用0.5的速度在時間6到達第2個地點，第三段用2的速度在時間8到達第3個地點，
解法1：
#include <stdio.h>
#define maxn 200005
long double st=0,en=1e9,mid;
int i,n;
int v[maxn][3];
bool check(long double x) {
long double minT, totalT=0;
for (int i = 0; i < n; i++) {
minT = v[i][2] / x;
totalT = minT + totalT;
if (totalT < v[i][0])
totalT = v[i][0];
else if (totalT > v[i][1])
return false;
}
return true;
}
int main(){
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d%d%d",&v[i][0], &v[i][1], &v[i][2]);
while(en-st>1e-9){
mid=(en+st)/2.00;
if(check(mid)) en=mid;
else st=mid;
}
printf("%.2f",double(st));
return 0;
}
Problem E. 移動圓盤
時間限制 1000 ms
記憶體限制 64 MB
題目描述
有ABC三根桿和一些圓盤，開始的時候圓盤從小到大摞在A桿上，小盤在上大盤在下，規定如果圓盤p摞在圓盤q上面，那么rp<=rq，rp和rq為p和q的半徑，
現在有若干個圓盤，半徑從1到n，半徑為i的圓盤有i個，每次操作可以移動一個圓盤，問把所有圓盤從A桿移動到C桿上最少需要幾次操作， 由于最終答案可能很大，所以答案對1e9+7取模輸出，
輸入資料
一個正整數n，n<=1e5
輸出資料
最少操作次數
樣例輸入
2
樣例輸出
4
樣例說明
第一步把半徑為1的圓盤從A放到B 第二步和第三步把兩個半徑為2的圓盤從A放到C 第四步把半徑為1的圓盤從B放到C
解法1：
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long cnt=0;
long long mod = 1e9 + 7;
for (long long i = 1; i <= n; i++)
{
cnt =(cnt*2+i)%mod;
}
cout << cnt<<endl;
}
第四次演算法作業
Problem A. 采藥（動規）
時間限制 1000 ms
記憶體限制 128 MB
題目描述
辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師，為此，他想拜附近最有威望的醫師為師，醫師為了判斷他的資質，給他出了一個難題，醫師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值，我會給你一段時間，在這段時間里，你可以采到一些草藥，如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大，”
如果你是辰辰，你能完成這個任務嗎？
輸入資料
輸入的第一行有兩個整數 T (1≤T≤1000) 和 M (1≤M≤100) 用一個空格隔開，T 代表總共能夠用來采藥的時間 ，M 代表山洞里的草藥的數目，接下來的 M 行每行包括兩個在 1 到100之間（包括 1 和100）的整數，分別表示采摘某株草藥的時間和這株草藥的價值，
輸出資料
輸出包括一行，這一行只包含一個整數，表示在規定的時間內，可以采到的草藥的最大總價值，
樣例輸入
70 3
71 100
69 1
1 2
樣例輸出
3
解法1
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1e4;
int f[maxn]; //f：草藥的總價值
int w[maxn], val[maxn]; //w: 時間花費 val:草藥價值
void solve(int m, int t) {
memset(f, 0, sizeof f);
for (int i = 1; i <= m; i++) {
for (int v = t; v > 0; v--) {
if (v >= w[i])
f[v] = max(f[v], f[v - w[i]] + val[i]);
}
}
cout << f[t];
}
int main() {
int m, t; //t 采藥的時間，m草藥的數目
cin >> t >> m;
for (int i = 1; i <= m; i++) {
cin>>w[i] >> val[i] ;
}
solve(m,t);
return 0;
}
Problem B. 裝箱問題（動規）
時間限制 1000 ms
記憶體限制 128 MB
題目描述
有一個箱子容量為v(正整數，o≤v≤20000)，同時有n個物品(o≤n≤30)，每個物品有一個體積 (正整數)，要求從 n 個物品中，任取若千個裝入箱內，使箱子的剩余空間為最小，
輸入資料
第一行，一個整數，表示箱子容量；
第二行，一個整數，表示有 n 個物品；
接下來 n 行，分別表示這 n 個物品的各自體積，
輸出資料
一個整數，表示箱子剩余空間，
樣例輸入
24
6
8
3
12
7
9
7
樣例輸出
0
解法1
# include <iostream>
# include <algorithm>
# include <cmath>
using namespace std;
int v;
int n;
int a[35];
int dp[20005];
int main() {
cin >> v >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i=1;i<=n;i++)
for(int j=v;j>=a[i];j--)
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
int minV = v - dp[v];
cout << minV;
return 0;
}
Problem C. 合唱隊形（動規）
時間限制 1000 ms
記憶體限制 128 MB
題目描述
? N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，使得剩下的K位同學排成合唱隊形，
合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1，2…，K，他們的身高分別為T1，T2，…，TK， 則他們的身高滿足T1< …< Ti> Ti+1> …> TK(1< =i< =K)，
你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形，
輸入資料
? 輸入的第一行是一個整數 N (2≤N≤100)， 表示同學的總數，第一行有 n 個整數，用空格分隔，第 i 個整數 Ti (130≤Ti≤230) 是第 i 位同學的身高(厘米)，
輸出資料
? 輸出包括一行，這一行只包含一個整數，就是最少需要幾位同學出列，
樣例輸入
8
186 186 150 200 160 130 197 220
樣例輸出
4
解法一
# include <iostream>
using namespace std;
int l[105],r[105],h[105],dp[105];
int main() {
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>h[i];
l[i]=r[i]=1;
}
for(int i=n-1;i>=1;i--){
for (int j=i+1;j<=n;j++)
{
if(h[i]>h[j]&&r[i]<=r[j]+1)
r[i]=r[j]+1;
}
}
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
if(h[i]>h[j]&&l[i]<=l[j]+1)
l[i]=l[j]+1;
}
}
int max=0;
for(int i=1;i<=n;i++){
dp[i]=l[i]+r[i]-1;
if(dp[i]>max)
max=dp[i];
}
cout<<n-max;
}
Problem D. 馬攔過河卒（動規）
時間限制 1000 ms
記憶體限制 128 MB
題目描述
棋盤上A點有一個過河卒，需要走到目標B點，卒行走的規則：可以向下、或者向右，同時在棋盤上C點有一個對方的馬，該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點，因此稱之為“馬攔過河卒”，
棋盤用坐標表示，A點(0, 0)、B點(n, m)(n, m為不超過15的整數)，同樣馬的位置坐標是需要給出的，現在要求你計算出卒從A點能夠到達B點的路徑的條數，假設馬的位置是固定不動的，并不是卒走一步馬走一步，
輸入資料
一行四個資料，分別表示 B 點坐標和馬的坐標，
輸出資料
一個資料，表示所有的路徑條數，
樣例輸入
6 6 3 3
樣例輸出
6
解法1
#include<iostream>
#define ll long long
using namespace std;
bool a[30][30];
ll dp[30][30];
//B(n,m) ma(x,y)
int main() {
int n, m, x, y;
cin >> n >> m >> x >> y;
dp[1][1] = 1;
n++; m++; x++; y++;
a[x][y] = 1;
a[x - 1][y + 2] = 1;
a[x - 1][y - 2] = 1;
a[x + 1][y + 2] = 1;
a[x + 1][y - 2] = 1;
a[x - 2][y - 1] = 1;
a[x - 2][y + 1] = 1;
a[x + 2][y - 1] = 1;
a[x + 2][y + 1] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++) {
if ((i != 1 || j != 1) && !a[i][j])
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
cout << dp[n][m];
}
Problem E. 傳球游戲（動規）
時間限制 1000 ms
記憶體限制 128 MB
題目描述
上體育課的時候，小蠻的老師經常帶著同學們一起做游戲，這次，老師帶著同學們一起做傳球游戲，
游戲規則是這樣的：n個同學站成一個圓圈，其中的一個同學手里拿著一個球，當老師吹哨子時開始傳球，每個同學可以把球傳給自己左右的兩個同學中的一個（左右任意），當老師再次吹哨子時，傳球停止，此時，拿著球沒傳出去的那個同學就是敗者，要給大家表演一個節目，
聰明的小蠻提出了一個有趣的問題：有多少種不同的傳球方法可以使得從小蠻手里開始傳的球，傳了m次以后，又回到小蠻手里，兩種傳球方法被視作不同的方法，當且僅當這兩種方法中，接到球的同學按接球順序組成的序列是不同的，比如有三個同學1號、2號、3號，并假設小蠻為1號，球傳了三次回到小蠻手里的方式有1-> 2-> 3-> 1和1-> 3-> 2-> 1，共2種，
輸入資料
輸入共一行，有兩個用空格隔開的整數 n,m (3≤n≤30,1≤m≤30)，
輸出資料
輸出共一行，有一個整數，標示符合題意的方法數，
樣例輸入
3 3
樣例輸出
2
樣例說明
40%的資料滿足：3< =n< =30 1< =m< =20
100%的資料滿足：3< =n< =30 1< =m< =30
解法1：
dp[i][j]： 傳了i次球，傳到編號為j的同學的方法數，
#include<iostream>
using namespace std;
int dp[40][40];
int main() {
int n, m, x, y;
cin >> n >> m;
dp[0][1] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
x = j - 1;
y = j + 1;
if (x == 0) x = n;
if (y == n + 1) y = 1;
dp[i][j] = dp[i - 1][x] + dp[i - 1][y];
}
}
cout << dp[m][1];
}
第五次演算法作業
Problem A. 單行最大子矩陣和問題（動規）
時間限制 1000 ms
記憶體限制 64 MB
題目描述
給定1×N的單行矩陣，矩陣每個元素都是-127到+127之間的整數，請找到一個連續子矩陣，使得其元素之和最大，例如行矩陣0 -2 -7 0 -2 11 -4 13 -5 -2，最大子矩陣和為11+(-4)+13=20.
輸入資料
多組測驗資料，每組資料的第一行為一個整數 N (N<=100)，第二行包含N個整數，為行矩陣的N個元素，每個元素介于-127到127之間，
輸出資料
最大子矩陣之和，每組對應一行，
樣例輸入
10
0 -2 -7 0 -2 11 -4 13 -5 -2
樣例輸出
20
解法1
#include <stdio.h>
int N;
int a[105];
int main(){
while(scanf("%d",&N)!=EOF){
for(int i=0;i<N;i++ ){
scanf("%d",&a[i]);
}
int sum=0;
int max=a[0];
for(int i=0;i<N;i++){
sum+=a[i];
if(sum<0)
sum=0;
if(sum>max)
max=sum;
}
printf("%d\n",max);
}
}
Problem B. 多行最大子矩陣和問題（動規）
時間限制 1000 ms
記憶體限制 64 MB
題目描述
給定N×N矩陣，矩陣元素都是-127到+127之間的整數，請找到一個子矩陣，使得其元素之和最大，例如給定4*4矩陣 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 最大子矩陣為 9 2 -4 1 -1 8 最大子矩陣和為9+2+（-4）+1+（-1）+8 = 15.
輸入資料
多組測驗資料，每組測驗資料的第一行整數 N (N<=100)，接下來N行元素，每行N個元素，每個元素介于-127到127之間，
輸出資料
最大子矩陣元素之和，每組測驗資料對應一行，
樣例輸入
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
樣例輸出
15
解法1
#include <stdio.h>
#include <string.h>
int n;
int a[105][105];
int temp[105];
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++ ){
for(int j=0;j<n;j++){
scanf("%d",&a[i][j]);
}
}
int max=-32767;
for(int i=0;i<n;i++){
memset(temp,0,sizeof(temp));
for(int j=i;j<n;j++){
int sum=0; int tempmax=-32767;
for(int k=0;k<n;k++){
temp[k]+=a[j][k];
sum+=temp[k];
if(sum<0) sum=0;
if(sum>tempmax) tempmax=sum;
}
if(tempmax>max) max=tempmax;
}
}
printf("%d\n",max);
}
}
Problem C. 小明的打工計劃 （動規）
時間限制 2000 ms
記憶體限制 64 MB
題目描述
作為一個有很多游戲想買但囊中羞澀的大學生，小明決定在這個暑假開始打工賺錢，經過一段時間的尋找，他一共找到了n個打工的招聘廣告，其中第i個打工的日期從li開始，到ri為止，一共付給他ci元錢，因為這些打工的時間都相互沖突，所以同一天小明最多參加一個打工，并且一個打工一旦開始，就必須一直作業到結束，不能中途退出，現在小明想要知道，這個暑假他打工最多能得到多少錢？
輸入資料
第一行一個整數n(1≤n≤10000001≤n≤1000000)，表示招聘廣告的數量， 接下來一共n行，每行3個整數li,ri,ci(1≤li≤ri≤1000000,1≤ci≤10000000001≤li≤ri≤1000000,1≤ci≤1000000000)，表示打工的開始時間，結束時間和報酬，
輸出資料
一行一個整數k，表示小明最多能夠得到的錢數，
樣例輸入
3
1 2 3
3 4 3
2 3 5
樣例輸出
6
解法1
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
struct job{
int l,r,w;
}a[1100000];
long long f[1100000];
int n,id;
bool cmp(job x,job y){
return (x.r<y.r )||(x.r==y.r && x.l<y.l);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].l>>a[i].r>>a[i].w;
}
sort(a+1,a+n+1,cmp);
id=1;
for(int i=1;i<=a[n].r;i++){
f[i]=f[i-1];
while(i==a[id].r&&id<=n){ // 可能有多個專案的結束時間一致
f[i]=max(f[i],f[a[id].l-1]+a[id].w);
id++;
}
}
cout<<f[a[n].r];
}
Problem D. 郵票面值設計（動規）
時間限制 1000 ms
記憶體限制 128 MB
題目描述
給定一個信封，最多只允許粘貼N張郵票，計算在給定M（N+M< =10）種郵票的情況下（假定所有的郵票數量都足夠）,如何設計郵票的面值，能得到最大max ，使得1～max之間的每一個郵資值都能得到，
例如，N=3，M＝2，如果面值分別為1分、4分，則在l分～6分之間的每一個郵資值都能得到（當然還有8分、9分和12分）：如果面值分別為1分、3分，則在1分～7分之間的每一個郵資值都能得到，可以驗證當N=3，M＝2時，7分就是可以得到連續的郵資最大值，所以MAX=7，面值分別為l分、3分，
樣例輸入：共一行，兩個整數，分表為N與M的值，
輸入資料
一行，分別為 N,M，
輸出資料
兩行，
第一行為 mm 種郵票的面值，按升序排列，各數之間用一個空格隔開，
第二行為最大值，
樣例輸入
3 2
樣例輸出
1 3
max=7
題解1
#include<bits/stdc++.h>
using namespace std;
#define MAXN 500
#define MAXNN 2000
#define INT register int
int n,k,ans=0;
int f[MAXNN],temp[MAXN],fin[MAXN];
inline int read()
{
int s=0,w=1;char c=getchar();
while (c<'0' || c>'9') c=getchar();
while (c>='0' && c<='9') {s=s*10+c-48; c=getchar();}
return s*w;
}
int DP(int N,int sum)
{
memset(f,127,sizeof(f));
f[0]=0;
INT i,j;
for (i=1;i<=N;++i)
for (j=temp[i];j<=sum*n;++j)
f[j]=min(f[j],f[j-temp[i]]+1);
i=1;
for (i=1;i<=sum*n;++i) if (f[i]>n) return i-1;
return n*sum;
}
void dfs(int take,int MAX,int sum)
{
if (take==k)
{
if (MAX>ans)
{
ans=MAX;
for (int i=1;i<=k;++i) fin[i]=temp[i];
}
return;
}
INT i;
for (i=temp[take]+1;i<=MAX+1;++i)
{
temp[take+1]=i;
int MAXnum=DP(take+1,sum+i);
dfs(take+1,MAXnum,sum+i);
}
return;
}
int main()
{
n=read();k=read();
temp[1]=1;
dfs(1,n,1);
for (int i=1;i<k;++i) printf("%d ",fin[i]);
printf("%d\nMAX=%d\n",fin[k],ans);
return 0;
}
Problem E. 導彈攔截（動規）
時間限制 1000 ms
記憶體限制 128 MB
題目描述
某國為了防御敵國的導彈襲擊，研發出一種導彈攔截系統，但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以后每一發炮彈都不能高于前一發的高度，某天，雷達捕捉到敵國的導彈來襲，由于該系統還在試驗階段，所以只有一套系統，因此有可能不能攔截所有的導彈，
輸入資料
輸入資料只有一行，該行包含若干個資料，之間用半角逗號隔開，表示導彈依次飛來的高度（導彈最多有 20枚，其高度為不大于 3×103 的正整數），
輸出資料
輸出資料只有一行，該行包含兩個資料，之間用半角逗號隔開，第一個資料表示這套系統最多能攔截的導彈數；第二個資料表示若要攔截所有導彈至少要再添加多少套這樣的系統，
樣例輸入
389,207,155,300,299,170,158,65
樣例輸出
6,1
解法1
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 9999
int down[N];//down[i]表示以i+1個字符結尾的最長遞減子序列
int up[N];//up[i]表示以i+1個字符結尾的最長非遞減子序列
int h[N];//表示高度
int n=0;
int main(){
while(cin>>h[n++]);
n--;
for(int i;i<n;i++)
down[i]=up[i]=1;//最壞情況下自身也是一個串
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(h[i]<h[j])
down[i]=max(down[i],down[j]+1);
else
up[i]=max(up[i],up[j]+1);
}
}
int maxd=0,maxu=0;
for(int i=0;i<n;i++){
maxd=max(maxd,down[i]);
maxu=max(maxu,up[i]);
}
cout<<maxd<<endl<<maxu<<endl;
return 0;
}
第六次演算法作業
Problem A. 合并果子(貪心)
時間限制 1000 ms
記憶體限制 128 MB
題目描述
在一個果園里，多多已經將所有的果子打了下來，而且按果子的不同種類分成了不同的堆，多多決定把所有的果子合成一堆，
每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和，可以看出，所有的果子經過n-1次合并之后，就只剩下一堆了，多多在合并果子時總共消耗的體力等于每次合并所耗體力之和，
因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節省體力，假定每個果子重量都為1，并且已知果子的種類數和每種果子的數目，你的任務是設計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值，
例如有3種果子，數目依次為1，2，9，可以先將1、2堆合并，新堆數目為3，耗費體力為3，接著，將新堆與原先的第三堆合并，又得到新的堆，數目為12，耗費體力為12，所以多多總共耗費體力=3+12=15，可以證明15為最小的體力耗費值，
輸入資料
輸入包括兩行，第一行是一個整數 n (1<＝n<103)，n (1<＝n<103)， 表示果子的種類數，第二行包含 n 個整數，用空格分隔，第 i個整數 ai (1<＝ai<2×103) 是第 i種果子的數目，
輸出資料
輸出包括一行，這一行只包含一個整數，也就是最小的體力耗費值，輸入資料保證這個值小于 231，
樣例輸入
3
1 2 9
樣例輸出
15
解法1
#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
int n;
int a[maxn];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n;
priority_queue<int, vector<int>, greater<int>> que; //小頂堆
for(int i = 0; i<n; i++){
cin>>a[i];
que.push(a[i]);
}
if(n==1){
cout<<0;
return 0;
}
int ans = 0;
while(!que.empty()){
int t1 = que.top(); que.pop();
int t2 = que.top(); que.pop();
ans+=t1+t2;
if(que.empty())break;
que.push(t1+t2);
}
cout<<ans;
return 0;
}
Problem B. 最小差距(貪心)
時間限制 1000 ms
記憶體限制 128 MB
題目描述
給定一些不同的一位數字，你可以從這些數字中選擇若干個，并將它們按一定順序排列，組成一個整數，把剩下的數字按一定順序排列，組成另一個整數，組成的整數不能以0開頭（除非這個整數只有1位），
例如，給定6個數字，0,1,2,4,6,7，你可以用它們組成一對數10和2467，當然，還可以組成其他的很多對數，比如210和764，204和176，這些對數中兩個數差的絕對值最小的是204和176，為28，
給定N個不同的0~9之間的數字，請你求出用這些數字組成的每對數中，差的絕對值最小的一對（或多對）數的絕對值是多少？
輸入資料
第一行包括一個數 T (T≤1000), 為測驗資料的組數，
每組資料包括兩行，第一行為一個數 N (2≤N≤10)， 表示數字的個數，下面一行為 N 個不同的一位數字，
輸出資料
T 行，每行一個數，表示第 i 個資料的答案，即最小的差的絕對值，
樣例輸入
2
6
0 1 2 4 6 7
4
1 6 3 4
樣例輸出
28
5
解法1
#include<bits/stdc++.h>
using namespace std;
int n;
int a[12];
int vis[12];
void solve(){
cin>>n;
for(int i = 1; i<=n; i++) cin>>a[i];
sort(a+1, a+n+1);
if(n==2){
cout<<a[2]-a[1]<<'\n';
return;
}
if(n&1){ //一共奇數個數字
if(a[1]==0) swap(a[1], a[2]);
int x = 0;
for(int i = 1; i<=n/2+1; i++) x = 10*x+a[i];
int y = 0;
for(int i = n; i>=n/2+2; i--) y = 10*y+a[i];
cout<<abs(x-y)<<'\n';
return;
}
int ret = 1e9;
for(int i = 2; i<=n; i++) { // 一共偶數個數字
if(a[i-1]==0) continue;
memset(vis, 0, sizeof(vis));
int x = a[i], y = a[i-1];
int l = 1, r = n;
vis[i] = vis[i-1] = 1;
for(int j = 1; j<=n/2-1; j++){
while(vis[l]) l++;
while(vis[r]) r--;
x = 10*x+a[l];
y = 10*y+a[r];
vis[l] = vis[r] = 1;
l++, r--;
}
ret = min(ret, abs(x-y));
}
cout<<ret<<'\n';
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int tt; cin>>tt;
while(tt--){
solve();
}
return 0;
}
Problem C. 上帝的愛好(貪心)
時間限制 1000 ms
記憶體限制 128 MB
題目描述
我們知道，詞都是按照詞牌來填的，上帝為了考驗小杉，只給了他四種詞牌，但只要壓韻就算符合詞牌，
小杉已經想好了N個意境優美的句子，每個句子都有一個韻腳，
符合要求的詞的句式應當有如下四種" XXYY" ，" XYXY" ，" XYYX" ，" XXXX" ，其中X或Y表示韻腳，
現在小杉想知道，從他想的N個句子之中，最多能按順序挑選出幾首符合條件的詞，
并且詞的句子間不能交錯，比如你選了1 4 6 8做為一首詩，那么7你就不能再選了，
輸入資料
每組測驗資料的
第一行有一個數 N (N≤4000)，
第二行有N個不超10^{3}的正整數，第i個整數表示第i個句子的韻腳，整數相同表示韻腳相同，
3030 的資料 N≤100N≤100
輸出資料
對每組測驗資料輸出一行，僅有一個數字，表示小杉最多能挑出幾首詞來，
樣例輸入
12
1 2 4 2 3 1 2 2 1 1 2 2
樣例輸出
2
樣例說明
樣例最多可以挑出兩首詞，一種方案如下：
1 2 4 6/9 10 11 12
解法1
#include <iostream>
using namespace std;
int a[10000];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
int s=0;
int cnt=0;
int j;
int ans=0;
for(int i=0;i<n;i++){
for(j=s;j<i;j++){
if(a[i]==a[j] &&a[i]&&a[j]){
cnt++;
a[i]=a[j]=0; //標記已用
break;
}
}
if(cnt==2){ //兩對相同的數
cnt =0;
s=i;
ans++;
}
}
cout<<ans;
return 0;
}
Problem D. 任務調度問題(貪心)
時間限制 1000 ms
記憶體限制 128 MB
題目描述
一個單位時間任務是恰好需要一個單位時間完成的任務，給定一個單位時間任務的有限集S，關于S 的一個時間表用于描述S 中單位時間任務的執行次序，時間表中第1 個任務從時間0 開始執行直至時間1 結束，第2 個任務從時間1 開始執行至時間2 結束，…，第n個任務從時間n-1 開始執行直至時間n結束，具有截止時間和誤時懲罰的單位時間任務時間表問題可描述如下：
(1) n 個單位時間任務的集合S={1,2,…,n}（n≤500）
(2) 任務i的截止時間d[i], 1≤i≤n, 1≤d[i]≤n，即要求任務i在時間d[i]之前結束；
(3) 任務i 的誤時懲罰1≤w[i]< 1000,1≤i≤n,即任務i 未在時間d[i]之前結束將招致w[i]的懲罰；若按時完成則無懲罰，
任務時間表問題要求確定S 的一個時間表（最優時間表）使得總誤時懲罰達到最小，
輸入資料
第一行是正整數 n， 表示任務數，接下來的 2 行中，每行有 n個正整數，分別表示各任務的截止時間和誤時懲罰，
輸出資料
將計算出的最小總誤時懲罰輸出
樣例輸入
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
樣例輸出
50
解法1
#include <iostream>
#include <algorithm>
using namespace std;
struct task{
int d,w;
}a[505];
bool cmp(task t1,task t2)
{
return t1.w>t2.w;
}
int main(){
int d[505];
int w[505];
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i].d;
int total=0;
for(int i=0;i<n;i++)
{
cin>>a[i].w;
total+=a[i].w;
}
sort(a,a+n,cmp);
int flag[505]={0};
int ans=0;
for(int i=0;i<n;i++){
for(int j=a[i].d-1;j>=0;j--){
if(flag[j]==0){
ans+=a[i].w;
flag[j]=1;
break;
}
}
}
cout<<total-ans;
return 0;
}
Problem E. sqy 的錫紙燙(貪心)
時間限制 1000 ms
記憶體限制 64 MB
題目描述
前不久 sqy 老師花了大價錢，去做了一個帥氣的錫紙燙，有著商業眼光的 sqy 一下子發現了大商機，于是他自己開了一家美容美發店，
sqy 找了剛剛做完紋理燙的大預言家 cbj 預測了未來，發現每個顧客都只在白天來美發店，并且第一次來店里的時候都會充一次價值 xi 的卡，然后從第二天開始，每天白天都會來這里打理頭發，而 sqy 僅收取成本價 1 元錢來吸引顧客，直到把卡掏空為止，這個顧客就再也不會回來，
黑心商人 sqy 找大預言家要來了每個顧客的充卡時間和充值金額，他準備在某一天晚上跑路，他想知道自己最多能卷走多少錢，
輸入資料
第一行包括一個整數 n(1≤n≤105)表示有 n 個顧客， 接下來共 n 行，每i+1行包括兩個整數 xi,yi 表示第 xi 天一個顧客來充值了 yi 元 (1≤xi≤106,0≤yi≤231?1)，
輸出資料
輸出一行包括一個整數 ans, 表示 sqy 最多能卷走多少錢，
樣例輸入
5
1 5
2 5
3 5
4 5
5 5
樣例輸出
15
樣例說明
在第五天的時候，第一個人消費4元還剩1元，第二個人消費3元還剩2元，第三個人消費2元還剩3元，第四個人消費1元還剩4元，第五個人還沒有開始消費就被卷錢跑路了，
#include <stdio.h>
#include <math.h>
#include <string.h>
#define MAX 1000010
using namespace std;
long long my_min(long long a,long long b){
if(a<b) return a;
else return b;
}
long long my_max(long long a,long long b){
if(a<b) return b;
else return a;
}
long long in[MAX];//收益
long long out[MAX]; //花費
long long ans =0;
int main(){
for (int i=0;i<1000010;i++)
in[i] = out[i] = 0;
long long n;
scanf("%lld",&n);
long long day,income;
for(int i=1;i<=n;i++){
scanf("%lld%lld",&day,&income);
in[day]+=income;
out[day+1]--;
long long leave=my_min(day+income+1,MAX);
out[leave] ++;
}
long long cur_out=0;//當天理發人數
long long cur_in=0;//當天收益
for(int i=1;i<=MAX-10;i++){
cur_out+=out[i];
cur_in=cur_in+in[i]+cur_out;
ans=my_max(ans,cur_in);
}
printf("%lld",ans);
return 0;
}
第七次演算法作業
Problem A. 海戰（dfs）
時間限制 1000 ms
記憶體限制 128 MB
題目描述
在這個著名的游戲中，在一個方形的盤上放置了固定數量和形狀的船只，每只船卻不能碰到其它的船，在這個題中，我們僅考慮船是方形的，所有的船只都是由圖形組成的方形，撰寫程式求出該棋盤上放置的船只的總數，
輸入資料
輸入檔案頭一行由用空格隔開的兩個整數 R 和 C 組成 ，1≤R,C≤1000，，1≤R,C≤1000， 這兩個數分別表示游戲棋盤的行數和列數，接下來的 R 行每行包含 C 個字符，每個字符可以為“#”，也可為“.”，“#”表示船只的一部分，“.”表示水，
輸出資料
為每一個段落輸出一行解，如果船的位置放得正確（即棋盤上只存在相互之間不能接觸的方形，如果兩個“#”號上下相鄰或左右相鄰卻分屬兩艘不同的船只，則稱這兩艘船相互接觸了），就輸出一段話“There are S ships.”,S表示船只的數量，否則輸出“Bad placement.”，
樣例輸入
6 8
.....#.#
##.....#
##.....#
.......#
#......#
#..#...#
樣例輸出
There are 5 ships.
方法1
- 從左到右，從上到下進行遍歷，如果是”#“（說明可能出現方形），則以該點作為基準點S(i,j)進行，進入下一步的判斷
- 以基準點向右，向下掃描單行和單列，找到連續出現”#“最大長度y和寬度x，
- 判斷以(i,j)為左上角的頂點，長寬分別為x,y的區域是否為方形，以及是否與其他的區域相鄰，即是否滿足如下的兩個條件
- 遍歷i+1~i+x-1行，每一行連續的寬度==x 以及該行j-1列的值！=’#‘
- 遍歷j~j+x-1列，每一列連續的長度==y以及該列j-1列的值！=’#‘
- 如果不滿足，則輸出Bad Placement, 否則ans++
#include<iostream>
using namespace std;
char a[1000][1000];
int r, c;
int ans = 0;
int check(int i, int j) {
int m,n;
int x=0, y=0;//行，數
for (m = i; m < r && a[m][j] == '#'; m++) {
if (j > 0 && a[m][j - 1] == '#')
break;
x++;
}
for (n = j; n < c && a[i][n] == '#'; n++) {
if (i > 0 && a[i - 1][n] == '#')
break;
y++;
}
for (m = i; m < i + x; m++) {
int tx = 0;
for (n = j; n < c && a[m][n]=='#'; n++) {
tx++;
}
if (tx != y)
return 0;
}
for (n = j; n < j + y; n++) {
int ty = 0;
for (m = i; m < r&&a[m][n]=='#'; m++) {
ty++;
}
if (ty != x)
return 0;
}
for (m = i; m < i + x; m++)
for (n = j; n < j + y; n++)
a[m][n] = '.';
ans++;
return 1;
}
int main() {
cin >> r >> c;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (a[i][j] == '#') {
int flag = check(i, j);
if (flag == 0) {
cout << "Bad placement." << endl;
return 0;
}
}
}
}
cout << "There are " << ans << " ships." << endl;
return 0;
}
方法2
方法1的check 函式復雜度高，每一行和每一列都要進行遍歷，方法2則通過尋找子結構來簡化判斷，可以發現在任意一個2*2的區域內如果出現了3個#, 則一定是有船相鄰，方法2對check 進行優化，
#include<iostream>
using namespace std;
char a[1000][1000];
int r, c;
int ans = 0;
int check(int i, int j) {
int cnt=0;
if(g[x][y]=='#') cnt++;
if(g[x+1][y]=='#') cnt++;
if(g[x][y+1]=='#') cnt++;
if(g[x+1][y+1]=='#') cnt++;
return cnt==3;
}
int main() {
cin >> r >> c;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (a[i][j] == '#') {
int flag = check(i, j);
if (flag == 0) {
cout << "Bad placement." << endl;
return 0;
}
}
}
}
cout << "There are " << ans << " ships." << endl;
return 0;
}
方法3
方法3則是通過dfs演算法，即每一次深搜的時候把與#連通的所有點改成*因為它們是同一艘船
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int r,c;
char map[1010][1010];
int fx[4]={0,-1,1,0};
int fy[4]={-1,0,0,1};
int dfs(int x,int y){
map[x][y]='*';
for(int i=0;i<4;i++){
if(x+fx[i]>0 && x+fx[i]<=r && y+fy[i]>0 && y+fy[i]<=c && map[x+fx[i]][y+fy[i]]=='#') dfs(x+fx[i],y+fy[i]);
}
} //把與#連通的所有點改成*因為它們是同一艘船
int check(int x, int y) {
int cnt=0;
if(g[x][y]=='#') cnt++;
if(g[x+1][y]=='#') cnt++;
if(g[x][y+1]=='#') cnt++;
if(g[x+1][y+1]=='#') cnt++;
return cnt==3;
}
int main(){
scanf("%d%d",&r,&c);
int i,j;
for(i=1;i<=r;i++){
for(j=1;j<=c;j++){
cin>>map[i][j];
}
}
int s=0;
for(i=1;i<=r;i++){
for(j=1;j<=c;j++){
if(i<r&&j<c&&check(i,j)==0){
printf("Bad placement.");
return 0; //不合法后面就沒必要繼續了
}
}
}
for(i=1;i<=r;i++){
for(j=1;j<=c;j++){
if(map[i][j]=='#'){
s++;
dfs(i,j);
}//因為前面已經確保了是合法的，現在只需統計船的數量
}
}
printf("There are %d ships.",s);
return 0;
}
Problem B. 礦床個數（dfs）
時間限制 1000 ms
記憶體限制 64 MB
題目描述
在一個被分成n*n個格子的平原上，有一些格子有鐵礦，兩格鐵礦如果相鄰那么就認為他們屬于同一個礦床，每個礦床都包含一個或更多個鐵礦，問一共有幾個礦床，
兩個格子只要有公共邊或公共點就算相鄰，
輸入資料
第一行為一個正整數n，n<=1000 接下來有n行，每行有n個字符，表示平原的對應位置有沒有鐵礦，*代表沒有，#代表有
輸出資料
礦床個數
樣例輸入
6
*#*###
###*#*
*##***
*#****
***###
******
樣例輸出
2
樣例說明
最下面三塊鐵礦屬于一個礦床，其他鐵礦屬于一個礦床，所以一共有兩個礦床
方法1
典型的dfs, 每次搜索周圍的8個點
#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
int n;
string a[maxn];
int di[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dj[] = {1, -1, 0, 0, 1, -1, 1, -1};
bool inB(int i, int j){
return 1<=i&&i<=n&&1<=j&&j<=n;
}
void dfs(int i, int j){
a[i][j] = '*';
for(int k = 0; k<8; k++){
int ii = i+di[k], jj = j+dj[k];
if(!inB(ii, jj)||a[ii][jj]=='*') continue;
dfs(ii, jj);
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
for(int i = 1; i<=n; i++){
cin>>a[i];
a[i] = " "+a[i];
}
int cnt = 0;
for(int i = 1; i<=n; i++){
for(int j = 1; j<=n; j++){
if(a[i][j]=='*') continue;
cnt++;
dfs(i, j);
}
}
cout<<cnt;
return 0;
}
Problem C. 8皇后（dfs）
時間限制 1000 ms
記憶體限制 64 MB
題目描述
眾所周知，八皇后問題是一個非常經典的演算法問題，現在將題目改為在n*m的棋盤上，放min(n,m)個互不攻擊的皇后，問有多少種放法，
輸入資料
兩個正整數n,m，n和m均不超過12
輸出資料
方案數
樣例輸入
2 3
樣例輸出
2
方法1
思路：一行一行得進行擺放，用for回圈來確定每一行中擺放的列數，用check判斷第j行的擺放位置與1~j-1行不沖突，
#include <iostream>
using namespace std;
int n, m;
int a[15];
int res = 0;
int check(int i, int j) {
int j1 = j, i1 = i, ok1 = 1;
while ((j1 > 1) && ok1) {
j1--;
if (a[j1] == i)
ok1 = 0;
}
j1 = j; i1 = i;
while ((j1 > 1) && (i1 > 1) && ok1) {
j1--; i1--;
if (a[j1] == i1)
ok1 = 0;
}
j1 = j; i1 = i;
while ((j1>1) && (i1 < n) && ok1) {
j1--; i1++;
if (a[j1] == i1)
ok1 = 0;
}
return ok1;
}
void queue(int j) {
if (j > m)
{
res++;
}
else {
for (int i = 1; i <= n; i++) {
if (check(i, j)) {
a[j] = i;
queue(j + 1);
}
}
}
}
int main() {
cin >> n >> m;
int temp;
if (n < m) {
temp = n;
n = m;
m = temp;
}
queue(1);
cout << res;
}
方法2
思路：dfs
一行一行得進行擺放，用for回圈來確定每一列,由于是一行一行得擺放所以不可能同行，我們只需要標記同列，同對角線，就行，會發現主對角線一條對角線上的行列和等于同一個常數，副對角線一條對角線行列差等于一個常數，只不過會是負數，防止下標是負數我們可以進行+n，
#include<bits/stdc++.h>
using namespace std;
#define maxn 50
int n, m;
int a[maxn][maxn];
const int bias = 25;
int visc[maxn], vis1[maxn], vis2[maxn];//表示這一列，主對角線，負對角線有沒有皇后
int cnt;
void dfs(int i){
if(i>n){
cnt++;
return;
}
for(int j = 1; j<=m; j++){
if(visc[j]||vis1[i+j]||vis2[i-j+bias]) continue;
visc[j] = vis1[i+j] = vis2[i-j+bias] = 1;
dfs(i+1);
visc[j] = vis1[i+j] = vis2[i-j+bias] = 0;
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
if(n>m) swap(n, m);
dfs(1);
cout<<cnt;
return 0;
}
Problem D. 無向圖的連通性（dfs）
時間限制 1000 ms
記憶體限制 64 MB
題目描述
給一個n個點，m條邊的無向圖，和一個起點s，一個終點t，問能不能從s經過一些邊走到t，能走到則輸出Yes，否則輸出No
點的編號從1到n
輸入資料
第一行為兩個正整數n，m，n<=1e5，m<=1e5 接下來m行每行兩個正整數t1，t2，代表t1到t2有一條無向邊 最后一行為兩個正整數s和t
輸出資料
Yes或No
樣例輸入
3 2
1 2
2 3
1 3
樣例輸出
Yes
方法1
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
int n, m;
vector<int> G[maxn];
int vis[maxn];
void dfs(int u){
if(vis[u]) return;
vis[u] = 1;
for(auto v:G[u]){
dfs(v);
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
for(int i = 1; i<=m ;i++){
int u, v; cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
int s, t; cin>>s>>t;
dfs(s);
cout<<(vis[t]?"Yes\n":"No\n");
return 0;
}
Problem E. 24點游戲(dfs)
時間限制 1000 ms
記憶體限制 128 MB
題目描述
幾十年前全世界就流行一種數字撲克游戲，至今仍有人樂此不疲．在中國我們把這種游戲稱為“算24點”，您作為游戲者將得到4個1-13（在撲克牌里用A代替1，J代替11，Q代替12，K代替13）之間的自然數作為運算元，而您的任務是對這4個運算元進行適當的算術運算（可以使用+、-、*、/、括號），判斷運算結果是否等于24，能輸出1，不能輸出0，
輸入資料
四個牌面值，牌面值與牌面值之間用一個空格隔開，
輸出資料
輸出 0 或 1 ，
樣例輸入
3 8 10 Q
樣例輸出
1
樣例說明
Q×(10/(8-3))=24
方法1
#include <iostream>
#include <vector>
using namespace std;
double nums[4];
int vist[4] = {0};
bool dfs(double res) {
double num;
bool last = true;
for (int i = 0; i < 4; ++i) {
if (!vist[i]) {
vist[i] = true;
num = nums[i];
if (res) {
if (dfs(res + num) || dfs(res - num) || dfs(num - res) ||
dfs(res * num) || dfs(res / num) || dfs(num / res)) {
return true;
}
}
else {
if (dfs(num)) {
return true;
}
}
vist[i] = false;
last = false;
}
}
return last && res == 24;
}
int main() {
string tmp;
for (int i = 0; i < 4; ++i) {
cin >> tmp;
if (tmp == "A") {
nums[i] = 1;
} else if (tmp == "J") {
nums[i] = 11;
} else if (tmp == "Q") {
nums[i] = 12;
} else if (tmp == "K") {
nums[i] = 13;
} else {
nums[i] = atoi(tmp.c_str());
}
}
if (dfs(0)) {
cout << 1 << endl;
} else {
cout << 0 << endl;
}
return 0;
}
期中測驗
Problem B. 等價運算式
時間限制 1000 ms
記憶體限制 128 MB
題目描述
明明進了中學之后，學到了代數運算式，有一天，他碰到一個很麻煩的選擇題，這個題目的題干中首先給出了一個代數運算式，然后列出了若干選項，每個選項也是一個代數運算式，題目的要求是判斷選項中哪些代數運算式是和題干中的運算式等價的，
這個題目手算很麻煩，因為明明對計算機編程很感興趣，所以他想是不是可以用計算機來解決這個問題，假設你是明明，能完成這個任務嗎？
這個選擇題中的每個運算式都滿足下面的性質：
1． 運算式只可能包含一個變數‘a’，
2． 運算式中出現的數都是正整數，而且都小于10000，
3． 運算式中可以包括四種運算‘+’（加），‘-’（減），‘’（乘），‘’（乘冪），以及小括號‘(’，‘)’，小括號的優先級最高，其次是‘’，然后是‘’，最后是‘+’和‘-’，‘+’和‘-’的優先級是相同的，相同優先級的運算從左到右進行，（注意：運算子‘+’，‘-’，‘*’，‘^’以及小括號‘(’，‘)’都是英文字符）
4． 冪指數只可能是1到10之間的正整數（包括1和10），
5． 運算式內部，頭部或者尾部都可能有一些多余的空格，
下面是一些合理的運算式的例子：
((a^1) ^ 2)^3，aa+a-a，((a+a))，9999+(a-a)a，1 + (a -1)3，110^9……
對于30%的資料，運算式中只可能出現兩種運算子‘+’和‘-’；
對于其它的資料，四種運算子‘+’，‘-’，‘*’，‘^’在運算式中都可能出現，
對于全部的資料，運算式中都可能出現小括號‘(’和‘)’，
輸入資料
輸入的第一行給出的是題干中的運算式，第二行是一個整數 n (2≤n≤26)， 表示選項的個數，后面 n 行，每行包括一個選項中的運算式，這 n 個選項的標號分別是 A,B,C,D……
輸入中的運算式的長度都不超過 50 個字符，而且保證選項中總有運算式和題干中的運算式是等價的，
輸出資料
輸出包括一行，這一行包括一系列選項的標號，表示哪些選項是和題干中的運算式等價的，選項的標號按照字母順序排列，而且之間沒有空格，
樣例輸入
( a + 1) ^2
3
(a-1)^2+4*a
a + 1+ a
a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a
樣例輸出
AC
#include <stack>
#include <iostream>
using namespace std;
int l[200];
const int mod = 1e9 + 7, x = 173;
stack<int>num;
stack<char>opera;
string s;
string read() {
string s;
char ch;
do {
ch = getchar();
} while (ch == '\n' || ch == '\r' || ch == ' ');
while (ch != '\n' && ch != '\r') {
if (ch != ' ') s += ch;
ch = getchar();
if (ch == EOF) break;
}
return s;
}
int get(int n1, int n2) {
unsigned long long ans = 1, pow = n1;
while (n2) {
if (n2 & 1) ans = ans * pow % mod;
pow = pow * pow % mod;
n2 >>= 1;
}
int res = ans % mod;
return res;
}
void jisuan() {
int op1, op2;
op1 = num.top();//取數字堆疊中的兩個數，注意順序是n2 (運算子) n1
num.pop();
op2 = num.top();//取數字堆疊中的兩個數
num.pop();
int aa;
switch (opera.top()) {
case '^':aa = get(op2, op1); break;
case '+':aa = (op1 + op2) % mod; break;
case '-':aa = (op2 - op1 + mod) % mod; break;
case '*':aa = ((long long)(op2 % mod) * (op1 % mod)) % mod; break;
}
num.push(aa);
opera.pop();
}
void pushStack() {
int len = (int)s.length(), sum = 0;
for (int i = 0; i < len; i++) {
if (s[i] == 'a') num.push(x);
else if (isdigit(s[i])) {
sum = sum * 10 + (s[i] - '0');
if (i == len - 1 || !isdigit(s[i + 1])) num.push(sum), sum = 0;
}
else {
if (s[i] == '(') {
opera.push('(');
continue;
}
else if (s[i] == ')') {
while (!opera.empty() && opera.top() != '(') jisuan();
if (!opera.empty() && opera.top() == '(') opera.pop();
continue;
}
while (!opera.empty() && l[s[i]] <= l[opera.top()]) jisuan();
opera.push(s[i]);
}
}
}
int main() {
l['^'] = 4; l['*'] = 3; l['+'] = 2; l['-'] = 2;//初始化運算子優先級
s = read();
int n, ans;
pushStack();//形成后綴運算式
while (!opera.empty()) {
if (opera.top() == '(') {//如果括號不匹配（多出括號的情況）
opera.pop(); continue;
}
jisuan();
}
ans = num.top();//記錄原運算式的值
cin >> n;
for (int i = 0; i < n; i++) {
while (!num.empty()) num.pop();//記得清空堆疊
while (!opera.empty()) opera.pop();
s = read();
pushStack();//形成后綴運算式
while (!opera.empty()) {
if (opera.top() == '(') {//如果括號不匹配（多出括號的情況）
opera.pop(); continue;
}
jisuan();
}
char result;
if (num.top() == ans) {
result = 'A' + i;
cout << result;
}
}
return 0;
}
Problem C. 求解多元一次方程組
時間限制 1000 ms
記憶體限制 128 MB
題目描述
賈老二是個品學兼優的好學生，但由于智商問題，算術學得不是很好，尤其是在解方程這個方面，雖然他解決 2x=2 這樣的方程游刃有余，但是對于 {x+y=3 x-y=1} 這樣的方程組就束手無策了，于是他要你來幫忙，前提是一次方程組且保證在integer的范圍內可以處理所有問題，
輸入資料
第一行一個數字 N (1≤N≤100) 表示要求的未知數的個數，同時也是所給的方程個數，
第 2 到 N+1 行，每行 N+1 個數，前 N 個表示第 1 到 N 個未知數的系數，第 N+1 個數表示 N 個未知數乘以各自系數后的加和，（保證有唯一整數解）
輸出資料
一行 N 個數，表示第 1 到 N 個未知數的值，
樣例輸入
2
1 1 3
1 –1 1
樣例輸出
2 1
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-6;
double a[100][100],b[100];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
scanf("%lf",&a[i][j]);
scanf("%lf",&b[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
if(fabs(a[j][i])>eps)
{
for(int k=1;k<=n;k++)
swap(a[j][k],a[i][k]);
swap(b[i],b[j]);
}
for(int j=1;j<=n;j++)
{
if(i==j)
continue;
double rate=a[j][i]/a[i][i];
for(int k=1;k<=n;k++)
a[j][k]-=a[i][k]*rate;
b[j]-=b[i]*rate;
}
}
for(int i=1;i<n;i++)
{
double ans=b[i]/a[i][i];
if(fabs(ans)<eps)
printf("%.0lf ",fabs(ans));
else
printf("%.0lf ",ans);
}
double ans=b[n]/a[n][n];
if(fabs(ans)<eps)
printf("%.0lf",fabs(ans));
else
printf("%.0lf",ans);
return 0;
}
Problem E. 最佳課題選擇(動規)
時間限制 1000 ms
記憶體限制 128 MB
題目描述
Matrix67要在下個月交給老師n篇論文，論文的內容可以從m個課題中選擇，由于課題數有限，Matrix67不得不重復選擇一些課題，完成不同課題的論文所花的時間不同，具體地說，對于某個課題i，若Matrix67計劃一共寫x篇論文，則完成該課題的論文總共需要花費Ai*x^Bi個單位時間（系數Ai和指數Bi均為正整數），給定與每一個課題相對應的Ai和Bi的值，請幫助Matrix67計算出如何選擇論文的課題使得他可以花費最少的時間完成這n篇論文，
輸入資料
第一行有兩個用空格隔開的正整數 n 和 m， 分別代表需要完成的論文數和可供選擇的課題數，
以下 m 行每行有兩個用空格隔開的正整數，其中，第 i 行的兩個數分別代表與第 i 個課題相對應的時間系數 Ai 和指數 Bi ，
對于 30 的資料 ，n≤10,m≤5;
對于100%的資料 ，n≤200,m≤20,Ai≤100,Bi≤5 ，
輸出資料
輸出完成 n 篇論文所需要耗費的最少時間，
樣例輸入
10 3
2 1
1 2
2 1
樣例輸出
19
#include<bits/stdc++.h>
using namespace std;
long long dp[210];
long long a[30],b[30];
long long findmin(long long x,long long y){
if(x<y)
return x;
else
return y;
}
long long get(long long a,long long b)//這個是快速冪 其實可以不要 因為b[ i ]很小
{
if(b==1) return a;
long long now=a,t=b,res=1;
while(t)
{
if(t&1) res*=now;
now*=now;
t>>=1;
}
return res;
}
int main()
{
long long m,n;
std::ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a[i]>>b[i];
}
memset(dp,0x7f,sizeof dp);
dp[0]=0;
for(int i=1;i<=m;i++)// 課題數
for(int j=n;j>0;j--) // 論文數
for(int t=j;t>0;t--) // 該課題對應的論文數
dp[j]=findmin(dp[j],dp[j-t]+a[i]*get(t,b[i]));
cout<<dp[n];
return 0;
}
Problem F. 逆序對的個數()
時間限制 1000 ms
記憶體限制 256 MB
題目描述
Ricky班里有n(2<=n<=100000)個人，每個人有一個學號ai(1<=ai<=n)，保證學號ai互不相同，Ricky手里有一張班級合影，他發現雖然大家是按身高從低到高排好隊的，但如果按學號看的話卻不一定是從小到大，他想看一看如果按照學號來看，這個隊排的有多亂，Ricky把混亂度定義為佇列中逆序對的個數，即：如果從前往后看，大家正好是按照學號從小到大排列的，那逆序對為0個，混亂度為0；而每能找到兩個人形成了學號大同學的在前，學號小的在后（即i < j且ai > aj），就稱其為一個逆序對，混亂度計數也要加1，由于Ricky班里人可能很多，Ricky實在數不過來了，現在告訴你合影上同學們的學號（按從前往后），請你幫忙撰寫程式計算一下混亂度，滿足一下Ricky的好奇心，
輸入資料
第一行有一個整數n(2<=n<=100000)，表示Ricky班上的人數； 第二行有n個整數a1,a2,…,an(1<=ai<=n)，表示合影上同學們的學號，
輸出資料
輸出一個整數，表示合影上排列的混亂度（逆序對個數）
樣例輸入
5
1 3 4 2 5
樣例輸出
2
樣例說明
其中(3,2) (4,2)形成兩個逆序對，所以混亂度為2
#include<cstdio>
#include<iostream>
using namespace std;
int n, a[100010], c[100010];
long long ans;
void mergesort(int b, int e)
{
if (b == e)
return;
int mid = (b + e) / 2, i = b, j = mid + 1, k = b;
mergesort(b, mid), mergesort(mid + 1, e);
while (i <= mid && j <= e)
if (a[i] <= a[j])
c[k++] = a[i++];
else
c[k++] = a[j++], ans += mid - i + 1;
while (i <= mid)
c[k++] = a[i++];
while (j <= e)
c[k++] = a[j++];
for (int l = b; l <= e; l++)
a[l] = c[l];
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
mergesort(0, n - 1);
printf("%lld", ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/394077.html
標籤：其他
上一篇：c# 搜索目錄中某些檔案
下一篇：c語言模塊化思想和操作