(IOICamp) 43. 翁山國與複利業 [Cost Flow]

https://judge.ioicamp.org/problems/43

Cost Flow (?)

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;

typedef pair<int,int> pii;

struct CostFlow {
 static const int MAX_N = 2e3 + 6;
 struct Edge {
  int to,cap,rev,cost;
 };
 int s,t,n;
 vector<Edge> edg[MAX_N];
 void init(int _n,int _s,int _t) {
  n=_n;
  s=_s;
  t=_t;
  for (int i=0;n>=i;i++) {
   edg[i].clear();
  }
 }
 #define SZ(x) ((int)(x).size())
 void add_edge(int from,int to,int cap,int cost) {
  edg[from].push_back({to,cap,SZ(edg[to]),cost});
  edg[to].push_back({from,0,SZ(edg[from])-1,-cost});
 }
 static const int INF = 1e9 + 7;
 int dis[MAX_N];
 int pre[MAX_N];
 int pre_id[MAX_N];
 bool in_que[MAX_N];
 pii flow(int k) {
  int flow=0,cost=0;
  while (true) {
   for (int i=0;n>=i;i++) {
    dis[i] = INF;
    in_que[i] = false;
   }
   queue<int> que;
   que.push(s);
   dis[s] = 0;
   while (!que.empty()) {
    int t=que.front();
    que.pop();
    in_que[t] = false;
    int id=0;
    for (Edge e:edg[t]) {
     if (e.cap > 0 && dis[e.to] > dis[t] + e.cost) {
      dis[e.to] = dis[t] + e.cost;
      pre[e.to] = t;
      pre_id[e.to] = id;
      if (!in_que[e.to]) {
       que.push(e.to);
       in_que[e.to] = true;
      }
     }
     id++;
    }
   }
   if (dis[t] == INF) break;
   int mn_flow = INF;
   for (int i=t;i!=s; i=pre[i]) {
    mn_flow = min(mn_flow,edg[pre[i]][pre_id[i]].cap);
   }
   if (cost + mn_flow * dis[t] > k) break;
   flow += mn_flow;
   for (int i=t;i!=s; i=pre[i]) {
    edg[pre[i]][pre_id[i]].cap -= mn_flow;
    edg[i][edg[pre[i]][pre_id[i]].rev].cap += mn_flow;
   }
   cost += mn_flow * dis[t];
  }
  return make_pair(flow,cost);
 }
} Flow;

int main () {
 int T;
 scanf("%d",&T);
 while (T--)
    {
        int n,m,k;
        scanf("%d %d %d",&n,&m,&k);
        Flow.init(n,1,n);
        for (int i=1;m>=i;i++)
        {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            Flow.add_edge(a,b,1,0);
            Flow.add_edge(b,a,1,c);
        }
        printf("%d\n",Flow.flow(k).first);
    }
}

(IOICamp) 86. 秘密讀書會 [AC自動機的DP]

https://judge.ioicamp.org/problems/86

AC自動機的DP。

把AC自動機上面的點當作狀態去DP，隨時統計到達當前狀態的方法數。

注意到達 Si 的時候，要把dp設為0，因為不能到達。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL,LL>  pii;
typedef pair<pii,LL> piii;
#define F first
#define S second
const LL mod = 1e9 + 7;
const int N = 106;

struct AC_Automata {
    static const int N = 2e4 + 6;
    static const int M = 106;
    static const int SIGMA = 26;
    LL dp[M][N];
    int ch[N][SIGMA];
    int val[N];
    int sz;
    int last[N],fail[N];
    int que[N],qs,qe;
    void init()
    {
        sz = 1;
        memset(ch[0],0,sizeof(ch[0]));
        qs = qe  = 0;
        memset(val,0,sizeof(val));
        memset(last,0,sizeof(last));
    }
    int idx(char c)
    {
        return c-'a';
    }
    int insert(string s,int v)
    {
        int now=0;
        int n=s.size();
        for (int i=0;n>i;i++)
        {
            int c=idx(s[i]);
            if (!ch[now][c])
            {
                memset(ch[sz],0,sizeof(ch[sz]));
                val[sz] = 0;
                ch[now][c] = sz++;
            }
            now = ch[now][c];
        }
        val[now] = v;
        return now;
    }
    void print(int j)
    {
        if (j)
        {
            //now we match string v[j]
            print(last[j]);  //may match multiple strings
        }
    }
    void getFail()
    {
        qs=0,qe=0;
        fail[0]=0;
        for (int c=0;SIGMA >c;c++)
        {
            int now=ch[0][c];
            if (now)
            {
                fail[now] = 0;
                que[qe++] = now;
                last[now] = 0;
            }
        }
        while (qs != qe)
        {
            int t=que[qs++];
            for (int c=0;SIGMA > c;c++)
            {
                int now=ch[t][c];
                if (!now) continue;
                que[qe++] = now;
                int v=fail[t];
                while (v && !ch[v][c]) v=fail[v];
                fail[now] = ch[v][c];
                last[now] = val[ fail[now] ]? fail[now]:last[ fail[now] ];
            }
        }
    }
    void Find(string s)
    {
        getFail();
        //cout<<"qe = "<<qe<<endl;
        int n=s.size();
        int now=0;
        for (int i=0;n>i;i++)
        {
            int c=idx(s[i]);
            while (now && !ch[now][c]) now = fail[now];
            now = ch[now][c];
        }
    }
    void AC_evolution()
    {
        for (qs=0;qs!=qe;)
        {
            int now=que[qs++];
            for (int i=0;SIGMA>i;i++)
            {
                if (ch[now][i] == 0) ch[now][i] = ch[fail[now]][i];
            }
        }
    }
    LL get_answer(int n)
    {
        memset(dp,0,sizeof(dp));
        dp[0][0] = 1;
        for (int i=0;n-1>=i;i++)
        {
            for (int j=0;sz>j;j++)
            {
                for (int c=0;SIGMA>c;c++)
                {
                    int nxt = ch[j][c];
                    if (!val[nxt] && !last[nxt])
                    {
                        dp[i+1][nxt] += dp[i][j];
                        dp[i+1][nxt] %= mod;
                    }
                }
            }
        }
        LL ret =0 ;
        for (int j=0;sz>j;j++)
        {
            ret += dp[n][j];
            ret %= mod;
        }
        return ret%mod;
    }
} ac;

string s[N];
int ed[N];

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        int n,m;
        cin >> n >> m;
        ac.init();
        for (int i=1;m>=i;i++)
        {
            cin >> s[i];
            ed[i] = ac.insert(s[i],i);
        }
        ac.getFail();
        ac.AC_evolution();
        cout<<ac.get_answer(n)<<endl;
    }
}

(IOICamp_Judge) 導遊讚哥讚！ [重心剖分]

https://judge.ioicamp.org/problems/78

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>
#include <cassert>
using namespace std;

#define int long long

typedef long long LL;
const int MAX_N = 1e4 +6;
const int MAX_M = 1e4 +6;
const int MAX_P = 18;

struct Edge {
    int to;
    LL w;
    void _() {
        cout<<"to = "<<to<<" , w = "<<w<<endl;
    }
};

Edge MP(int _to,LL _w) {
    return Edge{_to,_w};
}

vector<Edge> edg[MAX_N];

struct Cen {
    int par;
    LL add;
    LL minus;
    int sz;
    void _() {
        cout<<"par = "<<par<<" , add = "<<add<<" , minus = "<<minus<<" , sz = "<<sz<<endl;
    }
} cen[MAX_N];

int now[MAX_N];
int depth[MAX_N];
Edge lca[MAX_P][MAX_N];
bool visit[MAX_N];
int stamp;
int tin[MAX_N],tout[MAX_N];

void dfs1(int id,int p,LL w,int cur_depth) {
    tin[id] = stamp++;
    visit[id] = 1;
    lca[0][id] = MP(p,w);
    depth[id] = cur_depth;
    for (auto i:edg[id]) {
        if (!visit[i.to]) {
            dfs1(i.to,id,i.w,cur_depth+1);
        }
    }
    tout[id] = stamp++;
}

vector<int> v;
int sz[MAX_N];
int mx[MAX_N];

void dfs3(int id) {
    visit[id]=1;
    sz[id]=1;
    mx[id]=0;
    v.push_back(id);
    for (auto i:edg[id]) {
        if (!visit[i.to]) {
            dfs3(i.to);
            sz[id] += sz[i.to];
            mx[id] = max(mx[id],sz[i.to]);
        }
    }
}

Cen MP4(int par,LL add,LL minus,int sz) {
    return Cen{par,add,minus,sz};
}

void dfs2(int id,int par_cen) {
    v.clear();
    dfs3(id);
    int can=-1;
    int tot=v.size();
    for (auto i:v) {
        visit[i]=0;
        if (max(mx[i],tot-sz[i]) <= tot/2) {
            can = i;
        }
    }
    visit[can]=true;
    cen[can] = MP4(par_cen,0,0,0);
    for (auto i:edg[can]) {
        if (!visit[i.to]) {
            dfs2(i.to,can);
        }
    }
}

bool is_anc(int son,int parent) {
    return tin[son] >= tin[parent] && tout[son] <= tout[parent];
}

LL get_dis(int x,int y) {
    if (depth[x] > depth[y]) swap(x,y);
    if (x==y) return 0;
    //x is lower
    if(is_anc(y,x)) {
        //we need only from y to x
        LL ret=0;
        for (int i=MAX_P-1;i>=0;i--) {
            if (!is_anc(x,lca[i][y].to)) {
                ret += lca[i][y].w;
                y = lca[i][y].to;
            }
        }
        ret += lca[0][y].w;
        return ret;
    }
    else {
        int tx=x,ty=y;
        x=tx,y=ty;
        LL ret=0;
        for (int i=MAX_P-1;i>=0;i--) {
            if (!is_anc(x,lca[i][y].to)) {
                ret += lca[i][y].w;
                y = lca[i][y].to;
            }
        }
        ret += lca[0][y].w;
        x=ty,y=tx;
        for (int i=MAX_P-1;i>=0;i--) {
            if (!is_anc(x,lca[i][y].to)) {
                ret += lca[i][y].w;
                y = lca[i][y].to;
            }
        }
        ret += lca[0][y].w;
        return ret;
    }
}

void add(int id) {
    int now=id;
    while (now != -1) {
        cen[now].add += get_dis(now,id);
        cen[now].sz++;
        if (cen[now].par == -1) break;
        cen[now].minus += get_dis(cen[now].par,id);
        now = cen[now].par;
    }
}

void deleted(int id) {
    int now=id;
    while (now != -1) {
        cen[now].add -= get_dis(now,id);
        cen[now].sz--;
        if (cen[now].par == -1) break;
        cen[now].minus -= get_dis(cen[now].par,id);
        now = cen[now].par;
    }
}

LL query(int id) {
    int now=id;
    LL ret=0;
    int totsz=0;
    while (now != -1) {
        ret += (cen[now].add - cen[now].minus);
        ret += (cen[now].sz - totsz)*get_dis(id,now);
        totsz = cen[now].sz;
        now = cen[now].par;
    }
    return ret;
}

main () {
    int T;
    scanf("%lld",&T);
    while (T--) {
        int n,m,q;
        scanf("%lld %lld %lld",&n,&m,&q);
        for (int i=0;n>=i;i++) {
            edg[i].clear();
        }
        for (int i=1;n>i;i++) {
            int a,b,c;
            scanf("%lld %lld %lld",&a,&b,&c);
            edg[a].push_back(MP(b,c));
            edg[b].push_back(MP(a,c));
        }
        stamp=0;
        memset(visit,0,sizeof(visit));
        dfs1(1,1,0,1);
        for (int i=1;MAX_P>i;i++) {
            for (int j=1;n>=j;j++) {
                lca[i][j] = MP(lca[i-1][lca[i-1][j].to].to,lca[i-1][j].w+lca[i-1][lca[i-1][j].to].w);
            }
        }
        memset(visit,0,sizeof(visit));
        dfs2(1,-1);
        now[1]=1;
        for (int i=2;m>=i;i++) {
            add(1);
            now[i]=1;
        }
        while (q--) {
            int a,b;
            scanf("%lld %lld",&a,&b);
            if (a==1) {
                now[a]=b;
            }
            else {
                deleted(now[a]);
                now[a]=b;
                add(now[a]);
            }
            LL ret=query(now[1]);
            printf("%lld\n",ret);
            assert(ret>=0);
        }
    }
}

(IOICamp_Judge) 91.列印機問題 [1D/1D Convex DP優化，1D/1D Monge Condition]

https://judge.ioicamp.org/problems/91

因為怕題目之後不見，做個備份：

列印機問題

Time Limit: 1s

Description

你正在修機器學習的課程，因為作業太困難了，所以你決定把題目印下來慢慢研究。

現在有一台計費方式很奇怪的列印機，當你送出一份要列印的文件時，列印機會對文件中的每一頁算出列印該頁所需的成本，令該份文件每一頁的列印成本總和為 x，列印這份文件所需的價錢就是 x3+K（K 為給定的常數）。

為了省錢，你決定把整份作業拆成好幾份文件列印，但是列印完還要自己重新排列很麻煩，因此你決定每次送出去列印的文件都必須是在原始作業檔案中頁數連續的一段，例如第 2 頁到第 5頁。

整份作業總共有 N 頁，並順利算出每一頁的列印成本。現在你要經過數次如上的列印，確保自己拿到作業中每一頁的紙本（同一頁可以被列印多次），請問你所需花費的錢最少為多少？

Input Format

第一行有一個正整數 T，代表總共有幾筆測試資料。

每筆測試資料包含兩行，其中的第一行為兩個正整數 N,K，表示機器學習作業的頁數以及列印機計價方式中的常數 K。第二行包含 N 個整數，依序代表作業中第 1 頁列印成本、第 2頁列印成本、第 3 頁列印成本………第 N 頁列印成本。

• 1≤T≤100
• 1≤N≤105
• 1≤K≤1012
• 0≤每一頁的列印成本 ≤10
• 所有測試資料中的 N 加總不超過 106

Output Format

對於每筆測試資料，請輸出一行一個整數，代表用最佳方式列印所需花費的最少金額。

Sample Input

2
3 5
2 4 1
5 514
3 8 2 0 1

Sample Output

88
2108

Hint

在第一筆範例測試資料中，最佳方法是分別送出只包含第 1 頁的文件、只包含第 2 頁的文件、只包含第 3$3$ 頁的文件，共 3$3$ 份文件去列印，於是總花費的金額會是 (23+5)+(43+5)+(13+5)=88

在第二筆範例測試資料中，最佳方法是分別送出只包含第 1 頁的文件、只包含第 2 頁的文件、包含第 3$3$ 頁到第 5$5$ 頁的文件，共 3$3$ 份文件去列印，於是總花費的金額會是 (33+514)+(83+514)+((2+0+1)3+514)=2108

這題主要是用Convex 1D/1D DP優化

#include <iostream>
#include <stdio.h>
#include <queue>
#include <utility>
#include <stack>
#include <cstring>
using namespace std;

typedef pair<int,int> pii;
typedef pair<int,pii> piii;
typedef long long LL;
const int MAX_N = 1e5 + 6;

LL a[MAX_N],s[MAX_N],k;
LL dp[MAX_N];

LL f(LL i,LL j) {
    return dp[i]+ ( k+(s[j]-s[i])*(s[j]-s[i])*(s[j]-s[i]) );
}

struct Seg {
    LL i,l,r;
};

Seg MP(int _i,int _l,int _r) {
    return (Seg){_i,_l,_r};
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n;
        scanf("%d %lld",&n,&k);
        memset(s,0,sizeof(s));
        int m=1;
        for (int i=1;n>=i;i++) {
            scanf("%lld",&a[i]);
            if (a[i] == 0) {
                continue;
            }
            s[m] = s[m-1]+a[i];
            m++;
        }
        m--;
        memset(dp,0,sizeof(dp));
        dp[0]=0;
        deque<Seg> dq;
        dq.push_back(MP(0,1,m));
        for (int j=1;m>=j;j++) {
            while (dq.size()) {
                Seg tmp=dq.back();
                if (f(tmp.i,tmp.l) > f(j-1,tmp.l)) dq.pop_back();
                else break;
            }
            if (dq.size()) {
                Seg tmp=dq.back();
                int L=tmp.l,R=tmp.r+1;
                while (R-L>1) {
                    int mid=(L+R)>>1;
                    if (f(tmp.i,mid) > f(j-1,mid)) R=mid;
                    else L=mid;
                }
                dq.pop_back();
                dq.push_back(MP(tmp.i,tmp.l,L));
                if (L!=m) dq.push_back(MP(j-1,L+1,m));
                dp[j] = f(dq[0].i,j);
                if (dq[0].r==j) dq.pop_front();
                else {
                    Seg temp=dq.front();
                    dq.pop_front();
                    Seg ret=MP(temp.i,temp.l+1,temp.r);
                    dq.push_front(ret);
                }
            }
            else {
                dq.push_back(MP(j-1,j+1,n));
                dp[j] = f(j-1,j);
            }
        }
        if (m!=0)printf("%lld\n",dp[m]);
        else printf("%lld\n",k);
    }
}