ABC264 on 13rd E. Blackout 2 Problem: https://atcoder.jp/contests/abc264/tasks/abc264_e 問題文 ある国には N 個の都市と M 個の発電所があります。これらを総称して地点と呼びます。 地点には 1,2,…,N+M の番号がつけられており、そのうち都市は地点 1,2,…,N で発電所は地点 N+1,N+2,…,N+M です。 この国には電線が E 本あり、電線 i ( 1≤i≤E ) は地点 Ui と地点 Vi を双方向に結びます。 また、ある都市に 電気が通っている とは、ある都市から電線をいくつか辿って少なくともひとつの発電所に辿り着くことができる状態を言います。 今、 Q 個のイベントが起こります。そのうち i ( 1≤i≤Q ) 番目のイベントでは電線 Xi が切れ、その電線を辿ることができなくなります。一

The Question Fish eating fruit on jisuanke Given an undirected acyclic graph G, all possible path P in the graph, calculate: The first taste In the contest, a handsome foriegn teammate conviced me that this problem can be solve using LCA. I tried. And it did work, with the help of dijkstra. My solution is to, first of all, run dijkstra, and get the distance between root node and every other nodes. Then, calculate the LCA for every two nodes. The desired result is: It worked, but we got TLE for looping though all the nodes, which is . The second trial After the contest, I was told that this is a DP problem. You calculate the times an edge is accessed, times it with the weight, sum them up by the modulus of 3, you got the result. This one, however, also got TLE. Oh, FISH! The final solution The reason why the second solution still can

Concept 上下界网络流 顾名思义，比普通的网络流多出了下界。 考虑将下界的流量限制进行转化。将原来的边(e, v1->v2)拆边，拆出一条上界为 max-min 的边(e1)，和一条上界为 min 的边(e2, 虚拟存在)。 e2 需要满足满流方才有解，但满流的同时还需要保证流量守恒（入流==出流）。故而构造虚拟源点 SS 和虚拟汇点 TT . 对于点v, 若： 下限入流等于下限出流，则两者平衡，可以认为这两个流出流入的流量都不存在。 下限入流(flowin)大于下限出流(flowout)，则 SS 向 v 连一条容量为 flowin-flowout 的边，弥补不足流量。 下限入流(flowin)小于下限出流(flowout)，则 v 向 TT 连一条容量为 flowout-flowin 的边，弥补过剩流量。 当且仅当 SS 的所有边都满流时有解。跑一遍 SS 到 TT 的最大流，然后验证即可。 有源汇上下界可行

Problem 合怪升级，每只怪有他的等级和攻击力，以及是否为 tuner monster. 合怪必须一只 tuner monster 与一只 non-tuner monster 合，并且他们的等级之和必须等于合成的怪。只有特定等级和攻击力的怪可以被合成。某些合成怪必须用特定的某一只或某两只怪才能合成。 Solution 看懂题目后建图跑网络流。主要难点在建图。 将 tuner monster(t1) 连到源点，将 non-tuner monster(t2) 连到汇点， capacity 均为 1， cost 均为0。并且列举将该怪与所有另一种怪的组合，以合成等级为索引保存。注意最大等级上限为12，超过12的组合直接 pass 掉。 然后处理合成怪。在合成怪对应等级中搜索对应满足条件的组合，加入到 t1, t2 矩阵中。这里有一个必须搞的优化，就是只选攻击力最大且大于两只被合成怪的合成怪，对满足的 t1，t2 连 capacity 为 1， cost 为 t1 攻击力 加 t2 攻

Problem 给定数字串 S，求如下表达式的值： Solution 用前缀和转化该式。令 , 则 . 原式转化为： 二项展开，得： 将内外求和对调，使得可以预处理前缀和的和的p次方。式子化为： 预处理 , 复杂度 O(N*K). 对 , 处理每个答案，复杂度也是 O(N*K). 坑点： 每个case末尾输出空格PE. 最后不输出换行会WA... 于是我从PE改到了WA... Code #include <cstdio> #include <cstring> typedef long long LL; const LL MOD=1e9+7; const int MAXN=5e4+10; char S[MAXN]; LL pre[MAXN]; LL spre[MAXN][110]; LL ppre[MAXN][110]; LL C[110][110]; void init() { C[0][0]=1; for (int i=1;i<=100;++i) { C[0