【TopCoder】SRM 680 DIV 2
1 class BearPair {
2 public:
3 int pos[26];
4
5 int bigDistance(string s) {
6 int len = s.length();
7 int mx = -1;
8
9 rep(i, 0, len) {
10 rep(j, 0, len) {
11 if (s[j]==s[i])
12 continue;
13
14 mx = max(mx, abs(j-i));
15 }
16 }
17
18 return mx;
19 }
20 };2.BearChairs의findPositions2.1제목은 한 식당을 묘사하는데 의자가 한 줄로 늘어서 1부터 충분하게 길다. N개의 요소가 있는 수조인atLeast는 i번째 고객이 그의 의자 번호가atLeast[i]보다 크기를 원한다고 밝혔다.또한 임의의 두 고객의 의자 간의 간격이 최소한 d이어야 하며 고객이 최종적으로 얻은 의자 번호는 작을수록 좋다.여기에는 고객의 요구가 질서정연하다.최종 의자 번호를 구하다.2.2 기본적인 사고방식은 욕심이다. 첫 번째 고객이 가장 좋은 가능성은atLeast[k]번호를 받은 의자이다.만약 이때 이 고객과 전 k-1개 고객의 간격이 d보다 크다면 답은atLeast[k]이다.만약에 만족하지 않는다면 만약에 우리가 전 k-1개 고객의 의자 번호를 승차순으로 배열할 수 있다면 answer[j]-d
1 class BearChairs {
2 public:
3 static const int maxn = 1005;
4
5 vi findPositions(vi vc, int d) {
6 int sz = SZ(vc), tmp;
7 vi ret;
8 sti st;
9 sti::iterator iter;
10
11 rep(i, 0, sz) {
12 int pos = vc[i];
13 for (iter=st.begin(); iter!=st.end(); ++iter) {
14 tmp = *iter;
15 if (tmp-d<pos && pos<tmp+d) {
16 pos = tmp + d;
17 }
18 }
19
20 ret.pb(pos);
21 st.insert(pos);
22 }
23
24 return ret;
25 }
26
27 }; 2.4 데이터 발생기
1 import sys
2 import string
3 from random import randint
4
5
6 def GenData(fileName):
7 with open(fileName, "w") as fout:
8 t = 1
9 bound = 10**6
10 # fout.write("%d
" % (t))
11 for tt in xrange(t):
12 n = randint(1, 1000)
13 atLeast = []
14 for i in xrange(n):
15 x = randint(1, bound)
16 atLeast.append(x)
17 fout.write(" ".join(map(str, atLeast)) + "
")
18 d = randint(1, 10**6)
19 fout.write("%d
" % (d))
20
21
22 def MovData(srcFileName, desFileName):
23 with open(srcFileName, "r") as fin:
24 lines = fin.readlines()
25 with open(desFileName, "w") as fout:
26 fout.write("".join(lines))
27
28
29 def CompData():
30 print "comp"
31 srcFileName = "F:\Qt_prj\hdoj\data.out"
32 desFileName = "F:\workspace\cpp_hdoj\data.out"
33 srcLines = []
34 desLines = []
35 with open(srcFileName, "r") as fin:
36 srcLines = fin.readlines()
37 with open(desFileName, "r") as fin:
38 desLines = fin.readlines()
39 n = min(len(srcLines), len(desLines))-1
40 for i in xrange(n):
41 ans2 = int(desLines[i])
42 ans1 = int(srcLines[i])
43 if ans1 > ans2:
44 print "%d: wrong" % i
45
46
47 if __name__ == "__main__":
48 srcFileName = "F:\Qt_prj\hdoj\data.in"
49 desFileName = "F:\workspace\cpp_hdoj\data.in"
50 GenData(srcFileName)
51 MovData(srcFileName, desFileName)
52
53 3. BearFair2의 isFair3.1제목은 n(n%3==0)개의 원소를 포함하는 집합을 설명하는데 그 중의 원소는 모두 [1,b] 구간에 있는데 그 중에서mod3은 0,1,2의 원소 개수는 모두 n/3이다.기존의 두 길이는 모두 q수 그룹 upTo이고 quantity는 집합 중의 원소가 구간 [1, upTo[i]에 있는 수량이 quantity[i]임을 나타낸다.이 집합이 upTo와 Quantity를 충족시키는지 여부를 판정합니다.그 중에서 upTo의 원소는 [1,b] 구간에 있고quantity의 원소는 [1,n] 구간에 있고 b는 구간[11000] 안에 있다.3.2 기본적인 사고방식은 판정 문제이다. 먼저 upTo를first로 하고 Quantity를second로pair수조를 재구성하여 정렬한 후에 초보적인 가지치기를 할 수 있다.그러나 이런 집합이 존재하는지 아닌지는 한층 더 판정해야 한다.기본적인 사고방식은 네트워크 흐름이고 어려운 점은 어떻게 그림을 구축하는가이다.pair 트리 그룹의 매 결점 번호 1001...1001+q-1 대 1...b 번호 1...b대%3==0 결점mod0 대%3==1 결점mod1 대%3==2 결점mod2는 이렇게 그림을 만들 수 있다. 1)st는pair 결점에 가장자리를 만들고 용량은 대응하는quantity[i]-quantity[i-1]이다.2)pair결점은 그것이 포함하는 구간의 각 결점에 대해 변을 만들고 용량은 1이다.3)번호 1...b에 대응하는modx의 경계를 구축하고 용량은 1이다.4)modx는 ed에 대한 경계를 구축하고 용량은 n/3이다.pair수 그룹이 [1,b]를 덮어쓰지 않았을 수도 있고 나머지 구간에 대해 경계를 만들어야 합니다. 위와 유사합니다.그리고 최대 흐름이 n인지 아닌지를 판정하면 된다.Dinic을 사용하여 네트워크 흐름을 해결합니다.3.3 코드
1 class BearFair2 {
2
3 typedef struct {
4 int v, f, nxt;
5 } edge_t;
6
7 public:
8 static const int INF = 0x3f3f3f3f;
9 static const int maxv = 1100;
10 static const int maxe = 1e5+5;
11 static const int st = maxv - 1;
12 static const int ed = maxv - 2;
13 static const int mod0 = maxv - 3;
14 static const int mod1 = maxv - 4;
15 static const int mod2 = maxv - 5;
16
17 int head_[maxv];
18 int head[maxv], l;
19 int Q[maxv];
20 int dis[maxv];
21 edge_t E[maxe];
22 int n, b;
23
24 void init() {
25 memset(head, -1, sizeof(head));
26 l = 0;
27 }
28
29 void addEdge(int u, int v, int c) {
30 E[l].v = v;
31 E[l].f = c;
32 E[l].nxt = head[u];
33 head[u] = l++;
34
35 E[l].v = u;
36 E[l].f = 0;
37 E[l].nxt = head[v];
38 head[v] = l++;
39 }
40
41 bool bfs() {
42 int l = 0, r = 0;
43 int u, v, k;
44
45 memset(dis, 0, sizeof(dis));
46 Q[r++] = st;
47 dis[st] = 1;
48
49 while (l < r) {
50 u = Q[l++];
51 for (k=head[u]; k!=-1; k=E[k].nxt) {
52 v = E[k].v;
53 if (E[k].f && !dis[v]) {
54 dis[v] = dis[u] + 1;
55 if (v == ed)
56 return false;
57 Q[r++] = v;
58 }
59 }
60 }
61
62 return true;
63 }
64
65 int dfs(int u, int val) {
66 if (val==0 || u==ed)
67 return val;
68
69 int ret = 0, tmp;
70 int v;
71
72 for (int& k=head_[u]; k!=-1; k=E[k].nxt) {
73 v = E[k].v;
74 if (E[k].f && dis[v]==dis[u]+1 && (tmp=dfs(v, min(val, E[k].f)))>0) {
75 ret += tmp;
76 val -= tmp;
77 E[k].f -= tmp;
78 E[k^1].f += tmp;
79 if (val == 0)
80 break;
81 }
82 }
83
84 return ret;
85 }
86
87 int Dinic() {
88 int ret = 0, tmp;
89
90 while (1) {
91 if (bfs())
92 break;
93
94 memcpy(head_, head, sizeof(head));
95 while (1) {
96 tmp = dfs(st, INF);
97 if (tmp == 0)
98 break;
99 ret += tmp;
100 }
101 }
102
103 return ret;
104 }
105
106 string isFair(int n, int b, vector <int> upTo, vector <int> quan) {
107 this->n = n;
108 this->b = b;
109 init();
110
111 vpii vp;
112 int sz = SZ(upTo);
113
114 rep(i, 0, sz) {
115 vp.pb(mp(upTo[i], quan[i]));
116 }
117
118 sort(all(vp));
119 rep(i, 0, sz) {
120 if (vp[i].sec > vp[i].sec)
121 return "unfair";
122
123 if (i && vp[i].sec<vp[i-1].sec)
124 return "unfair";
125
126 if (i && vp[i].fir==vp[i-1].fir && vp[i].sec!=vp[i-1].sec)
127 return "unfair";
128 }
129
130 int fr = 1, pm = 0;
131
132 rep(i, 0, sz) {
133 addEdge(st, 1001+i, vp[i].sec-pm);
134 while (fr <= vp[i].fir) {
135 addEdge(1001+i, fr, 1);
136 ++fr;
137 }
138 pm = vp[i].sec;
139 }
140
141 if (fr <= b) {
142 addEdge(st, 1001+sz, n-pm);
143 while (fr <= b) {
144 addEdge(1001+sz, fr, 1);
145 ++fr;
146 }
147 }
148
149 for (int i=1; i<=b; i+=3)
150 addEdge(i, mod1, 1);
151 for (int i=2; i<=b; i+=3)
152 addEdge(i, mod2, 1);
153 for (int i=3; i<=b; i+=3)
154 addEdge(i, mod0, 1);
155
156 addEdge(mod0, ed, n/3);
157 addEdge(mod1, ed, n/3);
158 addEdge(mod2, ed, n/3);
159
160 int flow = 0;
161
162 flow = Dinic();
163 if (flow == n)
164 return "fair";
165 else
166 return "unfair";
167 }
168 };3.4 데이터 발생기
1 import sys
2 import string
3 from random import randint
4
5
6 def GenData(fileName):
7 with open(fileName, "w") as fout:
8 t = 1
9 bound = 10**6
10 # fout.write("%d
" % (t))
11 for tt in xrange(t):
12 n = randint(1, 16) * 3
13 b = randint(1, n)
14 fout.write("%d %d
" % (n, b))
15 q = randint(1, 50)
16 upTo = []
17 for i in xrange(q):
18 x = randint(1, b)
19 upTo.append(x)
20 fout.write(" ".join(map(str, upTo)) + "
")
21 quantity = []
22 for i in xrange(q):
23 x = randint(0, n)
24 quantity.append(x)
25 fout.write(" ".join(map(str, quantity)) + "
")
26
27
28 def MovData(srcFileName, desFileName):
29 with open(srcFileName, "r") as fin:
30 lines = fin.readlines()
31 with open(desFileName, "w") as fout:
32 fout.write("".join(lines))
33
34
35 def CompData():
36 print "comp"
37 srcFileName = "F:\Qt_prj\hdoj\data.out"
38 desFileName = "F:\workspace\cpp_hdoj\data.out"
39 srcLines = []
40 desLines = []
41 with open(srcFileName, "r") as fin:
42 srcLines = fin.readlines()
43 with open(desFileName, "r") as fin:
44 desLines = fin.readlines()
45 n = min(len(srcLines), len(desLines))-1
46 for i in xrange(n):
47 ans2 = int(desLines[i])
48 ans1 = int(srcLines[i])
49 if ans1 > ans2:
50 print "%d: wrong" % i
51
52
53 if __name__ == "__main__":
54 srcFileName = "F:\Qt_prj\hdoj\data.in"
55 desFileName = "F:\workspace\cpp_hdoj\data.in"
56 GenData(srcFileName)
57 MovData(srcFileName, desFileName)
58
59 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
