牛客小白月赛80
A 矩阵快速幂签到
A
解题思路
一个抽象题(❌)
就跟提示的一样，写几项就看出来了。$a_i$ = i + 1
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
const ll mod = 998244353;
ll n, m;
int a = 1, b = 2;
void solve()
{
cin >> n;
cout << n + 1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//int t; cin >> t; while (t -- )
solve();
return 0;
}
B 第一次放学
B
题意
n名学生，属于m个班级，放学后，有k名同学冲出了学校，但不知道冲出学校的同学的所在班级。
要求还未出校的学生中，最多有多少学生属于同一个班级。
解题思路
首先假设放学前，人数最多的班级为p班级。那么结果分两种情况：
- 除去p班级，剩下的班级总人数不小于k，那么p班级的人数就是答案
- 除去p班级，剩下的班级总人数小于k，那么p班级就要减去还需要冲出的人数
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int a[N];
int b[N];
int n, m;
void solve()
{
int k;
cin >> n >> m >> k;
int x = 0;
for (int i = 0; i < n; i ++ )
{
cin >> a[i];
b[a[i]] ++ ;
x = a[i];
}
if (m == 1) cout << b[x] - k;
else
{
sort(b + 1, b + m + 1);
if ((n - b[m]) >= k) cout << b[m];
else cout << b[m] - (k - (n - b[m]));
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//int t; cin >> t; while (t -- )
solve();
return 0;
}
C 又放学辣（简单）
C
题意
依旧是有n名同学，属于m个班级。放学后，有k名同学冲出学校。不同的是，现在有一个班在拖堂。
需要求出在剩下没有拖堂的班级中，还留在学校的人数最多的班级的最少可能人数
解题思路
设t为最多班级的最小可能人数。t的取值范围就是0 ~ n
设 j 为拖堂的班级，数组c[i]表示 i 班的人数 也就是需要保证$\sum_{i=1}^m{(c_i - t)}$ (i != j) < k
从小到大枚举t，知道找到最小的合适的 t 的值，就是 t 应取的值
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e2 + 10;
int n, m, k;
int a[N], c[N]; //a存第i个同学在哪个班级，b存第i个班级有多少人
void solve()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
c[a[i]] ++ ;
}
for (int j = 1; j <= m; j ++ )
{
//满足条件：除去拖堂的班级，剩下的班级人数大于k
if (n >= k + c[j])
{
int ans = 1e9;
//枚举t的所有可能取值，t就是所求的“留在学校的人数最多的班级的最少的可能人数”
for (int t = 0; t <= n; t ++ )
{
int sum = 0;
for (int i = 1; i <= m; i ++ )
{
if (i == j) continue;
sum += max(0, c[i] - t);
}
//如果冲出学校的同学小于k，则满足条件；从小到大枚举，直到找到最大的值，就是所求t的值
if (sum <= k) ans=min(ans, t);
}
cout << ans << " ";
}
//不满足条件，输出-1
else cout << -1 << " ";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//int t; cin >> t; while (t -- )
solve();
return 0;
}
D 又放学辣（进阶）
D
题意
题意与C相同，只增大了取值范围
解题思路
N 和 M 的取值在$10^6$以内，而C的做法时间复杂度为O($n^3$)。我们在C题的基础上进行优化。
用两次前缀和来预处理出 t 的所有值，这样 t 的查询的时间复杂度就降到了O(1)
我们希望ge[t] = $\sum_{i=1}^m{(c_i - t)}$。
ge[i] 的 最初含义是从 i+1 减到 i 会 多减去多少
- 比如有两个班级人数是5，那么从5到4，那么之后每一步就需要在原基础上多减2
第一次取前缀和后：ge[i] 的含义变为从 i+1 减到 i 会减去多少
第二次取前缀和后：ge[i] 的含义变为减到 i 总共需要减去多少
之后在二分找到符合条件的 t 的值即可。
- 二分时，需要去掉那个拖堂的班级 sum -= max(0ll, c[j] - mid);
- 附上一张图，便于今后回忆
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m, k;
ll c[N], ge[N]; //ge[i] 的意思是 从 i + 1 减到 i 会多减多少
void solve()
{
cin >> n >> m >> k;
for (int i = 0; i < n; i ++ )
{
int x;
cin >> x;
c[x] ++ ;
}
for (int i = 1; i <= m; i ++ )
{
if (c[i]) ge[c[i] - 1] ++ ;
}
//ge[i]的意思是 从 i + 1 减到 i 会 减去多少
for (int i = n; i >= 0; i -- ) ge[i] += ge[i + 1];
//ge[i]的意思是 减到 i 总共需要减多少
for (int i = n; i >= 0; i -- ) ge[i] += ge[i + 1];
for (int j = 1; j <= m; j ++ )
{
if (n - c[j] >= k)
{
int l = -1, r = n;
while (r - l > 1)
{
int mid = l + r >> 1;
ll sum = ge[mid];
sum -= max(0ll, c[j] - mid);
if (sum <= k) r = mid;
else l = mid;
}
cout << r << " ";
}
else
{
cout << -1 << " ";
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//int t; cin >> t; while (t -- )
solve();
return 0;
}
E 一种因子游戏
E
题意
Alice 和 Bob 打牌，他们各有n张牌。Alice先打出，Bob再打出。
如果Bob打出的牌与Alice的打出的牌不互质（最大公约数为1），则Alice获胜；都没有牌了，则Bob获胜。
解题思路
N的取值范围是500以内。所以可以接受O($n^3$)的时间复杂度。
所以可以用匈牙利算法来求二分图的最大匹配。（虽然做的时候并没有想到111）
只有最大匹配数为 n 时，Bob才会获胜。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> PII;
const int N = 500 + 10;
const int M = N * N;
int n, m;
int a[N], b[N];
int h[M], e[M], ne[M], idx;
int match[N];
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int gcd(int a, int b)
{
if (a < b) return gcd(b, a);
while (b)
{
int t = a % b;
a = b;
b = t;
}
return a;
}
bool find(int u)
{
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (st[j] == false)
{
st[j] = true;
if (match[j] == 0 || find(match[j]))
{
match[j] = u;
return true;
}
}
}
return false;
}
void solve()
{
memset(h, -1, sizeof h);
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ) cin >> b[i];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (gcd(a[i], b[j]) == 1) add(i, j);
int cnt = 0;
for (int i = 1; i <= n; i ++ )
{
memset(st, false, sizeof st);
if (find(i)) cnt ++ ;
}
if (cnt == n) cout << "Bob";
else cout << "Alice";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//int t; cin >> t; while (t -- )
solve();
return 0;
}
