前言
2023 年的第一篇考试总结……
赛时得分情况：
| A | B | C | D | E | F | G | \(\texttt{Total}\) | \(\texttt{Rank}\) |
|---|---|---|---|---|---|---|---|---|
| \(40\) | \(80\) | \(0\) | \(0\) | \(100\) | \(100\) | \(0\) | \(320\) | \(6\) |
考试总结完善情况
| A | B | C | D | E | F | G | \(\texttt{All}\) |
|---|---|---|---|---|---|---|---|
| √ | √ | √ | 没有题解 | √ | √ |
A. P1731 [NOI1999] 生日蛋糕
题面
你需要制作一个体积为 \(\pi N\) 的，\(M\) 层的，每层都是圆柱体的蛋糕。要求蛋糕从下至上的底面半径和高单调递减。
你需要求出满足以上条件的蛋糕中外表面积（就是每个蛋糕的侧面积与最上面的蛋糕的底面积的和）最小的方案。输出这个方案的蛋糕的外表面积除以 \(\pi\) 的值。如果无解请输出 \(0\)。
\(1 \leq N \leq 2 \times 10^4,1 \leq M \leq 15\)
题解
做法 1：我会暴搜！自下而上搜索，期望得分：\(0\sim20\operatorname{pts}\)。
做法 2：我会剪枝！预处理 \(L_i = \sum_{j=1}^{i}j^3\)。就是从上到下前 \(j\) 个蛋糕的最小体积和。然后如果当前体积 \(V\) 满足 \(V+L_{d}\gt n\)（\(d\) 为剩余层数），那么就可以减掉。枚举一层的高 \(H\) 时下界也可以改为 \(\dfrac{n-V-L_{d}}{R^2}\)（\(R\) 为枚举的半径）。结合上面的做法，期望得分 \(40\sim50\operatorname{pts}\)。
做法 3：我会剪枝！如体积减了枝 表面积也可以！
设第 \(i\) 层蛋糕的侧面积为 \(S_i\)。余下的为 \(F_i\)。
\[\begin{aligned}
&2V_i = \sum_{j=i+1}^{M}{R_{j}^2H_{j}}\\
&=\sum_{j=i+1}^{M}{R_{i+1}S_{i+1}}\\
&\leq R_{i+1}\sum_{j=i+1}^{M}{S_j}\\
&=R_{i+1}+F_i
\end{aligned}
\]
所以就可以推出来了。（如果直接预处理可以得到 \(70\) 分）。
\(s+2(n-v)\div r\) 要大于等于目前的答案。
结合上面的做法，期望得分 \(70\sim100\operatorname{pts}\)。
注意倒序枚举 \(H,R\) 比正序快，原因待查。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
const int N = 2e4+5;
int lmin[N];
int result=INT_MAX;
void dfs(int v,int s,int dep,int r,int h){
// v:已用体积 s:已用表面积 dep:剩余层数 r:上一个蛋糕的半径 h:上一个蛋糕的高
// 自下而上搜索
if(dep==0){
if(v==n) result=min(result, s);
return;
}
if(v+lmin[dep-1]>n) return;
if(2*(n-v)/r+s>=result) return;
for(int R=r-1;R>=dep;R--){
if(dep==m) s=R*R;
for(int H=min((n-v-lmin[dep-1])/(R*R),h-1);H>=dep;H--){
// 剪枝：H的上界其实是 (期望体积-已用体积-剩余的最大体积)/底面积
dfs(v+R*R*H,s+H*(R<<1),dep-1,R,H);
}
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
lmin[i]=i*i*i+lmin[i-1];// lmin[i]:前 i 层的最大体积。
}
dfs(0,0,m,n+1,n+1);
if(result >= INT_MAX) result=0;
cout<<result;
return 0;
}
B. P1463 [POI2001][HAOI2007] 反素数
题面
定义：如果一个数 \(k\) 是反质数(Antiprime)，当且仅当 \(\forall n(1 \leq n \lt k),g(k)\gt g(n)\)。其中 \(g(x)\) 为 \(x\) 的正因子个数。特别地，\(1\) 是反质数。
现在给定一个数 \(N\)。输出不超过 \(N\) 的最大的反质数。
\(1 \leq n \leq 2 \times 10^9\)。
题解
我会打表！以 \(O(n\sqrt{n})\) 的朴素暴力打表为例。大约 \(1\) 小时可以获得 \(80\) 分。大约 \(3\) 小时可以获得 \(100\) 分。
我会正解！
定理：对于一个反质数 \(p\)，当且仅当 \(p=P_1^{e_1}P_2^{e_2}\cdots P_{k}^{e_k}\)。满足 \(P_1,P_2,\cdots P_k\) 依次为前 \(k\) 个质数，且 \(e_1\sim e_k\) 单调不增。
\(\mathcal{Proof}\)：若 \(p\) 是一个不满足上命题的反质数，则将 \(e\) 从大到小排序后，一定存在另一个反质数 \(q=2^{e_1}3^{e_2}5^{e_3}\cdots\)。且 \(p>q,g(p)=g(q)\)，违背反质数定义，因此 \(p\) 一定不是反质数。原命题得证。
因为 \(2\times3\times5\times7\times11\times13\times17\times19\times21\times23\times29\times31=4211770292730\gt2\times10^9\)。所以最多只需要取 \(k=11\)。
又因为 \(2^{31}=2147483648>2\times10^9\)，所以 \(e\) 最大只需要取 \(31\)。
然后我们考虑暴搜即可。实际上不用加剪枝跑得飞快。
代码
#include <bits/stdc++.h>
using namespace std;
vector<int> prime={0,2,3,5,7,11,13,17,19,21,23,29,31};
int n,maxg,maxv;
void dfs(long long v,int g,int pri,int exp){
if((maxv>v&&maxg==g)||g>maxg){
maxg=g,maxv=v;
}
for(int j=1;j<=exp;j++){
v*=prime[pri];
if(v>n) break;
dfs(v,g*(j+1),pri+1,j);
}
}
signed main(){
cin>>n;
dfs(1,1,1,31);
cout<<maxv;
return 0;
}
C. P1985 [USACO07OPEN]翻转棋 Fliptile S
题面
给出一个 \(M\times N\) 的 \(01\) 矩阵。你可以进行任意次的操作。
每次操作你可以选择一个元素 \((i,j)\)。将其本身和与之相邻的元素取反。
你的目标是将这个矩阵变成全 \(0\) 矩阵。如果无法实现，输出
IMPOSSIBLE，否则输出一个矩阵，表示每个元素被取反的次数。可能有多种方案，这时输出字典序最小的那个。\(1 \leq N,M \leq 15\)
题解
以下“取反”会写成“翻转”。
先说结论：第 \(i+1\) 行的翻转方案，取决于第 \(i\) 行的翻转方案。
证明：显然。
于是我们可以枚举第一行翻转哪些元素（这个我们可以用二进制枚举子集的方法，这样子的优点是自然满足字典序从小到大遍历）。然后遍历矩阵，如果上一行同一列的元素是 \(1\)，那么就翻转这个元素。
然后发现前 \(M-1\) 行都会是 \(0\)。只需要看看最后的一行是不是全是 \(0\) 即可。
时间复杂度 \(O(2^N\cdot NM)\)。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[20][20];
int d[20];
int reving[20][20],nowret[20][20],ans[20][20],result;
vector<pair<int,int> > deltas = {{1,0},{0,1},{-1,0},{0,-1}};
void doit(int i,int j){
nowret[i][j]++;
reving[i][j]=reving[i][j]==1?0:1;
for(auto delta : deltas){
int x=i+delta.first,y=j+delta.second;
if(x<1||x>n||y<1||y>m) continue;
reving[x][y]=reving[x][y]==1?0:1;
}
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
result = 1e9;
for(int I=0;I<(1<<m);I++){
memset(nowret,0,sizeof(nowret));
memcpy(reving,a,sizeof(a));
bool flag=1;
for(int j=0;j<m;j++){
if((I>>j)&1) doit(1,j+1);
}
for(int i=2;i<=n;i++){
for(int j=1;j<=m;j++){
if(reving[i-1][j]) doit(i,j);
}
}
for(int i=1;i<=m&&flag;i++){
if(reving[n][i]) flag=0;
}
if(!flag) continue;
int ss = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ss+=nowret[i][j];
}
}
if(ss<result){
result=ss;
memcpy(ans,nowret,sizeof(ans));
}
}
if(result >= (n*m+1)){
cout<<"IMPOSSIBLE";
}
else{
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<ans[i][j]<<' ';
}
cout<<'\n';
}
}
return 0;
}
D. P2329 [SCOI2005]栅栏
题面
农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要 \(n\) 特定规格的木材。于是农夫约翰到木材店购买木材。可是木材店老板说他这里只剩下 \(m\) 个大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为 \(10\) 的木板可以切成长度为 \(8\) 和 \(2\) 的两个木板。
你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木材的规格，求约翰最多能够得到多少他所需要的木板。
\(1 \leq m \leq 50,1 \leq n \leq 10^3\)
题解
首先如果要拿到更多的木材，一定要从小的开始拿，于是可以对需求排序。
其次如果可以拿多必定可以拿少，所以答案具备可二分性。于是二分数量，判定函数考虑搜索，但暴力搜索一定会爆炸，我们考虑剪枝：
预处理前缀和，如果剩余木材不够需要，就可行性剪枝。
需求排序后重复的在一起，我们可以考虑如果和前一个一样就没必要再计算了。
这样就可以排在最优解第 \(8\) 位了。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[55],b[1005],sum[1005],asum,mid;
int nouse;
bool dfs(int want,int pos){
if(sum[mid]+nouse>asum) return 0;
if(want==0) return 1;
bool f=0;
for(int i=pos;i<=n;i++){
if(a[i]>=b[want]){
a[i]-=b[want];
if(a[i]<b[1]) nouse+=a[i];
if(b[want-1] == b[want]){
f=dfs(want-1,i);
}
else f=dfs(want-1,1);
if(a[i]<b[1]) nouse-=a[i];
a[i]+=b[want];
if(f) return 1;
}
}
return false;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
asum+=a[i];
}
cin>>m;
for(int i=1;i<=m;i++) cin>>b[i];
sort(b+1,b+m+1);
for(int i=1;i<=m;i++) sum[i]=sum[i-1]+b[i];
while(sum[m]>asum&&m) m--;
int l=0,r=m;
while(l<=r){
mid=(l+r)>>1;
if(dfs(mid,1)) l=mid+1;
else r=mid-1;
}
cout<<l-1;
}
E. P1514 [NOIP2010 提高组] 引水入城
题面
给出一个 \(N\times M\) 的矩阵 \(h\)。每个矩阵元素可以是蓄水厂或输水管。蓄水厂的坐标必须为 \((1,)\)。输水管可以是任意的，但同一个元素不能同时作为蓄水厂或输水管。但可以既不是蓄水厂也不是输水管。
水从蓄水厂出发，若 \(h_{a,b}\lt h_{c,d}\) 则水可以从 \((c,d)\) 流到 \((a,b)\)。
你需要求出 位于 \((N,)\) 的所有节点是否有水流过。如果有输出 \(1\)，并输出最少需要多少个蓄水厂。如果没有输出 \(0\)，并输出最少有多少个位于 \((N,)\) 的节点没有水流过。
\(1 \leq N,M \leq 500,1 \leq h_{i,j} \leq 10^6\)
题解
首先每一个蓄水厂覆盖的一定是底层的一个区间。于是我们可以使用记忆化搜索搞出来每一个节点 \((i,j)\) 如果作为蓄水厂，所覆盖的底层区间 \([l(i,j),r(i,j)]\)。递推公式如下：
\[\begin{aligned}
&l(i,j)=\begin{cases}
&j&(i=n)\\
&\min\limits_{(i,j) \operatorname{Can\ go\ to}(a,b)} l(a,b)
\end{cases}\\
&r(i,j)=\begin{cases}
&j&(i=n)\\
&\max\limits_{(i,j) \operatorname{Can\ go\ to}(a,b)} r(a,b)
\end{cases}
\end{aligned}
\]
然后遍历 \((N,)\) 看看是否都遍历到了，如果有没有遍历到的那么就是无解。输出没有遍历到的数量。
否则就是一个线段完美覆盖问题，贪心解决即可。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int h[505][505],l[505][505],r[505][505],vis[505][505];
vector<pair<int,int> > deltas = {{1,0},{0,1},{-1,0},{0,-1}};
void dp(int i,int j){
if(vis[i][j]) return;
vis[i][j]=1;
for(pair<int,int> delta : deltas){
int ni=i+delta.first,nj=j+delta.second;
if((ni<1||ni>n||nj<1||nj>m)||(!(h[i][j]>h[ni][nj]))){
continue;
}
dp(ni,nj);
l[i][j]=min(l[i][j],l[ni][nj]);
r[i][j]=max(r[i][j],r[ni][nj]);
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
memset(l,0x7f,sizeof(l));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>h[i][j];
if(i==n){
l[i][j]=j;r[i][j]=j;
}
}
}
for(int i=1;i<=m;i++){
if(!vis[1][i]) dp(1,i);
}
int nowater = 0;
for(int i=1;i<=m;i++){
if(!vis[n][i]) nowater++;
}
if(nowater) cout<<0<<'\n'<<nowater;
else{
cout<<1<<'\n';
int cursor=1;
int tot=0;
while(cursor<=m){
int ans=0;
for(int i=1;i<=m;i++){
if(l[1][i]<=cursor){
ans=max(ans,r[1][i]);
}
}
cursor=ans+1;
tot++;
}
cout<<tot;
}
return 0;
}
F. CF888E Maximum Subsequence
题面
给出一个长度为 \(n\) 的序列 \(a\)，输出在模 \(M\) 意义下最大的子序列和。
\(1 \leq n \leq 35,1 \leq M,a_i \leq 10^9\)
题解
我会骗分!输出 \(M-1\) 可以获得 \(75\) 分的好成绩。
我会折半搜索(Meet in Middle)!可以获得 \(100\) 分。
我们考虑先将序列 \(a\) 的所有元素模 \(M\)。然后对半暴力搜索。然后考虑如何合并答案。
先对左边（左右随意）的所有答案 \(L\) 排序，然后枚举右边的所有答案 \(R\)。假设枚举到 \(R_i\)。先用 lower_bound 二分出不大于 \(M-1-R_i\) 的值的位置 \(p\)。如果这个值正好等于我们要二分的数。那么直接输出 \(M-1\)。否则带给这个数的最大和一定是 \(L_{p-1}\) 或 \(\max L\)。（因为 \(0\leq L_i,R_i\lt M\)，所以 \(\max L\) 是 \(\geq p\) 中最好的，\(p-1\) 是 \(\lt p\) 中最好的）。
时间复杂度 \(O(n\cdot 2^{n\div2})\)。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,ansl,ansr;
int a[1000005],lans[1000005],rans[1000005],lansc,ransc;
int m;
void dfsl(int dep,int sum){
if(dep>(n>>1)){
lans[++lansc]=sum;
return;
}
dfsl(dep+1,sum);
dfsl(dep+1,(sum+a[dep])%m);
}
void dfsr(int dep,int sum){
if(dep>n){
rans[++ransc]=sum;
return;
}
dfsr(dep+1,sum);
dfsr(dep+1,(sum+a[dep])%m);
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]%=m;
}
if(n&1) n++;
dfsl(1,0);
dfsr((n>>1)+1,0);
sort(lans+1,lans+lansc+1);
int ans=*max_element(a+1,a+n+1);
for(int i=1;i<=ransc;i++){
int v=rans[i];
int x = lower_bound(lans+1,lans+lansc+1,m-1-v)-lans;
if(x==lansc+1){
ans=max(ans, (v+lans[lansc])%m);
}
else if(lans[x] == (m-1-v)){
cout<<(m-1)<<'\n';
return 0;
}
else{
int leftnear=0,maxv=lans[lansc];
if(x!=1) leftnear = lans[x-1];
ans=max(ans,max((v+leftnear)%m, (v+maxv)%m));
}
}
cout<<ans<<'\n';
return 0;
}
/*
now=7 m=15
10 11 12 13 14
*/
G. P3230 [HNOI2013]比赛
题面
有 \(N\) 支球队，每支球队按照 \(3-1-0\) 积分制进行比赛。已知每个球队的最后得分，输出有多少个不同的比赛方案。答案可能很大，你只需要对 \(10^9+7\) 取模即可。
\(3 \leq N \leq 100\)，保证数据有解。
