文章目錄
- A 空間
- 卡片
- 直線
- 貨物擺放
- 路徑
- 時間顯示
- G砝碼稱重
- H楊輝三角形
- 雙向排列
- J括號序列
注：有些代碼忘了考試時怎么寫的了，（我也懶得重新寫），所以很多題的代碼是acwing藍橋杯講解里的，我對其進行注釋和修改
A 空間
32位程式中，INT變數占用4個位元組
1mb=1024kb
1kb=1024B
1B=8b
B:byte
b:bit
32位二進制數是四個位元組
實際上就是求256MB有多少個32 bit
答案：256*1024*1024/4
= 67108864
卡片
直接模擬即可
#include<bits/stdc++.h>
#define debug(a,b) printf("%s = %d\n",a,b)
typedef long long ll;
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
return s*w;
}
int a[10];
bool iff(int x)
{
while (x)
{
int y = x % 10;
if (a[y])
a[y]--;
else
return 0;
x /= 10;
}
return 1;
}
int main() {
for (int i = 0; i <= 9; i++) a[i] = 2021;
for (int i = 1;; i++)
{
if (!iff(i))
{
cout << i - 1 << endl;
break;
}
}
return 0;
}
答案：3181
直線
比賽時用set實作的，忘了自己做的對不對，，
我當時做的方法是因為兩點確定一線，所以列舉兩個點，然后用set記錄斜率和截距（y=k*x+b）,但是k有可能不存在，所以最后的答案還要額外加上20
當時代碼懶得寫了，按照其他博主的寫法重新寫的，只不過用的不是set，存下所有k和b后，排序，將重復的k和b刪掉
#include<bits/stdc++.h>
#define debug(a,b) printf("%s = %d\n",a,b)
typedef long long ll;
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
return s*w;
}
const int maxn = 200000;
double eps=1e-8;
int n;
struct Line
{
double k, b;
bool operator< (const Line& t) const
{
if (k != t.k) return k < t.k;
return b < t.b;
}
}L[maxn];
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)(y2 - y1) / (x2 - x1);
double b = y1 - k * x1;
L[n ++ ] = {k, b};//存兩點所形成的直線
}
sort(L, L +maxn);
int res = 1;
for (int i = 1; i < n; i ++ )
if (fabs(L[i].k - L[i - 1].k) > eps || fabs(L[i].b - L[i - 1].b) > eps)//說明不是一條直線
res ++ ;
cout << res + 20 << endl;//加20是因為k不存在的直線也要考慮
return 0;
}
我當時的做法是對的，但是最后的答案忘了是不是這個
答案：40257
貨物擺放
LWH都是n的約數，問有多少種方案，其實就是求n的約數，用這些約數進行組合，因為約數不是很多，所以三重回圈列舉約數，看是否等于n
對n求約束，直接開方求就行（因為如果x是約數，那么n/x也是，所以只需要將范圍縮小到根號n）
（比賽時我是這么做的，確信）
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
int main()
{
LL n;
cin >> n;
vector<LL> d;
for (LL i = 1; i * i <= n; i ++ )
if (n % i == 0)
{
d.push_back(i);
if (n / i != i) d.push_back(n / i);
}
int res = 0;
for (auto a: d)
for (auto b: d)
for (auto c: d)
if (a * b * c == n)
res ++ ;
cout << res << endl;
return 0;
}
答案：2430
路徑
就是一個建邊跑最短路，，比賽時忘了gcd咋寫emm
好像有的用dp來做？
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2200, M = N * 50;
int n;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N];
bool st[N];
int gcd(int a, int b) // 歐幾里得演算法
{
return b ? gcd(b, a % b) : a;
}
void add(int a, int b, int c) // 添加一條邊a->b，邊權為c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void spfa() // 求1號點到n號點的最短路距離
{
int hh = 0, tt = 0;
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
q[tt ++ ] = 1;
st[1] = true;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
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]) // 如果佇列中已存在j，則不需要將j重復插入
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
}
int main()
{
n = 2021;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ )
for (int j = max(1, i - 21); j <= min(n, i + 21); j ++ )
{
int d = gcd(i, j);
add(i, j, i * j / d);
}
spfa();
printf("%d\n", dist[n]);
return 0;
}
答案：10266837
時間顯示
比賽時忘了1s等于多少ms，還好電腦自帶計算器里有時間的進制關系（狗頭🐕）
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int main()
{
LL n;
cin >> n;
n /= 1000;
n %= 86400;
int h = n / 3600;
n %= 3600;
int m = n / 60;
int s = n % 60;
printf("%02d:%02d:%02d\n", h, m, s);
return 0;
}
G砝碼稱重
背包問題
自己對dp真的不熟，，五一要好好練練dp
對于每個砝碼他有三個選擇，稱的左側，右側和不放，
我們設dp[i][j]表示前i個物品中，總質量為j的情況是否存在，dp為bool型
對于第j個物品，我們說了有三種選擇，所以我們可以得到轉移方程：
分別對應不選，放左側，放右側
dp[i][j]|=dp[i-1][j]
dp[i][j]|=dp[i-1][j-w[i]]
dp[i][j]|=dp[i-1][j+w[i]]
按照題目要求j-w[i]最小為-m，陣列不能用負下標，所以我們加一個偏移量B，保證陣列下標都為非負
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 200010, B = M / 2;
int n, m;
int w[N];
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 ++ ;
printf("%d\n", res);
return 0;
}
H楊輝三角形
因為楊輝三角形左右對稱，所以我們只考慮左半部分
我們進行列舉可以看出，斜列的數量不會超過20個，所以列舉每一個斜列，每個斜列的第一個元素也是遞增排列且有關系（第一個斜列的首元素為C(1,0),第二個為C(1,2),第三個為C(2,4),…C(x,2x)）,斜列內的元素是遞增排列的，且大小都有公式關系（比如第3個斜列，第一個元素是C(2,4),第二個元素是C(2,5),然后是C(2,6)…），然后二分找具體位置
如果第C(r,k)是我們要找的元素，他的位置就是r * (r + 1) / 2 + k + 1
思維題
妙啊，當時寫了一個半暴力，真想不到
#include <iostream>
#include <cstring>
#include <algorithm>
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;
}
return res;
}
bool check(int k)
{
//C(a,b)
//a>=2b,二分a
LL l = k * 2, r = n;
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 << endl;
return true;
}
int main()
{
cin >> n;
for (int k = 16; ; k -- )
if (check(k))
break;
return 0;
}
雙向排列
講解鏈接
J括號序列
肯定是dp，但是我不會，，，等會了再更新
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/282143.html
標籤：其他
下一篇：Linux_多執行緒與鎖