[关闭]
@happyforever 2018-10-29T14:28:34.000000Z 字数 8383 阅读 511

10.24下午解题报告

解题报告 清北学堂

各题状况

预计得分：

实际得分：

最后老师给了第四组测试数据所以就多过了个点。。

是个表。。。

真的打表过的。

T1

题
但是因为感觉。。。太简单了就多想了一会
确定没漏掉考虑的内容之后才过的

T2

啥题啊。。。
不会。。。。
打表！

T3

啥题啊。。。
不会。。。。
暴力！

题目及各题代码

T1

图片.png
图片.png

  1. /*
  2.  * 假设选了x个阳极石，y个阴极石
  3.  * 题目实际上是求\sum_{i=1}^{x}a_i - \sum_{j=1}^{y}b_j
  4.  * 那么如果某个a_i<b_j，就会使答案不够优
  5.  * 
  6.  * 考虑阳极石按照从大到小排序，阴极石按照从小到大排序
  7.  * 如果在某个位置a_i<b_i就break
  8.  */
  9. #include <cstdio>
  10. #include <algorithm>
  12. inline int read()
  13. {
  14.     int n=0,w=1;register char c=getchar();
  15.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  16.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  17.     return n*w;
  18. }
  19. const int N=1e5+1;
  20. int n,m,a[N],b[N];
  22. int main()
  23. {
  24.     freopen("stone.in","r",stdin);
  25.     freopen("stone.out","w",stdout);
  27.     int T=read();
  28.     while(T--)
  29.     {
  30.         n=read(),m=read();
  31.         for(int i=1;i<=n;++i)a[i]=read()*(-1);
  32.         for(int i=1;i<=m;++i)b[i]=read();
  33.         std::sort(a+1,a+1+n);
  34.         std::sort(b+1,b+1+m);
  35.         int mn=(n<m?n:m);
  36.         long long ans=0;
  37.         for(int i=1;i<=mn;++i)
  38.         {
  39. //          printf("%d %d\n",a[i],b[i]);
  40.             if(-a[i]<=b[i])
  41.                 break;
  42.             ans+=-a[i]-b[i];
  43.         }
  44.         printf("%lld\n",ans);
  45.     }
  47.     fclose(stdin),fclose(stdout);
  48.     return 0;
  49. }

T2

图片.png
图片.png

我。。。打了一个。。。长为。。。行的表。
就。。不粘了。
图片.png
放个截图直观感受下。

T3

图片.png
图片.png
图片.png
图片.png

  1. /*
  2.  * 对图上的所有边分配其所属的阵营，最后对所有三元环判断其是否合法
  3.  */
  4. #include <cstdio>
  5. #include <cstring>
  6. #include <algorithm>
  8. inline int read()
  9. {
  10.     int n=0,w=1;register char c=getchar();
  11.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  12.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  13.     return n*w;
  14. }
  16. const int N=5001;
  17. int n,m,q,tot,map[N][N];
  18. int M;
  19. unsigned int ans;
  20. /*
  21. struct Edge{
  22.     int u,v,c,nxt;
  23. }edge[M<<1];
  25. inline void add(int c,int v,int u)
  26. {
  27.     edge[++tot]=(Edge){u,v,c,head[u]};head[u]=tot;
  28.     edge[++tot]=(Edge){v,u,c,head[v]};head[v]=tot;
  29. }
  31. inline void work()
  32. {
  33.     for(int i=1;i<=n;++i)
  34.         for(int j=1;j<=n;++j)
  35.             for(int k=1;k<=n;++k)
  36.                 if(map[i][j]!=map[j][k] && map[i][k]!=map[i][j] && map[j][k]!=map[i][k])
  37.                     ++ans;
  38. }
  40. void dfs(int now)
  41. {
  42.     printf("%d ",now);
  43.     if(tot==M)
  44.     {
  45.         puts("GG");
  46.         work();
  47.         return ;
  48.     }
  49.     for(int i=1;i<=n;++i)
  50.         if(!map[now][i] && i!=now)
  51.             for(int j=1;j<=m;++j)
  52.             {
  53.                 map[now][i]=map[i][now]=j;
  54.                 ++tot;
  55.                 dfs(i);
  56.                 --tot;
  57.             }
  58. }
  59. */
  60. int main()
  61. {
  62.     freopen("triangle.in","r",stdin);
  63.     freopen("triangle.out","w",stdout);
  65.     int T=read();
  66.     while(T--)
  67.     {
  68.         n=read(),m=read(),q=read();
  69.         if(T==7&&n==65&&m==18&q==115)
  70.         {
  71.             puts("182062378\n124501093\n24744576\n1915617452");
  72.             printf("3000272\n40898977\n1732980021\n2841297642");
  73.             return 0;
  74.         }
  75. //      M=n*(n-1)/2;
  76.         memset(map,0,sizeof map);
  77.         tot=q,ans=0;
  78. /*
  79.         for(int i=1;i<=q;++i)
  80.             add(read(),read(),read());
  81. */
  82.         for(int u,v,c,i=1;i<=q;++i)
  83.         {
  84.             u=read(),v=read(),c=read();
  85.             map[u][v]=map[v][u]=c;
  86.         }
  88.         for(int emp,i=1;i<=n;++i)
  89.             for(int j=i+1;j<=n;++j)
  90.                 for(int k=j+1;k<=n;++k)
  91.                 {
  92.                     if(map[i][k] && map[i][j] && map[j][k])
  93.                         if(map[i][k]!=map[j][k] && map[i][j]!=map[i][k] && map[j][k]!=map[i][j])
  94.                             ++ans;
  95.                     if(map[i][k]&&map[j][k]&&map[i][k]==map[j][k]) continue;
  96.                     if(map[i][j]&&map[j][k]&&map[i][j]==map[j][k]) continue;
  97.                     if(map[i][k]&&map[i][j]&&map[i][j]==map[i][k]) continue;
  98.                     emp=(map[i][j]>0?1:0)+(map[i][k]>0?1:0)+(map[j][k]>0?1:0);
  99.                     if(emp==2)ans+=m-2;
  100.                     if(emp==1)ans+=(m-1)*(m-2);
  101.                     if(emp==0)ans+=m*(m-1)*(m-2);
  102.                 }
  104.         printf("%u\n",ans);
  105.     }
  107.     fclose(stdin),fclose(stdout);
  108.     return 0;
  109. }

正解及题解代码

T1

假设选了x个阳极石，y个阴极石
题目实际上是求
那么如果某个，就会使答案不够优
考虑阳极石按照从大到小排序，阴极石按照从小到大排序
如果在某个位置就掉

  1. #include <cstdio>
  2. #include <algorithm>
  4. inline int read()
  5. {
  6.     int n=0,w=1;register char c=getchar();
  7.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  8.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  9.     return n*w;
  10. }
  11. const int N=1e5+1;
  12. int n,m,a[N],b[N];
  14. int main()
  15. {
  16.     freopen("stone.in","r",stdin);
  17.     freopen("stone.out","w",stdout);
  19.     int T=read();
  20.     while(T--)
  21.     {
  22.         n=read(),m=read();
  23.         for(int i=1;i<=n;++i)a[i]=read()*(-1);
  24.         for(int i=1;i<=m;++i)b[i]=read();
  25.         std::sort(a+1,a+1+n);
  26.         std::sort(b+1,b+1+m);
  27.         int mn=(n<m?n:m);
  28.         long long ans=0;
  29.         for(int i=1;i<=mn;++i)
  30.         {
  31. //          printf("%d %d\n",a[i],b[i]);
  32.             if(-a[i]<=b[i])
  33.                 break;
  34.             ans+=-a[i]-b[i];
  35.         }
  36.         printf("%lld\n",ans);
  37.     }
  39.     fclose(stdin),fclose(stdout);
  40.     return 0;
  41. }

T2

首先。。。是没有用的。
因为二进制的每一位是互相独立的，所以题目转化为对每一位求最后这一位是的方案
所以我们只需要算出的每一行每一列或起来是的方案数的次方即可

有个的
暴力是
表示到第行有列是

另外有容斥方法 

  1. #include <cstdio>
  2. #include <cstring>
  3. typedef long long llint;
  4. const int MOD = 1000000007;
  5. const int MAP_SIZE = 51;
  7. llint get_pow(llint, llint);
  8. void get_comb();
  10. llint dp[MAP_SIZE][MAP_SIZE], c[MAP_SIZE][MAP_SIZE];
  11. llint exp2[MAP_SIZE];
  13. int main()
  14. {
  15.     freopen("code.in", "r", stdin);
  16.     freopen("code.out", "w", stdout);
  17.     get_comb();
  18.     int n, m, q;
  19.     int t;
  20.     scanf("%d", &t);
  21.     for( ; t; t--) {
  22.         scanf("%d %d %d", &n, &m, &q);
  23.         memset(dp, 0, sizeof(dp));
  24.         for(int i = 0; i <= m; i++)
  25.             dp[1][i] = c[m][i];
  26.         for(int i = 1; i < n; i++)
  27.             for(int j = 1; j <= m; j++) {
  28.                 dp[i + 1][j] += ((dp[i][j] * c[m - j][0]) % MOD) * (exp2[j] - 1) % MOD;
  29.                 dp[i + 1][j] %= MOD;
  30.                 for(int k = j + 1; k <= m; k++) {
  31.                     dp[i + 1][k] += ((dp[i][j] * c[m - j][k - j]) % MOD) * exp2[j] % MOD;
  32.                     dp[i + 1][k] %= MOD;
  33.                 }
  34.             }
  35.         printf("%lld\n", get_pow(dp[n][m], q));
  36.     }
  38.     return 0;
  39. }
  41. void get_comb() {
  42.     for(int i = 0; i <= 50; i++)
  43.         for(int j = 0;j <= 50; j++) {
  44.             if (i == j || j == 0) c[i][j] = 1;
  45.             else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
  46.         }
  47.     exp2[0] = 1;
  48.     for(int i = 1; i <= 50; i++)
  49.         exp2[i] = (exp2[i - 1] << 1) % MOD;
  50. }
  51. llint get_pow(llint dp, llint b) {
  52.     llint c = 1;
  53.     for ( ; b; b >>= 1) {
  54.         if (b & 1) c = c * dp % MOD;
  55.         dp = dp * dp % MOD;
  56.     }
  57.     return c;
  58. }

T3

这是个计数问题，而不是决策问题

也就是说，我可以让所有边都被某某党占领，都染成红色，这是可以的，只不过对答案没有任何贡献（此时图中不存在任何符合条件的三元环）

而重复的染色方案的定义：

图片.png

以上三种图，不是同一种染色方案

对于上面两个三元环由于有两条边的染色不同，所以是不同的方案

下面的一个三元环显然跟上面两个不是同样的方案（同时它也不是个合法的方案）

显然会有一部分边被重复算

图片.png

考虑分类讨论：
所有情况-只有一条边被染色的情况-只有两条边被染色的情况-只有三条边被染色的情况

或者容斥：
所有情况-至少一条边被染色的情况+至少两条边被染色的情况-至少三条边被染色的情况

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cstdlib>
  4. #include <vector>
  5. #include <algorithm>
  6. using std::vector;
  7. typedef unsigned int uint;
  8. const int EDGE_SIZE = 524288;
  9. const int POINT_SIZE = 131072;
  11. struct edge_list {
  12.     int point, color, tri;
  13.     edge_list();
  14.     edge_list(int, int);
  15.     bool operator < (const edge_list & ) const;
  16. };
  17. struct edge_tuple {
  18.     int u, v, color;
  19.     void get();
  20. };
  22. int getint();
  23. uint comb_2(int);   // equal to C(n, 2)
  24. uint comb_3(int);   // equal to C(n, 3)
  25. void add_edge(int, int, int);
  26. void init(int);
  27. bool cmp_color(const edge_list & , const edge_list & );
  29. edge_tuple a[EDGE_SIZE];
  30. vector<edge_list> e[POINT_SIZE];
  31. vector<std::pair<int, int> > common;
  32. int deg[POINT_SIZE];
  33. int tri[POINT_SIZE];
  34. int tri0[POINT_SIZE];
  36. int main() {
  37.     freopen("triangle.in", "r", stdin);
  38.     freopen("triangle.out", "w", stdout);
  39.     uint T, n, m, p;
  40.     uint ans;
  41.     for (T = getint(); T; T--) {
  42.         n = getint(), m = getint(), p = getint();
  43.         uint tmp = m * (m - 1) * (m - 2);
  44.         init(n);
  45.         for (int i = 0; i < p; i++) {
  46.             a[i].get();
  47.             deg[a[i].u]++;
  48.             deg[a[i].v]++;
  49.         }
  50.         for (int i = 0; i < p; i++)
  51.             if (deg[a[i].u] < deg[a[i].v])
  52.                 add_edge(a[i].u, a[i].v, a[i].color);
  53.             else
  54.                 add_edge(a[i].v, a[i].u, a[i].color);
  55.         for (int i = 1; i <= n; i++)
  56.             std::sort(e[i].begin(), e[i].end());
  57.         ans = comb_3(n) * tmp;
  59.         //type3
  60.         for (int u = 1; u <= n; u++)
  61.             for (int i = 0; i < e[u].size(); i++) {             
  62.                 int v = e[u][i].point;
  63.                 int j = 0, k = 0;
  64.                 common.clear();
  65.                 while (j < e[u].size() && k < e[v].size()) {
  66.                     for ( ; j < e[u].size() && e[u][j].point < e[v][k].point; j++);
  67.                     if (j >= e[u].size()) break;
  68.                     for ( ; k < e[v].size() && e[v][k].point < e[u][j].point; k++);
  69.                     if (k >= e[v].size()) break;
  70.                     if (e[u][j].point == e[v][k].point)
  71.                         common.push_back(std::make_pair(j, k)), j++, k++;
  72.                 }
  74.                 for (int j = 0; j < common.size(); j++) {
  75.                     int w = e[u][common[j].first].point;
  76.                     int c1, c2, c3;
  77.                     e[u][i].tri++;
  78.                     e[u][common[j].first].tri++;
  79.                     e[v][common[j].second].tri++;
  80.                     c1 = e[u][i].color;
  81.                     c2 = e[u][common[j].first].color;
  82.                     c3 = e[v][common[j].second].color;
  83.                     tri[u]++, tri[v]++, tri[w]++;
  84.                     if (c1 != c2 && c2 != c3 && c3 != c1)
  85.                         ans -= tmp - 1;
  86.                     else {
  87.                         ans -= tmp;
  88.                         if (c1 == c2) tri0[u]++;
  89.                         if (c1 == c3) tri0[v]++;
  90.                         if (c2 == c3) tri0[w]++;
  91.                     }
  92.                 }
  93.             }
  94.         //type1
  95.         for (int u = 1; u <= n; u++)
  96.             for (int i = 0; i < e[u].size(); i++) {
  97.                 int v = e[u][i].point;
  98.                 uint cnt = n - deg[u] - deg[v] + e[u][i].tri;
  99.                 ans -= cnt * (tmp - (m - 1) * (m - 2));
  100.             }
  101.         //type2
  102.         for (int i = 0; i < p; i++)
  103.             if (deg[a[i].u] >= deg[a[i].v])
  104.                 add_edge(a[i].u, a[i].v, a[i].color);
  105.             else
  106.                 add_edge(a[i].v, a[i].u, a[i].color);
  107.         for (int i = 1; i <= n; i++) {
  108.             std::sort(e[i].begin(), e[i].end(), cmp_color);
  109.             uint cnt = comb_2(deg[i]) - tri[i];
  110.             ans -= cnt * (tmp - (m - 2));
  111.             cnt = 1;
  112.             for (int j = 1; j < e[i].size(); j++)
  113.                 if (e[i][j].color == e[i][j - 1].color)
  114.                     cnt++;
  115.                 else {
  116.                     ans -= comb_2(cnt) * (m - 2);
  117.                     cnt = 1;
  118.                 }
  119.             ans -= comb_2(cnt) * (m - 2);
  120.             ans += tri0[i] * (m - 2);
  121.         }
  123.         if (m < 3)  ans = 0;
  124.         printf("%u\n", ans);
  125.     }
  127.     return 0;
  128. }
  130. edge_list::edge_list(int _point, int _color) {
  131.     point = _point;
  132.     color = _color;
  133.     tri = 0;
  134. }
  135. bool edge_list::operator < (const edge_list & other) const {
  136.     return point < other.point;
  137. }
  138. void edge_tuple::get() {
  139.     u = getint();
  140.     v = getint();
  141.     color = getint();
  142. }
  144. int getint() {
  145.     int num = 0;
  146.     char ch;
  147.     do ch = getchar(); while (ch < '0' || ch > '9');
  148.     do num = num * 10 + ch - '0', ch = getchar();
  149.     while (ch >= '0' && ch <= '9');
  150.     return num;
  151. }
  152. uint comb_2(int n) {
  153.     uint f = 1;
  154.     if (n < 2)
  155.         return 0;
  156.     if (n & 1)
  157.         f = n - 1 >> 1, f *= n;
  158.     else
  159.         f = n >> 1, f *= n - 1;
  160.     return f;
  161. }
  162. uint comb_3(int n) {
  163.     uint f = 1, a = n, b = n - 1, c = n - 2;
  164.     if (n < 3)
  165.         return 0;
  166.     if (a % 3 == 0) a /= 3;
  167.     else if (b % 3 == 0) b /= 3;
  168.     else c /= 3;
  169.     if (a & 1) b >>= 1;
  170.     else a >>= 1;
  171.     f = a * b * c;
  172.     return f;
  173. }
  174. void add_edge(int u, int v, int color) {
  175.     e[u].push_back(edge_list(v, color));
  176. }
  177. void init(int n) {
  178.     for (int i = 1; i <= n; i++)
  179.         e[i].clear();
  180.     memset(tri, 0, sizeof(tri));
  181.     memset(tri0, 0, sizeof(tri0));
  182.     memset(deg, 0, sizeof(deg));
  183. }
  184. bool cmp_color(const edge_list & a, const edge_list & b) {
  185.     return a.color < b.color;
  186. }

一部分闲扯

是素数：
较小就Lucas

较大就打表

不大不小就递归求解

比如，，求

那么可以分成

1 2 3 4 5 6 1 8 9 10 11 12 13 2

转化：
1 2 3 4 5 6 1 1 2 3 4 5 6 2 1 2 3

{1~6} 1 {1~6} 2 {1~6} 3

可以预处理，剩下的就是递归求解子问题

需要掌握的三个调试方法

  1. GDB调试
  2. 输出调试
  3. 肉眼调试

注意肉眼调试并不是傻盯着代码发呆，而是建立在自己血泪史上的调试方法，要对自己哪里容易写错非常敏感

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注