Day1

4813: [Cqoi2017]小Q的棋盘

树形背包DP。

 #include <cstdio>

 #define maxn 110

 #define R register

 #define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)

 struct Edge {

     Edge *next;

     int to;

 } *last[maxn], e[maxn << ], *ecnt = e;

 inline void link(R int a, R int b)

 {

     *++ecnt = (Edge) {last[a], b}; last[a] = ecnt;

     *++ecnt = (Edge) {last[b], a}; last[b] = ecnt;

 }

 int f1[maxn][maxn], f2[maxn][maxn], m;

 bool vis[maxn];

 void dfs(R int x)

 {

     vis[x] = ;

     for (R int i = ; i <= m; ++i) f1[x][i] = f2[x][i] = ;

     for (R Edge *iter = last[x]; iter; iter = iter -> next)

         if (!vis[iter -> to])

         {

             dfs(iter -> to);

             for (R int j = m; j; --j)

                 for (R int k = ; k < j; ++k)

                 {

                     cmax(f1[x][j], f2[x][j - k - ] + f1[iter -> to][k]);

                     k != j -  ? cmax(f1[x][j], f1[x][j - k - ] + f2[iter -> to][k]) : ;

                 }

             for (R int j = m; j >= ; --j)

                 for (R int k = ; k < j - ; ++k)

                     cmax(f2[x][j], f2[x][j - k - ] + f2[iter -> to][k]);

         }

 }

 int main()

 {

     R int n; scanf("%d%d", &n, &m);

     for (R int i = ; i < n; ++i) {R int a, b; scanf("%d%d", &a, &b); link(a, b);}

     dfs();

     R int ans = ;

     for (R int i = ; i <= m; ++i) cmax(ans, f1[][i]), cmax(ans, f2[][i]);

     printf("%d\n", ans);

     return ;

 }

D1T1

4814: [Cqoi2017]小Q的草稿

暂时还没做。marked。

4815: [Cqoi2017]小Q的表格

做完发现自己推式子和推结论的能力不足。这题有一个结论是只和对角线上的元素的权值有关，并且f[a,b]可以写成k*a*b的形式（这个结论我也是网上看的，但是我向BZOJ要的数据里这个条件并不满足，如果直接将题目给你的x/a/b得到的不会是一个整数，而把x/a/b改成模意义下x*a^(-1)*b^(-1)居然就能过了）。然后推出来是∑f[d]*∑∑(i*j*[gcd(i,j)==d])，然后还有一个结论是

∑i*[gcd(i,n)==1]=phi(n)*n/2。如果知道这两个结论应该剩下就只剩套路了（？）。设g[n] = ∑∑(i*j*[gcd(i,j)==1], 1<=i,j<=n),答案变成求∑f[d]*g[k/d]。然后k/d是根号分段的，根号枚举一下然后动态地求前缀和。前缀和这里用分块来实现根号修改O1查询。总的复杂度O(n+m√n)。

 #include <cstdio>

 #include <cmath>

 #define R register

 #define maxn 4000010

 #define maxs 2333

 typedef long long ll;

 const int mod = 1e9 + ;

 int pr[maxn], prcnt, phi[maxn], g[maxn], f[maxn];

 int sum[maxn], ssum[maxs];

 bool vis[maxn];

 inline int qpow(R int base, R int power)

 {

     R int ret = ;

     for (; power; power >>= , base = 1ll * base * base % mod)

         power &  ? ret = 1ll * ret * base % mod : ;

     return ret;

 }

 int gcd(R int a, R int b)

 {

     return !b ? a : gcd(b, a % b);

 }

 int main()

 {

     R int m, n; scanf("%d%d", &m, &n);

     phi[] = ; g[] = ; f[] = ;

     for (R int i = ; i <= n; ++i)

     {

         if (!vis[i]) pr[++prcnt] = i, phi[i] = i - ;

         g[i] = (g[i - ] + 1ll * i * i % mod * phi[i]) % mod;

         f[i] = 1ll * i * i % mod;

         for (R int j = ; j <= prcnt && 1ll * pr[j] * i <= n; ++j)

         {

             vis[i * pr[j]] = ;

             if (i % pr[j] == )

             {

                 phi[i * pr[j]] = phi[i] * pr[j];

                 break;

             }

             else phi[i * pr[j]] = phi[i] * phi[pr[j]];

         }

     }

     R int size = sqrt(n), tot = n / size + ;

 //    printf("\nsize%d\n", size);

     for (R int i = ; i <= n; ++i)

         if (i % size == ) ssum[i / size] = (ssum[i / size - ] + sum[i - ]) % mod, sum[i] = f[i];

         else sum[i] = (sum[i - ] + f[i]) % mod;

 //    for (R int i = 1; i <= n; ++i) printf("%d ", sum[i]); puts("");

     for (; m; --m)

     {

         R int a, b, k, d; R ll x;

         scanf("%d%d%lld%d", &a, &b, &x, &k);

 //        if (x % a != 0 || x % b != 0) puts("WA"), printf("%lld %d %d %d\n", x, a, b, m);

         x %= mod;

 //        printf("kk %lld\n", kk);

         f[d = gcd(a, b)] = 1ll * x * qpow(1ll * a * b % mod, mod - ) % mod * d % mod * d % mod;

         R int spos = d / size + ;

         for (R int i = d; i < spos * size; ++i) sum[i] = ((i % size ==  ?  : sum[i - ]) + f[i]) % mod;

         for (R int i = spos; i <= tot; ++i) ssum[i] = (ssum[i - ] + sum[i * size - ]) % mod;

 //        for (R int i = 1; i <= n; ++i) printf("%d ", sum[i]); puts("");

         R int ans = ;

         #define query(x) (sum[(x)] + ssum[(x) / size])

         for (R int i = , j; i <= k; i = j + )

         {

             j = k / (k / i);

             ans = (ans + 1ll * (query(j) % mod - query(i - ) % mod + mod) % mod * g[k / i]) % mod;

         }

         printf("%d\n", ans);

     }

     return ;

 }

D1T3

Day2

4822: [Cqoi2017]老C的任务

挺裸的二维数点问题。扫描线+树状数组简单维护即可。（将一个询问拆成几个前缀询问加加减减的形式）

 #include <cstdio>

 #include <algorithm>

 #define R register

 #define lowbit(_x) ((_x) & -(_x))

 #define maxn 100010

 struct Event {

     int type, id, x, l, r;

     inline bool operator < (const Event &that) const {return x < that.x || (x == that.x && type < that.type);}

 } p[maxn << ];

 int hash[maxn << ], hcnt, pcnt;

 typedef long long ll;

 ll b[maxn << ], ans[maxn];

 inline void add(R int pos, R int val)

 {

     for (; pos <= hcnt; pos += lowbit(pos)) b[pos] += val;

 }

 inline ll query(R int pos)

 {

     R ll ret = ;

     for (; pos; pos -= lowbit(pos)) ret += b[pos];

     return ret;

 }

 int main()

 {

     R int n, m, pcnt = ; scanf("%d%d", &n, &m);

     for (R int i = ; i <= n; ++i)

     {

         R int x, y, pi; scanf("%d%d%d", &x, &y, &pi);

         hash[++hcnt] = y;

         p[++pcnt] = (Event) {, , x, y, pi};

     }

     for (R int i = ; i <= m; ++i)

     {

         R int x_1, y_1, x_2, y_2; scanf("%d%d%d%d", &x_1, &y_1, &x_2, &y_2);

         hash[++hcnt] = y_1; hash[++hcnt] = y_2;

         p[++pcnt] = (Event) {, i, x_1 - , y_1, y_2};

         p[++pcnt] = (Event) {, i, x_2, y_1, y_2};

     }

     std::sort(hash + , hash + hcnt + );

     hcnt = std::unique(hash + , hash + hcnt + ) - hash - ;

     std::sort(p + , p + pcnt + );

     for (R int i = ; i <= pcnt; ++i)

     {

         p[i].l = std::lower_bound(hash + , hash + hcnt + , p[i].l) - hash;

         if (p[i].type == )

         {

             add(p[i].l, p[i].r);

         }

         else

         {

             p[i].r = std::lower_bound(hash + , hash + hcnt + , p[i].r) - hash;

             if (p[i].type == ) ans[p[i].id] -= query(p[i].r) - query(p[i].l - );

             else ans[p[i].id] += query(p[i].r) - query(p[i].l - );

         }

     }

     for (R int i = ; i <= m; ++i) printf("%lld\n", ans[i]);

     return ;

 }

D2T1

4823: [Cqoi2017]老C的方块

刚开始我连构图都没想到。后来看了题解完构图还是构错了。

将格子染成如上图所示的四种颜色，然后每一种方块都可以表示成0-1-2-3的形式。然后构建分层图，一条从s到t的路径表示的就是一个弃疗的方块，所以跑一个最小割即可。然后我一开始好像染色还染错了，注意一下染色的顺序（一定得都是0-1-2-3的形式），如果染不清楚的话可能会有奇怪的错误。还有，10w的网络流到底是怎么跑过去的，我不是很能理解啊。。。

 #include <cstdio>

 #include <map>

 #include <algorithm>

 #include <cstring>

 #define R register

 #define P std::pair<int, int>

 #define maxn 200010

 #define inf 0x7fffffff

 #define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))

 std::map<P, int> id;

 int x[maxn], y[maxn], w[maxn];

 struct Edge {

     Edge *next, *rev;

     int to, cap;

 } *last[maxn], *cur[maxn], e[maxn * ], *ecnt = e;

 inline void link(R int a, R int b, R int w)

 {

 //  printf("%d %d %d\n", a, b, w);

     *++ecnt = (Edge) {last[a], ecnt + , b, w}; last[a] = ecnt;

     *++ecnt = (Edge) {last[b], ecnt - , a, }; last[b] = ecnt;

 }

 int dep[maxn], q[maxn], s, t, ans;

 inline bool bfs()

 {

     memset(dep, -, (t + ) << );

     dep[q[] = t] = ; R int head = , tail = ;

     while (head < tail)

     {

         R int now = q[++head];

         for (R Edge *iter = last[now]; iter; iter = iter -> next)

             if (iter -> rev -> cap && dep[iter -> to] == -)

                 dep[q[++tail] = iter -> to] = dep[now] + ;

     }

     return dep[s] != -;

 }

 int dfs(R int x, R int f)

 {

     if (x == t) return f;

     R int used = ;

     for (R Edge* &iter = cur[x]; iter; iter = iter -> next)

         if (iter -> cap && dep[iter -> to] +  == dep[x])

         {

             R int v = dfs(iter -> to, dmin(f - used, iter -> cap));

             iter -> cap -= v;

             iter -> rev -> cap += v;

             used += v;

             if (used == f) return f;

         }

     return used;

 }

 void dinic()

 {

     while (bfs())

     {

         memcpy(cur, last, sizeof cur);

         ans += dfs(s, inf);

     }

 }

 void build(R int _x, R int _y, R int i)

 {

     R P next;

     next = std::make_pair(_x, _y);

     if (id[next]) link(id[next] <<  | , i << , inf);

 }

 int main()

 {

     R int c, r, n; scanf("%d%d%d", &c, &r, &n);

     for (R int i = ; i <= n; ++i)

     {

         scanf("%d%d%d", &x[i], &y[i], &w[i]);

         R P pos = std::make_pair(x[i], y[i]);

         id[pos] = i;

     }

     s = ; t = n *  + ;

     for (R int i = ; i <= n; ++i)

     {

         R int col = y[i] &  ? x[i] %  : (x[i] % ) ^ ;

 //      printf("x %d y %d col %d\n", x[i], y[i], col);

         link(i << , i <<  | , w[i]);

         if (col == )

         {

             link(s, i << , inf);

         }

         else if (col == )

         {

             build(x[i], y[i] - , i);

             build(x[i], y[i] + , i);

             build(x[i] + (y[i] &  ? - : ), y[i], i);

         }

         else if (col == )

         {

             build(x[i] + (y[i] &  ? - : ), y[i], i);

         }

         else if (col == )

         {

             build(x[i], y[i] - , i);

             build(x[i], y[i] + , i);

             build(x[i] + (y[i] &  ? - : ), y[i], i);

             link(i <<  | , t, inf);

         }

     }

     dinic();

     printf("%d\n", ans);

     return ;

 }

D2T2

4824: [Cqoi2017]老C的键盘

还没做。marked。

巴特西

Cqoi2017试题泛做