Loading... > 不说那么多,惊天水数据。 <!--more--> 先推歌曲吧。 <div class="weixinAudio"> <input type="hidden" name="url" value="https://www.starroad.top/usr/themes/handsome/libs/interface/Get.php?id=28724363&type=song&media=netease"> <input type="hidden" name="mp3" value="" > <input type="hidden" name="title" value="" > <input type="hidden" name="tips" value="" > <audio title="" tips="" class="WeChatAudio" preload="none"><source src="" type="audio/mpeg"></audio><div class="db audio_area "><div class="audio_wrp2 box-shadow-wrap-lg"><div class="audio_play_area "><i class="icon_audio_default"></i><i class="icon_audio_playing"></i></div><div class="audio_length">00:00</div><div class="db audio_info_area"><strong class="db audio_title">加载中……</strong><span class="audio_source text-muted">请稍等…… </span><div class="progress_bar_bg"><div class="progress_bar" style="width: 0%;"></div></div></div></div></div></div> <div class="weixinAudio"> <input type="hidden" name="url" value="https://www.starroad.top/usr/themes/handsome/libs/interface/Get.php?id=26092806&type=song&media=netease"> <input type="hidden" name="mp3" value="" > <input type="hidden" name="title" value="" > <input type="hidden" name="tips" value="" > <audio title="" tips="" class="WeChatAudio" preload="none"><source src="" type="audio/mpeg"></audio><div class="db audio_area "><div class="audio_wrp2 box-shadow-wrap-lg"><div class="audio_play_area "><i class="icon_audio_default"></i><i class="icon_audio_playing"></i></div><div class="audio_length">00:00</div><div class="db audio_info_area"><strong class="db audio_title">加载中……</strong><span class="audio_source text-muted">请稍等…… </span><div class="progress_bar_bg"><div class="progress_bar" style="width: 0%;"></div></div></div></div></div></div> <div class="weixinAudio"> <input type="hidden" name="url" value="https://www.starroad.top/usr/themes/handsome/libs/interface/Get.php?id=1301390808&type=song&media=netease"> <input type="hidden" name="mp3" value="" > <input type="hidden" name="title" value="" > <input type="hidden" name="tips" value="" > <audio title="" tips="" class="WeChatAudio" preload="none"><source src="" type="audio/mpeg"></audio><div class="db audio_area "><div class="audio_wrp2 box-shadow-wrap-lg"><div class="audio_play_area "><i class="icon_audio_default"></i><i class="icon_audio_playing"></i></div><div class="audio_length">00:00</div><div class="db audio_info_area"><strong class="db audio_title">加载中……</strong><span class="audio_source text-muted">请稍等…… </span><div class="progress_bar_bg"><div class="progress_bar" style="width: 0%;"></div></div></div></div></div></div> ## Problem A 玩具车 该题目为[Codeforces545A](http://codeforces.com/problemset/problem/545/A)原题,点击查看完整[翻译](https://www.luogu.org/problem/CF545A) ### 题面 `Susie`和他哥哥都很喜欢玩玩具车,今天他们将进行一场友谊赛。有$n$辆玩具车,每辆玩具车两两相撞,碰撞结果刚好组成了一个 $n \times n$的矩阵,$a_{i,j}$表示第$i$辆车与第$j$辆车的碰撞结果。在矩阵中只有五种数: - $-1$:表示两辆车没有相撞($-1$仅出现在对角线上) - $0$:表示两辆车都没有被撞翻。 - $1$:表示第$i$辆车被撞翻了。 - $2$:表示第$j$辆车被撞翻了。 - $3$:表示两辆车都被撞翻了。 比赛结束后,`Susie`想知道有多少辆车没有被撞翻,具体是哪些车。 ### 题解 统计每行$1$和$3$的个数,如果二者只要有其中之一,就意味着车翻了。 ### 代码 ```cpp #include <iostream> #include <cstring> #include <bitset> using namespace std; const int MAXN=1005; int main(){ #ifndef OFF_LINE freopen("toy.in","r",stdin); freopen("toy.out","w",stdout); #endif ios::sync_with_stdio(false); int n,ans=0; bitset<MAXN> vis; vis.set(); cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ int t; cin>>t; switch(t){ case -1: case 0: break; case 1: vis.reset(i); break; case 2: vis.reset(j); break; case 3: vis.reset(i); vis.reset(j); break; default: cerr<<"ERROR:"<<__LINE__<<endl; } } } cout<<n+vis.count()-MAXN<<endl; for(int i=1;i<=n;i++){ if(vis[i]){ cout<<i<<" "; } } cout<<endl; return 0; } ``` ## Problem B 花花的聚会 ### 题面 花花住在`H`国。`H`国有$n$个城市,其中$1$号城市为其首都。城市间有$n-1$条道路。从任意一个城市出发,都可以沿着这些道路一路走到首都。事实上,从任何一个城市走到首都的路径是唯一的。 过路并不是免费的。想要通过某一条道路,你必须使用一次过路券。`H`国一共有$m$种过路券,每张过路券以三个整数表示:$v,k, w$,表示你可以在城市$v$以价格$w$买到一张过路券。这张券可以使用$k$次。这意味着,拿着这张券通过了$k$条道路之后,这张券就不能再使用了。 请注意你同一时间最多只能拥有最多一张过路券。但你可以随时撕掉手中已有的过路券,并且在所在的城市再买一张。 花花家在首都。他有$q$位朋友,他希望把这些朋友们都邀请到他家做客。所以他想要知道每位朋友要花多少路费。他的朋友们都很聪明,永远都会选择一条花费最少的方式到达首都。花花需要准备晚餐去了,所以他没有时间亲自计算出朋友们将要花费的路费。你可以帮帮他么? ### 题解 #### 题意 有一棵$n$个节点的有根树,在某些节点$v_i$,可以选择花费$w_i$的代价,向上跳$[1,k_i]$步。现有$q$个询问,询问一些节点跳到根的最少代价。 #### 解法 不难发现,我们可以用动态规划的思想来解决这个问题。记$f_u$为$u$跳到根的最少代价。则不难得出转移方程:$f_u=minff[v]+wig$,其中$v$是$u$的祖先,且存在一种车票$u_i,w_i,k_i$并满足$dep[u] - dep[v] \leq ki$。这个`DP`方程的边界条件为$f_{root} = 0$。这样对于每种车票,我们可以暴力枚举所有合法的$v$,从而求得答案。优化该解法的`DP`转移。事实上我们只需在较快的时间内求得树上某一段区间的$minff[u]g$,即可较好地解决这个问题。而维护树上区间最值有树链剖分、动态树等许多数据结构能够胜任。在这里我们考虑用倍增的思想,维护$u$往上跳$2^i$步到的祖先$v$和$u$到$v$这一段$f$值的最小值,这样我们对于每一个节点$u$可以在$O(log_2n)$的时间内求得$minff[v]g$。时间复杂度为O(nlogn),期望得分100 分。 ### 代码 ```cpp #include <iostream> #include <vector> #include <limits.h> using namespace std; const int MAXN=100005; struct Edge{ int v; int next; }; int head[MAXN],cnt,fat[MAXN],dp[MAXN]; vector<pair<int,int>> vec[MAXN]; Edge e[MAXN<<1]; void addedge(int u,int v){ cnt++; e[cnt].v=v; e[cnt].next=head[u]; head[u]=cnt; } void pre_dfs(int u=1,int fa=0){ fat[u]=fa; for(int i=head[u];i;i=e[i].next){ if(fa!=e[i].v){ pre_dfs(e[i].v,u); } } } int dfs(int n){ int ans=INT_MAX; if(dp[n]||n==1){ return dp[n]; } for(unsigned int i=0;i<vec[n].size();i++){ int now=INT_MAX,x; x=fat[n]; for(int j=1;j<=vec[n][i].first;j++){ now=min(now,dfs(x)); x=fat[x]; } ans=min(ans,now+vec[n][i].second); } return dp[n]=ans; } int main(){ #ifndef OFF_LINE freopen("party.in","r",stdin); freopen("party.out","w",stdout); #endif ios::sync_with_stdio(false); int n,m,q; cin>>n>>m; for(int i=1;i<n;i++){ int a,b; cin>>a>>b; addedge(a,b); addedge(b,a); } pre_dfs(); for(int i=0;i<m;i++){ int v,k,w; cin>>v>>k>>w; vec[v].push_back(make_pair(k,w)); } cin>>q; while(q--){ int fr; cin>>fr; cout<<dfs(fr)<<endl; } return 0; } ``` ## Problem C 送信 ### 题面 小明是一名邮递员,他工作的城市被分为$n$个区域,由$n-1$土路连接,小明的公司在$1$号区域,接下来的日子里他有$m$个送信任务。由于城市化的推进,小明所在的城市计划将所有道路都改造成公路,所以小明不得不在他送信的途中走一些公路或土路。小明每次送信都是从邮局出发将信送到某个地方,他想知道每次送信的过程中走过的土路条数。 ### 题解 裸的`DFS`序,博主也很无语,为啥一群大佬写树链剖分? ### 代码 ```cpp #include <iostream> using namespace std; const int MAXN=250005; struct Edge{ int v; int next; }; int head[MAXN],cnt,dfs_clock,l[MAXN],r[MAXN],dep[MAXN]; Edge e[MAXN<<1]; void addedge(int u,int v){ cnt++; e[cnt].v=v; e[cnt].next=head[u]; head[u]=cnt; } void dfs(int u=1,int fa=0){ dep[u]=dep[fa]+1; l[u]=++dfs_clock; for(int i=head[u];i;i=e[i].next){ if(fa!=e[i].v){ dfs(e[i].v,u); } } r[u]=dfs_clock; } int sum[MAXN]; int lowbit(int x){ return x&-x; } void add(int pos,int num=1){ for(int i=pos;i<=dfs_clock;i+=lowbit(i)){ sum[i]+=num; } } int query(int pos){ int ans=0; for(int i=pos;i>0;i-=lowbit(i)){ ans+=sum[i]; } return ans; } int main(){ ios::sync_with_stdio(false); int n,m; cin>>n; for(int i=1;i<n;i++){ int a,b; cin>>a>>b; addedge(a,b); addedge(b,a); } dfs(); cin>>m; for(int i=n+m-1;i>0&&m!=0;i--){ char c; int x,y; cin>>c; switch(c){ case 'A': cin>>x>>y; if(dep[x]>dep[y]){ swap(x,y); } add(l[y]); add(r[y]+1,-1); break; case 'W': cin>>x; cout<<dep[x]-query(l[x])-1<<endl; m--; break; default: cerr<<"ERROR:"<<__LINE__<<endl; } } return 0; } ``` <hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于:淡淡的路瑶</p><p class="content-copyright">本文链接:<a class="content-copyright" href="https://www.starroad.top/archives/426.html">https://www.starroad.top/archives/426.html</a></p><p class="content-copyright">如果文章出现任何问题,请下方评论,紧急情况请发邮件。谢谢支持!</p></blockquote> Last modification:July 26th, 2019 at 11:09 am © 允许规范转载 Support 如果您觉得我的文章有用,给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat