赛时差点改出了 F,遂写比赛记录纪念。
delete .
ABC 的 T1 一般都直接看完样例就莽的,比如这个就一眼是将字符串中的 .
删去然后输出其他的。
Review record.
B. 3^A
发现 \(M\) 范围很小,可以直接处理出值域内所有三的不同次幂,然后从大的开始减即可。
因为把 \(5\times 10^5\) 当成 \(5\times 10^4\) 然后范围算小了怒吃一发罚时。
Review record.
C. Count ABC Again
单点修改数子串,暴力维护即可。开始先找出来每个串并标记,修改后再判一下就行。
因为判掉标记后没有再搜一次标记然后怒吃一发罚时。
Review record.
D. Buildings
这次的 D 居然不是浪费生命的小模拟。
发现正着很难实现正确复杂度,因为每次的起始高度不同会导致答案不同,硬性修改复杂度就到 \(\mathcal{O(n^2)}\) 了。于是倒着考虑,开始想的是维护一个单调不上升子序列,后来 5k 说假了。然后发现这是一个裸的单调栈,维护一个递减的单调栈,插入元素前栈的大小就是答案。
Review record.
E. K-th Largest Connected Components
一眼启发式合并。看到要求有序想到平衡树了,但一不想打二不太会打于是想别的。然后突然想到之前启发式合并好多就用 set 碾过去了,然后就尝试了一下,学了两个新函数:
- 合并两个 set 容器:
st[1].insert(st[2].begin(),st[2].end())
- 取出第 k 个元素(升序):
set<int>::iterator it;
it=st[1].begin();
advance(it,k);
然后并查集稍微维护一下,就 TLE 了,怒吃一发罚时。
5k 提醒 \(k\le 10\),即每个容器维护前十大的元素即可,多了就删点,然后就过了。
Review record.
F. Teleporting Takahashi 2
有点诈骗感的题。
发现 \(m\le 50\),而和这 \(m\) 条边无关的其他点只有一条路能走,这意味着到这些点时只有一种选择,那么我们完全可以将这些点合并到其他有价值的点上去,这样缩完图之后最多只有 \(101\) 个点,范围很小,思路就容易出了。
方案这类问题一般采取 dp 的办法。设 \(f_{i,j}\) 表示在点 \(i\) 花费为 \(j\) 的方案数,外层枚举花费,内层枚举缩完后的每个点,根据连边情况转移,状态转移方程为:
\[f_{v,i}+=f_{j,i-w}\ \ \ (i\ge w) \]
其中 \(v\) 为与 \(j\) 连接的边的终点,\(w\) 为边权。
发现最后有可能停在被合并的点上,于是我们记录每条有缩点的边的边权,最后特殊处理一下即可。
然后是细节处理。
缩点上,考虑记录每条边的出度入度,都为 \(0\) 的就合并掉,遇到其他的点就遇上一个缩完的点连边,记得连最后一个点和起点 \(1\) 的那条边!
dp 边界 \(f_{1,0}=1\),比较易得,其他就是取模问题等小事了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=2e5+5,NN=105;
const int mod=998244353;
int n,m,k,tot=1;// 缩后图中点个数
int ds[N],rpre[N],ff[NN];
// 每点度数 映射:原点->缩后点 缩点边权
ll f[NN][N],ans;
struct edge{int u,v;}e[55];
int hh[NN],ne[NN<<1],to[NN<<1],w[NN<<1],cnt;
namespace Wisadel
{
void Wadd(int u,int v,int va)
{
to[++cnt]=v;
w[cnt]=va;
ne[cnt]=hh[u];
hh[u]=cnt;
}
short main()
{
memset(hh,-1,sizeof hh);
n=qr,m=qr,k=qr;
for(int i(1);i<=m;i++) e[i].u=qr,e[i].v=qr,ds[e[i].u]++,ds[e[i].v]++;
rpre[1]=1;
int ddd=1,las=1;
for(int i(2);i<=n;i++)
{
if(!ds[i]) ddd++;// 没用的点使边权++
else rpre[i]=++tot,ff[las]=ddd,Wadd(las,tot,ddd),las=tot,ddd=1;
// 记录有关变量 连边
}
Wadd(las,1,ddd),ff[las]=ddd;
// 处理最后一个点和边
for(int i(1);i<=m;i++)
{
int u=rpre[e[i].u],v=rpre[e[i].v];
Wadd(u,v,1);
}
f[1][0]=1;
for(int i(1);i<=k;i++) for(int j(1);j<=tot;j++)
{// dp
for(int ee=hh[j];ee!=-1;ee=ne[ee])
{
int v=to[ee],va=w[ee];
if(i>=va)
f[v][i]=(f[v][i]+f[j][i-va])%mod;
}
}
for(int i(1);i<=tot;i++)
{
ans=(ans+f[i][k])%mod;
for(int j=1;j<=ff[i]-1;j++) ans=(ans+f[i][k-j])%mod;
// 计算没到缩点的情况的答案
}
printf("%lld\n",ans);
return Ratio;
}
}
signed main(){return Wisadel::main();}
Review record.
末
感觉打的还可以,5k 的鼓舞起了大作用。
再有 20min 可能就改出 F 了,改出 F 可能就上青了,上青了就去打 ARC 没空写这些了。那就是实力还不够吧,再沉淀沉淀,总会有结果的。
集训快乐。
完结撒花~
没有回复内容