Test 2018-09-19
| 英文代號 | rooftrellen | magnus | crixalis | roads |
| 時限 | 1 秒 | 1 秒 | 見題面 | 1 秒 |
| 輸入文件 | rooftrellen.in | magnus.in | crixalis.in | roads.in |
| 輸出文件 | rooftrellen.out | magnus.out | crixalis.out | roads.out |
| 內存限制 | 512MB | 512MB | 512MB | 512MB |
注意：
本次測試中，選手在讀入數據時會要求讀入一個數據編號，方便選手對于不同的數據設計不同的算法，
而每個編號對應的數據范圍也將在【數據規模和約定】 中體現。
而樣例輸入中的數據編號的作用僅僅是提醒選手不要忘了讀入編號，并不代表這個編號對應的數據就是樣例。
瘋狂生長
【問題背景】
在 Rooftrellen 周圍召喚出瘋狂生長的傷害性藤條和枝干，阻止被纏繞的敵人移動、閃爍、進入隱身或攻擊。
【問題描述】
樹精世界里有 $ n $ 顆藤蔓，每顆藤蔓都有一個高度 $ h_i $ 。
Rooftrellen 可以耗費一個單位的能量把任意一顆藤蔓拔高 $ 1 $ 個單位長度。
他想知道，能否恰好耗 費自身現有的 $ m $ 個單位的能量，使得藤蔓都變得一樣高？
【輸入格式】
第一行一個整數 ID，表示數據的編號。
第二行一個整數 T， 表示數據的組數。 接下來有 T 組數據。
對于每組數據：
第一行兩個整數 $ n， m $ ，表示藤蔓的數量和能量值。
第二行 n 個整數 $ h_1, h_2, …, h_n $ ，表示藤蔓的初始高度。
【輸出格式】
對于每組數據： 一行一個字符串 Yes 或 No，表示答案。
【樣例輸入】
5 3 5 6 1 2 3 3 4 5 7 1 2 3 3 4 5 8 1 2 3 3 4【樣例輸出】
No Yes No
【數據規模和約定】
對于100%的數據， $ h_i≤10^9 $ 。
【樣例說明】
樣例一，樣例三：沒有可行的方法。 樣例二：從左到右依次增加 3，2，1，1，0 個單位長度即可。
【提示】
1、注意題面中的“恰好”。
2、 注意區別 ID 和 T。
題解
顯然的貪心，先把所有藤蔓的高度都提到和最高的藤蔓一樣高
（因為題目要求必須一樣高而且不能讓它們下降）
然后看所得消耗與 $ m $ 的大小關系。如果所得消耗比 $ m $ 大，那么答案一定是No
如果所得消耗大于等于 $ m $ ，設所得消耗為 $ sum $ ，判斷 $ (m-sum) $ % $ n $ 是否等于 $ 0 $
（這個時候所有藤蔓一樣高，還是要保持一樣高一定要讓它們都再 $ +1 $ ）
代碼
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int ID,T,n,m,h[105],maxh,res; int main(){freopen("rooftrellen.in","r",stdin);freopen("rooftrellen.out","w",stdout);scanf("%d %d",&ID,&T);while(T--){scanf("%d %d",&n,&m); maxh=-1; res=0;for(int i=1;i<=n;++i){ scanf("%d",&h[i]); maxh=max(maxh,h[i]); }for(int i=1;i<=n;++i) res+=maxh-h[i];if(res==m) puts("Yes"); else if(res<m&&(m-res)%n==0) puts("Yes"); else if(res>m||(m-res)%n!=0) puts("No");}return 0; }兩極反轉
【問題背景】
Magnus 改變物質的屬性，將附近的敵人都拖拽到他的前方，并且以強力的 震擊對他們造成傷害和眩暈。
【問題描述】
猛犸世界中的數據網可以抽象成一個包含 $ n $ 個點 $ m $ 條邊的有向圖。
由于編寫防火墻的碼農比較偷懶，因此數據網經常遭到攻擊，某些邊的方向會變化，使得數據無法在節點之間相互傳遞。
這時 Magnus 的能力就起作用了，他 可以耗費 $ 1 $ 單位的體力值來使任意一條邊反向。
Magnus 想知道， 如果要把數據從節點 $ x_i $ 傳輸到節點 $ y_i $ ，他至少要耗費多少體力值呢？
【輸入格式】
第一行一個整數 ID，表示數據的編號。
第二行三個整數 $ n， m， q，$ 表示有向圖的點數，邊數和詢問數。
接下來 $ m $ 行，每行 2 個整數 $ x_i $ 和 $ y_i $ ，表示 $ x_i $ 和 $ y_i $ 之間有一條有向邊。
接下來 $ q $ 行，每行 2 個整數 $ x_i $ 和 $ y_i $ ，表示一組詢問。
【輸出格式】
$ q $ 行，每行一個正整數，表示至少耗費的體力值。 如果無法傳輸，輸出-1。
【樣例輸入一】
1 8 7 1 1 2 3 2 3 4 7 4 6 2 5 6 7 5 1 7【樣例輸出一】
2【樣例輸入二】
1 8 7 1 1 2 3 2 3 4 7 4 6 2 5 6 7 5 1 8【樣例輸出二】
-1
【樣例說明】
對于樣例一，只要將 $ 3 \rightarrow 2 $ 和 $ 7 \rightarrow 4 $ 兩條邊反向即可。
對于樣例二，節點 8 的入度和出度均為 0，所以無法傳輸。
【數據規模和約定】
【提示】
1、注意題面中的“如果”，每次詢問并不會真的將某些邊反向。
題解
此題考慮數據分治
對于前14個點，由于 $ q=1 $ ，我們考慮建圖，
對于有向邊 $ (u,v) $ ，我們存一條 $ u \rightarrow v \quad cost: 0 $ 的邊，
對于它的反向邊，我們存一條 $ v \rightarrow u \quad cost: 1 $ 的邊，
使 $ x $ 作為源點跑一遍 $ SPFA $ 即可。對于后面的數據，由于題目保證是一棵樹，考慮 $ LCA $ 和前綴和。
除了 $ dep $ ，我們多維護一個信息 $ dis $ 代表 $ 1 $ 節點到當前節點需要走多少條反向邊，
還是像之前一樣建邊，然后維護即可。
最后計算答案的時候，由于 $ x $ 點要往上走，它的反向邊與 $ 1 $ 到它的反向邊意義正好相反，我們要用 $ dep - dis $ 得到正確的反向邊數量對于一對 $ x_i,y_i $ ，它們的答案即為 $ ans=dep_x-dis_x+dis_y-dep_{lca} $
代碼
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; int ID,n,m,q; struct edge{ int v,w,nxt; }e[100005<<2]; int head[100005],tot; inline void add(int u,int v,int w){ e[++tot].v=v; e[tot].w=w; e[tot].nxt=head[u]; head[u]=tot; } int dis[100005]; bool vis[100005]; inline void spfa(int s){for(int i=1;i<=n;++i) dis[i]=0x3f3f3f3f;queue<int>q; q.push(s); dis[s]=0; while(!q.empty()){int u=q.front(); vis[u]=0; q.pop();for(int i=head[u];i;i=e[i].nxt)if(dis[e[i].v]>dis[u]+e[i].w){dis[e[i].v]=dis[u]+e[i].w;if(!vis[e[i].v]){ vis[e[i].v]=1; q.push(e[i].v); }}} } int dep[100005],f[100005][21]; void dfs(int u,int fa){dep[u]=dep[fa]+1; f[u][0]=fa;for(int j=1;j<=20;++j)f[u][j]=f[f[u][j-1]][j-1];for(int i=head[u];i;i=e[i].nxt){if(e[i].v==fa) continue;dis[e[i].v]=dis[u]+e[i].w;dfs(e[i].v,u);} } inline int lca(int u,int v){if(dep[u]>dep[v]) swap(u,v);for(int i=20;~i;--i)if(dep[u]<=dep[v]-(1<<i)) v=f[v][i];if(u==v) return u;for(int i=20;~i;--i)if(f[u][i]!=f[v][i]){ u=f[u][i]; v=f[v][i]; }return f[u][0]; } signed main(){freopen("magnus.in","r",stdin);freopen("magnus.out","w",stdout);scanf("%d",&ID);scanf("%d %d %d",&n,&m,&q);if(q==1){for(int i=1;i<=m;++i){int u,v;scanf("%d %d",&u,&v);add(u,v,0); add(v,u,1);}int x,y;scanf("%d %d",&x,&y);spfa(x);if(dis[y]==0x3f3f3f3f) puts("-1");else printf("%d",dis[y]);} else {for(int i=1;i<=m;++i){int u,v;scanf("%d %d",&u,&v);add(u,v,0); add(v,u,1);}dfs(1,0);while(q--){int x,y;scanf("%d %d",&x,&y);int Lca=lca(x,y);printf("%d\n",(dep[x]-dis[x])+dis[y]-dep[Lca]);}}return 0; }地震
【問題背景】
持續施法 - 在 2 秒吟唱后， Crixalis 向地中發送擾動，引起大地劇烈震動。
所有范圍內的敵人會受到傷害并被減速。每次后續震擊都會提高傷害傳播 半徑。可用神杖升級。
【問題描述】
Crixalis 平日很喜歡搗亂，這導致沙塵世界每隔一個小時就有一次地震發生。
沙塵世界所有的 $ n $ 幢建筑都在一條直線上，從左到右依次標號為 $ 1~n $ 。
每次地震由三個參數決定：受影響的建筑區間 $ [L_i, R_i] $ 以及地震的強度 $ F_i $ 。
任意時刻每幢建筑物都有一個高度， 用一個數字串來表示（可能含有前導 0）。
每一次地震來臨時，受影響建筑的高度數字串將根據地震的強度向左旋轉相應的位數， 但是不要忘了前導零的存在，
舉個例子：高度串是 120 的建筑連續受到 三次強度為 1 的地震的影響之后，高度串分別變為 201， 012， 120。
沙塵世界的守衛想出了一個保護建筑的方法，但有時需要知道某個區間內最高的建筑的高度。
現在給出了這 $ n $ 幢建筑初始的高度數字串，以及有以下兩種操作：
1、 U Li Ri Fi，表示 $ [L_i, R_i] $ 區間內的建筑受到了強度為 Fi 的地震的影響。
2、 Q Li Ri，表示詢問 $ [L_i, R_i] $ 區間內當前最高的建筑的高度。 你需要模擬這兩種操作，幫助守衛解決問題。
【輸入格式】
第一行一個整數 ID，表示數據的編號。
第二行兩個整數 $ n， q $ ， 表示建筑的數量和操作數。
第三行 $ n $ 個整數 $ a_1, a_2, …, a_n $ ，表示每幢建筑的初始高度串。
接下來 $ q $ 行，每行表示兩種操作中的某一種。
【輸出格式】
對于每個 Q 操作，輸出一行一個整數，表示該操作的答案。
注意輸出的整數不能包含前導 0。
【樣例輸入】
2 3 817 3140 832Q 1 3U 1 3 1Q 2 3Q 1 1U 1 3 2Q 1 3U 2 2 1Q 1 3【樣例輸出】
31401403 718323140
【數據規模和約定】
對于100%的數據，初始的高度數字串不包含前導 0， $ 1≤F_i≤60 $ 。
【樣例說明】
第一次 U 操作之后=>[71, 1403, 328]
第二次 U 操作之后=>[71, 0314, 832]
第三次 U 操作之后=>[71, 3140, 832]
【提示】
1、 雖然是高度數字串，但是應看做數字來比較大小而不是字典序。例如：0123 和 122 比較， 0123 的高度較大。
2、注意本題特殊的時間限制
代碼
- 線段樹，我寫掛了！題解的線段樹指針滿天飛，看看就好。（；′д｀）ゞ
Paid Roads
【題目描述】
這里有一個地圖，嗯~準確的說是一個藏寶圖。
你在 $ 1 $ 號點，寶藏在 $ n $ 號點， 所有的點編號 $ 1~n $ ，
這塊寶底的地形是很奇怪的，每兩個點之間有兩條通路，兩 個通路的長度是不一樣的，可能會有一條比較短，你可以任選一條，
但是其中一 條你只有在之前經過某個點的時才能通行，就好像這條路的通行證在那個點上一 樣。
現在想知道怎么樣走才能以最短的路程到達藏寶點。
【輸入格式】
第一行兩個用空格隔開的整數 $ n $ 和 $ m $ 分別表示節點的編號個數和該藏寶點路徑條數。
第二行到第 $ m + 1 $ 行每行 5 個整數 $ a，b，c，la，lb $ 描述從 $ a $ 點到 $ b $ 點的有向路，
$ la $ 表示之前經過 $ c $ 后，可以從 $ a $ 到 $ b $ 的路徑長度，
$ lb $ 表示隨時都可以通行的 $ a $ 到 $ b $ 的路徑長度。
【輸出格式】
一行一個整數表示的是從 $ 1 $ 到 $ n $ 的最短路程。如果沒有路輸出“ impossible”。
【輸入樣例】
4 5 1 2 1 10 10 2 3 1 30 50 3 4 3 80 80 2 1 2 10 10 1 3 2 10 50【輸出樣例】
110
【數據范圍】
$ n,m ≤ 10 $
$ la,lb ≤ (2<<31)-1 $
代碼
- 為什么沒有題解？這么小的數據直接分層圖最短路就可以了(￣y▽,￣)╭
轉載于:https://www.cnblogs.com/PotremZ/p/Test20180919.html
總結
以上是生活随笔為你收集整理的Test 2018-09-19的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Python爬虫之pyppeteer去除
- 下一篇： 使用PwDump导出本地Windows