A - The Two Routes
由题可得，1 到 n 的这条边要么是公路，要么是铁路，也就是说要么公交车直达，要么火车直达。如果是公路的话，铁路的最短路就是答案；如果是铁路的话，公路的最短路就是答案。
Code by ZXyang
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(),(x).end()
#define lowbit(x) x&-x
#define pb push_back
#define ls (id<<1)
#define rs (id<<1|1)
typedef long long ll;
typedef pair<ll,ll> pii;
typedef double db;
const int MAXN=3e6+10,MAXM=2e6+10;
const int INF=INT_MAX,SINF=0x3f3f3f3f;
const ll llINF=LLONG_MAX;
const int MOD=1e9+7,mod=998244353;
const int inv2=5e8+4;
struct Dijkstra_with_pile
{
int head[MAXN],to[MAXM],_next[MAXM],ecnt=0;
ll val[MAXM];
void init(int n=MAXN)
{
memset(head,0,n*sizeof(ll));
ecnt=0;
}
void add_Edge(int u,int v,ll w)
{
_next[++ecnt]=head[u];
to[ecnt]=v;
val[ecnt]=w;
head[u]=ecnt;
}
ll dis[MAXN];
priority_queue<pii,vector<pii>,greater<pii> >pq;
void dijkstra(int s)
{
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
while(!pq.empty())pq.pop();
pq.push({0,s});
while(!pq.empty())
{
int u=pq.top().second;
pq.pop();
for(int i=head[u];i;i=_next[i])
{
int v=to[i];
if(dis[v]>dis[u]+val[i])
{
dis[v]=dis[u]+val[i];
pq.push({dis[v],v});
}
}
}
}
}G;
int g[405][405],n,m;
int main()
{
scanf(
for(int i=1;i<=m;i++)
{
int u,v;
scanf(
g[u][v]=g[v][u]=1;
}
if(g[1][n])
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]^=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(g[i][j])G.add_Edge(i,j,1);
G.dijkstra(1);
if(G.dis[n]>INF)return puts("-1"),0;
cout<<G.dis[n];
return 0;
}
B - Lipshitz Sequence
不难发现 $\lceil\frac{|h_j-h_i|}{j-i}\rceil$ 取最大的一个必要条件就是 $|i-j|=1$，即相邻。这个画画图实际上就很显然了。
然后，这题要求所有的子区间的 $L(h)$，我们可以发现，对于一个最大的 $L(h)$，它可以影响一部分区间。我们先对 $h_i$ 做差分，然后实际上就是要找当前这个差分值所影响的区间。这个可以用单调栈来预处理，然后查询就很简单了。
Code by Vingying
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100050;
int n,q;
ll h[N],c[N];
int s[N],top;
ll L[N],R[N];
void gao()
{
for(int i=2;i<=n+1;++i)
{
while(top&&c[s[top]]<c[i])R[s[top--]]=i-1;
L[i]=s[top]+1;
s[++top]=i;
}
}
void solve()
{
cin>>n>>q;
for(int i=1;i<=n;++i)scanf(
for(int i=1;i<=n;++i)c[i]=abs(h[i]-h[i-1]);
c[n+1]=INT_MAX;
gao();
while(q--)
{
int l,r;
scanf(
ll ans=0;
for(int i=l+1;i<=r;++i)
{
ll LL=max(l*1ll,L[i]-1);
ll RR=min(r*1ll,R[i]);
ans+=c[i]*(i-LL)*(RR-i+1);
}
cout<<ans<<'\n';
}
}
int main()
{
int Test=1;
// cin>>Test;
while(Test--)
{
solve();
}
return 0;
}
C - Kleofáš and the n-thlon
期望dp嘛。设 $dp(i,j)$ 表示一个人打到第 $i$ 场比赛，当前得分为 $j$ 的概率。
对于前面而言，转移的时候我们实际上不需要管每个人的具体得分是多少，而是看这个人得这分数的概率是多少。首先，我们知道 Kleofáš 每一场的分数，那么对于其他人而言，他这一场肯定不能得与 Kleofáš 相同的分数。于是转移方程就出来了：$dp(i,j)=\sum\limits_{k=1}^{k\ne x_i and \min(j,m)}\frac{dp(i-1,j-k)}{(m-1)}$，最后我们只需要求 $\sum\limits_{j=1}^{(\sum{x_i})-1}dp(n,j)$ 就行。
Code by ZXyang
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(),(x).end()
#define lowbit(x) x&-x
#define pb push_back
#define ls (id<<1)
#define rs (id<<1|1)
typedef long long ll;
typedef pair<ll,ll> pii;
typedef double db;
const int MAXN=3e6+10,MAXM=2e6+10;
const int INF=INT_MAX,SINF=0x3f3f3f3f;
const ll llINF=LLONG_MAX;
const int MOD=1e9+7,mod=998244353;
const int inv2=5e8+4;
int n,m,x[MAXN],sum;
long double dp[105][100005];
int main()
{
scanf(
if (m==1) return puts("1"),0;
for(int i=1;i<=n;i++)
{
scanf(
sum+=x[i];
}
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
double tmp=dp[i-1][0]/(m-1);
for(int k=1;k<=i*m;k++)
{
if(k>=x[i])dp[i][k]-=dp[i-1][k-x[i]]/(m-1);
dp[i][k]+=tmp;
tmp+=dp[i-1][k]/(m-1);
if(k>m)tmp-=dp[i-1][k-m]/(m-1);
}
}
db ans=0;
for(int i=1;i<sum;i++)ans+=dp[n][i];
printf(
return 0;
}
D - Acyclic Organic Compounds
据 hrdg 说这就是一个裸的 Trie 树合并......
Code by HeRaNO
#include <bits/stdc++.h>
#define MAXN 300005
using namespace std;
int n,tot,cnt,ans,u,v,a[MAXN],son[MAXN][26],siz[MAXN];
char s[MAXN];
vector <int> g[MAXN];
inline void add(int u,int v)
{
g[u].push_back(v);g[v].push_back(u);
return ;
}
inline int merge(int x,int y)
{
int nxt=s[y]-'a',siz=1;
if (!son[x][nxt]){son[x][nxt]=y;return 0;}
for (int i=0;i<26;i++)
if (son[y][i]) siz+=merge(son[x][nxt],son[y][i]);
return siz;
}
inline void dfs(int x,int fa)
{
siz[x]=1;
for (auto v:g[x])
if (v!=fa)
{
dfs(v,x);
siz[x]+=siz[v]-merge(x,v);
}
if (a[x]+siz[x]>ans)
{
ans=a[x]+siz[x];
cnt=1;
}
else if (a[x]+siz[x]==ans) ++cnt;
return ;
}
int main()
{
scanf(
for (int i=1;i<=n;i++) scanf(
scanf(
for (int i=1;i<n;i++) scanf(
dfs(1,-1);
printf(
return 0;
}
E - A Museum Robbery
来啦来啦，动态维护 0-1 背包题来辣（
这个题第三种操作刚开始愣是没看懂，结果是让求当背包容量为 $1,2,...,k$ 时的最大价值。
来复习一下 0-1 背包吧：设 $dp(i,j)$ 表示当前到第 $i$ 个物品，背包容量为 $j$ 的最大价值。容易写出方程：$dp(i,j)=max(dp(i-1,j),dp(i-1,j-w_i)+v_i)$ ，其中 $w_i$ 是物品体积，$v_i$ 是物品价值。其中 $j$ 要倒序枚举，因为每种物品我们只能选一个。
回到这道题：我们显然不能每次都去求一次 0-1 背包，否则复杂度为 $\mathcal{O}(nkq)$，显然接受不了。
注意到：我们每一次增删物品对哪些询问会有影响呢？对于每一个询问，显然是询问当前有的物品。我们可以预处理出每一个物品在集合内出现的时间（记为 $s_i$）和被删的时间（记为 $e_i$），那么设时间区间为 $[l,r]$，如果一个询问在这个时间范围内，那么显然所询问的就是满足 $s_i\leq l$ 且 $r\leq e_i$ 的物品，因为这些物品在我询问的时候一定都在这个区间内。
所以，我们可以考虑对时间分治：将满足条件的物品拿来跑一次 0-1 背包，得到的答案可能会影响好几个询问，然后对于剩下的物品，就直接划分到左右两个区间依次分治下去就行。复杂度 $\mathcal{O}(nk\log q)$。
然后算答案的时候不要用快速幂......可以先预处理出不同幂的值然后再计算，否则会 t 掉。
话说 C++17 64位 跑得是真的快......不过本身好像比较玄学？
Code by Vingying
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=55050;
const ll p=1e7+19,Q=1e9+7;
int n,k,q,tot,tim=1;
inline ll mi(ll a,ll b){ll ret=1;while(b){if(b&1)ret*=a,re
struct entity
{
ll v,w;
int s,e;
}a[N];
ll dp[35][1050];
int query[100050];
void cdq(int l,int r,int dep,vector<int>vec)
{
if(l>r)return;
for(int i=1;i<=k;++i)dp[dep][i]=dp[dep-1][i];
for(int i=0;i<vec.size();++i)
{
if(a[vec[i]].s>l||a[vec[i]].e<r)continue;
for(int j=k;j;--j)
{
if(a[vec[i]].w>j)continue;
dp[dep][j]=max(dp[dep][j],dp[dep][j-a[vec[i]].w]+a[vec[i]].v);
}
}
if(l==r)
{
ll ans=0;
for(int i=k;i;--i)ans*=p,an
for(int i=1;i<=query[l];++i)printf(
return;
}
vector <int> L,R;
int mid=(l+r)>>1;
for(auto i:vec)
{
if(a[i].s<=l&&a[i].e>=r)continue;
if(a[i].e<=mid)L.push_back(i);
else if(a[i].s>mid)R.push_back(i);
else
{
L.push_back(i);
R.push_back(i);
}
}
cdq(l,mid,dep+1,L);
cdq(mid+1,r,dep+1,R);
}
vector <int> t;
int main()
{
cin>>n>>k;
tot=n;
for(int i=1;i<=n;++i)
{
scanf(
a[i].s=1;
}
cin>>q;
while(q--)
{
int op;scanf(
switch(op)
{
case 1:
{
ll v,w;
scanf(
++tim;++tot;
a[tot].s=tim;
a[tot].v=v;a[tot].w=w;
break;
}
case 2:
{
int id;scanf(
a[id].e=tim;++tim;
break;
}
case 3:
{
query[tim]++;
break;
}
}
}
for(int i=1;i<=tot;++i)
{
t.push_back(i);
if(a[i].e==0)a[i].e=tim;
}
cdq(1,tim,1,t);
return 0;
}
Comments NOTHING