Untitled
unknown
plain_text
2 years ago
11 kB
14
Indexable
Tan cong thanh tri
#include<iostream>
using namespace std;
int inf = 1000000;
int mayBD[105];
int A[105][105];
int visit[105];
int n;
int ans;
bool flag;
void dfs(int tempThanh, int thanh, int sl, int min, int d1, int d2){
if ( tempThanh == thanh && sl >= 3){
flag = true;
ans += min;
A[d1][d2] = 0;
A[d2][d1] = 0;
return;
}
for(int col =0; col< n; col++){
if (flag) return;
if (A[tempThanh][col] == 1 && (!visit[col] || (col == thanh && sl >= 3))){
visit[col] = 1;
int value = mayBD[tempThanh] + mayBD[col];
if( min > value) {
dfs(col,thanh,sl+1,value, tempThanh, col);
} else{
dfs(col,thanh,sl+1,min,d1,d2);
}
}
}
}
int main(){
freopen("input.txt", "r", stdin);
int T;
cin>>T;
for ( int tc = 1; tc <= T; tc++) {
cin>>n;
for( int i = 0; i< n; i++){
for( int j = 0; j<n; j++){
A[i][j] = 0;
}
}
int thanh, soMayBD,slKe, tempThanh;
for (int i = 0; i<n; i++) {
cin>>thanh>>soMayBD>>slKe;
mayBD[thanh] = soMayBD;
for(int k = 0; k< slKe; k++){
cin>>tempThanh;
A[thanh][tempThanh] = 1;
A[tempThanh][thanh] = 1;
}
}
ans = 0;
for(int thanh = 0; thanh <n; thanh++){
for( int i = 0; i<n; i++) {
visit[i] = 0;
}
visit[thanh] = 1;
flag = false;
dfs(thanh, thanh, 1, inf, -1, -1);
while(flag){
for( int i = 0; i<n; i++) {
visit[i] = 0;
}
visit[thanh] = 1;
flag = false;
dfs(thanh, thanh, 1, inf, -1, -1);
}
}
cout<<ans<<endl;
}
return 0;
}
Tiết kiệm điện
Văn phòng APS hiện tại đang có N bóng đèn và có K khóa. Các khóa được nối vào các bóng đèn theo quy luật như sau:
Khóa thứ K sẽ được nối vào các bóng đèn thứ K+n(K+1) (n>=0; 0<=K+n(K+1) <=N).
Ví dụ:
Khóa thứ 1 sẽ nối vào các bóng đèn số 1, 3, 5, 7,9…
Khóa thứ 2 sẽ nối vào các bóng đèn số 2, 5, 8, 11,…
Khóa thứ 3 sẽ nối vào các bóng đèn số 3, 7, 11, 15,…
Nếu khóa thứ k được thay đổi trạng thái, tất cả các bóng đèn đang nối với khóa k sẽ chuyển trạng thái (Bật->Tắt, tắt->bật).
Có một quy định được ban hành trong APS P: Nhân viên rời văn phòng cuối cùng phải có trách nhiệm tắt đèn trong văn phòng sao cho số lượng bóng đèn được tắt là lớn nhất. Tuy nhiên để thử thách tư duy của các nhân viên, nhân viên rời văn phòng cuối đó chỉ được phép thay đổi trạng thái khóa tối đa 3 lần, mỗi lần được chọn tối đa 1 khóa.
Hãy tạo một chương trình giúp các nhân viên tìm ra phương án tối ưu để tắt đèn với tối đa 3 lần tác động vào khóa^.^
Input:
Dòng 1 chứa số T là số TC.
Mỗi testcase bao gồm các thông tin sau:
- Dòng đầu tiên chứa số lượng bóng đèn N và số Khóa K (10<=N<=100, 3<=K<=10);
- Dòng tiếp theo là N bóng đèn, mỗi bóng đèn nhận 1 trong 2 trạng thái: 1 là bật, 0 là tắt.
OutPut:
In ra số lượng bóng đèn tối đa có thể tắt tại mỗi case.
Đáp số của mỗi TC in ra trên 1 dòng theo định dạng:
# TC Answer
Ví dụ:
Input
1
10 3 (10 bóng đèn và 3 khóa)
0 0 1 1 1 1 0 0 1 0 (lần lượt là 10 trạng thái của 10 bóng đèn, 1 là đang bật, 0 là đang tắt)
Output:
#1 6
Giải thích: Chọn tác động vào công tắc thứ 1, các bóng đèn sau sẽ bị thay đổi trạng thái:1 3 5 7 9
Stt bóng đèn 1 2 3 4 5 6 7 8 9 10
Ban đầu 0 0 1 1 1 1 0 0 1 0
Sau khi tác động vào khóa 1 1 0 0 1 0 1 1 0 0 0
#include <iostream>
using namespace std;
int N,K;
int Status[200];
int temp[200];
int Max;
int A[100];
int check[100];
int B[100];
int tinhTong(int TT[])
{
int sum = 0;
for(int i=1;i<=N;i++)
if(TT[i] == 0) sum++;
return sum;
}
void Update(int k, int TT[])
{
for(int i=k;i<=N;i=i+k+1)
{
TT[i] = 1 - TT[i];
}
}
//sinh chuoi nhi phan do dai 3
void BT(int k)
{
for(int i = 0 ;i<=1;i++)
{
B[k] = i;
if(k==3)
{
for(int i=1;i<=N;i++)
temp[i] = Status[i];
if(B[1] == 0 && B[2] == 0 && B[3] == 0) continue;
if(B[1] == 1) Update(A[1],temp);
if(B[2] == 1) Update(A[2],temp);
if(B[3] == 1) Update(A[3],temp);
int sum = tinhTong(temp);
if(sum>Max) Max = sum;
}
else BT(k+1);
}
}
//sinh tap con 3 phan tu cua K phan tu
void Try(int i)
{
for (int j = A[i - 1] + 1; j <= (K - 3 + i); j++)
{
A[i] = j;
if (i == 3)
{
BT(1);
}
else Try(i + 1);
}
}
int main()
{
//freopen("input.txt","r",stdin);
int tc;
cin>>tc;
for(int tci =1; tci<=tc; tci++)
{
cin>>N>>K;
Max = 0;
for(int i=1;i<=N;i++)
{
cin>>Status[i];
if(Status[i] == 0) Max++;
}
for(int i=0;i<=N;i++)
check[i] = 0;
A[0] = 0;
Try(1);
cout<<"#"<<tci<<" "<<Max<<endl;
}
}
100 9
0 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 0 1 0 1 1 1 0
96 5
0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 0 1 0 1
89 3
1 1 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0 0 1 1 0 1 1 1 1 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 1
14 3
1 1 0 1 0 1 0 0 1 1 1 0 1 0
84 6
0 0 0 0 1 1 0 1 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 1 1 0 0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1
43 3
0 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 0 0 0 0 0 1
62 9
1 1 1 0 1 0 1 1 0 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0
73 6
0 1 0 1 1 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 1 1 0 0 0 1 1 0 1
67 5
0 0 0 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 1 1 1 0 0
46 8
1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0
23 7
1 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0
Output
#1 59
#2 57
#3 48
#4 9
#5 53
#6 23
#7 41
#8 42
#9 43
#10 30
#11 16
#12 37
#13 42
#14 17
#15 15
#16 39
#17 12
#18 17
#19 51
#20 25
#21 17
#22 39
#23 32
#24 17
#25 18
#26 19
#27 9
#28 48
#29 53
#30 35
#31 13
#32 52
#33 41
#34 40
#35 24
#36 40
#37 53
#38 22
#39 28
#40 39
#41 40
#42 14
#43 62
#44 37
#45 59
#46 32
#47 19
#48 10
#49 46
#50 49
#51 36
#52 29
#53 50
#54 33
#55 26
#56 45
#57 34
#58 8
#59 36
#60 21
#61 56
#62 67
#63 35
#64 43
#65 56
#66 46
#67 46
#68 10
#69 22
#70 23
#71 9
#72 41
#73 21
#74 24
#75 49
#76 54
#77 40
#78 13
#79 45
#80 58
#81 44
#82 33
#83 22
#84 50
#85 15
#86 48
#87 30
#88 51
#89 49
#90 44
#91 24
#92 18
#93 32
#94 47
#95 44
#96 53
#97 10
#98 33
#99 41
#100 49
#101 33
#102 31
#103 27
#104 63
#105 16
#106 24
#107 27
#108 48
#109 16
#110 48
#111 18
#112 43
#113 32
#114 29
#115 15
#116 13
#117 51
#118 53
#119 42
#120 48
#121 44
#122 55
#123 24
#124 6
#125 41
#126 58
#127 47
#128 36
#129 37
#130 19
#131 31
#132 49
#133 32
#134 28
#135 48
#136 39
#137 43
#138 7
#139 16
#140 22
#141 56
#142 11
#143 21
#144 33
#145 60
#146 40
#147 35
#148 41
#149 39
#150 37
#151 57
#152 49
#153 47
#154 21
#155 12
#156 38
#157 24
#158 43
#159 41
#160 30
#161 21
#162 10
#163 14
#164 42
#165 49
#166 51
#167 33
#168 46
#169 29
#170 58
#171 23
#172 29
#173 15
#174 21
#175 38
#176 20
#177 21
#178 18
#179 20
#180 25
#181 15
#182 47
#183 12
#184 42
#185 43
#186 25
#187 53
#188 54
#189 58
#190 20
#191 9
#192 34
#193 35
#194 41
#195 55
#196 7
#197 52
#198 10
#199 17
#200 21
#201 17
#202 17
#203 16
#204 54
#205 30
#206 53
#207 54
#208 56
#209 28
#210 13
#211 21
#212 34
#213 50
#214 33
#215 7
#216 41
#217 45
#218 40
#219 22
#220 23
#221 48
#222 21
#223 56
#224 40
#225 11
#226 47
#227 46
#228 27
#229 68
#230 25
#231 28
#232 24
#233 43
#234 15
#235 47
#236 22
#237 22
#238 24
#239 29
#240 48
#241 55
#242 19
#243 24
#244 51
#245 43
#246 41
#247 10
#248 40
#249 20
#250 57
#251 37
#252 62
#253 21
#254 26
#255 34
#256 57
#257 27
#258 9
#259 10
#260 22
#261 53
#262 47
#263 27
#264 56
#265 63
#266 24
#267 45
#268 51
#269 52
#270 49
#271 14
#272 17
#273 31
#274 11
#275 14
#276 12
#277 42
#278 57
#279 50
#280 34
#281 46
#282 56
#283 24
#284 46
#285 34
#286 24
#287 24
#288 58
#289 58
#290 41
#291 20
#292 28
#293 24
#294 50
#295 57
#296 51
#297 31
#298 18
#299 28
#300 32
#301 25
#302 48
#303 59
#304 38
#305 21
#306 57
#307 25
#308 55
#309 51
#310 46
#311 38
#312 24
#313 56
#314 11
#315 35
#316 11
#317 51
#318 18
#319 13
#320 33
#321 17
#322 34
#323 59
#324 42
#325 10
#326 38
#327 31
#328 46
#329 54
#330 53
#331 13
#332 46
#333 20
#334 26
#335 50
#336 48
#337 14
#338 33
#339 25
#340 36
#341 10
#342 16
#343 52
#344 26
#345 17
#346 35
#347 34
#348 46
#349 52
#350 43
#351 30
#352 34
#353 63
#354 47
#355 36
#356 44
#357 27
#358 25
#359 24
#360 27
#361 55
#362 53
#363 54
#364 32
#365 8
#366 19
#367 23
#368 21
#369 8
#370 55
#371 42
#372 23
#373 54
#374 15
#375 53
#376 18
#377 27
#378 29
#379 11
#380 32
#381 52
#382 18
#383 38
#384 38
#385 22
#386 25
#387 30
#388 39
#389 60
#390 41
#391 44
#392 17
#393 21
#394 29
#395 9
#396 36
#397 35
#398 38
#399 33
#400 50
#401 18
#402 18
#403 64
#404 48
#405 20
#406 22
#407 18
#408 41
#409 26
#410 60
#411 55
#412 44
#413 44
#414 15
#415 44
#416 12
#417 47
#418 32
#419 42
#420 67
#421 13
#422 48
#423 24
#424 38
#425 58
#426 19
#427 10
#428 8
#429 28
#430 25
#431 31
#432 50
#433 9
#434 37
#435 15
#436 22
#437 30
#438 29
#439 32
#440 20
#441 13
#442 15
#443 39
#444 23
#445 20
#446 33
#447 35
#448 58
#449 39
#450 14
#451 26
#452 38
#453 29
#454 47
#455 38
#456 60
#457 29
#458 11
#459 41
#460 19
#461 18
#462 52
#463 19
#464 22
#465 43
#466 11
#467 24
#468 23
#469 36
#470 11
#471 56
#472 32
#473 28
#474 41
#475 46
#476 33
#477 11
#478 56
#479 46
#480 13
#481 38
#482 24
#483 28
#484 43
#485 36
#486 34
#487 25
#488 53
#489 51
#490 9
#491 9
#492 48
#493 9
#494 15
#495 44
#496 40
#497 21
#498 38
#499 11
#500 29
Editor is loading...