您當前位置：首頁 > php開源 > php教程 > 【codeforces #292(div 1)】ABC題解

【codeforces #292(div 1)】ABC題解

來源：程序員人生發布時間：2015-04-11 09:30:18 閱讀次數：3408次

Drazil is playing a math game with Varda.

Let's define $\text{[math]}$ for positive integer x as a product of factorials of its digits. For example, $\text{[math]}$ .

First, they choose a decimal number a consisting of n digits that contains at least one digit larger than 1. This number may possibly start with leading zeroes. Then they should find maximum positive number x satisfying following two conditions:

1. x doesn't contain neither digit 0 nor digit 1.

2. $\text{[math]}$ = $\text{[math]}$ .

Help friends find such number.

Input

The first line contains an integer n (1?≤?n?≤?15) ― the number of digits in a.

The second line contains n digits of a. There is at least one digit in a that is larger than 1. Number a may possibly contain leading zeroes.

Output

Output a maximum possible integer satisfying the conditions above. There should be no zeroes and ones in this number decimal representation.

Sample test(s)

input
4
1234

output
33222

input
3
555

output
555

Note

In the first case, $\text{[math]}$

貪心：

首先把原數x計算F(x)后所含有的123456789都統計出來。

然后把9拆成3*3；8拆成2*2*2；6拆成2*3；4拆成2*2；剩下的5和7不能拆，只能直接算階乘。

最后就剩下了許多個3和許多個2了，此時31定比2少。

最后從大到小順次輸出7，5，3，2便可。

#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cstdlib> using namespace std; char s[20]; int ans[10],cnt[10],a[10]; int main() { int n; scanf("%d",&n); scanf("%s",s); for (int i=0;i<n;i++) { int x=s[i]-'0'; for (int j=2;j<=x;j++) cnt[j]++; } a[1]=7,a[2]=5; for (int i=1;i<=2;i++) if (cnt[a[i]]) { ans[a[i]]=cnt[a[i]]; for (int j=2;j<=a[i];j++) cnt[j]-=ans[a[i]]; } cnt[3]+=(cnt[9]*2); cnt[2]+=(cnt[8]*3); cnt[2]+=cnt[6],cnt[3]+=cnt[6]; cnt[2]+=(cnt[4]*2); ans[3]=cnt[3],cnt[2]-=cnt[3]; ans[2]=cnt[2]; a[1]=7,a[2]=5,a[3]=3,a[4]=2; for (int i=1;i<=4;i++) for (int j=1;j<=ans[a[i]];j++) cout<<a[i]; cout<<endl; return 0; }

Drazil created a following problem about putting 1?×?2 tiles into an n?×?m grid:

"There is a grid with some cells that are empty and some cells that are occupied. You should use 1?×?2 tiles to cover all empty cells and no two tiles should cover each other. And you should print a solution about how to do it."

But Drazil doesn't like to write special checking program for this task. His friend, Varda advised him: "how about asking contestant only to print the solution when it exists and it is unique? Otherwise contestant may print 'Not unique' ".

Drazil found that the constraints for this task may be much larger than for the original task!

Can you solve this new problem?

Note that you should print 'Not unique' either when there exists no solution or when there exists several different solutions for the original task.

Input

The first line contains two integers n and m (1?≤?n,?m?≤?2000).

The following n lines describe the grid rows. Character '.' denotes an empty cell, and the character '*' denotes a cell that is occupied.

Output

If there is no solution or the solution is not unique, you should print the string "Not unique".

Otherwise you should print how to cover all empty cells with 1?×?2 tiles. Use characters "<>" to denote horizontal tiles and characters "^v" to denote vertical tiles. Refer to the sample test for the output format example.

Sample test(s)

input
3 3
...
.*.
...

output
Not unique

input
4 4
..**
*...
*.**
....

output
<>**
*^<>
*v**
<><>

input
2 4
*..*
....

output
*<>*
<><>

input
1 1
.

output
Not unique

input
1 1
*

output
*

Note

In the first case, there are indeed two solutions:

<>^ ^*v v<>

and

^<> v*^ <>v

so the answer is "Not unique".

第1眼看到這道題心想：這不是染色+2分圖匹配嗎？

然后就開始想怎樣快速判斷是不是2分圖的完全匹配是不是唯1？？最后光榮的在第36個數據上T了。。（誰有快速的方法。。求告知vv）

看題解才知道，其實和2分圖匹配1點關系都沒有。。

有點類似于拓撲排序:能夠用同1個紙片覆蓋的格子連1條邊，把兩個格子的度數+1（兩個格子之間最多1條邊）。

掃描1次所有格子的度數，度數為1的加入隊列，那末這些格子所對應的與他們1塊被覆蓋的格子是唯1的，出隊以后把隊列中對應格子的對應格子度數⑴，度數為1的再次入隊。

如果隊列為空以后，所有格子都被覆蓋好了，那末此圖有且唯一1個解；如果有格子沒有被覆蓋好，直接輸出"Not unique"，可能無解，也可能多解（是哪一種就不用管了）

代碼中Judge注釋掉的部份是暴力用2分圖來判定的；輸出答案的部份直接用2分圖來做了。

#include <iostream> #include <algorithm> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> using namespace std; int b,w,xx,yy,n,m,t,ti,v[2005][2005],fx[10][3],in[2005][2005],a[2005][2005],p[2005][2005]; char x[10],s[2005]; struct data { int x,y; }my[2005][2005]; queue<data> q; bool dfs(int x,int y) { for (int i=1;i<=4;i++) { int nx=x+fx[i][1],ny=y+fx[i][2]; if (nx<1||ny<1||nx>n||ny>m||a[nx][ny]!=1||v[nx][ny]==t) continue; v[nx][ny]=t; if (!my[nx][ny].x||dfs(my[nx][ny].x,my[nx][ny].y)) { my[nx][ny].x=x,my[nx][ny].y=y; return true; } } return false; } bool dfs2(int x,int y,int k) { for (int i=1;i<=4;i++) { int nx=x+fx[i][1],ny=y+fx[i][2]; if (nx==xx&&ny==yy&&!k) continue; if (nx<1||ny<1||nx>n||ny>m||a[nx][ny]!=1||v[nx][ny]==t) continue; v[nx][ny]=t; if (!my[nx][ny].x||dfs2(my[nx][ny].x,my[nx][ny].y,1)) { my[nx][ny].x=x,my[nx][ny].y=y; return true; } } return false; } bool Judge() { /* for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (!a[i][j]) { t++; for (int k=1;k<=4;k++) { int nx=i+fx[k][1],ny=j+fx[k][2]; if (my[nx][ny].x==i&&my[nx][ny].y==j) xx=nx,yy=ny; } if (in[xx][yy]==1) continue; my[xx][yy].x=0; if (dfs2(i,j,0)) return false; my[xx][yy].x=i,my[xx][yy].y=j; } return true;*/ for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { v[i][j]=0; if (in[i][j]==1) { data x; x.x=i,x.y=j; q.push(x); } } while (!q.empty()) { data x=q.front(); q.pop(); if (v[x.x][x.y]) continue; v[x.x][x.y]=1; for (int i=1;i<=4;i++) { int nx=x.x+fx[i][1],ny=x.y+fx[i][2]; if (nx<1||ny<1||nx>n||ny>m||v[nx][ny]||a[nx][ny]==⑴) continue; v[nx][ny]=1; for (int j=1;j<=4;j++) { int nxx=nx+fx[j][1],nyy=ny+fx[j][2]; in[nxx][nyy]--; if (in[nxx][nyy]==1) { data X; X.x=nxx,X.y=nyy; q.push(X); } } } } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (a[i][j]!=⑴&&!v[i][j]) return false; return true; } void Print() { x[1]='*',x[2]='<',x[3]='>',x[4]='^',x[5]='v'; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (a[i][j]==1) { int x=my[i][j].x,y=my[i][j].y; if (x==i) { p[x][min(j,y)]=2,p[x][max(j,y)]=3; } else { p[min(x,i)][j]=4,p[max(x,i)][j]=5; } } for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { if (!p[i][j]) printf("*"); else printf("%c",x[p[i][j]]); } printf(" "); } } int main() { fx[1][1]=fx[2][1]=0,fx[1][2]=1,fx[2][2]=⑴; fx[3][2]=fx[4][2]=0,fx[3][1]=1,fx[4][1]=⑴; scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%s",s); for (int j=0;j<m;j++) { if (s[j]=='*') a[i][j+1]=⑴; else a[i][j+1]=1&(i+j+1); } } b=0,w=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { if (a[i][j]==1) { b++; for (int k=1;k<=4;k++) { int nx=i+fx[k][1],ny=j+fx[k][2]; if (nx<1||ny<1||nx>n||ny>m) continue; if (a[nx][ny]==0)in[i][j]++,in[nx][ny]++; } } if (!a[i][j]) w++; } if (w!=b) { puts("Not unique"); return 0; } int ans=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (!a[i][j]) { t++; if (dfs(i,j)) ans++; } if (ans!=w) { puts("Not unique"); return 0; } if (Judge()) { Print(); } else { puts("Not unique"); } return 0; }

Drazil is a monkey. He lives in a circular park. There are n trees around the park. The distance between the i-th tree and (i?+?1)-st trees is di, the distance between the n-th tree and the first tree is dn. The height of the i-th tree is hi.

Drazil starts each day with the morning run. The morning run consists of the following steps:

Drazil chooses two different trees
He starts with climbing up the first tree
Then he climbs down the first tree, runs around the park (in one of two possible directions) to the second tree, and climbs on it
Then he finally climbs down the second tree.

But there are always children playing around some consecutive trees. Drazil can't stand children, so he can't choose the trees close to children. He even can't stay close to those trees.

If the two trees Drazil chooses are x-th and y-th, we can estimate the energy the morning run takes to him as 2(hx?+?hy)?+?dist(x,?y). Since there are children on exactly one of two arcs connecting x and y, the distance dist(x,?y) between trees x and yis uniquely defined.

Now, you know that on the i-th day children play between ai-th tree and bi-th tree. More formally, if ai?≤?bi, children play around the trees with indices from range [ai,?bi], otherwise they play around the trees with indices from $\text{[math]}$ .

Please help Drazil to determine which two trees he should choose in order to consume the most energy (since he wants to become fit and cool-looking monkey) and report the resulting amount of energy for each day.

Input

The first line contains two integer n and m (3?≤?n?≤?105, 1?≤?m?≤?105), denoting number of trees and number of days, respectively.

The second line contains n integers d1,?d2,?...,?dn (1?≤?di?≤?109), the distances between consecutive trees.

The third line contains n integers h1,?h2,?...,?hn (1?≤?hi?≤?109), the heights of trees.

Each of following m lines contains two integers ai and bi (1?≤?ai,?bi?≤?n) describing each new day. There are always at least two different trees Drazil can choose that are not affected by children.

Output

For each day print the answer in a separate line.

Sample test(s)

input
5 3
2 2 2 2 2
3 5 2 1 4
1 3
2 2
4 5

output
12
16
18

input
3 3
5 1 4
5 1 4
3 3
2 2
1 1

output
17
22
11

線段樹/RMQ

首先復制1次，變環為鏈。

說說我的線段樹做法：

對1個區間，保護3個值：

ma: “ |____|”的最大值

L_:“|__”的最大值

_R:“__|”的最大值

然落后行區間合并甚么的就能夠了。

題解給出的是RMQ算法：

如果要求x-y這1段的值：(h[y]*2+d[1]+d[2]+d[3]+...d[y⑴])+(h[x]*2-d[1]-d[2]-d[3]-...-d[x⑴])

對第1部份記為A[y],第2部份記為B[x]，只要用RMQ求區間最大的A[]和B[]相加便可（可以證明順序1定不會反過來）

我的線段樹代碼（1開始數組開到20w會RE...）

#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #define LL long long #define M 2000000+5 using namespace std; struct data { int l,r; LL ma,l_,_r; }a[M*2]; int n,m; LL h[M],s[M],d[M],inf; data Push_up(data a,data b) { data c; c.l=a.l,c.r=b.r; c.ma=max(a.l_+b._r+d[a.r],max(a.ma,b.ma)); c.l_=max(b.l_,a.l_+s[b.r⑴]-s[a.r⑴]); c._r=max(a._r,b._r+s[a.r]-s[a.l⑴]); return c; } void Build(int x,int l,int r) { a[x].l=l,a[x].r=r; if (l==r) { a[x].ma=-inf; a[x].l_=a[x]._r=h[l]; return; } int m=(l+r)>>1; Build(x<<1,l,m); Build((x<<1)+1,m+1,r); a[x]=Push_up(a[x<<1],a[(x<<1)+1]); } data Get(int x,int l,int r) { if (l<=a[x].l&&r>=a[x].r) return a[x]; int m=(a[x].l+a[x].r)>>1; if (r<=m) return Get(x<<1,l,r); if (l>m) return Get((x<<1)+1,l,r); return Push_up(Get(x<<1,l,r),Get((x<<1)+1,l,r)); } int main() { inf=(LL)1e18; scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) cin>>d[i],d[n+i]=d[i]; for (int i=1;i<=n*2;i++) s[i]=s[i⑴]+d[i]; for (int i=1;i<=n;i++) cin>>h[i],h[i]*=2LL,h[n+i]=h[i]; Build(1,1,n*2); for (int i=1;i<=m;i++) { int l,r; scanf("%d%d",&l,&r); if (l<=r) cout<<Get(1,r+1,l⑴+n).ma<<endl; else cout<<Get(1,r+1,l⑴).ma<<endl; } return 0; }

感悟：

定式思惟太可怕。。。

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生

------分隔線----------------------------

上一篇 Spring發送郵件總結（附源碼）

下一篇 Codeforces 520D. Cubes 貪心模擬

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關注

欄目熱點

多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

【codeforces #292(div 1)】ABC題解