【HNOI2013】题解 bzoj3139~bzoj3144-白红宇

【HNOI2013】题解 bzoj3139~bzoj3144

阅读量：5175 次

发布时间：2019-06-13

本文共 11092 字，大约阅读时间需要 36 分钟。

比赛

　　题目: http://www.lydsy.com/JudgeOnline/problem.php?id=3139

　　题解:

　　　　3$\le$N$\le$10，比较明显是一个搜索题，一开始我是直接搜了，没有记忆化，如果先枚举每一队可以的胜负平，加上合法性判断，再进行枚举，那么是可以拿到70分的，这里有一个重要的剪枝，在枚举了每一队的情况后一定要判断胜场+负场是否相等，这里有20分。。

　　　　　　以下正解:

　　　　在爆搜的时候我们每一队每一队去枚举，我们尝试着记忆化。

　　　　首先我们发现，对于一组数据，得分序列(读入序列)的顺序和答案是无关的，那么我们记忆当还有x个队没有处理时，每一队的剩余得分为$a_{n - x + 1}$，$a_{n - x + 2}$，......，$a_{n}$ 这个状态对答案的贡献，通过对这个数组的排序，我们可以大量去重，甚至不需要加太多的优化都可以AC。

1 #include 
      
        2 #define rep(i, a, b) for (int i = a; i <= b; i++) 3 #define drep(i, a, b) for (int i = a; i >= b; i--) 4 #define REP(i, a, b) for (int i = a; i < b; i++) 5 #define mp make_pair 6 #define pb push_back 7 #define clr(x) memset(x, 0, sizeof(x)) 8 #define xx first 9 #define yy second10 using namespace std;11 typedef long long i64;12 typedef pair
       
         pii;13 const int inf = 0x3f3f3f3f;14 const i64 INF = 0x3f3f3f3f3f3f3f3fll;15 template 
        
          void Max(T &a, T b) { if (a < b) a = b; }16 template 
         
           void Min(T &a, T b) { if (a > b) a = b; }17 //***************************************************************18 19 int n;20 struct Conditions {21     int a[11];22     inline long long hash() {23         long long ret = 0;24         rep(i, 0, n) ret = ret * 28 + a[i];25         return ret;26     }27     inline void Sort() { sort(a + n - a[0] + 1, a + 1 + n); }28 } start, bound;29 map 
          
            M;30 const int mod = 1e9 + 8;31 long long dfs(int step, Conditions now) {32     if (now.a[0] == 1) return M[now.hash()];33     if (now.a[n - now.a[0] + 1] > 3 * (n + 1 - step)) return -1;34     if (step > n) {35         now.a[0]--;36         now.Sort();37         if (M[now.hash()]) return M[now.hash()];38         return M[now.hash()] = dfs(n - now.a[0] + 2, now);39     }40     long long res = 0, tmp;41     int idx = n - now.a[0] + 1;42     if (now.a[idx] >= 3) {43         now.a[idx] -= 3;44         tmp = dfs(step + 1, now);45         if (tmp != -1) (res += tmp) %= mod;46         now.a[idx] += 3;47     }48     if (now.a[idx] >= 1 && now.a[step] >= 1) {49         now.a[idx] -= 1, now.a[step] -= 1;50         tmp = dfs(step + 1, now);51         if (tmp != -1) (res += tmp) %= mod;52         now.a[idx] += 1, now.a[step] += 1;53     }54     if (now.a[step] >= 3) {55         now.a[step] -= 3;56         tmp = dfs(step + 1, now);57         if (tmp != -1) (res += tmp) %= mod;58         now.a[idx] += 1;59         now.a[step] += 3;60     }61     res = res ? res : -1;62     return res;63 }64 int main() {65     scanf("%d", &n);66     start.a[0] = n;67     rep(i, 1, n) scanf("%d", &start.a[i]);68     start.Sort();69     bound.a[0] = 1, bound.a[n] = 0; M[bound.hash()] = 1;70     printf("%lld\n", dfs(2, start));71     return 0;72 }

View Code

消毒

　　题目: http://www.lydsy.com/JudgeOnline/problem.php?id=3140

　　题解:

　　　　a * b * c$\le$5000，所以min(a, b, c)$\le$18。

　　　　首先如果用长度为p * q * r的立方题来框住这些点，我们可以把它变成用 1 * p * q 或者 1 * q * r 或者 p * 1 * r的立方体来覆盖，答案不会更差。

　　　　那么我们可以用来填充的无非是上面3种的立方体来覆盖，那么我们可以枚举最小的那一维，剩下的用二分图最小点覆盖。

　　　　我们把最小的那一维旋转到x轴上，我们二进制枚举这一维复杂度为$2^{18}$，剩下的我们只能用 p * q * 1 或者 p * 1 * r 来覆盖剩下的点，那么我们把不能用x轴(1 * q * r)覆盖的点分别映射到y轴，z轴上去，之后二分图最小点覆盖，也就是最大匹配，记得matrix67大神证明过König定理 http://www.matrix67.com/blog/archives/116?replytocom=4432

1 #include 
      
        2 #define rep(i, a, b) for (int i = a; i <= b; i++) 3 #define drep(i, a, b) for (int i = a; i >= b; i--) 4 #define REP(i, a, b) for (int i = a; i < b; i++) 5 #define pb push_back 6 #define mp make_pair 7 #define clr(x) memset(x, 0, sizeof(x)) 8 #define xx first 9 #define yy second10 using namespace std;11 typedef long long i64;12 typedef pair
       
         pii;13 const int inf = 0x3f3f3f3f;14 const i64 INF = 0x3f3f3f3f3f3f3f3f;15 template 
        
          void Max(T &a, T b) { if (a < b) a = b; }16 template 
         
           void Min(T &a, T b) { if (a > b) a = b; }17 //********************************************************************18 19 const int maxn = 5005;20 21 struct point {22     int x, y, z; point() {}23     point(int _x, int _y, int _z) :24         x(_x), y(_y), z(_z) {}25 } one[maxn];26 int cnt_one;27 struct Ed {28     int u, v, nx; Ed() {}29     Ed(int _u, int _v, int _nx) :30         u(_u), v(_v), nx(_nx) {}31 } E[maxn];32 int G[maxn], edtot;33 void addedge(int u, int v) {34     E[++edtot] = Ed(u, v, G[u]);35     G[u] = edtot;36 }37 int A, B, C;38 39 bool t[maxn], used[maxn]; int belong[maxn];40 bool dfs(int x) {41     for (int i = G[x]; i; i = E[i].nx) {42         if (used[E[i].v]) continue;43         used[E[i].v] = 1;44         if (!belong[E[i].v] || dfs(belong[E[i].v])) {45             belong[E[i].v] = x;46             return true;47         }48     }49     return false;50 }51 int ans;52 void solve() {53     static int hsh[maxn]; int hsh_cnt(0);54     rep(i, 1, cnt_one) hsh[hsh_cnt++] = one[i].x;55     sort(hsh, hsh + hsh_cnt); hsh_cnt = unique(hsh, hsh + hsh_cnt) - hsh;56     REP(s, 0, 1 << hsh_cnt) {57         rep(i, 1, A) t[i] = 0;58         int tmp(0);59         REP(i, 0, hsh_cnt) if (s >> i & 1) t[hsh[i]] = 1, tmp++;60         edtot = 0; rep(i, 1, B) G[i] = 0;61         rep(i, 1, cnt_one) if (!t[one[i].x]) addedge(one[i].y, one[i].z);62         rep(i, 1, C) belong[i] = 0;63         rep(i, 1, B) {64             rep(j, 1, C) used[j] = 0;65             if (dfs(i)) tmp++;66             if (tmp > ans) break;67         }68         Min(ans, tmp);69     }70 }71 72 int main() {73     int T; scanf("%d", &T);74     while (T--) {75         scanf("%d%d%d", &A, &B, &C);76         cnt_one = 0;77         rep(i, 1, A) rep(j, 1, B) rep(k, 1, C) {78             int id; scanf("%d", &id);79             if (id == 1) one[++cnt_one] = point(i, j, k);80         }81         if (B > A) { swap(A, B); rep(i, 1, cnt_one) swap(one[i].x, one[i].y); }82         if (C > A) { swap(A, C); rep(i, 1, cnt_one) swap(one[i].x, one[i].z); }83         ans = A;84         solve();85         printf("%d\n", ans);86     }87 }

View Code

旅行

　　题目: http://www.lydsy.com/JudgeOnline/problem.php?id=3141

　　题解:

数列

　　题目: http://www.lydsy.com/JudgeOnline/problem.php?id=3142

　　题解:

　　　　原数列$\underbrace{ a_{1},a_{2},a_{3}......a_{k} }_{k}$

　　　　构造数列$b_{i}=a_{i}-a_{i-1}$

　　　　那么我们得到$\underbrace{ b_{1},b_{2},b_{3}......a_{k-1} }_{k-1}$

　　　　我们考虑每个不同数列的不同贡献。

　　　　贡献为:$n-b_{1}-b_{2}-b_{3}-b_{4}-b_{k-1}$

　　　　因为$m*(k-1)>n$所以每一个数列都有如上贡献，共有$m^{k-1}$种情况

　　　　那么求和

　　　　n的贡献是$n*m^{k-1}$

　　　　对于剩下的每一项，任取一项，在这一项取1时，共有$m^{k-2}$个数列，取2时，共有$m^{k-2}$个数列......

　　　　那么对于$b_{k}$对答案的贡献是$(\sum_{i=1}^{m})*m^{k-2}$

　　　　所以总答案为$n*m^{k-1}+(k-1)*(\sum_{i=1}^{m})*m^{k-2}$

1 #include 
      
        2 #define rep(i, a, b) for (int i = a; i <= b; i++) 3 #define drep(i, a, b) for (int i = a; i >= b; i++) 4 #define REP(i, a, b) for (int i = a; i < b; i++) 5 #define mp make_pair 6 #define pb push_back 7 #define xx first 8 #define yy second 9 using namespace std;10 typedef long long ll;11 typedef pair
       
         pii;12 const int inf = 0x3f3f3f3f;13 const ll INT = 0x3f3f3f3f3f3f3f3fll;14 template 
        
          void Max(T &a, T b) { if (a < b) a = b; }15 template 
         
           void Min(T &a, T b) { if (a > b) a = b; }16 //******************************************************************17 18 ll n, m, k, p;19 ll POW(ll base, ll num) {20     ll ret = 1;21     while (num) {22         if (num & 1) (ret *= base) %= p;23         (base *= base) %= p;24         num >>= 1;25     }26     return ret;27 }28 int main() {29     scanf("%lld%lld%lld%lld", &n, &k, &m, &p);30     ll ans1 = n % p;31     (ans1 *= POW(m , k - 1)) %= p; 32     ll ans2 = (m * (m + 1) / 2) % p;33     (ans2 *= POW(m, k - 2)) %= p;34     (ans2 *= k - 1) %= p;35     printf("%lld", ((ans1 - ans2) % p + p) % p);36     return 0;37 }

View Code

游走

　　题目: http://www.lydsy.com/JudgeOnline/problem.php?id=3143

　　题解:

　　　　首先贪心，编号小的经过次数一定多，那么我们只需要求出每一条边的经过次数即可，因为是等可能的，那么这个不好求的经过求每一个点的经过次数$P_{i}$，那么每一条边$(x,y)$的经过次数$G_{i}=\frac{P_{x}}{degree_{x}}+\frac{P_{y}}{degree_{y}}$

　　　　那么问题转化为了如何求解$P_{i}$

　　　　我们发现$P_{i}=\sum_{\forall(x,i)}\frac{P_{x}}{degree_{x}}+\sum_{\forall(i,x)}\frac{P_{x}}{degree_{x}}$

　　　　但是有特殊情况$P_{1}=\sum_{\forall(x,i)}\frac{P_{x}}{degree_{x}}+\sum_{\forall(i,x)}\frac{P_{x}}{degree_{x}}+1$

　　　　　　　　　　　$P_{n}=1$

　　　　那么很明显了，高斯消元，有一个地方需要注意，在消元之中，$P_{n}$应该置为0，应为只要到达n是出不来的。

　　$1^{-10}$才过。。。好像long double直接过的样子。。。

1 #include 
      
        2 #define rep(i, a, b) for (int i = a; i <= b; i++) 3 #define drep(i, a, b) for (int i = a; i >= b; i++) 4 #define REP(i, a, b) for (int i = a; i < b; i++) 5 #define mp make_pair 6 #define pb push_back 7 #define xx first 8 #define yy second 9 #define eps 1e-1010 using namespace std;11 typedef long long ll;12 typedef pair
       
         pii;13 const int inf = 0x3f3f3f3f;14 const ll INT = 0x3f3f3f3f3f3f3f3fll;15 template 
        
          void Max(T &a, T b) { if (a < b) a = b; }16 template 
         
           void Min(T &a, T b) { if (a > b) a = b; }17 //******************************************************************18 19 const int maxn = 505, maxm = 250005;20 21 double eq[maxn][maxn];22 pii E[maxm]; int ed_tot;23 int deg[maxn];24 double A[maxm], val[maxn];25 26 void gauss(int m, int n) {27     rep(i, 1, n) {28         if (fabs(eq[i][i]) < eps) rep(j, i, m) { if (fabs(eq[j][i]) > eps) swap(eq[i], eq[j]); break; }29         rep(j, i + 1, n + 1) eq[i][j] /= eq[i][i];30         eq[i][i] = 1;31         rep(j, 1, m) if (i != j && fabs(eq[j][i]) > eps) {32             double t = eq[j][i];33             rep(k, i, n + 1) eq[j][k] -= t * eq[i][k];34         }35     }36     rep(i, 1, m) val[i] = eq[i][n + 1];37 }38 39 int main() {40     int n, m; scanf("%d%d", &n, &m);41     rep(i, 1, m) {42         int x, y; scanf("%d%d", &x, &y);43         E[++ed_tot] = mp(x, y);44         deg[x]++, deg[y]++;45     }46     rep(i, 1, m) {47         eq[E[i].xx][E[i].yy] = 1.0 / deg[E[i].yy];48         eq[E[i].yy][E[i].xx] = 1.0 / deg[E[i].xx];49     }50     rep(i, 1, n) eq[n][i] = 0;51     eq[1][n + 1] = -1;52     rep(i, 1, n) eq[i][i] = -1;53     gauss(n, n);54     //val[n] = 1;55     rep(i, 1, m) {56         A[i] += val[E[i].xx] / deg[E[i].xx];57         A[i] += val[E[i].yy] / deg[E[i].yy];58     }59     sort(A + 1, A + 1 + m);60     double ans(0);61     rep(i, 1, m) ans += (m - i + 1) * A[i];62     printf("%.3lf\n", ans);63     return 0;64 }