2020级训练赛11.01

电报

一、题目

校内OJ 题目描述 给出 $N$ 个点，每个点的出度均为 $1$，给出这 $N$ 个点初始指向的点 $A_i$，和改变这个点指向的目标所需要的价值 $C_i$。 求让所有点强连通的最小花费。 输入格式 第一行输入一个数 $N$ 表示点的个数。 之后的 $N$ 行每行两个数 $A_i$ $C_i$ 表示第 $i$ 个点指向第 $A_i$ 个点，更改该点指向的点花费为 $C_i$。 输出格式 共一行，为让所有点强连通的最小花费。

二、解法

可以发现题目给出的图的形态应该是很多基环树，然后图不一定联通。 我们先考虑把基环树改成环，然后再断开每个环的一条边，然后把环们接起来。 考虑基环树上接上的树怎么把他搞成链，对于每一个分支，我们断开除最大边外的所有边，然后把他们接到链尾（这里我们不需要实际改变图的形态，只需要统计答案）。 发现环上的每个点都有可能连出去若干条链，我们先考虑把链连环的边都拆掉，但我们必须要拆掉一条环边才能让链接上来，我们给每条环边一次复活的机会，消耗$c[x]-gg[a[x]]$（$gg[x]$表示链连环的最大边权），如果消耗$<0$，直接复活，如果一个联通块的消耗都$\ge 0$，那么也要断掉消耗最小的边。 这样我们就有了若干个环，发现在上一个操作中已经断开了至少一个环边，把剩下的环接在一起即可。

#include <cstdio> #include <vector> #include <cstring> #include <queue> using namespace std; const int MAXN = 100005; int read() { int x=0,flag=1;char c; while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1; while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*flag; } int n,tot,flag=1,all,f[MAXN],is[MAXN]; int a[MAXN],c[MAXN],in[MAXN],gg[MAXN]; long long ans; vector<int> cy[MAXN]; struct edge { int v,c,next; }e[MAXN]; int main() { n=read(); for(int i=1;i<=n;i++) { a[i]=read();c[i]=read(); e[++tot]=edge{i,c[i],f[a[i]]},f[a[i]]=tot; in[a[i]]++; } queue<int> q; for(int i=1;i<=n;i++) is[i]=1; for(int i=1;i<=n;i++) if(in[i]==0) { is[i]=0; flag=0; q.push(i); } while(!q.empty()) { int t=q.front(); q.pop(); in[a[t]]--; if(in[a[t]]==0) { is[a[t]]=0; q.push(a[t]); } } for(int i=1;i<=n;i++) { if(is[i]==0) { int Max=0; for(int j=f[i];j;j=e[j].next) { Max=max(Max,e[j].c); ans+=e[j].c; } ans-=Max; } else { for(int j=f[i];j;j=e[j].next) if(is[e[j].v]==0) { gg[i]=max(gg[i],e[j].c); ans+=e[j].c; } int x=i; if(is[x]==1) all++; while(is[x]==1) { cy[all].push_back(x); is[x]=2; x=a[x]; } } } if(all>1 || !flag) { for(int i=1;i<=all;i++) { int Min=0x3f3f3f3f; for(int j=0;j<cy[i].size();j++) { Min=min(Min,c[cy[i][j]]-gg[a[cy[i][j]]]); } if(Min>=0) ans+=Min; for(int j=0;j<cy[i].size();j++) { if(c[cy[i][j]]-gg[a[cy[i][j]]]<0) ans+=c[cy[i][j]]-gg[a[cy[i][j]]]; } } } printf("%lld\n",ans); }

三、总结

做了这么多类似的题，我就简单的总结一下吧： 1、先分析题目给出图的形态（这往往是最重要的）。 2、具体分析，通常要结合贪心，操作时不用实际改变图的形态，只用统计答案。

路由表

一、题目

题目描述 路由表查找是路由器在转发 IP 报文时的重要环节。通常路由表中的表项由目的地址、掩码、下一跳（Next Hop）地址和其他辅助信息组成。例如：

目的地址掩码长度下一跳0.0.0.0/1192.168.1.1128.0.0.0/1192.168.1.18.8.8.0/24192.168.1.18.8.8.8/32192.168.1.253

当路由器收到一个 IP 报文时，会将报文中的目的 IP 地址与路由表中的表项逐条进行比较，选择匹配且最明确的表项，将报文转发给该表项中指定的下一跳。 匹配的过程是将报文中的目的地址和表项中的目的地址分别转为二进制串，再查看表项中的掩码长度，若掩码长度为 $x$，则将两个二进制串的前 $x$ 位进行比较，如果相同则认为匹配。 所谓最明确是指在有多个表项匹配时，掩码长度最大的表项。也可以理解为匹配的二进制位最多的项。 IP 地址转为二进制串的操作是把地址中 $4$ 个整数（一定在 $0$ 到 $255$ 的范围内）分别转为 $8$ 位二进制数，再顺序拼接起来，得到一个 $32$ 位的二进制串。例如，192.168.1.253 转为二进制串后为 11000000 10101000 00000001 11111101。 我们以报文的目的地址为 8.8.8.8 为例，说明其在上述路由表的匹配过程。

8.8.8.800001000 00001000 00001000 000010000.0.0.0/100000000 00000000 00000000 00000000128.0.0.0/110000000 00000000 00000000 000000008.8.8.0/2400001000 00001000 00001000 000000008.8.8.8/3200001000 00001000 00001000 00001000

上表将地址均转为二进制串，并用红色标记出待比较的位（由掩码长度决定）。将红色部分与报文中的目的地址比较，可知 0.0.0.0/1、8.8.8.0/24、8.8.8.8/32 均能够匹配。路由器从中选取掩码长度最长（/32）的表项 8.8.8.8/32，将报文转发给其对应的下一跳地址 192.168.1.253。 在实际的核心路由器中，路由表通常较大（现在互联网的全局路由表已经接近 $60$ 万条记录），并且会随着新接入设备不断扩张。为了分析路由表变化对转发产生的影响，网络工程师想要知道一段时间内某个 IP 地址的路由表项选择发生了多少次变化（变化是指由于最明确匹配等因素选择了不同的表项，不考虑下一跳地址）。

输入格式 第一行为整数 $M$，表示共有 $M$ 次操作。接下来 $M$ 行，每行描述一次操作。操作有两种： A <D>/<L> 其中 $D$ 为一个 IP 地址，$L$ 为整数 $(1\le L\le 32)$。添加一条表项至路由表，其目的地址为 $D$，掩码长度为 $L$。下一跳地址由于没有用到，故省略。 Q <D> <a> <b> 其中 $D$ 为一个 IP 地址，$a,b$ 为正整数 $(a\le b)$。查询从第 $a$ 次至第 $b$ 次添加表项期间（含 $a,b$），目的地址 $D$ 的路由表项选择发生了多少次变化。保证查询时表中至少有 $b$ 个表项。

输出格式 包含若干行，每行仅有一个整数，依次对应每个查询操作。

数据范围与提示 对于一次查询的一种理解方式是：无视其它所有查询操作，只看添加操作。先清空路由表，然后执行第 $1$ 到 $a-1$ 次添加操作。之后再统计第 $a$ 到 $b$ 次添加操作过程中匹配改变的次数。 对于 $30\%$ 的数据，$M\le 10^3$； 对于 $100\%$ 的数据，$M\le 10^6$。 设一条表项的掩码长度为 $L$，数据保证将目的地址转为二进制串后，末尾的 $32-L$ 位均为 $0$。另外，保证不会重复添加目的地址和掩码长度都相同的表项。

二、解法

看到这道题一定就想到了$trie$树（虽然我以前没打过）。 考虑$A$操作的前$L$位放进$trie$树中，然后拿询问的二进制串拿去匹配。 易得$y$比$x$更明确，所以只有当$x$比$y$先出现是才有可能$x,y$都对答案有贡献，所以我们在插入时打上时间戳，然后我们维护一个单调栈，维护时间单调递增，答案就是栈的大小，然后筛出不在$[l,r]$的贡献。

#include <cstdio> const int MAXN = 1000005; int read() { int x=0,flag=1;char c; while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1; while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*flag; } int n,m,rt,cnt,len,st[35]; char s[35]; struct edge { int ls,rs,t; }tr[MAXN<<2]; void add(int num,int now) { int cnt=0; while(num>0) s[now*8-(++cnt)]=(num%2)+'0',num/=2; for(int i=1;i<=8-cnt;i++) s[(now-1)*8+i-1]='0'; } void updata(int &x,int now,int val) { if(!x) x=++cnt; if(now==len) { tr[x].t=val; return ; } if(s[now]=='0') updata(tr[x].ls,now+1,val); else updata(tr[x].rs,now+1,val); } int main() { n=read(); while(n--) { char op; scanf("%c",&op); if(op=='A') { add(read(),1);add(read(),2);add(read(),3);add(read(),4);len=read(); updata(rt,0,++m); } else { add(read(),1);add(read(),2);add(read(),3);add(read(),4); int l=read(),r=read(); int x=rt,top=0,now=0; while(x) { if(!x) break; if(tr[x].t) { while(top>0 && st[top]>=tr[x].t) top--; st[++top]=tr[x].t; } if(s[now]=='0') x=tr[x].ls; else x=tr[x].rs; now++; } int ans=top; for(int i=1;i<=top;i++) if(st[i]<l || st[i]>r) ans--; printf("%d\n",ans); } } }

飞扬的小鸟

一、题目

点此看题

二、解法

先写暴力$dp$吧，定义$dp[i][j]$为到了$(i,j)$时的最小步数，则有转移： $\{\begin{array}{l}dp[i+1][j-y[i]]=dp[i][j]+1\\ dp[i+1][j+k\times x[i]]=dp[i][j]+k\end{array}$ 现在的问题就是$k$的枚举很耗时，发现很它像完全背包，考虑把转移状态存在$dp[i][j+x[i]]$中，这样以后的转移就可以用$dp[i][j+x[i]]$直接转移，但是我们只是为了$k$的更新，所以我们要先更新第一个转移。

#include <cstdio> #include <cstring> #include <iostream> #define inf 0x3f3f3f3f using namespace std; const int MAXN = 10005; const int MAXM = 1005; int read() { int x=0,flag=1;char c; while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1; while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*flag; } int n,m,k,x[MAXN],y[MAXN],p[MAXN],l[MAXN],h[MAXN]; int dp[MAXN][MAXM],ans=inf; bool mp[MAXN][MAXM]; signed main() { n=read();m=read();k=read(); for(int i=0;i<n;i++) x[i]=read(),y[i]=read(); for(int i=1;i<=k;i++) { p[i]=read();l[i]=read();h[i]=read(); for(int j=1;j<=l[i];j++) mp[p[i]][j]=1; for(int j=m;j>=h[i];j--) mp[p[i]][j]=1; } memset(dp,0x3f,sizeof dp); for(int i=0;i<=m;i++) dp[0][i]=0; for(int i=0;i<n;i++) { for(int j=0;j<=m;j++) if(j-y[i]>0 && !mp[i][j] && !mp[i+1][j-y[i]]) dp[i+1][j-y[i]]=min(dp[i+1][j-y[i]],dp[i][j]); for(int j=0;j<=m;j++) { if(dp[i][j]==inf) continue; dp[i][min(j+x[i],m)]=min(dp[i][min(j+x[i],m)],dp[i][j]+1); if(!mp[i+1][min(j+x[i],m)]) dp[i+1][min(j+x[i],m)]=min(dp[i+1][min(j+x[i],m)],dp[i][j]+1); } } for(int j=1;j<=m;j++) ans=min(ans,dp[n][j]); if(ans==inf) { puts("0"); ans=0; for(int i=1;i<=k;i++) { bool flag=0; for(int j=l[i]+1;j<h[i];j++) if(dp[p[i]][j]!=inf) flag=1; if(flag)ans++; } printf("%d\n",ans); } else { puts("1"); printf("%d\n",ans); } }