把 \(A,B\) 写完后胡完 \(C\) 就跑路了，感觉很有质量。
S6A. 「KDOI-11」打印
线段树维护区间结束时间最早的打印机，如果全局结束时间最早的打印机的结束时间小于当前文件起始时间，那么线段树二分寻找最小编号，否则直接取结束时间最早打印机即可。
点击查看代码
#include <bits/stdc++.h>
#define fr first
#define se second
#define Un unsigned
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define pLi pair<LL,int>
#define pLL pair<LL,LL>
#define __ __int128
#define LD long double
#define VE vector<LL>
#define DB double
#define Ve vector<int>
using namespace std;
inline int read()
{
int x = 0,f = 1;char ch = getchar();
while(!isdigit(ch)) (ch == '-') && (f = -1),ch = getchar();
while(isdigit(ch)) x = x*10+ch-48,ch = getchar();
return x*f;
}
const int N = 2e5+5;
struct Line{int t,s,id;}L[N];
struct tree{int l,r;pLi mn;}tr[N<<2];
Ve ve[N];
void build(int l,int r,int i)
{
tr[i].l = l,tr[i].r = r;
if (l == r) return (void)(tr[i].mn = {0,l});
int mid = (l+r)>>1;
build(l,mid,i<<1),build(mid+1,r,i<<1|1);
tr[i].mn = min(tr[i<<1].mn,tr[i<<1|1].mn);
}
void M(int p,LL k,int i)
{
if (tr[i].l == tr[i].r) return (void)(tr[i].mn.fr = k);
if (p <= tr[i<<1].r) M(p,k,i<<1);
else M(p,k,i<<1|1);
tr[i].mn = min(tr[i<<1].mn,tr[i<<1|1].mn);
}
inline pii Q(int k,int i)
{
if (tr[i].l == tr[i].r) return tr[i].mn;
if (tr[i<<1].mn.fr < k) return Q(k,i<<1);
return Q(k,i<<1|1);
}
int main()
{
int n = read(),m = read();
for (int i = 1;i <= n;i++) L[i] = {read(),read(),i};
sort(L+1,L+n+1,[](Line a,Line b){return a.s < b.s;});
build(1,m,1);
for (int i = 1;i <= n;i++)
{
if (tr[1].mn.fr < L[i].s)
{
auto [x,y] = Q(L[i].s,1);
ve[y].pb(L[i].id),M(y,L[i].s+L[i].t-1,1);
}
else
{
auto [x,y] = tr[1].mn;
ve[y].pb(L[i].id),M(y,x+L[i].t,1);
}
}
for (int i = 1;i <= m;i++)
{
printf("%d",ve[i].size());
sort(begin(ve[i]),end(ve[i]));
for (auto j : ve[i]) printf(" %d",j);
printf("\n");
}
return 0;
}
S6B. 「KDOI-11」飞船
观察一下 \(t_i\) 是正整数，最小为 \(1\)，直觉地列个式子，设当前速度为 \(v\)，当 \(\frac{10^9}{v}\le \frac{10^9}{4v}+1\) 时再进行加速就只会更劣了，解一下得 \(v\ge\frac{3\times10^9}{4}\)，也就是说 \(v\) 最大就是 \(\frac{3\times10^9}{4}\) 左右。（赛时唐了不等式解错了算成了 \(3\times10^9\)）
速度有了上界那么考虑压入状态。首先 \(x_i=1\) 是没有任何用处的，剩下有用的只有 \(x_i=2,3,4\)，那么设 \(f_{i,a,b,c}\) 代表到达 \(i\) 加油站时乘了 \(a\) 个 \(2\)，\(b\) 个 \(3\)，\(c\) 个 \(4\)，\(a,b,c\) 上界大概分别是 \(30,20,15\)，看起来不太能过的样子，不过很多状态代表的 \(v\) 值其实是不合法的，枚举的时候及时跳出是可以过的。
这时候会发现我们做了一件很傻的事情是把 \(2\) 和 \(4\) 分开记录了，但是 \(4=2^2\) 我们根本没必要分开，于是只需要记 \(f_{i,a,b}\) 这时候就非常可过了，空间不太够用所以要滚动数组优化。
最后说一下如何转移。
\(f_{i,a,b}=f_{i-1,a,b}+\frac{p_i-p_{i-1}}{2^a3^b}\)
\(f_{i,a,b}=\min(f_{i,a,b},f_{i,a-1,b}+t_i)\ \ \ \texttt{if }x_i=2\)
\(f_{i,a,b}=\min(f_{i,a,b},f_{i,a,b-1}+t_i)\ \ \ \texttt{if }x_i=3\)
\(f_{i,a,b}=\min(f_{i,a,b},f_{i,a-2,b}+t_i)\ \ \ \texttt{if }x_i=4\)
由于我们使用了滚动数组来优化空间，所以我们需要把询问离线下来处理。
点击查看代码
#include <bits/stdc++.h>
#define fr first
#define se second
#define Un unsigned
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define pLi pair<LL,int>
#define pLL pair<LL,LL>
#define __ __int128
#define LD long double
#define VE vector<LL>
#define DB double
#define Ve vector<int>
using namespace std;
inline int read()
{
int x = 0,f = 1;char ch = getchar();
while(!isdigit(ch)) (ch == '-') && (f = -1),ch = getchar();
while(isdigit(ch)) x = x*10+ch-48,ch = getchar();
return x*f;
}
const int N = 1e5+5;
int p[N],t[N],x[N],l[33];
LL pw[33][21];
DB f[2][33][21],ans[N];
vector < pii > ve[N];
int main()
{
int n = read(),Q = read();
for (int i = 1;i <= n;i++)
p[i] = read(),t[i] = read(),x[i] = read();
for (int i = 1;i <= Q;i++)
{
int y = read(),pos = lower_bound(p+1,p+n+1,y)-p;
ve[pos].pb({y,i}),ans[i] = 1e15;
}
pw[0][0] = 1;
for (int i = 0;i <= 32;i++)
{
if (i) pw[i][0] = pw[i-1][0]*2;
for (int j = 1;j <= 20;j++)
{
pw[i][j] = pw[i][j-1]*3,l[i] = j;
if (pw[i][j] > 3e9) break;
}
}
for (int i = 0;i <= 32;i++)
for (int j = 0;j <= l[i];j++)
f[0][i][j] = 1e15;
f[0][0][0] = 0;
for (int i = 1;i <= n;i++)
{
bool id = i&1;
for (int j = 0;j <= 32;j++)
for (int k = 0;k <= l[j];k++)
f[id][j][k] = f[!id][j][k]+(p[i]-p[i-1])*1.0/pw[j][k];
for (auto [y,x] : ve[i])
for (int j = 0;j <= 32;j++)
for (int k = 0;k <= l[j];k++)
ans[x] = min(ans[x],f[!id][j][k]+(y-p[i-1])*1.0/pw[j][k]);
for (int j = 32;j >= 0;j--)
{
for (int k = l[j];k >= 0;k--)
{
if (x[i] == 2 && j)
f[id][j][k] = min(f[id][j][k],f[id][j-1][k]+t[i]);
if (x[i] == 3 && k)
f[id][j][k] = min(f[id][j][k],f[id][j][k-1]+t[i]);
if (x[i] == 4 && j > 1)
f[id][j][k] = min(f[id][j][k],f[id][j-2][k]+t[i]);
}
}
}
for (auto [y,x] : ve[n+1])
for (int j = 0;j <= 32;j++)
for (int k = 0;k <= l[j];k++)
ans[x] = min(ans[x],f[n&1][j][k]+(y-p[n])*1.0/pw[j][k]);
for (int i = 1;i <= Q;i++) printf("%.10lf\n",ans[i]);
return 0;
}
S6C. 「KDOI-11」简单的字符串问题 2
赛时少考虑了一些东西，会补的。
标签：ch,int,11.17,long,define,id,getchar From： https://www.cnblogs.com/ZepX-D/p/18550515