第一題：門(mén)禁系統(tǒng)
濤濤最近要負(fù)責(zé)圖書(shū)館的管理工作，需要記錄下每天讀者的到訪情況。
每位讀者有一個(gè)編號(hào)，每條記錄用讀者的編號(hào)來(lái)表示。
給出讀者的來(lái)訪記錄，請(qǐng)問(wèn)每一條記錄中的讀者是第幾次出現(xiàn)。
輸入格式
輸入的第一行包含一個(gè)整數(shù)?n，表示濤濤的記錄條數(shù)。
第二行包含?n?個(gè)整數(shù)，依次表示濤濤的記錄中每位讀者的編號(hào)。
輸出格式
輸出一行，包含?n?個(gè)整數(shù)，由空格分隔，依次表示每條記錄中的讀者編號(hào)是第幾次出現(xiàn)。
數(shù)據(jù)范圍
1≤n≤1000，
讀者的編號(hào)為不超過(guò)?n?的正整數(shù)。輸入樣例：
5 1 2 1 1 3輸出樣例：
1 1 2 3 1
?解題思路：直接使用哈希表，檢查每一個(gè)元素是否需要我們的輸出
以下是代碼：
c++
#include<iostream>
using namespace std;
const int N = 1010;
int a[N];
int n;
int main()
{
cin >> n;
for(int i = 0;i < n;i ++)
{
int x;
cin >> x;
a[x] ++;
cout << a[x] << " ";
}
return 0;
}Python
n = int(input())
l = list(map(int , input().split()))
d = {}
for i in l:
d[i] = 1 if i not in d else d[i] + 1
print(d[i] , end = ' ')第二題：門(mén)禁系統(tǒng)
在圖像編碼的算法中，需要將一個(gè)給定的方形矩陣進(jìn)行?Z?字形掃描(Zigzag Scan)。
給定一個(gè)?n×n?的矩陣，Z?字形掃描的過(guò)程如下圖所示：
對(duì)于下面的?4×4 的矩陣，
1 5 3 9 3 7 5 6 9 4 6 4 7 3 1 3對(duì)其進(jìn)行?Z?字形掃描后得到長(zhǎng)度為?16?的序列：
1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3。請(qǐng)實(shí)現(xiàn)一個(gè)?Z?字形掃描的程序，給定一個(gè)?n×n?的矩陣，輸出對(duì)這個(gè)矩陣進(jìn)行?Z?字形掃描的結(jié)果。
輸入格式
輸入的第一行包含一個(gè)整數(shù)?n，表示矩陣的大小。
輸入的第二行到第?n+1?行每行包含?n?個(gè)正整數(shù)，由空格分隔，表示給定的矩陣。
輸出格式
輸出一行，包含?n×n?個(gè)整數(shù)，由空格分隔，表示輸入的矩陣經(jīng)過(guò)?Z?字形掃描后的結(jié)果。
數(shù)據(jù)范圍
1≤n≤500，
矩陣元素為不超過(guò)?1000?的正整數(shù)。輸入樣例：
4 1 5 3 9 3 7 5 6 9 4 6 4 7 3 1 3輸出樣例：
1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3
??解題思路：模擬，觀察圖片可以發(fā)現(xiàn)一共有四個(gè)方向
這四個(gè)方向可以使用偏移量數(shù)組進(jìn)行模擬
當(dāng)然，這里來(lái)一種不一樣的方法，我們發(fā)現(xiàn)可以只是用一個(gè)flag標(biāo)記即可解決問(wèn)題。
使用一個(gè)flag標(biāo)記控制前兩種方向移動(dòng)，因?yàn)橛?1 +1，所以是有可能躍出邊界的，因此我們?cè)谶@個(gè)坐標(biāo)躍出邊界時(shí)，判斷，然后將溢出的坐標(biāo)置0，并且將flag置反（通過(guò)測(cè)試可以發(fā)現(xiàn)每一次需要轉(zhuǎn)彎的時(shí)候往往就是某一個(gè)坐標(biāo)溢出的時(shí)候）
以下是代碼：
c++
#include<iostream>
using namespace std;
const int N = 510;
int n;
int a[N][N];
int main()
{
cin >> n;
for(int i = 0;i < n;i ++)
for(int j = 0;j < n;j ++)
cin >> a[i][j];
int x = 0 , y = 0;
// 方向一：ture就x--，y++。方向二：false就x++，y--。
bool f = true;
while(x != n || y != n)
{
if(x < n && y < n) cout << a[x][y] << " ";
if(f) x -- , y ++;
else x ++ , y --;
if(x < 0) x = 0 , f = !f;
if(y < 0) y = 0 , f = !f;
}
return 0;
}第三題：集合競(jìng)價(jià)
某股票交易所請(qǐng)你編寫(xiě)一個(gè)程序，根據(jù)開(kāi)盤(pán)前客戶(hù)提交的訂單來(lái)確定某特定股票的開(kāi)盤(pán)價(jià)和開(kāi)盤(pán)成交量。
該程序的輸入由很多行構(gòu)成，每一行為一條記錄，記錄可能有以下幾種：
buy p s?表示一個(gè)購(gòu)買(mǎi)股票的買(mǎi)單，每手出價(jià)為?p，購(gòu)買(mǎi)股數(shù)為?s。sell p s?表示一個(gè)出售股票的賣(mài)單，每手出價(jià)為?p，出售股數(shù)為?s。cancel i?表示撤銷(xiāo)第?i?行的記錄。被撤銷(xiāo)的記錄一定是前兩種。如果開(kāi)盤(pán)價(jià)為?p0，則系統(tǒng)可以將所有出價(jià)至少為?p0?的買(mǎi)單和所有出價(jià)至多為?p0?的賣(mài)單進(jìn)行匹配。
因此，此時(shí)的開(kāi)盤(pán)成交量為出價(jià)至少為?p0?的買(mǎi)單的總股數(shù)和所有出價(jià)至多為?p0?的賣(mài)單的總股數(shù)之間的較小值。
你的程序需要確定一個(gè)開(kāi)盤(pán)價(jià)，使得開(kāi)盤(pán)成交量盡可能地大。
如果有多個(gè)符合條件的開(kāi)盤(pán)價(jià)，你的程序應(yīng)當(dāng)輸出最高的那一個(gè)。
輸入格式
輸入數(shù)據(jù)有任意多行，每一行是一條記錄。
保證輸入合法。股數(shù)為不超過(guò)?1e8?的正整數(shù)，出價(jià)為精確到恰好小數(shù)點(diǎn)后兩位的正實(shí)數(shù)，且不超過(guò)?10000.00。
輸出格式
你需要輸出一行，包含兩個(gè)數(shù)，以一個(gè)空格分隔。
第一個(gè)數(shù)是開(kāi)盤(pán)價(jià)，第二個(gè)是此開(kāi)盤(pán)價(jià)下的成交量。
開(kāi)盤(pán)價(jià)需要精確到小數(shù)點(diǎn)后恰好兩位。
數(shù)據(jù)范圍
對(duì)于?100%?的數(shù)據(jù)，輸入的行數(shù)不超過(guò)?5000。
0<p≤1e4
1≤s≤1e8
數(shù)據(jù)保證一定存在某個(gè)開(kāi)盤(pán)價(jià)使得成交量不為?0。
保證輸入合法。數(shù)據(jù)保證?cancel?指令只會(huì)取消?buy?和?sell?記錄。輸入樣例：
buy 9.25 100 buy 8.88 175 sell 9.00 1000 buy 9.00 400 sell 8.92 400 cancel 1 buy 100.00 50輸出樣例：
9.00 450
?解題思路：首先使用結(jié)構(gòu)體記錄每一條信息，注意cancel信息使用 ***** 進(jìn)行標(biāo)記，剩下兩個(gè)參數(shù)記為-1即可。
由于數(shù)據(jù)量很小因此可以在的復(fù)雜度完成。
直接根據(jù)題目進(jìn)行模擬即可。
以下是代碼：
c++
#include<iostream>
using namespace std;
const int N = 5010;
typedef long long ll;
struct record
{
// cancel 狀態(tài)為"*****"
string st;
double p;
ll money;
}r[N];
int idx = 1;
int main()
{
string s1;
double p;
ll mon;
while(cin >> s1 >> p)
{
if(s1 == "cancel") r[(int)p].st = "*****" , r[idx ++] = {s1 , -1 , -1};
else
{
cin >> mon;
r[idx ++] = {s1 , p , mon};
}
}
p = -1;// 開(kāi)盤(pán)價(jià)
ll res = -1;// 交易量
for(int i = 1;i < idx;i ++)
{
if(r[i].st == "*****") continue;
ll buy = 0 , sell = 0;
double p0 = r[i].p;
for(int j = 1;j < idx;j ++)
{
// 出價(jià)至少為 p0 的買(mǎi)單
if(r[j].st == "buy" && r[j].p >= p0) buy += r[j].money;
// 出價(jià)至多為 p0 的賣(mài)單
if(r[j].st == "sell" && r[j].p <= p0) sell += r[j].money;
}
// cout << p0 << " " << buy << " " << sell << endl;
ll x = min(buy , sell);
if(res < x) res = x , p = p0;
else if(res == x)
{
if(p < p0) p = p0;
}
}
printf("%.2lf %lld" , p , res);
return 0;
}第四題：最優(yōu)灌溉
雷雷承包了很多片麥田，為了灌溉這些麥田，雷雷在第一個(gè)麥田挖了一口很深的水井，所有的麥田都從這口井來(lái)引水灌溉。
為了灌溉，雷雷需要建立一些水渠，以連接水井和麥田，雷雷也可以利用部分麥田作為“中轉(zhuǎn)站”，利用水渠連接不同的麥田，這樣只要一片麥田能被灌溉，則與其連接的麥田也能被灌溉。
現(xiàn)在雷雷知道哪些麥田之間可以建設(shè)水渠和建設(shè)每個(gè)水渠所需要的費(fèi)用（注意不是所有麥田之間都可以建立水渠）。請(qǐng)問(wèn)灌溉所有麥田最少需要多少費(fèi)用來(lái)修建水渠。
輸入格式
輸入的第一行包含兩個(gè)正整數(shù)?n,m，分別表示麥田的片數(shù)和雷雷可以建立的水渠的數(shù)量。麥田使用?1,2,3,…… 依次標(biāo)號(hào)。
接下來(lái)?m?行，每行包含三個(gè)整數(shù)?ai,bi,ci，表示第?ai 片麥田與第?bi?片麥田之間可以建立一條水渠，所需要的費(fèi)用為?ci。
輸出格式
輸出一行，包含一個(gè)整數(shù)，表示灌溉所有麥田所需要的最小費(fèi)用。
數(shù)據(jù)范圍
前?20%?的評(píng)測(cè)用例滿(mǎn)足：n≤5。
前?40%?的評(píng)測(cè)用例滿(mǎn)足：n≤20。
前?60%?的評(píng)測(cè)用例滿(mǎn)足：n≤100。
所有評(píng)測(cè)用例都滿(mǎn)足：1≤n≤1000，1≤m≤100,000，0≤ci≤10,000
保證一定可以灌溉到所有麥田，并且無(wú)重邊和自環(huán)（補(bǔ)充這個(gè)條件是為了和官方數(shù)據(jù)保持一致）。
注意，關(guān)于?ci?的取值范圍，官網(wǎng)標(biāo)注的是?ci≥1，但是經(jīng)過(guò)實(shí)際測(cè)試，官方數(shù)據(jù)中包含?ci=0?的數(shù)據(jù)，因此在這里予以修正，并添加相應(yīng)數(shù)據(jù)。輸入樣例：
4 4 1 2 1 2 3 4 2 4 2 3 4 3輸出樣例：
6樣例解釋
建立以下三條水渠：麥田?1?與麥田?2、麥田?2?與麥田?4、麥田?4?與麥田?3。
?解題思路：經(jīng)典的最小生成樹(shù)算法，可以使用Kruskal算法或是prim算法，這里直接是Kruskal算法，注意數(shù)據(jù)可能很大，開(kāi)longlong就行
以下是代碼：
c++
// Kruskal算法
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010 , M = 1e5 + 10;
int p[N];
int n , m;
struct nodes
{
int a , b;
long long c;
}node[M];
int idx = 0;
void init()
{
for(int i = 1;i <= n;i ++)
p[i] = i;
}
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
bool cmp(nodes x , nodes y)
{
return x.c < y.c;
}
int main()
{
cin >> n >> m;
init();
while(m --)
{
int a , b , c;
cin >> a >> b >> c;
node[idx ++] = {a , b , c};
}
// 根據(jù)權(quán)值進(jìn)行排序
sort(node , node + idx , cmp);
int cnt = 0;
long long res = 0;
for(int i = 0;i < idx;i ++)
{
// cout << node[i].a << " " << node[i].b << " " << node[i].c << endl;
int fa = find(node[i].a) , fb = find(node[i].b);
if(fa != fb)
{
p[fa] = fb;
cnt += 1;
res += node[i].c;
}
if(cnt == n - 1) break;
}
cout << res << endl;
return 0;
}第五題：貨物調(diào)度
某公司要處理一個(gè)周期性的物流問(wèn)題。
有?n?個(gè)城市，第?i?個(gè)城市在每周的第?j(1≤j≤7) 天會(huì)生產(chǎn)?aij?噸某種貨物，同時(shí)需要消耗?bij?噸該種貨物。
已知每周的產(chǎn)量等于消耗量（即?aij?之和等于?bij?之和）。
城市之間有?m?條道路，第?k?條道路連接了城市?sk?和?tk。
一條道路上運(yùn)輸?1?噸貨物有一個(gè)固定的成本?ck。
道路都可以雙向使用。
每天運(yùn)輸?shù)呢浳锪繘](méi)有限制。
城市之間的距離并不遠(yuǎn)，貨物可以從任意一個(gè)城市運(yùn)輸?shù)饺我饬硪粋€(gè)城市并且在當(dāng)天到達(dá)。
貨物如果在當(dāng)天沒(méi)有被消耗掉，就需要存放在倉(cāng)庫(kù)里過(guò)夜。
第?i?個(gè)城市的倉(cāng)庫(kù)容量為?vi，存放?11?噸貨物過(guò)一夜所需的成本是?wi。
請(qǐng)你計(jì)算該公司如果每周循環(huán)性地按照一個(gè)固定的流程調(diào)度貨物的話，該公司在最優(yōu)方案下每周需要為貨物的運(yùn)輸和存儲(chǔ)消耗多少成本。
輸入格式
輸入的第一行有兩個(gè)正整數(shù)?n?和?m，即城市的個(gè)數(shù)和道路的條數(shù)。
接下來(lái)有?n?行，每行包含?16?個(gè)整數(shù)，用以描述第?i?個(gè)城市的相關(guān)數(shù)據(jù)。其中第?i 行包含的數(shù)為?ai1,ai2,ai3,ai4,ai5,ai6,ai7,bi1,bi2,bi3,bi4,bi5,bi6,bi7,vi,wi
接下來(lái)有?m?行，每行包含?3?個(gè)整數(shù)，用以描述一條道路的相關(guān)數(shù)據(jù)。其中第?k?行包含的數(shù)為?sk,tk?和?ck。
輸入數(shù)據(jù)中城市的編號(hào)均為?1?到?n?之間。
輸入數(shù)據(jù)的每行的行首行尾均保證沒(méi)有空格，兩個(gè)數(shù)之間恰好被一個(gè)空格隔開(kāi)。
輸出格式
你只需要輸出一個(gè)數(shù)，即最優(yōu)方案下每周的支出。
數(shù)據(jù)范圍
對(duì)于?100%?的數(shù)據(jù)，1≤n≤100，1≤m≤500，0≤aij,bij,vi≤1000≤，1≤wi,ck≤100。
數(shù)據(jù)保證倉(cāng)庫(kù)夠用。
數(shù)據(jù)保證無(wú)重邊和自環(huán)。（補(bǔ)充這個(gè)條件是為了和官方數(shù)據(jù)保持一致）輸入樣例：
3 3 0 0 0 0 5 0 0 0 0 0 0 0 0 0 2 4 0 0 0 0 0 0 0 2 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 3 0 0 0 0 2 5 1 2 1 1 3 5 2 3 1輸出樣例：
67樣例解釋
城市?1?每周五生產(chǎn)?5?噸貨物，把其中?2?噸運(yùn)到存儲(chǔ)費(fèi)用低廉的城市?2?存儲(chǔ)，把?1?噸運(yùn)到城市?3 存儲(chǔ)，剩下的?2?噸留在城市?1。
在次周一的時(shí)候城市?2?會(huì)消耗掉存放在那里的?2?噸貨物。
為了節(jié)約存儲(chǔ)成本，將囤放在城市?1?的貨物運(yùn)到城市?2?存放。
周三再將所有貨物運(yùn)到城市?3?以滿(mǎn)足該城市的需求。
在此方案下，每周的運(yùn)輸成本為?8，每周的存儲(chǔ)成本為?59，因此每周的總支出為?67。
?解題思路：網(wǎng)絡(luò)流的經(jīng)典問(wèn)題?（但是我不會(huì)）
學(xué)習(xí)學(xué)習(xí)
以下是代碼：
c++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 710, M = (N * 3 + 500 * 7 * 2) * 2 + 10, INF = 0x3f3f3f3f;
int n, m, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
int get(int a, int b)
{
if (b == 8) b = 1;
return (a - 1) * 7 + b;
}
void add(int a, int b, int c, int d)
{
e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++ ;
}
bool spfa()
{
int hh = 0, tt = 1;
memset(d, 0x3f, sizeof d);
memset(incf, 0, sizeof incf);
q[0] = S, d[S] = 0, incf[S] = INF;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (f[i] && d[ver] > d[t] + w[i])
{
d[ver] = d[t] + w[i];
pre[ver] = i;
incf[ver] = min(incf[t], f[i]);
if (!st[ver])
{
q[tt ++ ] = ver;
if (tt == N) tt = 0;
st[ver] = true;
}
}
}
}
return incf[T] > 0;
}
void EK(int& flow, int& cost)
{
flow = cost = 0;
while (spfa())
{
int t = incf[T];
flow += t, cost += t * d[T];
for (int i = T; i != S; i = e[pre[i] ^ 1])
{
f[pre[i]] -= t;
f[pre[i] ^ 1] += t;
}
}
}
int main()
{
cin >> n >> m;
S = 0, T = n * 7 + 1;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ )
{
int c, d;
for (int j = 1; j <= 7; j ++ )
{
cin >> c;
add(S, get(i, j), c, 0);
}
for (int j = 1; j <= 7; j ++ )
{
cin >> c;
add(get(i, j), T, c, 0);
}
cin >> c >> d;
for (int j = 1; j <= 7; j ++ )
add(get(i, j), get(i, j + 1), c, d);
}
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
for (int i = 1; i <= 7; i ++ )
{
add(get(a, i), get(b, i), INF, c);
add(get(b, i), get(a, i), INF, c);
}
}
int flow, cost;
EK(flow, cost);
cout << cost << endl;
return 0;
}這兩篇可以學(xué)習(xí)記錄一下?
最大流 - OI Wiki (oi-wiki.org)文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-556908.html
網(wǎng)絡(luò)流簡(jiǎn)介 - OI Wiki (oi-wiki.org)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-556908.html
到了這里，關(guān)于第三次CCF計(jì)算機(jī)軟件能力認(rèn)證的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
