牛客小白月赛23
A-膜法记录
知识点：贪心+枚举+二进制状态压缩+预处理
题意：一个$n \times m$的01矩阵，行操作可使某一行变为全0，列操作可使某一列变为全0，问能否使用少于a次行操作和少于b次列操作得到全0矩阵。$1\leq n \leq20，1\leq m \leq {10^5}$。
贪心：先使用行操作使得存在非0的列数尽可能的少。
枚举：枚举每一行是否使用行操作，复杂度${2^n}$。对于一种行操作情况$x$，假设消去了$g(x)$列，则还需要$m-g(x)$次列操作。此题的关键就在于如何去枚举以及如何快速求得$g(x)$值。
二进制状态压缩：把每一列从下往上看成一个二进制数，则数的范围在$[0,{2^n-1}]$之间。假设$f(x)$表示值为$x$的列出现了$f(x)$次，则$g(x)=\sum_{i=0}^{x}{f(i)}，\quad i\bigodot x=x$。
总结：此题在赛中完全没思路。一是没注意到数值范围，二是没有想过枚举这方面，总的来说对二进制状态压缩不敏感。
假设一个$4\times6$的矩阵如下所示
| c1 | c2 | c3 | c4 | c5 | c6 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 |
| $f(2)$ | $f(4)$ | $f(5)$ | $f(13)$ | $f(14)$ |
|---|---|---|---|---|
| 1 | 1 | 2 | 1 | 1 |
举例：行操作为13（1101），则上图的第2、3、4、5都被置为全0，$g(13)=f(4)+f(5)=3$。
预处理：
- 初始化$f(x)、g(x)$均为0.
- 先遍历每一列，得到$f(x)$。
- 遍历每一行$i$，如果$x\&(1<<i)=0$，则$g(y)+=f(x)，\quad y=x|(1<<i)$。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e5 + 117;
const int MAXM = 1e5 + 117;
int T;
int n, m, a, b, maxnum;
char s[27][MAXN];
int cnt[1100017];
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d%d%d", &n, &m, &a, &b);
for(int i = 0; i < n; i++) scanf("%s", s[i]);
maxnum = 1 << n;
for(int i = 0; i < maxnum; i++) cnt[i] = 0;
for(int j = 0; j < m; j++) {
int t = 0;
for(int i = 0; i < n; i++) {
if(s[i][j] == '*') t |= (1 << i);
}
cnt[t]++;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < maxnum; j++) {
if((j & (1 << i)) == 0) cnt[j | (1 << i)] += cnt[j];
}
}
bool pr = false;
for(int i = 0; i < maxnum; i++) {
if(__builtin_popcount(i) <= a && m - cnt[i] <= b) {
pr = true;
break;
}
}
if(pr) puts("yes");
else puts("no");
}
return 0;
}B-阶乘
知识点：二分+质因分解
二分：若$n!\%p=0$，则有$(n+1)!\%p=0$，答案具有单调性，可二分。
质因分解：若$n!$中的质因子个数都不小于$p$的质因子个数，则$n!$是$p$的倍数。
总结：赛中想到了二分和质因分解，但是不会阶乘质因分解，遂卒。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e5 + 117;
const int MAXM = 1e5 + 117;
int T;
int p;
int prime[MAXN];
void getPrime(int n) {
memset(prime, 0, sizeof(prime));
for(int i = 2; i <= n; i++) {
if(!prime[i]) prime[++prime[0]] = i;
for(int j = 1; j <= prime[0] && prime[j] <= n / i; j++) {
prime[prime[j]*i] = 1;
if(i % prime[j] == 0) break;
}
}
}
int fatCnt;
int factor[117][2];
void getFactors(int x) {
fatCnt = 0;
int tmp = x;
for(int i = 1; prime[i] <= tmp / prime[i]; i++) {
if(tmp % prime[i] == 0) {
factor[fatCnt][0] = prime[i];
factor[fatCnt][1] = 0;
while(tmp % prime[i] == 0) {
factor[fatCnt][1]++;
tmp /= prime[i];
}
fatCnt++;
}
}
if(tmp != 1) {
factor[fatCnt][0] = tmp;
factor[fatCnt++][1] = 1;
}
}
bool check(int n) {
for(int i = 0; i < fatCnt; i++) {
int cnt = 0, t = n;
while(t) {//阶乘质因分解
cnt += t / factor[i][0];
t /= factor[i][0];
}
if(cnt < factor[i][1]) return false;
}
return true;
}
int erfen() {
int l = 1, r = p;
while(l <= r) {
int mid = (l + r) / 2;
if(check(mid)) r = mid - 1;
else l = mid + 1;
}
return l;
}
int main() {
getPrime(100000);
scanf("%d", &T);
while(T--) {
scanf("%d", &p);
getFactors(p);
printf("%d\n", erfen());
}
return 0;
}C-完全图
知识点：完全图+贪心+二分+__int128
完全图：$n$个点的完全图有$\tbinom{n}{2}$条边，逆向思维：有$n$个孤立的点添加$\tbinom{n}{2}-m$条边得到连通块最少。
贪心：除非必须连接孤立点，否则在连通块内部加边。
二分：完全图的边数随点数单调递增，可二分判断。
__int128：$n$达到$10^{18}$数量级，long long不足以存放（小声吐槽出题人居然py）。
总结：赛中并没有想到逆向思维，所以当时纠结了一下怎么删才能连通块最多。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e5 + 117;
const int MAXM = 1e5 + 117;
int T;
__int128 n, m;
inline __int128 read() {
__int128 x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline void print(__int128 x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9)
print(x / 10);
putchar(x % 10 + '0');
}
void erfen() {
__int128 l = 1, r = n;
while(l <= r) {
__int128 mid = (l + r) / 2;
if(mid * (mid - 1) / 2 >= m) r = mid - 1;
else l = mid + 1;
}
print(n - l + 1);
putchar(10);
}
int main() {
scanf("%d", &T);
while(T--) {
n = read();
m = read();
m = n * (n - 1) / 2 - m;
erfen();
}
return 0;
}D-病毒传染
高能数学题，不会。。。
E-A+B问题
知识点：补码
补码：在计算机系统中，数值一律用补码来表示和存储，在逻辑上，最大值和最小值是紧挨着的，如下图所示，这就会有最大值+1=最小值、最小值-1=最大值。故任给$a、c$均有$b=c-a，min \leq b \leq max$，所以答案一定是4294967296。
总结：想了半小时才琢磨出来，大佬都是秒A，对细节掌握的太菜了。
F-美丽的序列I
暂未领悟
G-树上求和
知识点：贪心+计数
贪心：所有路径中出现次数多的边贪心权值小的颜色。
计数：朴素的做法是枚举所有的路径统计每条边出现的次数，然而复杂度不能被接受。假设边$i$的左边有$l(i)$个点，则边$i$的右边有$n-l(i)$个点，边在所有路径中出现的总次数为$l(i)*(n-l(i))$。只需要一次dfs即可求出所有的$l(i)$。
总结：赛后看自己的代码发现边当成有向边也过了，可能是数据水了也可能是自己对题意把握的不够准确，需警惕无向边的加边。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 2e5 + 117;
int n;
struct Edge {
int to, next;
LL cnt;
} edge[MAXN];
bool vis[MAXN];
int head[MAXN], tot;
void init() {
tot = 0;
memset(head, -1, sizeof(head));
memset(vis, false, sizeof(vis));
}
void addedge(int u, int v) {
edge[tot].to = v;
edge[tot].cnt = 0;
edge[tot].next = head[u];
head[u] = tot++;
}
LL dfs(int id) {
vis[id] = true;
LL ret = 1;
for(int i = head[id]; i != -1; i = edge[i].next) {
if(vis[edge[i].to]) continue;
LL num = dfs(edge[i].to);
edge[i].cnt = num * (n - num);
ret += num;
}
return ret;
}
bool cmp(Edge a, Edge b) {
return a.cnt > b.cnt;
}
int main() {
init();
scanf("%d", &n);
for(int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
dfs(1);
sort(edge, edge + tot, cmp);
LL ans = 0;
for(int i = 1; i < n; i++) ans += i * edge[i - 1].cnt;
printf("%lld\n", ans);
return 0;
}H-奇怪的背包问题增加了
知识点：贪心
贪心：虚假的背包问题，实则是贪心。因为物品的体积全为2的次幂，所以应该优先选体积大的。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 2e5 + 117;
int T, n;
char s[MAXN];
struct node {
int x;
int id;
} a[MAXN];
bool cmp(node a, node b) {
if(a.x != b.x) return a.x > b.x;
return a.id < b.id;
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &a[i].x);
a[i].id = i;
}
sort(a, a + n, cmp);
int sum = 1 << 30, num;
for(int i = 0; i < n; i++) {
num = 1 << a[i].x;
if(sum >= num) sum -= num, s[a[i].id] = '1';
else s[a[i].id] = '0';
}
if(sum) puts("impossible");
else puts(s);
}
return 0;
}I-寻找子串
知识点：后缀+枚举
后缀：假设子串$[i,j]$为字典序最大的子串，则满足$j=n-1$，即字符串的后缀。
枚举：字符串长度不超过1000，$O(n^2)$的枚举都能AC。
总结：string的使用相当不熟练，也是因为平时用的少。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 2e5 + 117;
string s, ans;
int main() {
cin >> s;
while(!s.empty()) {
if(ans < s) ans = s;
s.erase(0, 1);
}
cout << ans << endl;
return 0;
}J-最大的差
小白赛温暖的签到题。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 2e5 + 117;
int n;
int a[MAXN];
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
sort(a, a + n);
printf("%d\n", a[n - 1] - a[0]);
return 0;
}版权属于：小影
本文链接：http://kindkidll.com/index.php/archives/93/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。
