精神不佳，選擇了在場(chǎng)外同步劃水

沒(méi)想到實(shí)際做起來(lái)手感還好，早知道就報(bào)名了……

該打

?

未完待續(xù)233

A. Andryusha and Socks

模擬，模擬大法好。注意每次是先判斷完能不能收進(jìn)柜子，再算桌子上的襪子數(shù)量的。

?

1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=100010; 9 int read(){ 10 int x=0,f=1;char ch=getchar(); 11 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 int a[mxn],n; 16 int cnt[mxn]; 17 int main(){ 18 int i,j,x; 19 n=read(); 20 int now=0,ans=0; 21 for(i=1;i<=n*2;i++){ 22 x=read(); 23 cnt[x]++; 24 now++; 25 if(cnt[x]==2)cnt[x]=0,now-=2; 26 ans=max(ans,now); 27 } 28 printf("%d\n",ans); 29 return 0; 30 } A

?

B. The Meeting Place Cannot Be Changed

判能否到達(dá)，肯定是判走得最慢的那個(gè)人。

二分終點(diǎn)不知可不可行，我選擇二分時(shí)間。在限定時(shí)間內(nèi)假設(shè)所有的人都往左走，找最后一個(gè)，再假設(shè)所有人往右走，找最后一個(gè)。如果這兩個(gè)“最后”可以相遇，該時(shí)間可行。

精度1e-8就T了，1e-7正合適

1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const double eps=1e-7; 9 const int mxn=100010; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 14 return x*f; 15 } 16 int n; 17 double ans=0; 18 double tmL[mxn],tmR[mxn]; 19 struct fri{ 20 double w,v; 21 }f[mxn]; 22 int cmp(fri a,fri b){ 23 return a.w<b.w; 24 } 25 bool solve(double lim){ 26 double ML=1000000010; 27 for(int i=1;i<=n;i++){ 28 double pos=f[i].v*lim+(double)f[i].w; 29 ML=min(ML,pos); 30 } 31 double MR=-1000000010; 32 for(int i=1;i<=n;i++){ 33 double pos=(double)f[i].w-f[i].v*lim; 34 MR=max(MR,pos); 35 } 36 if(ML-MR>=eps)return 1; 37 return 0; 38 } 39 int main(){ 40 int i,j; 41 n=read(); 42 for(i=1;i<=n;i++){ 43 f[i].w=read(); 44 } 45 for(i=1;i<=n;i++){ 46 f[i].v=read(); 47 } 48 sort(f+1,f+n+1,cmp); 49 double ans=1000000001000; 50 double l=0,r=1000000010; 51 while(r-l>=eps){ 52 double mid=(l+r)/2; 53 if(solve(mid)){ 54 ans=mid; 55 r=mid; 56 } 57 else l=mid; 58 } 59 printf("%.10lf\n",ans); 60 return 0; 61 } B

?

C. Andryusha and Colored Balloons

直接DFS，根據(jù)父結(jié)點(diǎn)和當(dāng)前結(jié)點(diǎn)已有的顏色，來(lái)判斷子結(jié)點(diǎn)可以選什么顏色

?

1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #include<set> 9 using namespace std; 10 const int mxn=400010; 11 int read(){ 12 int x=0,f=1;char ch=getchar(); 13 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 14 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 15 return x*f; 16 } 17 struct edge{ 18 int v,nxt; 19 }e[mxn<<1]; 20 int hd[mxn],mct=0; 21 void add_edge(int u,int v){ 22 e[++mct].nxt=hd[u];e[mct].v=v;hd[u]=mct;return; 23 } 24 int n; 25 int ans[mxn]; 26 bool vis[mxn];int cnt=0; 27 void DFS(int u,int fa){ 28 int cho=1; 29 for(int i=hd[u];i;i=e[i].nxt){ 30 int v=e[i].v; 31 if(v==fa)continue; 32 while(cho==ans[u] || cho==ans[fa])cho++; 33 ans[v]=cho; 34 if(!vis[cho]){ 35 vis[cho]=1; 36 cnt++; 37 } 38 cho++; 39 DFS(v,u); 40 } 41 return; 42 } 43 int main(){ 44 int i,j,u,v; 45 n=read(); 46 for(i=1;i<n;i++){ 47 u=read();v=read(); 48 add_edge(u,v); 49 add_edge(v,u); 50 } 51 ans[1]=1;vis[1]=1;cnt++; 52 DFS(1,0); 53 printf("%d\n",cnt); 54 for(i=1;i<=n;i++){ 55 printf("%d ",ans[i]); 56 } 57 printf("\n"); 58 return 0; 59 } C

?

D. Innokenty and a Football League

time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Innokenty is a president of a new football league in Byteland. The first task he should do is to assign short names to all clubs to be shown on TV next to the score. Of course, the short names should be distinct, and Innokenty wants that all short names consist of?three letters.

Each club's full name consist of two words: the team's name and the hometown's name, for example, "DINAMO BYTECITY". Innokenty doesn't want to assign strange short names, so he wants to choose such short names for each club that:

the short name is the same as three first letters of the team's name, for example, for the mentioned club it is "DIN",

or, the first two letters of the short name should be the same as the first two letters of the team's name, while the third letter is the same as the first letter in the hometown's name. For the mentioned club it is "DIB".

Apart from this, there is a rule that if for some club?x?the second option of short name is chosen, then there should be no club, for which the first option is chosen which is the same as the first option for the club?x. For example, if the above mentioned club has short name "DIB", then no club for which the first option is chosen can have short name equal to "DIN". However, it is possible that some club have short name "DIN", where "DI" are the first two letters of the team's name, and "N" is the first letter of hometown's name. Of course, no two teams can have the same short name.

Help Innokenty to choose a short name for each of the teams. If this is impossible, report that. If there are multiple answer, any of them will suit Innokenty. If for some team the two options of short name are equal, then Innokenty will formally think that only one of these options is chosen.

Input

The first line contains a single integer?n?(1?≤?n?≤?1000)?— the number of clubs in the league.

Each of the next?n?lines contains two words?— the team's name and the hometown's name for some club. Both team's name and hometown's name consist of uppercase English letters and have length at least?3?and at most?20.

Output

It it is not possible to choose short names and satisfy all constraints, print a single line "NO".

Otherwise, in the first line print "YES". Then print?n?lines, in each line print the chosen short name for the corresponding club. Print the clubs in the same order as they appeared in input.

If there are multiple answers, print any of them.

Examples input 2
DINAMO BYTECITY
FOOTBALL MOSCOW output YES
DIN
FOO input 2
DINAMO BYTECITY
DINAMO BITECITY output NO input 3
PLAYFOOTBALL MOSCOW
PLAYVOLLEYBALL SPB
GOGO TECHNOCUP output YES
PLM
PLS
GOG input 3
ABC DEF
ABC EFG
ABD OOO output YES
ABD
ABE
ABO Note

In the first sample Innokenty can choose first option for both clubs.

In the second example it is not possible to choose short names, because it is not possible that one club has first option, and the other has second option if the first options are equal for both clubs.

In the third example Innokenty can choose the second options for the first two clubs, and the first option for the third club.

In the fourth example note that it is possible that the chosen short name for some club?x?is the same as the first option of another club?yif the first options of?x?and?y?are different.

?

暴力+二分圖匹配

腦補(bǔ)了網(wǎng)絡(luò)流等各種奇怪的方法，然而沒(méi)有什么頭緒。

再看看數(shù)據(jù)范圍，啊，暴力你好，網(wǎng)絡(luò)流再見(jiàn)

首先O(N^2)找出所有按照第一種編碼會(huì)沖突的隊(duì)伍，強(qiáng)制它們使用第二種編碼，且不可改變。

然后依次判斷每支隊(duì)伍選擇的編碼方式，這里用到類似匈牙利算法的調(diào)整方式，如果當(dāng)前決策和之前的沖突，嘗試DFS向前調(diào)整，如果沒(méi)有可行方案就判NO

1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 using namespace std; 10 const int INF=1e9; 11 const int mxn=100010; 12 int read(){ 13 int x=0,f=1;char ch=getchar(); 14 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 15 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 16 return x*f; 17 } 18 map<string,int>mp; 19 string s1[1010],s2[1010]; 20 int vis[mxn]; 21 int cho[mxn]; 22 int n,cnt; 23 int link[mxn]; 24 bool DFS(int p){ 25 if(cho[p]!=2 && !vis[mp[s1[p]]]){ 26 vis[mp[s1[p]]]=1; 27 if(!link[mp[s1[p]]] || DFS(link[mp[s1[p]]])){ 28 link[mp[s1[p]]]=p; 29 cho[p]=1; 30 return 1; 31 } 32 } 33 if(!vis[mp[s2[p]]]){ 34 vis[mp[s2[p]]]=1; 35 if(!link[mp[s2[p]]] || DFS(link[mp[s2[p]]])){ 36 link[mp[s2[p]]]=p; 37 cho[p]=2; 38 return 1; 39 } 40 } 41 return 0; 42 } 43 int main(){ 44 n=read(); 45 int i,j; 46 for(i=1;i<=n;i++){ 47 cin>>s1[i]>>s2[i]; 48 s1[i]=s1[i].substr(0,3); 49 s2[i]=s1[i].substr(0,2)+s2[i].substr(0,1); 50 if(!mp[s1[i]])mp[s1[i]]=++cnt; 51 if(!mp[s2[i]])mp[s2[i]]=++cnt; 52 } 53 for(i=1;i<=n;i++){ 54 memset(vis,0,sizeof vis); 55 for(j=1;j<=n;j++){ 56 if(i==j)continue; 57 if(s1[i]==s1[j]){ 58 cho[i]=2;break; 59 } 60 } 61 if(!DFS(i)){ 62 printf("NO\n"); 63 return 0; 64 } 65 } 66 printf("YES\n"); 67 for(i=1;i<=n;i++){ 68 if(cho[i]==2){ 69 cout<<s2[i]<<endl; 70 } 71 else cout<<s1[i]<<endl; 72 } 73 return 0; 74 } D

?

?

E. Underground Lab

time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

The evil Bumbershoot corporation produces clones for gruesome experiments in a vast underground lab. On one occasion, the corp cloned a boy Andryusha who was smarter than his comrades. Immediately Andryusha understood that something fishy was going on there. He rallied fellow clones to go on a feud against the evil corp, and they set out to find an exit from the lab. The corp had to reduce to destroy the lab complex.

The lab can be pictured as a connected graph with?n?vertices and?m?edges.?k?clones of Andryusha start looking for an exit in some of the vertices. Each clone can traverse any edge once per second. Any number of clones are allowed to be at any vertex simultaneously. Each clone is allowed to stop looking at any time moment, but he must look at his starting vertex at least. The exit can be located at any vertex of the lab, hence each vertex must be visited by at least one clone.

Each clone can visit at most??vertices before the lab explodes.

Your task is to choose starting vertices and searching routes for the clones. Each route can have at most??vertices.

Input

The first line contains three integers?n,?m, and?k?(1?≤?n?≤?2·105,?n?-?1?≤?m?≤?2·105,?1?≤?k?≤?n)?— the number of vertices and edges in the lab, and the number of clones.

Each of the next?m?lines contains two integers?xi?and?yi?(1?≤?xi,?yi?≤?n)?— indices of vertices connected by the respective edge. The graph is allowed to have self-loops and multiple edges.

The graph is guaranteed to be connected.

Output

You should print?k?lines.?i-th of these lines must start with an integer?ci?()?— the number of vertices visited by?i-th clone, followed by?ci?integers?— indices of vertices visited by this clone in the order of visiting. You have to print each vertex every time it is visited, regardless if it was visited earlier or not.

It is guaranteed that a valid answer exists.

Examples input 3 2 1
2 1
3 1 output 3 2 1 3 input 5 4 2
1 2
1 3
1 4
1 5 output 3 2 1 3
3 4 1 5 Note

In the first sample case there is only one clone who may visit vertices in order (2, 1, 3), which fits the constraint of 6 vertices per clone.

In the second sample case the two clones can visited vertices in order (2, 1, 3) and (4, 1, 5), which fits the constraint of 5 vertices per clone.

?

?

DFS序 腦洞題

吼題，吼題。剛開(kāi)始毫無(wú)頭緒，然后注意到每個(gè)人可以走2n/k個(gè)結(jié)點(diǎn)。←也就是說(shuō)，每個(gè)結(jié)點(diǎn)走兩遍都足夠了。

那么先找出圖的生成樹(shù)，然后處理出DFS序，讓每個(gè)人按DFS序能走多遠(yuǎn)走多遠(yuǎn)，達(dá)到限制就再換一個(gè)人走，就可以了。

注意這種貪心法可能用不完所有的人就出解了，但實(shí)際上要輸出所有人的行走方案。因?yàn)闆](méi)有注意到這個(gè)，一直WA 7。

　　↑解決方案是讓沒(méi)有用到的人都輸出1 1（待在原地）

?

1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=600010; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 14 return x*f; 15 } 16 struct edge{ 17 int v,nxt; 18 }e[mxn]; 19 int hd[mxn],mct=0; 20 void add_edge(int u,int v){ 21 e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return; 22 } 23 int n,m,k,lim; 24 int ans[mxn],cnt=0; 25 vector<int>ve[mxn]; 26 int fa[mxn]; 27 int find(int x){ 28 return fa[x]==x?x:fa[x]=find(fa[x]); 29 } 30 inline void upd(int u){ 31 if(ans[cnt]<lim){ 32 ans[cnt]++; 33 ve[cnt].push_back(u); 34 } 35 else{ 36 ++cnt;ans[cnt]++; 37 ve[cnt].push_back(u); 38 } 39 return; 40 } 41 void DFS(int u,int ff){ 42 for(int i=hd[u];i;i=e[i].nxt){ 43 int v=e[i].v; 44 if(v==ff)continue; 45 upd(u); 46 DFS(v,u); 47 } 48 upd(u); 49 return; 50 } 51 int main(){ 52 int i,j,u,v; 53 n=read();m=read();k=read(); 54 lim=(2*n+k-1)/k; 55 for(i=1;i<=n;i++)fa[i]=i; 56 for(i=1;i<=m;i++){ 57 u=read();v=read(); 58 int fu=find(u),fv=find(v); 59 if(fu!=fv){ 60 add_edge(u,v); 61 add_edge(v,u); 62 fa[fu]=fv; 63 } 64 } 65 cnt=1; 66 DFS(1,0); 67 for(i=1;i<=k;i++){ 68 if(!ans[i]){ 69 printf("1 1\n"); 70 continue; 71 } 72 printf("%d ",ans[i]); 73 for(j=0;j<ve[i].size();j++){ 74 printf("%d ",ve[i][j]); 75 } 76 printf("\n"); 77 } 78 return 0; 79 } E

?

?

F. Axel and Marston in Bitland

time limit per test 5 seconds memory limit per test 256 megabytes input standard input output standard output

A couple of friends, Axel and Marston are travelling across the country of Bitland. There are?n?towns in Bitland, with some pairs of towns connected by one-directional roads. Each road in Bitland is either a pedestrian road or a bike road. There can be multiple roads between any pair of towns, and may even be a road from a town to itself. However, no pair of roads shares the starting and the destination towns along with their types simultaneously.

The friends are now located in the town 1 and are planning the travel route. Axel enjoys walking, while Marston prefers biking. In order to choose a route diverse and equally interesting for both friends, they have agreed upon the following procedure for choosing the road types during the travel:

• The route starts with a pedestrian route.
• Suppose that a beginning of the route is written in a string?s?of letters P (pedestrain road) and B (biking road). Then, the string??is appended to?s, where??stands for the string?s?with each character changed to opposite (that is, all pedestrian roads changed to bike roads, and vice versa).

In the first few steps the route will look as follows: P, PB, PBBP, PBBPBPPB, PBBPBPPBBPPBPBBP, and so on.

After that the friends start travelling from the town 1 via Bitlandian roads, choosing the next road according to the next character of their route type each time. If it is impossible to choose the next road, the friends terminate their travel and fly home instead.

Help the friends to find the longest possible route that can be travelled along roads of Bitland according to the road types choosing procedure described above. If there is such a route with more than?1018?roads in it, print -1 instead.

Input

The first line contains two integers?n?and?m?(1?≤?n?≤?500,?0?≤?m?≤?2n2)?— the number of towns and roads in Bitland respectively.

Next?m?lines describe the roads.?i-th of these lines contains three integers?vi,?ui?and?ti?(1?≤?vi,?ui?≤?n,?0?≤?ti?≤?1), where?vi?and?uidenote start and destination towns indices of the?i-th road, and?ti?decribes the type of?i-th road (0 for a pedestrian road, 1 for a bike road). It is guaranteed that for each pair of distinct indices?i,?j?such that?1?≤?i,?j?≤?m, either?vi?≠?vj, or?ui?≠?uj, or?ti?≠?tj?holds.

Output

If it is possible to find a route with length strictly greater than?1018, print -1. Otherwise, print the maximum length of a suitable path.

Examples input 2 2
1 2 0
2 2 1 output 3 input 2 3
1 2 0
2 2 1
2 2 0 output -1 Note

In the first sample we can obtain a route of length 3 by travelling along the road 1 from town 1 to town 2, and then following the road 2 twice from town 2 to itself.

In the second sample we can obtain an arbitrarily long route by travelling the road 1 first, and then choosing road 2 or 3 depending on the necessary type.

?

?

倍增 位運(yùn)算 bitset

博主當(dāng)然會(huì)做這種題啦，只要用心思考很快就能得出解法了。

——可是聽(tīng)說(shuō)博主的代碼是從standings榜上rank4那里抄來(lái)的，連變量名都沒(méi)怎么改就貼到博客上了呢 ?

——啊啊啊啊啊啊啊啊啊啊讀書(shū)人的事，怎么能算抄呢……是學(xué)習(xí)……學(xué)習(xí)！ ?

（好像有點(diǎn)熟悉）

用bitset存儲(chǔ)狀態(tài)，倍增以u(píng)為起點(diǎn)走2^k步可以到哪些點(diǎn)。

處理完?duì)顟B(tài)以后，從2^61開(kāi)始倒著貪心。

1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #include<bitset> 9 using namespace std; 10 const int mxn=510; 11 int read(){ 12 int x=0,f=1;char ch=getchar(); 13 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 14 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 15 return x*f; 16 } 17 bitset<502>f[2][65][mxn];//類型 倍增長(zhǎng)度 起始點(diǎn)=終點(diǎn) 18 bitset<502>p,q; 19 int n,m; 20 int main(){ 21 int i,j,u,v,w; 22 n=read();m=read(); 23 for(i=1;i<=m;i++){ 24 u=read();v=read();w=read(); 25 --u;--v; 26 f[w][0][u][v]=1; 27 } 28 for(int k=1;k<62;k++){ 29 for(i=0;i<n;i++){ 30 for(j=0;j<n;j++){ 31 if(f[0][k-1][i][j])f[0][k][i]|=f[1][k-1][j]; 32 if(f[1][k-1][i][j])f[1][k][i]|=f[0][k-1][j]; 33 } 34 } 35 } 36 for(i=0;i<n;i++) 37 if(f[0][61][0][i]){ 38 printf("-1\n");return 0; 39 } 40 bool tp=0; 41 long long ans=0; 42 p[0]=1; 43 for(int k=61;k>=0;k--){ 44 for(i=0;i<n;i++)q[i]=0; 45 for(j=0;j<n;j++)if(p[j]) q|=f[tp][k][j]; 46 if(q.any()){ 47 tp^=1; 48 ans+=(1LL<<k); 49 p=q; 50 } 51 } 52 if(ans>1e18)ans=-1; 53 printf("%I64d\n",ans); 54 return 0; 55 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/SilverNebula/p/6511368.html

總結(jié)

以上是生活随笔為你收集整理的CodeForces Round #403 (Div.2) A-F的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。