Codeforces Round #364 (Div. 1) (差一個后綴自動機)

B.?Connecting Universities

大意: 給定樹, 給定2*k個點, 求將2*k個點兩兩匹配, 每個匹配的貢獻為兩點的距離, 求貢獻最大值

單獨考慮每條邊$(u,v)$的貢獻即可, 最大貢獻顯然是左右兩側點的最小值.

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <bitset>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
//headconst int N = 1e6+10;
int n, k;
int a[N], sz[N];
vector<int> g[N];
ll ans;void dfs(int x, int fa) {sz[x] = a[x];for (int y:g[x]) if (y!=fa) { dfs(y,x), sz[x]+=sz[y];ans += min(sz[y], k-sz[y]);}
}int main() {scanf("%d%d", &n, &k),k*=2;REP(i,1,k) { int t;scanf("%d", &t);a[t] = 1;}REP(i,2,n) {int u, v;scanf("%d%d", &u, &v);g[u].pb(v),g[v].pb(u);}dfs(1,0);printf("%lld\n", ans);
}

C. Break Up

大意: 無向有權圖有重邊自環, 求刪除兩條邊使得s與t不連通, 且兩條邊的邊權和最小.

先求出任意一條最短路徑, 邊數顯然不超過$n$, 暴力枚舉這$n$條邊然后再tarjan即可, 復雜度O(n(m+n))

算是挺簡單的了, 還是打了好久, 一直卡在怎么判斷刪除一條邊后是否連通, 后來發現tarjan后從s->t經過的橋一定是一條鏈, 所以直接dfs就好了, 最后還要注意邊權1e9+1e9爆掉0x3f3f3f3f了.

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <bitset>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = ~0u>>1;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
//headconst int N = 3e4+10;
int n, m, S, T;
int w[N];
struct _ {int to,id;} fa[N];
vector<_> g[N];
int dfn[N], low[N], isbridge[N], clk;
void tarjan(int x, int fa, int z) {dfn[x]=low[x]=++clk;for (auto &&e:g[x]) if (e.id!=z) {int y = e.to, id = e.id;if (!dfn[y]) {tarjan(y,id,z);low[x]=min(low[x],low[y]);if (low[e.to]>dfn[x]) isbridge[id]=1;} else if (dfn[y]<dfn[x]&&id!=fa) { low[x]=min(low[x],dfn[y]);}}
}
int vis[N], c[N];
int dfs(int x) {if (x==T) return 1;for (auto e:g[x]) if (!vis[e.id]) {vis[e.id] = 1;if (dfs(e.to)) return c[e.id] = 1;}return 0;
}int main() {scanf("%d%d%d%d", &n, &m, &S, &T);REP(i,1,m) { int u, v;scanf("%d%d%d", &u, &v, w+i);g[u].pb({v,i}), g[v].pb({u,i});}queue<int> q;fa[S].to=-1, q.push(S);while (q.size()) {int x = q.front(); q.pop();for (auto &&e:g[x]) if (!fa[e.to].to) {fa[e.to]={x,e.id}, q.push(e.to);}}if (!fa[T].to) return puts("0\n0"),0;int ans = INF;vector<int> vec;for (int x=T; x!=S; x=fa[x].to) {int id = fa[x].id;memset(vis,0,sizeof vis);memset(c,0,sizeof c);vis[id] = 1;if (!dfs(S)) {if (ans>w[id]) ans = w[id],vec.clear(),vec.pb(id);continue;}memset(dfn,0,sizeof dfn);memset(isbridge,0,sizeof isbridge);clk = 0;tarjan(S,0,id);REP(i,1,m) if (c[i]&&isbridge[i]&&ans>w[id]+w[i]) {ans=w[id]+w[i];vec.clear();vec.pb(id), vec.pb(i);}}if (ans==INF) return puts("-1"),0;printf("%d\n%d\n", ans, int(vec.size()));for (int t:vec) printf("%d ", t); hr;
}

D.?Huffman Coding on Segment

莫隊一下, 然后將出現次數小于等于$\sqrt{n}$的暴力合, 其余的用堆合, 復雜度$O(m\sqrt{n}logn)$, 看了下最優解, 好像可以排序一下省去堆從而優化掉一個log

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <bitset>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
//head#ifdef ONLINE_JUDGE
const int N = 1e6+10;
#else
const int N = 111;
#endifint n, m, sqn;
int blo[N], cnt[N], sum[N], s[N], a[N];
struct _ {int l,r,id;bool operator < (const _ & rhs) const {return blo[l]^blo[rhs.l]?l<rhs.l:blo[l]&1?r<rhs.r:r>rhs.r;}
} e[N];
ll ans[N];
vector<int> q;void upd(int x, int d) {--sum[cnt[x]];cnt[x]+=d;++sum[cnt[x]];
}ll calc() {ll ans = 0;REP(i,1,sqn) s[i] = sum[i];priority_queue<int,vector<int>,greater<int> > Q;int pre = 0;REP(i,1,sqn) if (s[i]) {if (pre) {int x = pre+i;ans += x;if (x>sqn) Q.push(x);else ++s[x];--s[i], pre = 0;}if (s[i]&1) --s[i], pre = i;ans += s[i]*i;if (i*2<=sqn) s[i*2]+=s[i]/2;else {REP(j,1,s[i]/2) Q.push(i*2);}}if (pre) Q.push(pre);for (auto i:q) if (cnt[i]>sqn) Q.push(cnt[i]);while (Q.size()>1) {int x = Q.top(); Q.pop();x += Q.top(); Q.pop();ans += x, Q.push(x);}return ans;
}int main() {scanf("%d", &n), sqn = sqrt(n);REP(i,1,n) scanf("%d",a+i),++cnt[a[i]],blo[i]=i/sqn;REP(i,1,N-1) if (cnt[i]>sqn) q.pb(i);memset(cnt,0,sizeof cnt);scanf("%d", &m);REP(i,1,m) scanf("%d%d",&e[i].l,&e[i].r),e[i].id=i;sort(e+1,e+1+m);int ql=1,qr=0;REP(i,1,m) {while (ql<e[i].l) upd(a[ql++],-1);while (qr>e[i].r) upd(a[qr--],-1);while (ql>e[i].l) upd(a[--ql],1);while (qr<e[i].r) upd(a[++qr],1);ans[e[i].id]=calc();}REP(i,1,m) printf("%lld\n", ans[i]);
}

E.?Cool Slogans

后綴自動機還沒學, 以后補了

轉載于:https://www.cnblogs.com/uid001/p/10574977.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/394652.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/394652.shtml
英文地址,請注明出處:http://en.pswp.cn/news/394652.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Python黑魔法

1. 賦值 In [1]: x 1...: y 21...: print x, y...: ...: x, y y, x...: print x, y 1 21 21 1 2. 列表合并 In [2]: a1 [(2,3),(3,4)]...: a2 [(4,5)]...: a a1 a2...: print a [(2, 3), (3, 4), (4, 5)] 3. 字典合并 方式1: In [3]: d1 {a: 1}...: d2 {b: 2}...: ...…

python時間差怎么轉換為數字_pandas進行時間數據的轉換和計算時間差并提取年月日...

#pd.to_datetime函數 #讀取數據 import pandas as pd data pd.read_csv(police.csv) #將stop_date轉化為datetime的格式的dataframe&#xff0c;存到stop_datetime data[stop_datetime] pd.to_datetime(data.stop_date) #自定義一個時間&#xff0c;計算時間差 data_new pd.…

人臉識別html5效果,用HTML5實現人臉識別

注&#xff1a;今天 HTML5 小組沙龍《論道 HTML5 》分享時有朋友問到一個問題&#xff0c; getUserMedia 是否會支持人臉識別&#xff0c;我當時的答案是這應該是應用來實現的功能&#xff0c;而不是規范要完成的工作。而我之前在網上看到過一篇關于 getUserMedia 和人臉識別的…

企業如何尋找最合適的托管數據中心,以維持IT和業務的增長運營

想象一下&#xff0c;當您興奮地拿了鑰匙&#xff0c;走進您剛買的新家時&#xff0c;才突然意識到新家還沒通電&#xff0c;互聯網寬帶也還沒有通&#xff0c;而想要找個電工或者別的相關技術支持人員也不見蹤影。而且&#xff0c;更糟糕的是&#xff0c;您似乎還聽到您附近的…

gt爵士變形步驟_代碼廣播簡介:您可以編碼為24/7的爵士節拍

gt爵士變形步驟閱讀本文時&#xff0c;您可以繼續閱讀Code Radio。 (You can go ahead and start listening to Code Radio while you read this) Most developers I know listen to music while they code. When the meetings are over, the headphones come out.我認識的大多…

python3中format方法_[翻譯]python3中新的字符串格式化方法-----f-string

從python3.6開始,引入了新的字符串格式化方式,f-字符串. 這使得格式化字符串變得可讀性更高,更簡潔,更不容易出現錯誤而且速度也更快. 在本文后面,會詳細介紹f-字符串的用法. 在此之前,讓我們先來復習一下python中字符串格式化的方法. python中傳統的字符串格式化方法. 在pytho…

華為mate40會不會有鴻蒙系統,鴻蒙OS系統正式推送,拿華為Mate40更新后,發現了優缺點...

自從鴻蒙系統正式推送之后&#xff0c;筆者一直都帶著好奇心在體驗著HarmonyOS 2帶來的變化&#xff0c;生怕錯過驚喜&#xff0c;也擔心系統本身會出現不足。因為鴻蒙系統就像是年輕人一樣&#xff0c;才剛剛出爐&#xff0c;需要時間去磨練&#xff0c;然后才能發揮出真正強大…

jstack使用

jstack主要用來查看某個Java進程內的線程堆棧信息&#xff0c;根據堆棧信息我們可以定位到具體代碼&#xff0c;所以它在JVM性能調優中使用得非常多&#xff0c;語法格式如下&#xff1a; jstack [option] pid jstack [option] executable core jstack [option] [server-id]rem…

如何使用TensorFlow對象檢測API播放Quidditch

by Bharath Raj巴拉斯拉吉(Bharath Raj) 如何使用TensorFlow對象檢測API播放Quidditch (How to play Quidditch using the TensorFlow Object Detection API) Deep Learning never ceases to amaze me. It has had a profound impact on several domains, beating benchmarks …

刪除目錄軟鏈接注意事項

2019獨角獸企業重金招聘Python工程師標準>>> 實驗環境&#xff1a; 在root 目錄下創建一個目錄 1 ,并在該目錄下創建一個2.txt 的文件&#xff0c;寫入內容 1.txt: [rootserver ~]# mkdir 1 [rootserver ~]# echo 1.txt > 1/2.txt [rootserver ~]# tree 1 1 └─…

html如何模擬點擊,Javascript 模擬點擊事件(點擊鏈接與html點擊) 兼容IE/Firefox

一把情況下模擬點擊一般兩個方面&#xff0c;模擬點擊超級連接事件firefox的兼容的函數為對HTMLAnchorElement 加入onclick事件try {// create a element so that HTMLAnchorElement is accessibledocument.createElement(a);HTMLElement.prototype.click function () {if (ty…

mvn編寫主代碼與測試代碼

maven編寫主代碼與測試代碼 3.2 編寫主代碼 項目主代碼和測試代碼不同&#xff0c;項目的主代碼會被打包到最終的構件中&#xff08;比如jar&#xff09;&#xff0c;而測試代碼只在運行測試時用到&#xff0c;不會被打包。默認情況下&#xff0c;Maven假設項目主代碼位于src/…

打印速度快點的打印機_SLM推出了功能強大的新型金屬3D打印機,速度快20倍

德國金屬3D打印機制造商SLM Solutions在Formnext Connect貿易展覽會上推出了功能強大的新系統NXG XII 600。SLM的大幅面機器配備了十二個可同時運行的1 KW激光器&#xff0c;使其速度比該公司自己的單激光SLM 280快20倍。NXG XII 600經過定制設計&#xff0c;可大量生產大型零件…

把轉變為json_如何使用7行JSON將您的網站轉變為移動應用程序

把轉變為jsonby Ethan通過伊桑 將Web引擎融合到本機應用程序的新方法 (A New Approach for Blending Web Engine into Native Apps) What if I told you the 7 lines of JSON above, colored in orange is all you need to turn a website into a mobile app? No need to rew…

1.7Oob 繼承關系中構造方法的使用

1&#xff1a;父類中最好要有一個空參數的構造方法&#xff0c;因為默認的構造方法在自定義了構造方法后就不存在了&#xff0c;需要顯示的寫出來。 若父類中沒有空參數的構造方法&#xff0c;則子類必須有自定義的構造方法&#xff0c;且用super&#xff08;&#xff09;調用父…

JavaScript浮點運算0.2+0.1 !== 0.3

浮點運算JavaScript 本文主要討論JavaScript的浮點運算&#xff0c;主要包括 JavaScript number基本類型二進制表示十進制浮點數的精度number 數字類型 在JavaScript中&#xff0c;數字只有number這一種類型; var intS 2,floatA 0.1; typeof intS; // number typeof floatA…

html獲取data-*值,html5 獲取和設置data-*屬性值的四種方法講解

1、獲取id的對象2、需要獲取的就是data-id 和 dtat-vice-id的值一&#xff1a;getAttribute()方法const getId document.getElementById(getId);// //getAttribute()取值屬性console.log(getId.getAttribute("data-id"));//console.log(getId.getAttribute("da…

三菱模擬量輸入與輸出程序_初學PLC是學習西門子還是三菱?

PLC的種類繁多&#xff0c;品牌大多分為歐系、日系、美系。德系PLC以西門子為主&#xff0c;日系有三菱、歐姆龍、松下……&#xff0c;美系有羅克韋爾(A-B)通用電氣(GE)公司、莫迪(MODICON)公司等。美國和歐洲的PLC技術是在相互隔離情況下獨立研究開發的&#xff0c;因此美國和…

性能測試十四:Xshell鏈接linux虛擬機

一、先裝一個linux虛擬機 VBoxcentos1、先下載Linux鏡像文件的ovf或者OVA文件2、打開vbox&#xff0c;點擊菜單欄“管理”-“導入虛擬電腦3、選擇解壓路徑中的ovf或者OVA文件&#xff0c;點擊下一步 4、點擊“導入”&#xff0c;等待完成5、導入成功后&#xff0c;選擇新導入的…

代碼編寫工具_我希望在開始編寫代碼時就已經知道的工具:已復習

代碼編寫工具by Mario Hoyos通過馬里奧霍約斯(Mario Hoyos) 我希望在開始編寫代碼時就已經知道的工具&#xff1a;已復習 (Tools I wish I had known about when I started coding: Revisited) A few days ago, I wrote this article for freeCodeCamp which has since gone o…