[LibreOJ 2058][TJOI2016]求和
求\(\sum_{i = 0}^n\sum_{j = 0}^i \begin{Bmatrix}i\\ j\end{Bmatrix}2^jj!\)。
\(1\leq n\leq 10^5\)。
[LibreOJ 2100][TJOI2015]线性代数
颓一波式子可以发现答案就是\(ABA^T-CA^T\)。然后发现对于一个\(B\)中的元素\(B_{i, j}\)要对答案做出贡献要求\(A_i\)和\(A_j\)都为1，而\(A_i\)为1会导致答案减去一个\(C_i\)。
因此我们可以分别对\(B\)中元素和\(A\)中元素建点。\(B\)中元素会带来收益，但是要求依赖两个\(A\)中元素。而\(A\)中元素会带来一定的笋丝。这个就已经事很明显的最大权闭合子图力，，，
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
const int maxn = 505;
const int maxno = 500 * 500 + 500 + 5;
const int maxm = 2 * (500 * 500 * 3 + 500 + 5);
int first[maxno];
int next[maxm], to[maxm], flow[maxm], cap[maxm];
int gcnt = 0;
void add_edge(int u, int v, int c) {
gcnt ++;
next[gcnt] = first[u]; first[u] = gcnt;
to[gcnt] = v; cap[gcnt] = c; flow[gcnt] = 0;
}
void ins_edge(int u, int v, int c) {
add_edge(u, v, c); add_edge(v, u, 0);
}
int rev(int i) {
if(1 & i) {
return i + 1;
} else {
return i - 1;
}
}
int d[maxno];
int s, t, num;
bool bfs() {
static bool vis[maxno];
std::fill(vis, vis + num + 1, false);
std::fill(d, d + num + 1, 0);
std::queue<int> Q; Q.push(s);
d[s] = 1; vis[s] = true;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(int i = first[u]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && cap[i] > flow[i]) {
d[v] = d[u] + 1;
Q.push(v); vis[v] = true;
}
}
}
return vis[t];
}
int cur[maxno];
int dfs(int x, int a) {
if(a == 0 || x == t) return a;
int ret = 0;
for(int &i = cur[x]; i; i = next[i]) {
int v = to[i], f;
if(d[v] == d[x] + 1 && (f = dfs(v, std::min(a, cap[i] - flow[i]))) > 0) {
ret += f; a -= f;
flow[i] += f; flow[rev(i)] -= f;
if(a == 0) break;
}
}
if(a > 0) d[x] = -1;
return ret;
}
int dinic() {
int ret = 0;
while(bfs()) {
for(int i = 0; i <= num; i ++) cur[i] = first[i];
ret += dfs(s, 0x7f7f7f7f);
}
return ret;
}
int n;
int main() {
int ans = 0;
scanf("%d", &n);
s = 0, t = n * n + n + 1;
num = t;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= n; j ++) {
int u = (i - 1) * n + j; int val; scanf("%d", &val);
ans += val; ins_edge(s, u, val);
ins_edge(u, n * n + i, 0x7f7f7f7f);
ins_edge(u, n * n + j, 0x7f7f7f7f);
}
}
for(int i = 1; i <= n; i ++) {
int val; scanf("%d", &val);
ins_edge(n * n + i, t, val);
}
ans -= dinic();
printf("%d\n", ans);
return 0;
}
[LibreOJ 2102][TJOI2015]弦论
xjbYY了一下竟然就艹过去了……
如果说是我们知道了每个点出发能得到的串有多少个，我们就能用类似树上求\(k\)大的求法来搞了。问题来了，怎么知道这个？
我先说一下不重复的情况吧，首先到达这个点就有一种串了，然后我们加上他的出边（注意是转移边！）指向的点的值就行了。重复的情况我们考虑一下\(|Right(x)|\)就能搞出来了
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <queue>
#include <algorithm>
#include <set>
const int maxn = 500005;
const int maxno = maxn * 4;
const int bufsiz = 50 * 1024 * 1024;
typedef long long ll;
int fa[maxno], ch[maxno][26];
int len[maxno];
ll ans[maxno][2], val[maxno];
int rt, last;
int cur;
inline void init_sam() {
rt = last = 1;
cur = 1;
ans[1][0] = ans[1][1] = -1LL;
}
inline int alloc_node(int l = 0, int f = 0) {
int ret = ++ cur;
len[ret] = l; fa[ret] = f;
ans[ret][0] = ans[ret][1] = -1LL;
return ret;
}
inline int idx(char c) {
return c - 'a';
}
inline void extend(char cx) {
int c = idx(cx);
int np = alloc_node(len[last] + 1);
val[np] = 1LL;
int p = last;
while(p && !(ch[p][c])) ch[p][c] = np, p = fa[p];
if(!p) {
fa[np] = rt;
} else {
int q = ch[p][c];
if(len[q] == len[p] + 1) {
fa[np] = q;
} else {
int nq = alloc_node(len[p] + 1, fa[q]);
memcpy(ch[nq], ch[q], sizeof(ch[q]));
fa[q] = fa[np] = nq;
while(p && ch[p][c] == q) ch[p][c] = nq, p = fa[p];
}
}
last = np;
}
int lc[maxno], rb[maxno];
inline void add_edge(int c, int f) {
rb[c] = lc[f];
lc[f] = c;
}
void dfs_1(int x) {
for(int i = lc[x]; i; i = rb[i]) {
dfs_1(i);
val[x] += val[i];
}
}
void dfs_2(int x) {
if(ans[x][0] != -1LL) return;
ans[x][0] = 1LL; ans[x][1] = val[x];
for(int c = 0; c < 26; c ++) {
int v = ch[x][c];
if(v) {
dfs_2(v);
ans[x][0] += ans[v][0];
ans[x][1] += ans[v][1];
}
}
}
inline void process() {
for(int i = 2; i <= cur; i ++) {
add_edge(i, fa[i]);
}
dfs_1(1); dfs_2(1);
#ifdef LOCAL
for(int i = 1; i <= cur; i ++) {
printf("ans[%d] : (%lld, %lld)\n", i, ans[i][0], ans[i][1]);
}
#endif
}
char ret[maxno];
void search(ll k, int typ) {
static ll val_0[maxno];
for(int i = 1; i <= cur; i ++) {
val_0[i] = 1;
}
ll *self[2] = {val_0, val};
k += self[typ][1];
if(k > ans[1][typ]) {
ret[0] = '-', ret[1] = '1';
return;
}
int cnt = 0;
int u = 1;
while(k > self[typ][u]) {
int used = 0;
k -= self[typ][u];
for(int c = 0; c < 26; c ++) {
int v = ch[u][c];
if(!v) continue;
used ++;
if(k > ans[v][typ]) {
k -= ans[v][typ];
} else {
ret[cnt ++] = c + 'a';
#ifdef LOCAL
printf("Towardsing %d with %c\n", v, c + 'a');
printf("k : %lld\n", k);
#endif
u = v; break;
}
}
// if(used == 0) break;
}
}
int main() {
static char S[maxn];
scanf("%s", S); int n = strlen(S);
int typ; ll k; scanf("%d%lld", &typ, &k);
init_sam();
for(int i = 0; i < n; i ++) {
extend(S[i]);
}
process();
search(k, typ);
puts(ret);
return 0;
}
[BZOJ 3171][TJOI2013]循环格
流量平衡入门中……
我竟然想民白了……
这个题就是要求每个点在且仅在一个环中，这样每个点的入、出度都是1。出度肯定是1，接下来我们想想怎么保证入度为1。
我们建两排点（也可以说是拆点？），一排表示流出，一排表示接受。然后流出点向相邻的接收点连边，费用的话考虑是否和原来这一格的方向不一样就行了。
这个不需要判断是否满流啥的……因为一定有解（比如说每个行构成一个环啥的）。
代码：
/**************************************************************
Problem: 3171
User: danihao123
Language: C++
Result: Accepted
Time:28 ms
Memory:13844 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
const int maxn = 20;
typedef long long ll;
char S[maxn][maxn];
int tot = 0; int num[maxn][maxn][2];
int R, C;
char D[4] = {'L', 'R', 'U', 'D'};
int tow(int i, int j, char dir, int flag) {
int dx = 0, dy = 0;
if(dir == 'L') {
dx = -1;
} else if(dir == 'R') {
dx = 1;
} else if(dir == 'U') {
dy = -1;
} else if(dir == 'D') {
dy = 1;
}
int nx = (i + dy + R) % R;
int ny = (j + dx + C) % C;
return num[nx][ny][flag];
}
const int maxno = 100005;
const int maxe = 400005;
int first[maxno];
int next[maxe], from[maxe], to[maxe], flow[maxe], cap[maxe];
ll cost[maxe];
int gcnt = 0;
void add_edge(int u, int v, int f, ll c) {
gcnt ++;
next[gcnt] = first[u];
first[u] = gcnt;
from[gcnt] = u; to[gcnt] = v;
cap[gcnt] = f; flow[gcnt] = 0;
cost[gcnt] = c;
}
int rev(int i) {
return ((i - 1) ^ 1) + 1;
}
void ins_edge(int u, int v, int f, ll c = 0LL) {
#ifdef LOCAL
printf("Inserting Edge (%d, %d, %d, %lld)\n", u, v, f, c);
#endif
add_edge(u, v, f, c);
add_edge(v, u, 0, -c);
}
const ll LINF = 0x7f7f7f7f7f7f7f7fLL;
bool spfa(int s, int t, int &f, ll &c) {
static ll d[maxno];
static bool inq[maxno];
static int a[maxno], p[maxno];
std::fill(d, d + tot + 1, LINF);
std::fill(inq, inq + tot + 1, false);
std::fill(a, a + tot + 1, 0);
std::fill(p, p + tot + 1, 0);
d[s] = 0;
std::queue<int> Q; Q.push(s); inq[s] = true;
a[s] = 0x7fffffff;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i = first[u]; i; i = next[i]) {
if(cap[i] > flow[i]) {
int v = to[i];
if(d[v] > d[u] + cost[i]) {
d[v] = d[u] + cost[i];
a[v] = std::min(a[u], cap[i] - flow[i]); p[v] = i;
if(!inq[v]) {
Q.push(v); inq[v] = true;
}
}
}
}
}
if(a[t] == 0) return false;
f += a[t];
c += (ll(a[t])) * d[t];
for(int e = p[t]; e; e = p[from[e]]) {
flow[e] += a[t];
flow[rev(e)] -= a[t];
}
return true;
}
void mcmf(int s, int t, int &f, ll &c) {
while(spfa(s, t, f, c));
}
int main() {
tot = 1; int s = 0, t = 1;
scanf("%d%d", &R, &C);
for(int i = 0; i < R; i ++) {
scanf("%s", S[i]);
for(int j = 0; j < C; j ++) {
num[i][j][0] = ++ tot;
num[i][j][1] = ++ tot;
}
}
for(int i = 0; i < R; i ++) {
for(int j = 0; j < C; j ++) {
ins_edge(s, num[i][j][0], 1);
ins_edge(num[i][j][1], t, 1);
for(int it = 0; it < 4; it ++) {
int u = num[i][j][0];
int v = tow(i, j, D[it], 1);
ins_edge(u, v, 1, (D[it] == S[i][j]) ? 0LL : 1LL);
}
}
}
int f = 0; ll c = 0;
mcmf(s, t, f, c);
printf("%lld\n", c);
return 0;
}
[BZOJ 3172]单词
首先……出题人语文不太好……估计和我这种语文很差的人还有差距……
这个提的意思是，给你若干个单词，输出每个单词在所有单词（而不是把所有单词连起来）中出现的次数。
然后肯定要AC自动机上失配函数搞一波辣……把BFS序倒过来搜，传递出现次数即可。还有这个题的数据范围好像也比给出的小很多……
代码：
/**************************************************************
Problem: 3172
User: danihao123
Language: C++
Result: Accepted
Time:232 ms
Memory:115080 kb
****************************************************************/
#include <cstdio>
#include <cstring>
const int maxn=205;
const int maxnode=1*1e6+5;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int cnt[maxnode];
namespace ACAutomate{
// Trie
const int sigma_size=26;
int Tree[maxnode][sigma_size];
int siz;
inline int idx(char c){
return c-'a';
}
void InitAC(){
siz=0;
CL_ARR(Tree[0],0);
}
int Insert(char *s){
register int i,n=strlen(s);
register int u=0,c;
REP(i,n){
c=idx(s[i]);
if(!Tree[u][c]){
siz++;
Tree[u][c]=siz;
CL_ARR(Tree[siz],0);
}
u=Tree[u][c];
cnt[u]++;
}
return u;
}
// AC Automate
int f[maxnode];
int Q[maxnode];
void InitFail(){
register int i,u,x,v,head=0,tail=0;
f[0]=0;
REP(i,sigma_size){
u=Tree[0][i];
if(u){
f[u]=0;
Q[tail++]=u;
}
}
while(head<tail){
u=Q[head];
head++;
REP(i,sigma_size){
x=Tree[u][i];
if(!x){
continue;
}
Q[tail++]=x;
v=f[u];
while(v && !Tree[v][i])
v=f[v];
f[x]=Tree[v][i];
}
}
for(i=tail-1;i>=0;i--)
cnt[f[Q[i]]]+=cnt[Q[i]];
}
};
char buf[maxnode];
int pos[maxn];
int main(){
int n;
register int i;
scanf("%d",&n);
ACAutomate::InitAC();
REP_B(i,n){
scanf("%s",buf);
pos[i]=ACAutomate::Insert(buf);
}
ACAutomate::InitFail();
REP_B(i,n){
printf("%d\n",cnt[pos[i]]);
}
return 0;
}
