2017百度之星预赛B

自用笔记算法

2017百度之星预赛B

题目要求

車是中国象棋中的一种棋子，它能攻击同一行或同一列中没有其他棋子阻隔的棋子。一天，小度在棋盘上摆起了许多車……他想知道，
在一共N×M个点的矩形棋盘中摆最多个数的車使其互不攻击的方案数。他经过思考，得出了答案。但他仍不满足，想增加一个条件：对于任何一个車A，
如果有其他一个車B在它的上方（車B行号小于車A），那么車A必须在車B的右边（車A列号大于車B）。
现在要问问你，满足要求的方案数是多少。

第一行一个正整数T，表示数据组数。
对于每组数据：一行，两个正整数N和M（N<=1000，M<=1000）
对于每组数据输出一行，代表方案数模1000000007（1e9+7）。

参考AC代码(分块打表)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<bits/stdc++.h>
#define maxn 1050
#define LL long long 
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
const LL mod=1e9+7;
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
LL fac[] = {1, 641102369, 578095319, 5832229, 259081142, 974067448, 316220877, 690120224, 251368199, 980250487, 682498929, 
    134623568, 95936601, 933097914, 167332441, 598816162, 336060741, 248744620, 626497524, 288843364, 491101308, 245341950, 
    565768255, 246899319, 968999, 586350670, 638587686, 881746146, 19426633, 850500036, 76479948, 268124147, 842267748, 
    886294336, 485348706, 463847391, 544075857, 898187927, 798967520, 82926604, 723816384, 156530778, 721996174, 299085602, 
    323604647, 172827403, 398699886, 530389102, 294587621, 813805606, 67347853, 497478507, 196447201, 722054885, 228338256, 
    407719831, 762479457, 746536789, 811667359, 778773518, 27368307, 438371670, 59469516, 5974669, 766196482, 606322308, 86609485, 
    889750731, 340941507, 371263376, 625544428, 788878910, 808412394, 996952918, 585237443, 1669644, 361786913, 480748381, 
    595143852, 837229828, 199888908, 526807168, 579691190, 145404005, 459188207, 534491822, 439729802, 840398449, 899297830, 
    235861787, 888050723, 656116726, 736550105, 440902696, 85990869, 884343068, 56305184, 973478770, 168891766, 804805577, 
    927880474, 876297919, 934814019, 676405347, 567277637, 112249297, 44930135, 39417871, 47401357, 108819476, 281863274, 
    60168088, 692636218, 432775082, 14235602, 770511792, 400295761, 697066277, 421835306, 220108638, 661224977, 261799937, 
    168203998, 802214249, 544064410, 935080803, 583967898, 211768084, 751231582, 972424306, 623534362, 335160196, 243276029, 
    554749550, 60050552, 797848181, 395891998, 172428290, 159554990, 887420150, 970055531, 250388809, 487998999, 856259313, 
    82104855, 232253360, 513365505, 244109365, 1559745, 695345956, 261384175, 849009131, 323214113, 747664143, 444090941, 
    659224434, 80729842, 570033864, 664989237, 827348878, 195888993, 576798521, 457882808, 731551699, 212938473, 509096183, 
    827544702, 678320208, 677711203, 289752035, 66404266, 555972231, 195290384, 97136305, 349551356, 785113347, 83489485, 
    66247239, 52167191, 307390891, 547665832, 143066173, 350016754, 917404120, 296269301, 996122673, 23015220, 602139210, 
    748566338, 187348575, 109838563, 574053420, 105574531, 304173654, 542432219, 34538816, 325636655, 437843114, 630621321, 
    26853683, 933245637, 616368450, 238971581, 511371690, 557301633, 911398531, 848952161, 958992544, 925152039, 914456118, 
    724691727, 636817583, 238087006, 946237212, 910291942, 114985663, 492237273, 450387329, 834860913, 763017204, 368925948, 
    475812562, 740594930, 45060610, 806047532, 464456846, 172115341, 75307702, 116261993, 562519302, 268838846, 173784895, 
    243624360, 61570384, 481661251, 938269070, 95182730, 91068149, 115435332, 495022305, 136026497, 506496856, 710729672, 
    113570024, 366384665, 564758715, 270239666, 277118392, 79874094, 702807165, 112390913, 730341625, 103056890, 677948390,
     339464594, 167240465, 108312174, 839079953, 479334442, 271788964, 135498044, 277717575, 591048681, 811637561, 353339603, 
     889410460, 839849206, 192345193, 736265527, 316439118, 217544623, 788132977, 618898635, 183011467, 380858207, 996097969, 
     898554793, 335353644, 54062950, 611251733, 419363534, 965429853, 160398980, 151319402, 990918946, 607730875, 450718279, 
     173539388, 648991369, 970937898, 500780548, 780122909, 39052406, 276894233, 460373282, 651081062, 461415770, 358700839, 
     643638805, 560006119, 668123525, 686692315, 673464765, 957633609, 199866123, 563432246, 841799766, 385330357, 504962686, 
     954061253, 128487469, 685707545, 299172297, 717975101, 577786541, 318951960, 773206631, 306832604, 204355779, 573592106, 
     30977140, 450398100, 363172638, 258379324, 472935553, 93940075, 587220627, 776264326, 793270300, 291733496, 522049725, 
     579995261, 335416359, 142946099, 472012302, 559947225, 332139472, 499377092, 464599136, 164752359, 309058615, 86117128, 
     580204973, 563781682, 954840109, 624577416, 895609896, 888287558, 836813268, 926036911, 386027524, 184419613, 724205533, 
     403351886, 715247054, 716986954, 830567832, 383388563, 68409439, 6734065, 189239124, 68322490, 943653305, 405755338, 
     811056092, 179518046, 825132993, 343807435, 985084650, 868553027, 148528617, 160684257, 882148737, 591915968, 701445829, 
     529726489, 302177126, 974886682, 241107368, 798830099, 940567523, 11633075, 325334066, 346091869, 115312728, 473718967, 
     218129285, 878471898, 180002392, 699739374, 917084264, 856859395, 435327356, 808651347, 421623838, 105419548, 59883031, 
     322487421, 79716267, 715317963, 429277690, 398078032, 316486674, 384843585, 940338439, 937409008, 940524812, 947549662, 
     833550543, 593524514, 996164327, 987314628, 697611981, 636177449, 274192146, 418537348, 925347821, 952831975, 893732627, 
     1277567, 358655417, 141866945, 581830879, 987597705, 347046911, 775305697, 125354499, 951540811, 247662371, 343043237, 
     568392357, 997474832, 209244402, 380480118, 149586983, 392838702, 309134554, 990779998, 263053337, 325362513, 780072518, 
     551028176, 990826116, 989944961, 155569943, 596737944, 711553356, 268844715, 451373308, 379404150, 462639908, 961812918, 
     654611901, 382776490, 41815820, 843321396, 675258797, 845583555, 934281721, 741114145, 275105629, 666247477, 325912072, 
     526131620, 252551589, 432030917, 554917439, 818036959, 754363835, 795190182, 909210595, 278704903, 719566487, 628514947, 
     424989675, 321685608, 50590510, 832069712, 198768464, 702004730, 99199382, 707469729, 747407118, 302020341, 497196934, 
     5003231, 726997875, 382617671, 296229203, 183888367, 703397904, 552133875, 732868367, 350095207, 26031303, 863250534, 
     216665960, 561745549, 352946234, 784139777, 733333339, 503105966, 459878625, 803187381, 16634739, 180898306, 68718097, 
     985594252, 404206040, 749724532, 97830135, 611751357, 31131935, 662741752, 864326453, 864869025, 167831173, 559214642, 
     718498895, 91352335, 608823837, 473379392, 385388084, 152267158, 681756977, 46819124, 313132653, 56547945, 442795120, 
     796616594, 256141983, 152028387, 636578562, 385377759, 553033642, 491415383, 919273670, 996049638, 326686486, 160150665, 
     141827977, 540818053, 693305776, 593938674, 186576440, 688809790, 565456578, 749296077, 519397500, 551096742, 696628828, 
     775025061, 370732451, 164246193, 915265013, 457469634, 923043932, 912368644, 777901604, 464118005, 637939935, 956856710, 
     490676632, 453019482, 462528877, 502297454, 798895521, 100498586, 699767918, 849974789, 811575797, 438952959, 606870929,
     907720182, 179111720, 48053248, 508038818, 811944661, 752550134, 401382061, 848924691, 764368449, 34629406, 529840945, 
     435904287, 26011548, 208184231, 446477394, 206330671, 366033520, 131772368, 185646898, 648711554, 472759660, 523696723,
     271198437, 25058942, 859369491, 817928963, 330711333, 724464507, 437605233, 701453022, 626663115, 281230685, 510650790,
     596949867, 295726547, 303076380, 465070856, 272814771, 538771609, 48824684, 951279549, 939889684, 564188856, 48527183,
     201307702, 484458461, 861754542, 326159309, 181594759, 668422905, 286273596, 965656187, 44135644, 359960756, 936229527,
      407934361, 267193060, 456152084, 459116722, 124804049, 262322489, 920251227, 816929577, 483924582, 151834896, 167087470,
       490222511, 903466878, 361583925, 368114731, 339383292, 388728584, 218107212, 249153339, 909458706, 322908524, 
       202649964, 92255682, 573074791, 15570863, 94331513, 744158074, 196345098, 334326205, 9416035, 98349682, 882121662, 
       769795511, 231988936, 888146074, 137603545, 582627184, 407518072, 919419361, 909433461, 986708498, 310317874, 373745190, 
       263645931, 256853930, 876379959, 702823274, 147050765, 308186532, 175504139, 180350107, 797736554, 606241871, 384547635, 
       273712630, 586444655, 682189174, 666493603, 946867127, 819114541, 502371023, 261970285, 825871994, 126925175, 701506133,
        314738056, 341779962, 561011609, 815463367, 46765164, 49187570, 188054995, 957939114, 64814326, 933376898, 329837066, 
        338121343, 765215899, 869630152, 978119194, 632627667, 975266085, 435887178, 282092463, 129621197, 758245605, 827722926,
         201339230, 918513230, 322096036, 547838438, 985546115, 852304035, 593090119, 689189630, 555842733, 567033437, 
         469928208, 212842957, 117842065, 404149413, 155133422, 663307737, 208761293, 206282795, 717946122, 488906585, 414236650, 
         280700600, 962670136, 534279149, 214569244, 375297772, 811053196, 922377372, 289594327, 219932130, 211487466, 701050258, 
         398782410, 863002719, 27236531, 217598709, 375472836, 810551911, 178598958, 247844667, 676526196, 812283640, 863066876, 
         857241854, 113917835, 624148346, 726089763, 564827277, 826300950, 478982047, 439411911, 454039189, 633292726, 48562889,
         802100365, 671734977, 945204804, 508831870, 398781902, 897162044, 644050694, 892168027, 828883117, 277714559, 713448377,
         624500515, 590098114, 808691930, 514359662, 895205045, 715264908, 628829100, 484492064, 919717789, 513196123, 748510389,
        403652653, 574455974, 77123823, 172096141, 819801784, 581418893, 15655126, 15391652, 875641535, 203191898, 
        264582598, 880691101, 907800444, 986598821, 340030191, 264688936, 369832433, 785804644, 842065079, 423951674, 
        663560047, 696623384, 496709826, 161960209, 331910086, 541120825, 951524114, 841656666, 162683802, 629786193, 
        190395535, 269571439, 832671304, 76770272, 341080135, 421943723, 494210290, 751040886, 317076664, 672850561, 
        72482816, 493689107, 135625240, 100228913, 684748812, 639655136, 906233141, 929893103, 277813439, 814362881, 
        562608724, 406024012, 885537778, 10065330, 60625018, 983737173, 60517502, 551060742, 804930491, 823845496, 
        727416538, 946421040, 678171399, 842203531, 175638827, 894247956, 538609927, 885362182, 946464959, 116667533, 
        749816133, 241427979, 871117927, 281804989, 163928347, 563796647, 640266394, 774625892, 59342705, 256473217, 
        674115061, 918860977, 322633051, 753513874, 393556719, 304644842, 767372800, 161362528, 754787150, 627655552, 
        677395736, 799289297, 846650652, 816701166, 687265514, 787113234, 358757251, 701220427, 607715125, 245795606, 
        600624983, 10475577, 728620948, 759404319, 36292292, 491466901, 22556579, 114495791, 647630109, 586445753, 482254337,
        718623833, 763514207, 66547751, 953634340, 351472920, 308474522, 494166907, 634359666, 172114298, 865440961, 
        364380585, 921648059, 965683742, 260466949, 117483873, 962540888, 237120480, 620531822, 193781724, 213092254, 
        107141741, 602742426, 793307102, 756154604, 236455213, 362928234, 14162538, 753042874, 778983779, 25977209, 49389215,
        698308420, 859637374, 49031023, 713258160, 737331920, 923333660, 804861409, 83868974, 682873215, 217298111, 
        883278906, 176966527, 954913, 105359006, 390019735, 10430738, 706334445, 315103615, 567473423, 708233401, 48160594, 
        946149627, 346966053, 281329488, 462880311, 31503476, 185438078, 965785236, 992656683, 916291845, 881482632, 
        899946391, 321900901, 512634493, 303338827, 121000338, 967284733, 492741665, 152233223, 165393390, 680128316, 
        917041303, 532702135, 741626808, 496442755, 536841269, 131384366, 377329025, 301196854, 859917803, 676511002, 373451745, 
        847645126, 823495900, 576368335, 73146164, 954958912, 847549272, 241289571, 646654592, 216046746, 205951465, 3258987, 
        780882948, 822439091, 598245292, 869544707, 698611116, 0
};
const LL M=1e6;
LL get(LL x){
    if(x>=mod) return 0;
    if(x==0) return 1;
    LL res=fac[x/M]%mod;
    for(LL i=x/M*M+1;i<=x;i++){
        res=res*i%mod;
    }
    return res;
}
LL solve(int n,int m){
    LL a=get(m),b=get(n-m),c=get(n);
    a=qpow(a,mod-2),b=qpow(b,mod-2);
    return c%mod*a%mod*b%mod;
} 
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(n<m) swap(n,m);
        cout<<solve(n,m)<<endl;
    }
    return 0;
}

参考AC代码(暴力求阶乘)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const LL mod=1e9+7;
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
LL get(LL x){
    LL ans=1;
    while(x){
        ans=(ans*x)%mod;
        x--;
    }
    return ans;
}
LL solve(int n,int m){
    LL a=get(m),b=get(n-m),c=get(n);
    a=qpow(a,mod-2),b=qpow(b,mod-2);
    return a%mod*b%mod*c%mod;
} 
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(n<m) swap(n,m);
        cout<<solve(n,m)<<endl;
    }
    return 0;
}

参考AC代码(预处理组合数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
#define maxn 1005
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
const int mod=1e9+7;
int c[maxn][maxn];
void init(){
	mm(c,0);
	c[0][0]=1;
	for(int i=0;i<maxn;i++){
		c[i][0]=c[i][i]=1;
		for(int j=1;j<i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
	}
}
int main(){
//	freopen("input.txt","r",stdin);
	init();
	int t; scanf("%d",&t);
	while(t--){
		int n,m;
		scanf("%d%d",&n,&m);
		if(n<m) swap(n,m);
		printf("%d\n",c[n][m]);
	}
	return 0;
}

思路

由于向右的限制关系 实际答案为Cnm的组合数 则问题转换为组合数取模
思路一：可以解决nm过大的问题 此题其实不需要
思路二：暴力求阶乘 水过
思路一和思路二注意要求逆元
思路三：预处理组合数 当nm再大一两维就会mle

HDU 6115

题目要求

我们将A省简化为由N个城市组成，某些城市之间存在双向道路，而且A省的交通有一个特点就是任意两个城市之间都能通过道路相互到达，且在不重复经过城市的情况下
任意两个城市之间的到达方案都是唯一的聪明的你一定已经发现，这些城市构成了树这样一个结构。
现在百度陆续开了许许多多的子公司。每家子公司又会在各城市中不断兴建属于该子公司的办公室。
由于各个子公司之间经常有资源的流动，所以公司员工常常想知道，两家子公司间的最小距离。
我们可以把子公司看成一个由办公室组成的集合。那么两个子公司A和B的最小距离定义为min(dist(x，y))（x∈A，y∈B）其中dist(x，y)表示两个办公室之间的最短路径长度
现在共有Q个询问，每次询问分别在两个子公司间的最小距离

第一行一个正整数T，表示数据组数。
对于每组数据：
第一行两个正整数N和M。城市编号为1至N，子公司编号为1至M。
接下来N-1行给定所有道路的两端城市编号和道路长度。
接下来M行，依次按编号顺序给出各子公司办公室所在位置，每行第一个整数G，表示办公室数，接下来G个数为办公室所在位置。
接下来一个整数Q，表示询问数。
接下来Q行，每行两个正整数a,b(a不等于b），表示询问的两个子公司。
【数据范围】
0<=边权<=100
1<=N,M,Q,工厂总数<=100000
对于每个询问，输出一行，表示答案。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node{
    int to,w;
    node(int to,int w):to(to),w(w){}
};
vector<node>e[maxn];
vector<int>e2[maxn];
int n; 
int vis[maxn],deep[maxn],f[maxn],anc[maxn][25];
int dis[maxn];
void dfs(int x,int fa){
    anc[x][0]=f[x];
    for(int i=1;i<=20;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
    for(int i=0;i<e[x].size();i++){
        int next=e[x][i].to;
        if(next!=fa){
            f[next]=x;
            deep[next]=deep[x]+1;
            dfs(next,x);
        }
    }
}
int lca(int x,int y){
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=20;i>=0;i--) if(deep[anc[x][i]]>=deep[y]) x=anc[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--) if(anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
    return f[x];
}
void dfs2(int id){
    for(int i=0;i<e[id].size();i++){
        int next=e[id][i].to,ww=e[id][i].w;
        if(vis[next]) continue;
        dis[next]=dis[id]+ww;
        vis[next]=1;
        dfs2(next);
    }
}
int solve(int x,int y){
    int f=lca(x,y);
    int ans=dis[x]+dis[y]-2*dis[f];
    return ans;
}
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;i++) e[i].clear(),e2[i].clear();
        for(int i=1;i<=n-1;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            e[u].push_back(node(v,w));
            e[v].push_back(node(u,w));
        }
        memset(f,0,sizeof(f));
        memset(anc,0,sizeof(anc));
        memset(deep,0,sizeof(deep));
        deep[1]=1;
        dfs(1,0);
        memset(dis,0,sizeof(dis));
        memset(vis,0,sizeof(vis));
        vis[1]=1;
        dfs2(1);
        for(int i=1;i<=m;i++){
            int num; scanf("%d",&num);
            while(num--){
                int x; scanf("%d",&x);
                e2[i].push_back(x);
            }
        }
        int q;
        scanf("%d",&q);
        while(q--){
            int a,b;
            scanf("%d%d",&a,&b);
            int Min=inf;
            int len1=e2[a].size(),len2=e2[b].size();
            for(int i=0;i<len1;i++){
                for(int j=0;j<len2;j++){
                    int x=e2[a][i];
                    int y=e2[b][j];
                    Min=min(Min,solve(x,y));
                }
            }
            printf("%d\n",Min);
        }
    }
    return 0;
}

思路

暴力枚举子公司的办公室 问题就转换为求树上两点的最短距离 lca水过

HDU 6118

题目要求

度度熊参与了喵哈哈村的商业大会，但是这次商业大会遇到了一个难题：
喵哈哈村以及周围的村庄可以看做是一共由n个片区，m条公路组成的地区。
由于生产能力的区别，第i个片区能够花费a[i]元生产1个商品，但是最多生产b[i]个。
同样的，由于每个片区的购买能力的区别，第i个片区也能够以c[i]的价格出售最多d[i]个物品。
由于这些因素，度度熊觉得只有合理的调动物品，才能获得最大的利益。
据测算，每一个商品运输1公里，将会花费1元。
那么喵哈哈村最多能够实现多少盈利呢？

本题包含若干组测试数据。
每组测试数据包含：
第一行两个整数n,m表示喵哈哈村由n个片区、m条街道。
接下来n行，每行四个整数a[i],b[i],c[i],d[i]表示的第i个地区，能够以a[i]的价格生产，最多生产b[i]个，以c[i]的价格出售，最多出售d[i]个。
接下来m行，每行三个整数,u[i],v[i],k[i]，表示该条公路连接u[i],v[i]两个片区，距离为k[i]
可能存在重边，也可能存在自环。
满足:
1<=n<=500,
1<=m<=1000,
1<=a[i],b[i],c[i],d[i],k[i]<=1000,
1<=u[i],v[i]<=n
输出最多能赚多少钱。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
#define maxn 550
#define inf 0x3f3f3f3f
using namespace std;
struct Edge{
    int from,to,cap,flow,cost;
    Edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),flow(flow),cost(cost){}
};
struct MCMF{
    int n,m,s,t;
    vector<Edge>edges;
    vector<int>G[maxn];
    int inq[maxn],d[maxn],p[maxn],a[maxn];
    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++) G[i].clear();
        edges.clear();
    }
    void AddEdge(int from,int to,int cap,int cost){
        edges.push_back(Edge(from,to,cap,0,cost));
        edges.push_back(Edge(to,from,0,0,-cost));
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    bool BellmanFord(int s,int t,int &flow,int& cost){
        for(int i=0;i<n;i++) d[i]=inf;
        memset(inq,0,sizeof(inq));
        d[s]=0,inq[s]=1,p[s]=0,a[s]=inf;
        queue<int>Q;
        Q.push(s);
        while(!Q.empty()){
            int u=Q.front();  Q.pop();
            inq[u]=0;
            for(int i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(e.cap>e.flow && d[e.to]>d[u]+e.cost){
                    d[e.to]=d[u]+e.cost;
                    p[e.to]=G[u][i];
                    a[e.to]=min(a[u],e.cap-e.flow);
                    if(!inq[e.to]){
                        Q.push(e.to);
                        inq[e.to]=1;
                    }
                }
            }
        }
        if(d[t]>0) return false;
        flow+=a[t];
        cost+=d[t]*a[t];
        int u=t;
        while(u!=s){
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
            u=edges[p[u]].from;
        }
        return true;
    }
    int Mincost(int s,int t){
        int flow=0,cost=0;
        while(BellmanFord(s,t,flow,cost));
        return cost;
    }
}mc;
int main(){
//    freopen("input.txt","r",stdin);
    int nn,mm;
    while(scanf("%d%d",&nn,&mm)!=EOF){
        mc.init(maxn);
        int S=0,T=nn+1;
        for(int i=1;i<=nn;i++){
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            mc.AddEdge(S,i,b,a);
            mc.AddEdge(i,T,d,-c);
        }
        for(int i=1;i<=mm;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            mc.AddEdge(u,v,inf,w);
            mc.AddEdge(v,u,inf,w);
        }
        int ans=-mc.Mincost(S,T);
        printf("%d\n",ans);
    }
    return 0;
}

思路

流量不固定的s-t最小流裸题
注意流量增广为正时停止增广 城市和城市之间建双向边 因为可以双边贸易
注意a c w和ans的正负就好了

HDU 6119

题目要求

度度熊喜欢着喵哈哈村的大明星——星星小姐。
为什么度度熊会喜欢星星小姐呢？
首先星星小姐笑起来非常动人，其次星星小姐唱歌也非常好听。
但这都不是最重要的，最重要的是，星星小姐拍的一手好代码！
于是度度熊关注了星星小姐的贴吧。
一开始度度熊决定每天都在星星小姐的贴吧里面签到。
但是度度熊是一个非常健忘的孩子，总有那么几天，度度熊忘记签到，于是就断掉了他的连续签到。
不过度度熊并不是非常悲伤，因为他有m张补签卡，每一张补签卡可以使得某一忘签到的天，变成签到的状态。
那么问题来了，在使用最多m张补签卡的情况下，度度熊最多连续签到多少天呢？

本题包含若干组测试数据。
第一行两个整数n，m，表示有n个区间，这n个区间内的天数，度度熊都签到了；m表示m张补签卡。
接下来n行，每行两个整数(l[i],r[i])，表示度度熊从第l[i]天到第r[i]天，都进行了签到操作。
数据范围：
1<=n<=100000
0<=m<=1000000000
0<=l[i]<=r[i]<=1000000000
注意，区间可能存在交叉的情况。
输出度度熊最多连续签到多少天。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
#define maxn 100050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node{
    int l,r;
}pre[maxn],cur[maxn];
int cmp(node a,node b){
    if(a.l==b.l) return a.r<b.r;
    return a.l<b.l;
}
int main(){
//    freopen("input.txt","r",stdin);
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        mm(pre,0),mm(cur,0);
        for(int i=1;i<=n;i++) scanf("%d%d",&pre[i].l,&pre[i].r);
        sort(pre+1,pre+1+n,cmp);
        cur[1].l=pre[1].l,cur[1].r=pre[1].r;
        int num=1;
        for(int i=2;i<=n;i++){
            if(pre[i].l<=cur[num].r){
                if(pre[i].r>cur[num].r) cur[num].r=pre[i].r;
            }
            else{
                num++;
                cur[num].l=pre[i].l;
                cur[num].r=pre[i].r;
            }
        }
        int ans=cur[1].r-cur[1].l+1+m;
        int sum=0,f=1;
        for(int i=2;i<=num;i++){
            sum+=cur[i].l-cur[i-1].r-1;
            while(sum>m){
                sum-=cur[f+1].l-cur[f].r-1;
                f++;                             //f维护最左边的位置
            }
            ans=max(ans,cur[i].r-cur[f].l+1+m-sum);  //m-sum剩余还能签到的天数
        }
        printf("%d\n",ans);
    }
    return 0;
}

思路

区间排序后合并
每次去维护间隔 用m去补签 若间隔和大于m 则从左删去一些间隔保持间隔和小于sum 同时维护ans最大值
类似于一个最大窗口为m的单调队列

本文标题:2017百度之星预赛B

文章作者:Hippopmonkey

发布时间:2017-08-14, 10:41:03

最后更新:2017-08-14, 11:19:41

原始链接:http://xuboming8.github.io/2017/08/14/2017百度之星预赛B/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 2017百度之星预赛B
    1. 1.0.1. 题目要求
    2. 1.0.2. 参考AC代码(分块打表)
    3. 1.0.3. 参考AC代码(暴力求阶乘)
    4. 1.0.4. 参考AC代码(预处理组合数)
    5. 1.0.5. 思路
  2. 1.1. HDU 6115
    1. 1.1.1. 题目要求
    2. 1.1.2. 参考AC代码
    3. 1.1.3. 思路
  3. 1.2. HDU 6118
    1. 1.2.1. 题目要求
    2. 1.2.2. 参考AC代码
    3. 1.2.3. 思路
  4. 1.3. HDU 6119
    1. 1.3.1. 题目要求
    2. 1.3.2. 参考AC代码
    3. 1.3.3. 思路
|