上海月赛 24 年 12 月丙组
你画我猜
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
if (6 <= n && n <= 8)
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
最长连签
算两次最长连续非零子串。
基础做法就是记录当前连续长度和答案,遇到非零就加一,遇到零就说明上一段结束了。
#include <bits/stdc++.h>
using namespace std;
int T;
int n, x;
int main()
{
cin >> T;
while (T--)
{
cin >> n;
int nowA, ansA, nowB, ansB;
nowA = ansA = 0;
for (int i = 1; i <= n; i++)
{
cin >> x;
if (x)
nowA++;
else
{
ansA = max(ansA, nowA);
nowA = 0;
}
}
ansA = max(ansA, nowA);
nowB = ansB = 0;
for (int i = 1; i <= n; i++)
{
cin >> x;
if (x)
nowB++;
else
{
ansB = max(ansB, nowB);
nowB = 0;
}
}
ansB = max(ansB, nowB);
if (ansA > ansB)
cout << "Bob\n";
else if (ansB > ansA)
cout << "Bella\n";
else
cout << "Draw\n";
}
return 0;
}
充电问题
这题读题容易读错导致觉得是很难的题。如果每个插座充完一辆车能继续下一辆的话,就会相对麻烦很多。但作为丙组第三题不可能那么难,所以仔细读题后会注意到只能配对一次。
所以直接贪心充的快的充容量大的就好了。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int T;
int n, m, h;
int a[MAXN + 5];
int b[MAXN + 5];
bool cmp(int x, int y)
{
return x > y;
}
int main()
{
cin >> T;
while (T--)
{
cin >> n >> m >> h;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
cin >> b[i];
sort(a + 1, a + n + 1, cmp);
sort(b + 1, b + m + 1, cmp);
int ans = 0;
for (int i = 1; i <= min(n, m); i++)
{
ans += min(a[i], b[i] * h);
}
cout << ans << "\n";
}
return 0;
}
找子序列
因为希望按位与运算后为 a[i] & m != a[i]
的 a[i]
都是不能选的,只要选了一个最后的与运算和就肯定得不到
那满足条件的
#include <bits/stdc++.h>
using namespace std;
int T, n, m, ai;
int main()
{
cin >> T;
while (T--)
{
cin >> n >> m;
int sum = -1;
for (int i = 1; i <= n; i++)
{
cin >> ai;
if ((ai & m) == m)
sum = sum & ai;
}
if (sum == m)
cout << "Yes\n";
else
cout << "No\n";
}
return 0;
}
查找 404
简化版问题的做法
如果没有 *
那其实很简单,是一个经典的数数题。一般常见的思路是看结尾或者看中间的位置。如果看结尾,那遇到
cnt4[i] = cnt4[i - 1];
cnt40[i] = cnt40[i - 1];
cnt404[i] = cnt404[i - 1];
if (s[i] == '4')
{
cnt4[i] ++;
cnt404[i] += cnt40[i];
}
else
cnt40[i] += cnt4[i];
当然也可以枚举中间的
本题思路
和上面简化版题目的做法类似,无非是当前会出现
实际上完全可以用和前面类似的方法。
如果在
我的写法是在中间位置数,我觉得更清晰。每次遇到
其实 pre0[] nxt0[]
没必要算,但随手保留了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1'000'000'000 + 7;
const int MAXN = 100000;
int T, n, cntStarAll, cntStar;
string s;
int two[MAXN + 5];
// pre4[i]: s[1]~s[i] 有几个 '4'
// nxt4[i]: s[i]~s[n] 有几个 '4'
int pre4[MAXN + 5], nxt4[MAXN + 5];
int pre0[MAXN + 5], nxt0[MAXN + 5];
int pre_[MAXN + 5], nxt_[MAXN + 5];
signed main()
{
two[0] = 1;
for (int i = 1; i <= 100000; i++)
two[i] = two[i - 1] * 2 % MOD;
cin >> T;
while (T--)
{
cin >> n;
cin >> s;
s = "^" + s;
//---- init ----
cntStarAll = 0;
for (int i = 1; i <= n; i++)
if (s[i] == '*')
cntStarAll++;
pre4[0] = pre0[0] = pre_[0] = 0;
for (int i = 1; i <= n; i++)
{
pre4[i] = pre4[i - 1] + (s[i] == '4');
pre0[i] = pre0[i - 1] + (s[i] == '0');
pre_[i] = pre_[i - 1] + (s[i] == '*');
}
nxt4[n + 1] = nxt0[n + 1] = nxt_[n + 1] = 0;
for (int i = n; i >= 1; i--)
{
nxt4[i] = nxt4[i + 1] + (s[i] == '4');
nxt0[i] = nxt0[i + 1] + (s[i] == '0');
nxt_[i] = nxt_[i + 1] + (s[i] == '*');
}
//---- work ----
int ans = 0;
for (int i = 2; i <= n - 1; i++)
{
if (s[i] == '4')
continue;
if (s[i] == '0')
cntStar = cntStarAll;
if (s[i] == '*')
cntStar = cntStarAll - 1;
if (s[i] == '0' || s[i] == '*')
{
// 404
ans += pre4[i - 1] * nxt4[i + 1] % MOD * two[cntStar] % MOD;
ans %= MOD;
// *04 or 40*
if (cntStar == 0)
continue;
ans += pre_[i - 1] * nxt4[i + 1] % MOD * two[cntStar - 1] % MOD;
ans %= MOD;
ans += pre4[i - 1] * nxt_[i + 1] % MOD * two[cntStar - 1] % MOD;
ans %= MOD;
// *0*
if (cntStar == 1)
continue;
ans += pre_[i - 1] * nxt_[i + 1] % MOD * two[cntStar - 2] % MOD;
ans %= MOD;
}
}
cout << ans << "\n";
}
return 0;
}