题目 P5289 [十二省联考 2019] 皮配 - 洛谷 | 计算机科学教育新生态
参考题解 题解-十二省联考2019 皮配 - oier_hzy - 博客园
(第一次写这么难的题, 看着题解才勉强能写出来)
不考虑讨厌的导师, 超时的写法
设F[i][j] 为考虑完当前城市时, 选择蓝派系i人, 鸭派系j人的方案数
设两个辅助数组 P,G, P是如果当前城市选择蓝派系的方案数, G是当前城市选择红派系的方案数, citysum[zo]是当前城市的总人数,枚举当前城市中的每个学校, 如果当前学校是当前城市的第一个, 如果当前学校选择R派系P[i][j] += F[i - citysum[zo]][j],如果当前学校选择鸭派系P[i][j]+= F[i - citysum[zo]][j - s[it]] ,P[i][j] = F[i - citysum[zo]][j] + F[i - citysum[zo]][j - s[it]]; 若当前学校不是城市中的第一个学校 P[i][j] = P[i][j] + P[i][j - s[it]] 使数组G = F, 对于数组G来说G[i][j] = G[i][j] + G[i][j - s[it]], 最后F[i][j] = P[i][j] + G[i][j]即为考虑完当前城市的方案数
最后整合答案, 因为选择红派系的人数不能超过c1, 即为i >= all - c1,i还要满足 i <= c0,同理, all - d1 <= j <= d0
void solve(){int n, c;cin >> n >> c;int c0,c1,d0,d1;cin >> c0 >> c1 >> d0 >> d1;vector<int> s(n + 1), b(n + 1);vector<int> citysum(c + 1);vector<vector<int>> citysch(c + 1);int all = 0;for(int i = 1; i <= n; i++) cin >> b[i] >> s[i], citysum[b[i]] += s[i], citysch[b[i]].push_back(i), all += s[i];int k;cin >> k;while(k --){int x, y;cin >> x >> y;}vector<vector<int>> F(c0 + 1, vector<int> (d0 + 1)); F[0][0] = 1;for(int zo = 1; zo <= c; zo++) {if(citysch[zo].empty()) continue;vector<vector<int>> P(c0 + 1, vector<int> (d0 + 1)),G(c0 + 1, vector<int> (d0 + 1));for(auto it : citysch[zo]) {if(it == citysch[zo].front()) {for(int i = citysum[zo]; i <= c0; i++) {for(int j = 0; j <= d0; j++) {P[i][j] = F[i - citysum[zo]][j];if(j >= s[it]) P[i][j] = (P[i][j] + F[i - citysum[zo]][j - s[it]]) % mod;}}continue;}for(int i = 0; i <= c0; i++) {for(int j = d0; j >= s[it]; j--) P[i][j] = (P[i][j] + P[i][j - s[it]]) % mod;// 0;}}G = F;for(auto it : citysch[zo]) {for(int i = 0; i <= c0; i++) {for(int j = d0; j >= s[it]; j--) G[i][j] = (G[i][j] + G[i][j - s[it]]) % mod; }}for(int i = 0; i <= c0; i++) {for(int j = 0; j <= d0; j++) F[i][j] = ((P[i][j] + G[i][j]) % mod + mod) % mod;}}int ans = 0;for(int i = max(0, all - c1); i <= c0; i++){for(int j = max(0,all - d1); j <= d0; j++) ans = (ans + F[i][j]) % mod/*, cout << F[i][j] << ' '*/;}cout << ans << endl;
}
考虑优化时间
一个学校选择是红蓝派系 , 鸭R派系是独立的, 所以分开考虑
设f[i]为选择蓝派系人数为i的方案数, g[j]为选择鸭派系为j的方案数
枚举每个城市 f[i] += f[i - citysum[zo]], 枚举每个学校 g[i] += g[i - s[j]]
对于f来说 all - c1<= i <= c0是满足条件的 g来说 all - d1 <= j <= d0 是满足条件的
答案即为(pre_f[c0] - pre_f[all - c1 - 1]) * (pre_g[d0] - pre_g[all - d0 - 1]);
考虑上讨厌的导师
记录每个城市是否有讨厌的导师, 每个学校是否有讨厌的导师
对于没有讨厌导师的城市 还用上一个优化时间的f的求法, 对于没有讨厌老师的学校, 也用g的求法
对于有讨厌的导师的城市, 采用第一次没有优化时间的写法
void solve1() {int n, c;cin >> n >> c;int c0,c1,d0,d1;cin >> c0 >> c1 >> d0 >> d1;vector<int> s(n + 1), b(n + 1), schhate(n + 1, -1);vector<int> citysum(c + 1), cityhate(n + 1);vector<vector<int>> citysch(c + 1);int all = 0;for(int i = 1; i <= n; i++) cin >> b[i] >> s[i], citysum[b[i]] += s[i], citysch[b[i]].push_back(i), all += s[i];int k;cin >> k;vector<int> f(c0 + 1), g(d0 + 1), pre_f(c0 + 1), pre_g(d0 + 1);pre_f[0] = f[0] = 1, pre_g[0] = g[0] = 1;while(k --){int x, y;cin >> x >> y;schhate[x] = y;cityhate[b[x]] = 1;}for(int i = 1; i <= n; i++) {if(schhate[i] == -1) {for(int j = d0; j >= s[i]; j--) g[j] = (g[j] + g[j - s[i]]) % mod;}}for(int i = 1; i <= d0; i++) pre_g[i] = (pre_g[i - 1] + g[i]) % mod;for(int i = 1; i <= c; i++) {if(!cityhate[i] && !citysch[i].empty()) {for(int j = c0; j >= citysum[i]; j--) f[j] = (f[j] + f[j - citysum[i]]) % mod;}}for(int i = 1; i <= c0; i++) pre_f[i] = (pre_f[i - 1] + f[i]) % mod;vector<vector<int>> F(c0 + 1, vector<int> (d0 + 1)); F[0][0] = 1;int Cs = 0, Ss = 0;for(int zo = 1; zo <= c; zo++) {if(citysch[zo].empty()) continue;if(!cityhate[zo]) continue;vector<vector<int>> P(c0 + 1, vector<int> (d0 + 1)),G(c0 + 1, vector<int> (d0 + 1));int cnt = 0;G = F;for(auto it : citysch[zo]) {if(schhate[it] == -1) continue;if(++cnt == 1) {if(!schhate[it]) {for(int i = c0; i >= citysum[zo]; i--) {for(int j = 0; j <= d0; j++) {P[i][j] = F[i - citysum[zo]][j] % mod;}}}if(schhate[it] == 1)for(int i = c0; i >= citysum[zo]; i--) {for(int j = d0; j >= s[it]; j--) {P[i][j] = F[i - citysum[zo]][j - s[it]] % mod;}}if(schhate[it] <= 1) {for(int i = 0; i <= c0; i++) {for(int j = d0; j >= s[it]; j--) {G[i][j] = (G[i][j] + G[i][j - s[it]]) % mod;}}}if(schhate[it] >= 2) {for(int i = c0; i >= citysum[zo]; i--) {for(int j = d0; j >= 0; j--) {P[i][j] = F[i - citysum[zo]][j];if(j >= s[it]) P[i][j] = (P[i][j] + F[i - citysum[zo]][j - s[it]]) % mod;}}}if(schhate[it] == 3) {for(int i = 0; i <= c0; i++) {for(int j = d0; j >= s[it]; j--) {G[i][j] = G[i][j - s[it]];}for(int j = 0; j < s[it]; j++) G[i][j] = 0;}}continue;}if(schhate[it] == 1)for(int i = citysum[zo]; i <= c0; i++) {for(int j = d0; j >= s[it]; j--) {P[i][j] = P[i][j - s[it]] % mod;}for(int j = 0; j < s[it]; j++) P[i][j] = 0;}if(schhate[it] <= 1) {for(int i = 0; i <= c0; i++) {for(int j = d0; j >= s[it]; j--) {G[i][j] = (G[i][j] + G[i][j - s[it]]) % mod;}}}if(schhate[it] >= 2) {for(int i = citysum[zo]; i <= c0; i++) {for(int j = d0; j >= 0; j--) {if(j >= s[it]) P[i][j] = (P[i][j] + P[i][j - s[it]]) % mod;}}}if(schhate[it] == 3) {for(int i = 0; i <= c0; i++) {for(int j = d0; j >= s[it]; j--) {G[i][j] = G[i][j - s[it]];}for(int j = 0; j < s[it]; j++) G[i][j] = 0;}}}for(int i = 0; i <= c0; i++) {for(int j = 0; j <= d0; j++) F[i][j] = ((P[i][j] + G[i][j]) % mod + mod) % mod;}}ll ans = 0;for(int i=0;i<=c0;++i)for(int j=0;j<=d0;++j) {int l1 = max(0, all - c1 - i), r1 = c0 - i; if(l1 > r1) continue;int l2 = max(0, all - d1 - j), r2 = d0 - j; if(l2 > r2) continue;int vf = pre_f[r1]; if(l1) vf += mod - pre_f[l1-1];int vg = pre_g[r2]; if(l2) vg += mod - pre_g[l2-1];ans = (ans + 1ll * vf * vg % mod * F[i][j] % mod) % mod;}cout << ans << endl;}
有一个点TLE了, 卡一下常数, 每一次让G = F时间有点高, 每一次F数组并不是满的, 只需要记录到当前城市最多有几个人, 只要把不超过当前总人数的部分复制过去就行了
第一次AC代码
void solve1() {int n, c;cin >> n >> c;int c0,c1,d0,d1;cin >> c0 >> c1 >> d0 >> d1;vector<int> s(n + 1), b(n + 1), schhate(n + 1, -1);vector<int> citysum(c + 1), cityhate(n + 1);vector<vector<int>> citysch(c + 1);int all = 0;for(int i = 1; i <= n; i++) cin >> b[i] >> s[i], citysum[b[i]] += s[i], citysch[b[i]].push_back(i), all += s[i];int k;cin >> k;vector<int> f(c0 + 1), g(d0 + 1), pre_f(c0 + 1), pre_g(d0 + 1);pre_f[0] = f[0] = 1, pre_g[0] = g[0] = 1;while(k --){int x, y;cin >> x >> y;schhate[x] = y;cityhate[b[x]] = 1;}for(int i = 1; i <= n; i++) {if(schhate[i] == -1) {for(int j = d0; j >= s[i]; j--) g[j] = (g[j] + g[j - s[i]]) % mod;}}for(int i = 1; i <= d0; i++) pre_g[i] = (pre_g[i - 1] + g[i]) % mod;for(int i = 1; i <= c; i++) {if(!cityhate[i] && !citysch[i].empty()) {for(int j = c0; j >= citysum[i]; j--) f[j] = (f[j] + f[j - citysum[i]]) % mod;}}for(int i = 1; i <= c0; i++) pre_f[i] = (pre_f[i - 1] + f[i]) % mod;vector<vector<int>> F(c0 + 1, vector<int> (d0 + 1)); vector<vector<int>> P(c0 + 1, vector<int> (d0 + 1)),G(c0 + 1, vector<int> (d0 + 1));F[0][0] = 1;int Cs = 0, Ss = 0;for(int zo = 1; zo <= c; zo++) {if(citysch[zo].empty()) continue;if(!cityhate[zo]) continue;int cnt = 0;Cs += citysum[zo], Cs = min(Cs, c0);for(int i = 0; i <= Cs; i++) {for(int j = 0; j <= Ss; j++) G[i][j] = F[i][j];}for(int i = 0; i <= Cs; i++) {for(int j = 0; j <= Ss; j++) P[i][j] = 0;}for(auto it : citysch[zo]) {if(schhate[it] == -1) continue;int last = Ss;Ss += s[it], Ss = min(Ss, d0);if(++cnt == 1) {if(!schhate[it]) {for(int i = Cs; i >= citysum[zo]; i--) {for(int j = 0; j <= Ss; j++) {P[i][j] = F[i - citysum[zo]][j] % mod;}}}if(schhate[it] == 1)for(int i = Cs; i >= citysum[zo]; i--) {for(int j = Ss; j >= s[it]; j--) {P[i][j] = F[i - citysum[zo]][j - s[it]] % mod;}}if(schhate[it] <= 1) {for(int i = 0; i <= Cs; i++) {for(int j = Ss; j >= s[it]; j--) {G[i][j] = (G[i][j] + G[i][j - s[it]]) % mod;}}}if(schhate[it] >= 2) {for(int i = Cs; i >= citysum[zo]; i--) {for(int j = Ss; j >= 0; j--) {P[i][j] = F[i - citysum[zo]][j];if(j >= s[it]) P[i][j] = (P[i][j] + F[i - citysum[zo]][j - s[it]]) % mod;}}}if(schhate[it] == 3) {for(int i = 0; i <= Cs; i++) {for(int j = Ss; j >= s[it]; j--) {G[i][j] = G[i][j - s[it]];}for(int j = 0; j < s[it]; j++) G[i][j] = 0;}}continue;}if(schhate[it] == 1)for(int i = citysum[zo]; i <= Cs; i++) {for(int j = Ss; j >= s[it]; j--) {P[i][j] = P[i][j - s[it]] % mod;}for(int j = 0; j < s[it]; j++) P[i][j] = 0;}if(schhate[it] <= 1) {for(int i = 0; i <= Cs; i++) {for(int j = Ss; j >= s[it]; j--) {G[i][j] = (G[i][j] + G[i][j - s[it]]) % mod;}}}if(schhate[it] >= 2) {for(int i = citysum[zo]; i <= Cs; i++) {for(int j = Ss; j >= 0; j--) {if(j >= s[it]) P[i][j] = (P[i][j] + P[i][j - s[it]]) % mod;}}}if(schhate[it] == 3) {for(int i = 0; i <= Cs; i++) {for(int j = Ss; j >= s[it]; j--) {G[i][j] = G[i][j - s[it]];}for(int j = 0; j < s[it]; j++) G[i][j] = 0;}}}for(int i = 0; i <= Cs; i++) {for(int j = 0; j <= Ss; j++) F[i][j] = ((P[i][j] + G[i][j]) % mod + mod) % mod;}}ll ans = 0;for(int i=0;i<=Cs;++i)for(int j=0;j<=Ss;++j) {int l1 = max(0, all - i - c1), r1 = c0 - i;if(r1 < l1) continue;int l2 = max(0, all - j - d1), r2 = d0 - j;if(r2 < l2) continue;int a = pre_f[r1], b = pre_g[r2];if(l1) a = ((a - pre_f[l1 - 1]) % mod + mod) % mod;if(l2) b = ((b - pre_g[l2 - 1]) % mod + mod) % mod;ans += 1ll * a * b % mod * F[i][j] % mod;ans %= mod;}cout << ans << endl;}
简化整合之后代码
void solve1() {int n, c;cin >> n >> c;int c0,c1,d0,d1;cin >> c0 >> c1 >> d0 >> d1;vector<int> s(n + 1), b(n + 1), schhate(n + 1, -1);vector<int> citysum(c + 1), cityhate(n + 1);vector<vector<int>> citysch(c + 1);int all = 0;for(int i = 1; i <= n; i++) cin >> b[i] >> s[i], citysum[b[i]] += s[i], citysch[b[i]].push_back(i), all += s[i];int k;cin >> k;vector<int> f(c0 + 1), g(d0 + 1), pre_f(c0 + 1), pre_g(d0 + 1);pre_f[0] = f[0] = 1, pre_g[0] = g[0] = 1;while(k --){int x, y;cin >> x >> y;schhate[x] = y;cityhate[b[x]] = 1;}for(int i = 1; i <= n; i++) {if(schhate[i] == -1) {for(int j = d0; j >= s[i]; j--) g[j] = (g[j] + g[j - s[i]]) % mod;}}for(int i = 1; i <= d0; i++) pre_g[i] = (pre_g[i - 1] + g[i]) % mod;for(int i = 1; i <= c; i++) {if(!cityhate[i] && !citysch[i].empty()) {for(int j = c0; j >= citysum[i]; j--) f[j] = (f[j] + f[j - citysum[i]]) % mod;}}for(int i = 1; i <= c0; i++) pre_f[i] = (pre_f[i - 1] + f[i]) % mod;vector<vector<int>> F(c0 + 1, vector<int> (d0 + 1)); vector<vector<int>> G(c0 + 1, vector<int> (d0 + 1));F[0][0] = 1;int Cs = 0, Ss = 0;for(int zo = 1; zo <= c; zo++) {if(citysch[zo].empty()) continue;if(!cityhate[zo]) continue;Cs += citysum[zo], Cs = min(Cs, c0);for(int i = 0; i <= Cs; i++) {for(int j = 0; j <= Ss; j++) G[i][j] = F[i][j];}for(auto it : citysch[zo]) {if(schhate[it] == -1) continue;Ss += s[it], Ss = min(Ss, d0);if(schhate[it] == 1)for(int i = 0; i <= Cs; i++) {for(int j = Ss; j >= s[it]; j--) {F[i][j] = F[i][j - s[it]] % mod;}for(int j = 0; j < s[it]; j++) F[i][j] = 0;}if(schhate[it] <= 1) {for(int i = 0; i <= Cs; i++) {for(int j = Ss; j >= s[it]; j--) {G[i][j] = (G[i][j] + G[i][j - s[it]]) % mod;}}}if(schhate[it] >= 2) {for(int i = 0; i <= Cs; i++) {for(int j = Ss; j >= 0; j--) {if(j >= s[it]) F[i][j] = (F[i][j] + F[i][j - s[it]]) % mod;}}}if(schhate[it] == 3) {for(int i = 0; i <= Cs; i++) {for(int j = Ss; j >= s[it]; j--) {G[i][j] = G[i][j - s[it]];}for(int j = 0; j < s[it]; j++) G[i][j] = 0;}}}for(int j = 0; j <= Ss; j++) {for(int i = Cs; i >= citysum[zo]; i--) F[i][j] = F[i - citysum[zo]][j];for(int i = 0; i < citysum[zo] && i <= Cs; i++) F[i][j] = 0;} for(int i = 0; i <= Cs; i++) {for(int j = 0; j <= Ss; j++) F[i][j] = (F[i][j] + G[i][j]) % mod;}}ll ans = 0;for(int i=0;i<=Cs;++i)for(int j=0;j<=Ss;++j) {int l1 = max(0, all - i - c1), r1 = c0 - i;if(r1 < l1) continue;int l2 = max(0, all - j - d1), r2 = d0 - j;if(r2 < l2) continue;int a = pre_f[r1], b = pre_g[r2];if(l1) a = ((a - pre_f[l1 - 1]) % mod + mod) % mod;if(l2) b = ((b - pre_g[l2 - 1]) % mod + mod) % mod;ans += 1ll * a * b % mod * F[i][j] % mod;ans %= mod;}cout << ans << endl;}