A 数列删除
至少删除 \(m\) 个数，意思就是最多保留 \(n-m\) 个数。
删除的总和最小，意思就是保留的总和最大。
非降子序列问题可以用经典的动态规划来解决。
用 \(f[i][j]\) 表示，当前选的最后一个数是 \(a[i]\)，一共选了 \(j\) 个数，选的数总和最大是多少。
转移就是枚举上一个数 \(a[k]\)，满足 \(k<i\&\&a[k]\leq a[i]\)，\(f[i][j]\) 可以用 \(f[k][j-1]+a[i]\) 转移。
#include<bits/stdc++.h>
using namespace std;
int f[1010][1010];
int a[1010];
int main() {
int n, m, i, j, k, sum = 0, ans = 0;
cin >> n >> m;
for ( i = 1 ; i <= n ; i++)
cin >> a[i], sum += a[i];
for ( i = 1; i <= n; i++ ) {
f[i][1] = a[i];
for (j = 2; j <= n-m; j++)
for (k = 1; k < i; k++)
if (a[k] <= a[i])
f[i][j] = max(f[i][j], f[k][j-1]+a[i]);
for (j = 1; j <= n-m; j++)
ans=max(ans, f[i][j]);
}
cout<<sum-ans;
return 0;
}
B 游戏升级
对应题目数据范围：
\(10pts\)：输出 \(0\) 即可。
\(20pts\)：暴力即可。
\(20pts\)：\(x>A_1\) 时小明无法升级，暴力枚举小于等于 \(A_1\) 的 \(x\)，大于 \(A_1\) 的整体处理。
\(20pts\)：即 \(\lfloor \frac {A_1}x\rfloor=\lfloor \frac {A_2}x\rfloor\)。乱设的部分分，其实是提醒你考虑 \(\lfloor \frac {A_1}x\rfloor\) 的取值种类。
对于 \(100\%\) 的数据：只需要发现 \(\lfloor \frac {A_i}x\rfloor\) 的取值种类只有 \(O(\sqrt{A_i})\) 种。然后这题就没了，可以用类似整除分块的写法求出有多少组这样的取值。复杂度 \(O(T\sqrt{A})\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--) {
int a1, b1, a2, b2, n;
cin >> a1 >> b1 >> a2 >> b2 >> n;
int ans = 0;
for (int l = 1, r, i; l <= a1 + 1; l = r + 1) {
i = a1 / l;
r = i ? a1 / i : 1e9;
int j = i + b1 - b2;
if (j < 0 || j > a2)
continue;
int l2 = a2 / (j + 1) + 1, r2 = j ? a2 / j : 1e9;
// cerr<<"> "<<i<<" "<<j<<" "<<l<<" "<<r<<" "<<l2<<" "<<r2<<endl;
l2 = max(l, l2);
r2 = min(r, r2);
r2 = min(n, r2);
if (l2 <= r2)
ans += r2 - l2 + 1;
}
cout << ans << '\n';
}
}
C 难题
测试点 \(1,2\)
暴力枚举初始的 \(x,y\)，然后不断进行 \(x=x+y,y=x+y\) 判断是否存在某一时刻 \(x=X\)。
测试点 \(3,4\)
只枚举初始 \(x\) 的取值，设 \(y=k\)，然后带入 \(x=x+y,y=x+y\) 的过程中，每个时刻 \(x\) 的值是 \(ak+b\) 的形式，其中 \(a,b\) 是定值，然后就是判断 \(ak+b=X\) 是否有 \(k\in [1,M]\) 的解了。
测试点 \(5,6\)
输出上面的 \(a,b\) 可以发现 \(a=f_i,b=f_{i+1}\)，其中 \(i\) 为奇数。
然后就是求 \(xf_i+yf_{i+1}=N(x\in [0,N],y\in [0,M])\) 的解的个数，因为 \(gcd(f_i,f_{i+1})=1\)，可以用扩欧求一个特解 \(x_0,y_0\)。满足条件的 \(x\equiv x_0~mod~f_{i+1},y\equiv y_0~mod~f_i\)，因此可以找到 \(x\) 最大且满足条件的解 \((x_1,y_1)\)，和 \(x\) 最小且满足条件的解 \((x_2,y_2)\)，于是可以算出当前情况下，解的个数为 \(\frac{x_1-x_2}{f_{i+1}}\)。复杂度为 \(O(nlog^2X)\)。
测试点 \(7-10\)
输出每一组 \(x_0,y_0\)，会发现 \(x_0=-f_{i-1},y_0=f_{i-2}\)。可用归纳法证明：
假设 \(-f_if_{i-1}+f_{i+1}f_{i-2}=1\) 成立，那么
\[-f_{i+1}f_i+f_{i+2}f_{i-1}\\ =-f_{i+1}(f_{i-1}+f_{i-2})+(f_{i+1}+f_i)f_{i-1}\\ =-f_{i+1}f_{i-2}+f_if_{i-1}=-1 \]所以 \(-f_{i+2}f_{i+1}+f_{i+3}f_i=1\)（注意上面枚举的 \(i\) 为奇数），然后就可以优化掉一个 \(log\)。
关于细节
若没开 __\(int128\)，或没判断 \(x=0\)，或只枚举了 \(70\) 个斐波那契数，会 \(WA\)。
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0;
short f = 1;
char c = getchar();
for (; c < '0' || c > '9'; c = getchar())
if (c == '-')
f = -1;
for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= f;
return;
}
#define LL long long
#define ll __int128
const int N = 2e5 + 5;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1, y = 0;
return a;
}
ll t = exgcd(b, a % b, y, x);
y -= a / b * x;
return t;
}
ll get_inv(ll a, ll p) {
ll x = 0, y = 0;
ll t = exgcd(a, p, x, y);
ll ans = x / t % p;
return (ans + p) % p;
}
ll inv[N];
int main() {
int T;
read(T);
ll a = 1, b = 1;
int idx = 0;
while (1) {
if (a > 1e18)
break;
inv[++idx] = get_inv(a, b);
a = a + b;
b = a + b;
}
while (T--) {
ll x, n, m;
read(x), read(n), read(m);
ll a = 1, b = 1;
LL ans = 0;
int idx = 0;
if (x == 0) {
puts("1");
continue;
}
while (1) {
if (a > x)
break;
ll tmp = x % b * inv[++idx] % b;
ll X = tmp, Y = (x - tmp * a) / b;
if (Y > m) {
ll k = (Y - m) / a + ((Y - m) % a != 0);
Y -= k * a, X += k * b;
if (Y + a <= m)
Y += a, X -= b;
}
if (X >= 0 && X <= n && Y >= 0 && Y <= m)
ans += min(Y / a, (n - X) / b) + 1;
a = a + b;
b = a + b;
}
printf("%lld\n", ans);
}
}
D 迷宫逃亡
若知道从安全区 \(i\) 走到安全区 \(j\) 的最短路，并以此为边权连边，容易想到最小生成树，询问时回答路径最大边权。
可以只保留可能出现在最小生成树上的边。注意到如果从 \(x\) 到 \(z\) 的最优路径经过了 \(y\)，那么只要连上 \((x,y),(y,z)\)，不需要连 \((x,z)\)。因此可以跑一个多源 \(bfs\)，计算距离每个湿地最近的是哪个安全区，即每个安全区的管辖范围（是一个连通块）。如果两个连通块不接壤，中间至少间隔一个 \(y\)，连边是不优的。若有接壤就连边。
注意到 \(bfs\) 过程中就可以找到所有接壤的地方，即拓展到一个更新过的位置，且所属安全区不同。这样连出来的边数是 \(O(nm)\) 的，总时间复杂度 \(O((nm+p+q)logp)\)。
#include <algorithm>
#include <cstdio>
#define M 2005
#define N 200005
using namespace std;
char a[M][M];
int R,C,en,d[N],f[N],b[M][M],qx[M*M],qy[M*M],px[M*M],py[M*M],ax[N][20],pre[N][20],head[N];
const int dx[4]={1,0,-1,0},
dy[4]={0,1,0,-1};
struct edge
{
int v,w,nxt;
}e[N*2];
int find(int);
bool mrg(int,int);
void dfs(int,int);
void adde(int,int,int);
pair<int,int> lca(int,int);
int main()
{
int i,k,r,n,q,x,y,u,v,tp,tq,nx,ny;
scanf("%d %d %d %d",&R,&C,&n,&q);
for(i=1;i<=R;++i)scanf("%s",a[i]+1);
for(i=1;i<=n;++i)
{
scanf("%d %d",&x,&y);
f[i]=b[px[i]=x][py[i]=y]=i;
}
tp=n;
for(r=0;tp;++r)
{
tq=0;
for(i=1;i<=tp;++i)
{
x=px[i];y=py[i];
for(k=0;k<4;++k)
if(b[nx=x+dx[k]][ny=y+dy[k]]&&mrg(b[x][y],b[nx][ny]))
adde(b[x][y],b[nx][ny],r*2);
}
for(i=1;i<=tp;++i)
{
x=px[i];y=py[i];
for(k=0;k<4;++k)
if(b[nx=x+dx[k]][ny=y+dy[k]])
{
if(mrg(b[x][y],b[nx][ny]))
adde(b[x][y],b[nx][ny],r*2+1);
}
else if(nx&&nx<=R&&ny&&ny<=C&&a[nx][ny]=='.')
{
b[nx][ny]=b[x][y];
qx[++tq]=nx;qy[tq]=ny;
}
}
for(i=1;i<=tq;++i)
{px[i]=qx[i];py[i]=qy[i];}
tp=tq;
}
for(i=1;i<=n;++i)if(!d[i])dfs(i,0);
while(q--)
{
scanf("%d %d",&u,&v);auto k=lca(u,v);
if(!k.first)puts("-1");
else printf("%d\n",k.second);
}
return 0;
}
void dfs(int u,int fa)
{
int i,v;
d[u]=d[pre[u][0]=fa]+1;
for(i=1;i<=18;++i)
{
pre[u][i]=pre[pre[u][i-1]][i-1];
ax[u][i]=max(ax[u][i-1],ax[pre[u][i-1]][i-1]);
}
for(i=head[u];i;i=e[i].nxt)
if((v=e[i].v)!=fa)
{ax[v][0]=e[i].w;dfs(v,u);}
}
pair<int,int> lca(int u,int v)
{
int i,ans=0;
if(d[u]>d[v])swap(u,v);
for(i=18;i>=0;--i)
if(d[u]<=d[v]-(1<<i))
{ans=max(ans,ax[v][i]);v=pre[v][i];}
if(u==v)return {u,ans};
for(i=18;i>=0;--i)
if(pre[u][i]!=pre[v][i])
{
ans=max(ans,max(ax[u][i],ax[v][i]));
u=pre[u][i];v=pre[v][i];
}
ans=max(ans,max(ax[u][0],ax[v][0]));
return {pre[u][0],ans};
}
int find(int u){return u==f[u]?u:(f[u]=find(f[u]));}
bool mrg(int u,int v){u=find(u);v=find(v);f[v]=u;return u!=v;}
void adde(int u,int v,int w)
{
e[++en].v=v;e[en].w=w;
e[en].nxt=head[u];head[u]=en;
swap(u,v);
e[++en].v=v;e[en].w=w;
e[en].nxt=head[u];head[u]=en;
}
E 点格游戏
容易发现连通分量的形状只可能是环或者链，先讨论链的情况：
这是一条长度为 \(5\) 的链，若先手操作任意一条边，会形如：
此时后手有两种选择：
-
填满整条链，获得等同于链长的分数，然后还要再操作一步，相当于删除一条链，交换先后手。
-
把链填成只剩两个相邻的格子，获得链长 \(-2\) 的分数，后手画两个格子中间的边，接下来先后手不变。
第二种选择图示如下：
环的情况类似，但如果后手想先后手顺序不变，需要让出四个格子。
还有一些特殊情况，例如长度为 \(1/2\) 的链，先手一定会优先从小到大操作这些链，每次操作让后手获得链上的格子，同时交换先后手。
至此流程已经明了：
-
先手选择长度为 \(1/2\) 的链，后手获得链上的格子，同时交换先后手。
-
先手选择一条链/一个环，后手选择交换先后手/先后手不变，获得相应分数。
容易发现先手选的链/环一定是当前链/环中长度最小的，可以设 \(dp_{i,j}\) 表示当前只剩下最大的 \(i\) 条链，\(j\) 个环，此时游戏分数的最大值是多少，可以从 \(dp_{i+1,j}\) 和 \(dp_{i,j+1}\) 转移过来。由于链的两端一定在边界处，最多只有 \(n+m\) 条链，复杂度 \(O(nm(n+m))\)。
#include <bits/stdc++.h>
using namespace std;
const int N=405,inf=1e9;
inline void Max(int &a,int b){if(a<b)a=b;}
inline bool cmp(int x,int y){return x>y;}
int g1[N][N],g2[N][N],n,m,id[N][N],f[N][N];
int sz[N],fa[N];
inline int find_fa(int x){
return x==fa[x]?x:fa[x]=find_fa(fa[x]);
}
bool flag[N];
inline void merge(int x,int y){
x=find_fa(x);y=find_fa(y);
if(x!=y){
fa[y]=x;sz[x]+=sz[y];
flag[x]|=flag[y];
}else{
flag[x]=1;
}
}
char s[N];
int b[N],cnt1,c[N],cnt2;
int main(){
scanf("%d %d",&n,&m);
int tot=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)id[i][j]=++tot,fa[tot]=tot,sz[tot]=1;
for(int i=1;i<=n+1;++i){
scanf("%s",s+1);
for(int j=1;j<=m;++j)g1[i][j]=(s[j]=='1');
}
for(int i=1;i<=n;++i){
scanf("%s",s+1);
for(int j=1;j<=m+1;++j)g2[i][j]=(s[j]=='1');
}
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
if(i<n){
if(!g1[i+1][j])merge(id[i][j],id[i+1][j]);
}
if(j<m){
if(!g2[i][j+1])merge(id[i][j],id[i][j+1]);
}
}
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
if(fa[id[i][j]]!=id[i][j])continue;
if(!g1[i][j]||!g1[i+1][j]||!g2[i][j]||!g2[i][j+1]){
if(flag[id[i][j]])b[++cnt1]=sz[id[i][j]];
else c[++cnt2]=sz[id[i][j]];
}
}
sort(b+1,b+1+cnt1,cmp);sort(c+1,c+1+cnt2,cmp);
for(int i=1;i<=cnt1+cnt2;++i){
for(int j=0,k;j<=cnt2&&j<=i;++j){
k=i-j;
if(k>cnt1)continue;
f[j][k]=-inf;
if(j){
if(c[j]<=2)Max(f[j][k],-f[j-1][k]-c[j]);
else Max(f[j][k],min(-f[j-1][k]-c[j],f[j-1][k]-c[j]+4));
}
if(k)Max(f[j][k],min(-f[j][k-1]-b[k],f[j][k-1]-b[k]+8));
}
}
printf("%d\n",f[cnt2][cnt1]);
return 0;
}```