河北賽區C++ B組省一，省內排名第六
第一次參加藍橋杯，也做過以前省賽的題目
今年的省賽風格大變，完全不同于往常，搜索、暴力等常考演算法沒有出現，反而出現了大量的思維題和dp題目，
編程題的最后兩個題目完全不符合B組的難度
試題 A: 空間
答案：256 * 1024 * 1024 / 4 = 67108864
試題 B: 卡片
小藍有很多數字卡片，每張卡片上都是數字 0 到 9，
小藍準備用這些卡片來拼一些數，他想從 1 開始拼出正整數，每拼一個，
就保存起來，卡片就不能用來拼其它數了，
小藍想知道自己能從 1 拼到多少，
例如，當小藍有 30 張卡片，其中 0 到 9 各 3 張，則小藍可以拼出 1 到 10，
但是拼 11 時卡片 1 已經只有一張了，不夠拼出 11，
現在小藍手里有 0 到 9 的卡片各 2021 張，共 20210 張，請問小藍可以從 1
拼到多少？
提示：建議使用計算機編程解決問題，
分析：
開一個桶，記錄一下每張牌的個數，一旦發現湊某個數時牌不夠用了，check函式直接回傳false，注意最后答案要減一
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int s[10];
bool check(int x)
{
while (x)
{
int t = x % 10;
x /= 10;
if ( -- s[t] < 0) return false;
}
return true;
}
int main()
{
for (int i = 0; i < 10; i ++ ) s[i] = 2021;
for (int i = 1; ; i ++ )
if (!check(i))
{
cout << i - 1 << endl;
return 0;
}
return 0;
}
答案：3181
試題 C: 直線
在平面直角坐標系中，兩點可以確定一條直線，如果有多點在一條直線上，那么這些點中任意兩點確定的直線是同一條，
給定平面上 2 × 3 2 × 3 2×3 個整點 { ( x , y ) ∣ 0 ≤ x < 2 , 0 ≤ y < 3 , x ∈ Z , y ∈ Z } \left \{ (x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z\right \} {(x,y)∣0≤x<2,0≤y<3,x∈Z,y∈Z}，即橫坐標是 0 到 1 (包含 0 和 1)
之間的整數、縱坐標是 0 0 0 到 $2 $(包含 0 0 0和 2 2 2) 之間的整數的點，這些點一共確定了 11 11 11 條不同的直線，
給定平面上 20 × 21 20 × 21 20×21個整點 { ( x , y ) ∣ 0 ≤ x < 20 , 0 ≤ y < 21 , x ∈ Z , y ∈ Z } \left \{(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z\right \} {(x,y)∣0≤x<20,0≤y<21,x∈Z,y∈Z}，即橫坐標是 0 到 19 (包含 0
和 19) 之間的整數、縱坐標是 0 到 20 (包含 0 和 20) 之間的整數的點，請問這些點一共確定了多少條不同的直
線，
分析：
兩點確定一條直線，四重for回圈列舉兩個點的坐標，求出斜率和縱截距，注意特判斜率不存在的情況x1==x2
但是set存浮點數有誤差，不妨將所有直線放到vector中，然后以斜率為第一關鍵字，縱截距為第二關鍵字排序，相鄰元素的差值>1e-8就可以判為不相等
#include <iostream>
#include <cstring>
#include <algorithm>
#include<cmath>
using namespace std;
struct Line{
double k,b;
bool operator<(const Line &t) const{
if(k!=t.k) return k<t.k;
else return b<t.b;
}
};
vector<Line> v;
int main(){
for(int x1=0;x1<20;x1++){
for(int y1=0;y1<21;y1++){
for(int x2=0;x2<20;x2++){
for(int y2=0;y2<21;y2++){
if(x1!=x2){
double k=(double)(y1-y2)/(x1-x2);
double b=y1-k*x1;
v.push_back({k,b});
}
}
}
}
}
sort(v.begin(),v.end());
int res=1;
for(int i=0;i<v.size()-1;i++){
if(fabs(v[i].k-v[i+1].k)>1e-8 || fabs(v[i].b-v[i+1].b)>1e-8){
res++;
}
}
cout<<res+20;
}
試題 D: 貨物擺放
小藍有一個超大的倉庫，可以擺放很多貨物，
現在，小藍有 n n n 箱貨物要擺放在倉庫，每箱貨物都是規則的正方體，小藍規定了長、寬、高三個互相垂直的方向，每箱貨物的邊都必須嚴格平行于長、寬、高，
小藍希望所有的貨物最終擺成一個大的立方體，即在長、寬、高的方向上分別堆 L 、 W 、 H L、W、H L、W、H 的貨物，滿足 n = L × W × H n = L × W × H n=L×W×H，
給定 n n n，請問有多少種堆放貨物的方案滿足要求，
例如，當 n = 4 n = 4 n=4 時，有以下 6 6 6種方案： 1 × 1 × 4 、 1 × 2 × 2 、 1 × 4 × 1 、 2 × 1 × 2 、 2 × 2 × 1 、 4 × 1 × 1 1×1×4、1×2×2、1×4×1、2×1×2、 2 × 2 × 1、4 × 1 × 1 1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1，
請問，當 n = 2021041820210418 n = 2021041820210418 n=2021041820210418 （注意有 16 位數字）時，總共有多少種方案？
提示：建議使用計算機編程解決問題，
分析：
預處理出n的所有約數，大約有100多個，然后三重for回圈判斷三個數乘積是否等于n即可
時間復雜度 O ( n 3 ) O(n^3) O(n3)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
vector<ll> v;
int main(){
ll n=2021041820210418;
for(ll i=1;i*i<=n;i++){
if(n%i==0){
v.push_back(i);
if(n/i!=i){
v.push_back(n/i);
}
}
}
int res=0;
for(auto a:v){
for(auto b:v){
for(auto c:v){
if(a*b*c==n){
res++;
}
}
}
}
cout<<res;
return 0;
}
試題 E: 路徑
小藍學習了最短路徑之后特別高興，他定義了一個特別的圖，希望找到圖中的最短路徑，
小藍的圖由 2021 2021 2021 個結點組成，依次編號 1 1 1至 2021 2021 2021，
對于兩個不同的結點 a , b a, b a,b，如果 a a a 和 b b b 的差的絕對值大于 21 21 21，則兩個結點之間沒有邊相連；如果 a a a 和 b b b 的差的絕對值小于等于 21 21 21，則兩個點之間有一條長度為 a a a和 b b b 的最小公倍數的無向邊相連，
例如：結點 1 1 1 和結點 23 23 23 之間沒有邊相連；結點 3 3 3 和結點 24 24 24 之間有一條無向邊，長度為 24 24 24；結點 15 15 15 和結點 25 25 25 之間有一條無向邊，長度為 75 75 75，
請計算，結點 1 1 1 和結點 2021 2021 2021 之間的最短路徑長度是多少，
提示：建議使用計算機編程解決問題，
分析：
簡單的最短路問題，可以用spfa，dijkstra，甚至是floyd演算法解決
#include<bits/stdc++.h>
using namespace std;
const int N=2030,M=100005;
int h[N],e[M],w[M],ne[M],idx;
int dist[N];
bool st[N];
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void spfa(){
queue<int> q;
memset(dist,0x3f,sizeof dist);
dist[1]=0;
q.push(1);
st[1]=true;
while(!q.empty()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
if(!st[j]){
st[j]=true;
q.push(j);
}
}
}
}
}
int main(){
memset(h, -1, sizeof h);
for(int i=1;i<=2021;i++){
for(int j=i+1;j<=2021;j++){
if(abs(i-j)<=21){
add(i,j,i*j/__gcd(i,j));
add(j,i,i*j/__gcd(i,j));
}
}
}
spfa();
cout<<dist[2021];
return 0;
}
試題 F: 時間顯示
小藍要和朋友合作開發一個時間顯示的網站，
在服務器上，朋友已經獲取了當前的時間，用一個整數表示，值為從 1970 1970 1970 年 1 1 1 月 1 1 1 日 00 : 00 : 00 00:00:00 00:00:00 到當前時刻經過的毫秒數，
現在，小藍要在客戶端顯示出這個時間，
小藍不用顯示出年月日，只需要顯示出時分秒即可，毫秒也不用顯示，直接舍去即可，
給定一個用整數表示的時間，請將這個時間對應的時分秒輸出，
輸入格式
輸入一行包含一個整數，表示時間，
輸出格式
輸出時分秒表示的當前時間，格式形如 HH:MM:SS，其中 HH 表示時，值為
0
0
0 到
23
23
23，MM 表示分，值為
0
0
0 到
59
59
59，SS 表示秒，值為
0
0
0 到
59
59
59，
時、分、秒不足兩位時補前導 0 0 0，
資料范圍
對于所有評測用例，給定的時間為不超過 1 0 18 10^{18} 1018 的正整數，
輸入樣例1：
46800999
輸出樣例1：
13:00:00
輸入樣例2：
1618708103123
輸出樣例2：
01:08:23
分析：
n / = 1000 n/=1000 n/=1000，得到秒數
一天有 24 ? 60 ? 60 = 86400 24*60*60=86400 24?60?60=86400秒， n % = 86400 n\%=86400 n%=86400可以得到最后一天的秒數
最后一天的小時數 h = n / 3600 h=n/3600 h=n/3600，然后 n % = 3600 n\%=3600 n%=3600
分鐘數 m = n / 60 m=n/60 m=n/60，最后的秒數 s = n % 60 s=n\%60 s=n%60
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int main(){
ll n;
cin>>n;
n/=1000;
n%=86400;
ll h=n/3600;
n%=3600;
ll m=n/60;
ll s=n%60;
printf("%02lld:%02lld:%02lld",h,m,s);
}
考場上的源代碼（沒有考慮公式，直接列舉做的，能過60%資料）：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int main(){
ll n;
cin>>n;
n/=1000;
ll h=0,m=0,s=0;
while(n--){
s++;
if(s==60){
m++;
s=0;
if(m==60){
m=0;
h++;
if(h==24){
h=0;
}
}
}
}
printf("%02lld:%02lld:%02lld",h,m,s);
}
試題 G: 砝碼稱重
你有一架天平和 N N N 個砝碼，這 N N N 個砝碼重量依次是 W 1 , W 2 , ? ? ? , W N W_1,W_2,···,W_N W1?,W2?,???,WN?，
請你計算一共可以稱出多少種不同的正整數重量？
注意砝碼可以放在天平兩邊，
輸入格式
輸入的第一行包含一個整數 N N N，
第二行包含 N N N 個整數： W 1 , W 2 , W 3 , ? ? ? , W N W_1,W_2,W_3,···,W_N W1?,W2?,W3?,???,WN?，
輸出格式
輸出一個整數代表答案，
資料范圍
對于
50
50%
50 的評測用例，
1
≤
N
≤
15
1≤N≤15
1≤N≤15，
對于所有評測用例，
1
≤
N
≤
100
1≤N≤100
1≤N≤100，
N
N
N 個砝碼總重不超過
1
0
5
10^5
105，
輸入樣例：
31 4 6
輸出樣例：
10
樣例解釋
能稱出的 1010 種重量是： 1 、 2 、 3 、 4 、 5 、 6 、 7 、 9 、 10 、 11 1、2、3、4、5、6、7、9、10、11 1、2、3、4、5、6、7、9、10、11，
1 = 1；2 = 6 ? 4 (天平一邊放 6，另一邊放 4)；3 = 4 ? 1；4 = 4；5 = 6 ? 1；6 = 6；7 = 1 + 6；9 = 4 + 6 ? 1；10 = 4 + 6；11 = 1 + 4 + 6，
分析：
方法1：背包dp（有限制的選擇問題）
狀態表示 f [ i , j ] f[i,j] f[i,j]：集合：只從前 i i i個物品中選，且總重量為 j j j的所有方案的集合
? 屬性：是否非空(bool)
狀態計算：【1】不選 w i w_i wi?： f [ i , j ] = f [ i ? 1 , j ] f[i,j]=f[i-1,j] f[i,j]=f[i?1,j]
? 【2】選 + w i +w_i +wi?： f [ i , j ] = f [ i ? 1 ] [ j ? w [ i ] ] f[i,j]=f[i-1][j-w[i]] f[i,j]=f[i?1][j?w[i]]
? 【3】選 ? w i -w_i ?wi?： f [ i , j ] = f [ i ? 1 ] [ j + w [ i ] ] f[i,j]=f[i-1][j+w[i]] f[i,j]=f[i?1][j+w[i]]
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=200005,B=M/2;
int w[N],n,m;
bool f[N][M];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&w[i]),m+=w[i];
f[0][B]=true;
for(int i=1;i<=n;i++){
for(int j=-m;j<=m;j++){
f[i][j+B]=f[i-1][j+B];
if(j-w[i]>=-m) f[i][j+B]|=f[i-1][j-w[i]+B];
if(j+w[i]<=m) f[i][j+B]|=f[i-1][j+w[i]+B];
}
}
int res=0;
for(int j=1;j<=m;j++){
if(f[n][j+B]) res++;
}
cout<<res;
return 0;
}
方法2：母函式
這里套用了母函式的模板，沒有用dp方法做，因為恰好是不久前學到的一個原題
#include <bits/stdc++.h>
using namespace std;
const int N=1050,M = 1000005;
int c1[M],c2[M],w[N];
int main(){
int n;
scanf("%d",&n);
int maxl=0;
for(int i=0;i<n;i++) {
scanf("%d",&w[i]);
maxl+=w[i];
}
c1[0]=1;c1[w[0]]=1;
for(int i=1;i<n;i++){
for(int j=0;j<=maxl;j++){
for(int k=0;k<=w[i];k+=w[i]){
c2[j+k]+=c1[j];
c2[abs(j-k)]+=c1[j];
}
}
for(int j=0;j<=maxl;j++){
c1[j]=c2[j];
c2[j]=0;
}
}
int cnt=0;
for(int i=1;i<=maxl;i++){
if(c1[i]) cnt++;
}
cout<<cnt;
}
試題 H: 楊輝三角形
下面的圖形是著名的楊輝三角形：
如果我們按從上到下、從左到右的順序把所有數排成一列，可以得到如下數列：
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...
給定一個正整數 N N N，請你輸出數列中第一次出現 N N N 是在第幾個數？
輸入格式
輸入一個整數 N N N，
輸出格式
輸出一個整數代表答案，
資料范圍
對于
20
20%
20 的評測用例，
1
≤
N
≤
10
1≤N≤10
1≤N≤10；
對于所有評測用例，
1
≤
N
≤
1
0
9
1≤N≤10^9
1≤N≤109，
輸入樣例：
6
輸出樣例：
13
如圖所示，從最后一個斜條開始列舉到第一個斜條，每一個斜條的第一個數均為 C ( 2 k , k ) C(2k,k) C(2k,k)，在每一個斜條中二分查找，時間復雜度 O ( 16 l o g n ) O(16logn) O(16logn)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll C(int a,int b){
ll res=1;
for(int i=a,j=1;j<=b;i--,j++){
res=res*i/j;
if(res>n) return res;//防止爆long long
}
return res;
}
bool check(int k){
ll l=k*2,r=max((ll)n,l);
while(l<r){
ll mid=l+r>>1;
if(C(mid,k)>=n) r=mid;
else l=mid+1;
}
if(C(r,k)!=n) return false;
cout<<r*(r+1)/2+k+1;//r的前面有r行
return true;
}
int main(){
cin>>n;
for(int k=16;;k--){
if(check(k)) break;
}
return 0;
}
試題 I: 雙向排序
給定序列 ( a 1 , a 2 , ? ? ? , a n ) = ( 1 , 2 , ? ? ? , n ) (a_1,a_2,···,a_n)=(1,2,···,n) (a1?,a2?,???,an?)=(1,2,???,n)，即 a i = i a_i=i ai?=i，
小藍將對這個序列進行 m m m 次操作，每次可能是將 a 1 , a 2 , ? ? ? , a q i a_1,a_2,···,a_{q_i} a1?,a2?,???,aqi?? 降序排列，或者將 a q i , a q i + 1 , ? ? ? , a n a_{q_i},a_{q_{i+1}},···,a_n aqi??,aqi+1??,???,an?升序排列，
請求出操作完成后的序列，
輸入格式
輸入的第一行包含兩個整數 n , m n,m n,m，分別表示序列的長度和操作次數，
接下來 m m m 行描述對序列的操作，其中第 i i i 行包含兩個整數 p i , q i p_i,q_i pi?,qi?表示操作型別和引數，當 p i = 0 p_i=0 pi?=0 時，表示將 a 1 , a 2 , ? ? ? , a q i a_1,a_2,···,a_{q_i} a1?,a2?,???,aqi?? 降序排列；當 p i = 1 p_i=1 pi?=1 時，表示將 a q i , a q i + 1 , ? ? ? , a n a_{q_i},a_{q_{i+1}},···,a_n aqi??,aqi+1??,???,an?升序排列，
輸出格式
輸出一行，包含 n n n 個整數，相鄰的整數之間使用一個空格分隔，表示操作完成后的序列，
資料范圍
對于
30
%
30\%
30% 的評測用例，
n
,
m
≤
1000
n,m≤1000
n,m≤1000；
對于
60
%
60\%
60% 的評測用例，
n
,
m
≤
5000
n,m≤5000
n,m≤5000；
對于所有評測用例，
1
≤
n
,
m
≤
1
0
5
，
0
≤
p
i
≤
1
，
1
≤
q
i
≤
n
1≤n,m≤10^5，0≤p_i≤1，1≤q_i≤n
1≤n,m≤105，0≤pi?≤1，1≤qi?≤n，
輸入樣例：
3 3
0 3
1 2
0 2
輸出樣例：
3 1 2
樣例解釋
原數列為 ( 1 , 2 , 3 ) (1,2,3) (1,2,3)，
第 1 1 1 步后為 ( 3 , 2 , 1 ) (3,2,1) (3,2,1)，
第 2 2 2 步后為 ( 3 , 1 , 2 ) (3,1,2) (3,1,2)，
第 3 3 3 步后為 ( 3 , 1 , 2 ) (3,1,2) (3,1,2)，與第 2 2 2 步操作后相同，因為前兩個數已經是降序了，
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n, m;
PII stk[N];
int ans[N];
int main()
{
scanf("%d%d", &n, &m);
int top = 0;
while (m -- )
{
int p, q;
scanf("%d%d", &p, &q);
if (!p)
{
while (top && stk[top].x == 0) q = max(q, stk[top -- ].y);
while (top >= 2 && stk[top - 1].y <= q) top -= 2;
stk[ ++ top] = {0, q};
}
else if (top)
{
while (top && stk[top].x == 1) q = min(q, stk[top -- ].y);
while (top >= 2 && stk[top - 1].y >= q) top -= 2;
stk[ ++ top] = {1, q};
}
}
int k = n, l = 1, r = n;
for (int i = 1; i <= top; i ++ )
{
if (stk[i].x == 0)
while (r > stk[i].y && l <= r) ans[r -- ] = k -- ;
else
while (l < stk[i].y && l <= r) ans[l ++ ] = k -- ;
if (l > r) break;
}
if (top % 2)
while (l <= r) ans[l ++ ] = k -- ;
else
while (l <= r) ans[r -- ] = k -- ;
for (int i = 1; i <= n; i ++ )
printf("%d ", ans[i]);
return 0;
}
試題 J: 括號序列
給定一個括號序列，要求盡可能少地添加若干括號使得括號序列變得合法，當添加完成后，會產生不同的添加結果，請問有多少種本質不同的添加結果，
兩個結果是本質不同的是指存在某個位置一個結果是左括號，而另一個是右括號，
例如，對于括號序列 ((()，只需要添加兩個括號就能讓其合法，有以下幾種不同的添加結果：()()()、()(())、(())()、(()()) 和 ((()))，
輸入格式
輸入一行包含一個字串 s s s，表示給定的括號序列，序列中只有左括號和右括號，
輸出格式
輸出一個整數表示答案，答案可能很大，請輸出答案除以 1000000007 1000000007 1000000007 (即 1 0 9 + 7 10^9+7 109+7) 的余數，
資料范圍
對于
40
40%
40 的評測用例，
∣
s
∣
≤
200
|s|≤200
∣s∣≤200，
對于所有評測用例，
1
≤
∣
s
∣
≤
5000
1≤|s|≤5000
1≤∣s∣≤5000，
輸入樣例：
((()
輸出樣例：
5
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5010, MOD = 1e9 + 7;
int n;
char str[N];
LL f[N][N];
LL work()
{
memset(f, 0, sizeof f);
f[0][0] = 1;
for (int i = 1; i <= n; i ++ )
if (str[i] == '(')
{
for (int j = 1; j <= n; j ++ )
f[i][j] = f[i - 1][j - 1];
}
else
{
f[i][0] = (f[i - 1][0] + f[i - 1][1]) % MOD;
for (int j = 1; j <= n; j ++ )
f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % MOD;
}
for (int i = 0; i <= n; i ++ )
if (f[n][i])
return f[n][i];
return -1;
}
int main()
{
scanf("%s", str + 1);
n = strlen(str + 1);
LL l = work();
reverse(str + 1, str + n + 1);
for (int i = 1; i <= n; i ++ )
if (str[i] == '(') str[i] = ')';
else str[i] = '(';
LL r = work();
printf("%lld\n", l * r % MOD);
return 0;
}
最后總結一下本次比賽吧：
填空題對了1 2 5
編程題第一個，直接列舉做的(我太菜了)
第二個應該是天平稱重，恰好是前幾天hdu培訓中關于母函式的一道原題，15分滿分
后面楊輝三角那題，寫了個滾動陣列，勉強能跑50000的資料，，
雙向排序直接sort騙分，，
最后一題不會，，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/282151.html
標籤：其他