2023年10月15日
今天是补题大作战！
AcwingRound125 A 数量
题目理解
语法题
代码实现
void solve()
{
int cnt = 0;
int n;
cin >> n;
for(int i = 1; i <= n; i++)
if(i % 2 == 0 && i % 3 != 0)
cnt++;
cout << cnt;
return;
}
AcwingRound125 B 三元组
题目理解
分三种情况讨论：
- a[0] == a[1] == a[2]
- a[0] != a[1] == a[2]
- a[1] != a[2]
代码实现
void solve()
{
int n;
cin >> n;
vector<int> a(n);
ll cnt = 0;
for(int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
if(a[1] == a[2] && a[1] != a[0])
{
for(int i = 0; i < n; i++)
if(a[i] > a[2])
break;
else
cnt++;
ll k = cnt - 2;
cout << (k + 1) * k / 2;
}else if(a[1] != a[2]){
for(int i = 2; i < n; i++)
if(a[i] > a[2])
break;
else
cnt++;
cout << cnt;
}else if(a[1] == a[2] && a[1] == a[0])
{
for(int i = 0; i < n; i++)
if(a[i] > a[2])
break;
else
cnt++;
ll res = 0;
ll k = cnt - 2;
while(k >= 1)
{
res += ((k + 1) * k) >> 1;
k--;
}
cout << res;
}
return;
}
Acwing487 金明的运算方案
题目理解
代码实现
int n, m;
PII master[N];
vector<PII> servent[N];
int f[M];
void solve()
{
cin >> m >> n;
for(int i = 1; i <= n; i++)
{
int v, p, q;
cin >> v >> p >> q;
p *= v;
if(!q) master[i] = {v, p};
else servent[q].push_back({v, p});
}
for(int i = 1; i <= n; i++)
for(int u = m; u >= 0; u--)
{
for(int j = 0; j < 1 << servent[i].size(); j++) // 二的n次种方案
{
int v = master[i].v, w = master[i].w;
for(int k = 0; k < (int)servent[i].size(); k++) // 枚举每一个从品
if(j >> k & 1)
{
v += servent[i][k].v;
w += servent[i][k].w;
}
if(u >= v) f[u] = max(f[u], f[u - v] + w);
}
}
cout << f[m] << endl;
return;
}
Acwing291 蒙德里安的梦想
题目理解
代码实现
const int N = 12, M = 1 << N;
int n, m;
ll f[N][M];
bool st[M];
void solve()
{
while(cin >> n >> m, n || m)
{
memset(f, 0, sizeof f);
memset(st, 0, sizeof st);
// 预处理所有的状态，是否不存在连续奇数个0
for(int i = 0; i < 1 << n; i++)
{
st[i] = true;
int cnt = 0;
for(int j = 0; j < n; j++)
if(i >> j & 1) // 当前这一位是1
{
if(cnt & 1) st[i] = false; //cnt & 1 == cnt % 2
cnt = 0;
}else cnt++;
if(cnt & 1) st[i] = false; // 查看连续的空着的个数是否为奇数
}
// 开始dp
f[0][0] = 1; // 最开始的时候
for(int i = 1; i <= m; i++)
for(int j = 0; j < 1 << n; j++)
for(int k = 0; k < 1 << n; k++)
if((j & k) == 0 && st[j | k])
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;
}
return;
}
Acwing1064 小国王
题目理解
代码实现
const int N = 12, M = (1 << N) + 10, K = 110;
int n, m;
ll f[N][K][M];
vector<ll> state; // 每一个合法状态
ll id[M], cnt[M]; // 每一个状态和下标直接的映射关系， cnt是每一个状态中1的个数
vector<ll> head[M]; // 每一个状态可以转移到的其他状态
bool check(int u)
{
for(int i = 0; i < n; i++)
if((u >> i & 1) && (u >> (i + 1) & 1))
return false;
return true;
}
int count(int u)
{
int res = 0;
for(int i = 0; i < n; i++)
if(u >> i & 1)res++;
return res;
}
void solve()
{
cin >> n >> m;
// 找到合法状态
for(int i = 0; i < 1 << n; i++)
if(check(i)) // 是否存在两个连续的1
state.push_back(i);
// 处理哪两个状态可以相互转移
for(int i = 0; i < (int)state.size(); i++)
for(int j = 0; j < (int)state.size(); j++)
{
int a = state[i], b = state[j];
if((a & b) == 0 && check(a | b)) // 条件
head[a].push_back(b);
}
f[0][0][0] = 1;
for(int i = 1; i <= n + 1; i++) // 多算一行hh，可以把答案好写
for(int j = 0; j <= m; j++)
for(int a = 0; a < (int)state.size(); a++)
for(int b = 0; b < (int)head[state[a]].size(); b++)
{
int c = count(state[a]);
if(j >= c) // 一定要满足摆放的上限
f[i][j][state[a]] += f[i - 1][j - c][head[state[a]][b]];
}
cout << f[n + 1][m][0]; // 拜访了n + 1行，但是摆了0个
return;
}
Div.3 Round863 B Conveyor Belts
题目大意
给了传送带的阶数，给了启起始位置，和终止位置，每跨一级是一个花费。问最小花费是多少
题目理解
很明显我在阶数相同的地方，无需花费，因为直接可以到达。所以花费最少就是阶数差，只需要判断终点和起点，分别在第几圈然后做差即可。
代码实现
void solve()
{
ll n, x1, y1, x2, y2;
cin >> n >> x1 >> y1 >> x2 >> y2;
ll l1 = min(min(x1, n - x1 + 1), min(y1, n - y1 + 1));
ll l2 = min(min(x2, n - x2 + 1), min(y2, n - y2 + 1));
cout << abs(l1 - l2) << endl;
return;
}
Div.3 Round863 C Restore the Array
题目大意
给了你n-1个数，这n-1个数，是n个数中两两比较大的那个值。问你原序列，可能是什么样子？
题目理解
首先，第一个和倒数第二个值一定要输出，然后中间大的我们去两者的小值即可。
代码实现
void solve(){
int n;
cin >> n;
vector<int>b(n-1), a;
for(int i = 0; i < n - 1; i++) cin >> b[i];
a.push_back(b[0]);
for(int i = 0; i < n - 2; i++){
a.push_back(min(b[i], b[i + 1]));
}
a.push_back(b[n - 2]);
for(auto i : a) cout << i << ' ';
cout << "\n";
}
蓝桥杯第一次双周赛 A题 三带一
题目理解
直接map统计，看是否存在3和1即可
代码实现
void solve()
{
string s;
cin >> s;
map<char, int> mp;
for(int i = 0; i < 4; i++)
{
if(!mp.count(s[i]))
{
mp[s[i]] = 1;
}else
mp[s[i]]++;
}
int a, b, i = 0;
for(auto p:mp)
{
if(i % 2) a = p.y;
else b = p.y;
i++;
}
if(a == 3 && b == 1 || a == 1 && b == 3)
{
cout << "Yes" << endl;
}else
cout << "No" << endl;
return;
}
蓝桥杯第一次双周赛 B 数树数
题目理解
遇到R乘2，遇L * 2 + 1即可
代码实现
void solve()
{
int n, q;
cin >> n >> q;
while(q--)
{
string s;
cin >> s;
int res = 1;
for(int i = 0; i < (int)s.size(); i++)
{
if(s[i] == 'R')
res *= 2;
else
res = res * 2 - 1;
}
cout << res << endl;
}
return;
}
蓝桥杯第一次周赛 C 分组
题目理解
直接二分极差，然后判断在这个极差下的分组能否小于等于k，如果不行就扩大极差，如果可以就减小极差
代码实现
const int N = 1e5 + 10;
int a[N], k, n;
bool check(int u)
{
int cnt = 1, idx = 1;
for(int i = 1; i <= n; i++)
{
if(a[i] - a[idx] > u)
{
cnt++;
idx = i;
}
}
if(cnt > k) return false;
return true;
}
void solve()
{
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
int l = 0, r = a[n] - a[1];
while(l < r)
{
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << l;
}
蓝桥杯第一次双周赛 D 锻炼
题目理解
多个完全背包，把每个需要可以连续锻炼的天数看作一个单独的完全背包。然后用map存下来，对于每个时间段进行求解完全背包即可。然后把答案累加
代码实现
const int N = 2e5 + 10, M = (1 << 20) + 10;
ll f[M];
void solve()
{
vector<ll> p;
ll qq = 1;
for(int i = 0; i < 22; i++)
{
p.push_back(qq);
qq *= 2;
}
int n, m, q;
cin >> n >> m >> q;
ll res = 0;
unordered_map<int, int> mp;
int idx = 1;
for(int i = 0; i < q; i++)
{
int x, day;
cin >> x;
day = x - idx;
idx = x + 1;
if(day <= 0 && i != q - 1) continue;
if(!mp.count(day))
mp[day] = 1;
else mp[day]++;
if(i == q - 1)
{
if(!mp.count(n - x))
mp[n-x] = 1;
else
mp[n-x]++;
}
}
vector<ll> v, w;
for(int i = 0; i < m; i++)
{
ll a, b;
cin >> a >> b;
w.push_back(b);
v.push_back(p[a]);
}
for(auto p : mp)
{
int V = p.x;
memset(f, 0, sizeof f);
for(int i = 0; i < m; i++)
for(int j = v[i]; j <= V; j++) // 完全背包正着枚举
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
res += f[V] * p.y;
}
cout << res;
return;
}