yp155136 coding area

2017年9月7日星期四

(Hackerrank) Tower Breakers, Again!

https://www.hackerrank.com/challenges/kitty-and-katty

#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <set>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

#define SZ(x) ((int)(x).size())
typedef pair<int,int> pii;
const int MAX_N = 1e5 +6;
int prime[MAX_N];

void build() {
    prime[0] = prime[1] = 1;
    for (int i=2;MAX_N>i;i++) {
        if (prime[i] == 0) {
            prime[i]=i;
            for (long long j=i*1LL*i;MAX_N>j;j+=i) {
                prime[j] = i;
            }
        }
    }
}

vector<pii> get_prime_divisor(int x) {
    vector<pii> ret;
    while (x!=1) {
        pii tmp;
        tmp.first = prime[x];
        int cnt=0;
        int pp=prime[x];
        while (x%pp==0) {
            x/=pp;
            cnt++;
        }
        tmp.second = cnt;
        ret.emplace_back(tmp);
    }
    return ret;
}

vector<int> get_divisor(int x) {
    vector<pii> prime_divisor=get_prime_divisor(x);
    int sz=SZ(prime_divisor);
    queue<pii> que;
    que.push({1,0});
    vector<int> ret;
    while (!que.empty()) {
        pii p=que.front();
        que.pop();
        if (p.second == sz) {
            ret.emplace_back(p.first);
            continue;
        }
        int t=1;
        for (int i=0;prime_divisor[p.second].second>=i;i++) {
            que.push(make_pair(p.first*t,p.second+1));
            t*=prime_divisor[p.second].first;
        }
    }
    return ret;
}

int dp[MAX_N];

const int MAGIC = 60;

void doo(int id) {
    vector<int> ret=get_divisor(id);
    int cnt[MAGIC];
    sort(ret.begin(),ret.end());
    memset(cnt,0,sizeof(cnt));
    for (int i:ret) {
        if (i==id) continue;
        if (dp[i] == -1) doo(i);
        cnt[((id/i)%2==0?0:dp[i])]=1;
    }
    for (int i=0;MAGIC>i;i++) {
        if (!cnt[i]) {
            dp[id] = i;
            break;
        }
    }
}

int main () {
    build();
    int T;
    scanf("%d",&T);
    memset(dp,-1,sizeof(dp));
    dp[1] = 0;
    while (T--) {
        int n;
        scanf("%d",&n);
        int ans=0;
        for (int i=1;n>=i;i++) {
            int h;
            scanf("%d",&h);
            if (dp[h] != -1) ans ^= dp[h];
            else {
                doo(h);
                ans ^= dp[h];
            }
        }
        if (ans) puts("1");
        else puts("2");
    }
}

(Hackerrank) Tower Breakers, Revisited!

https://www.hackerrank.com/challenges/tower-breakers-revisited-1

SG value

#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <set>
#include <queue>
#include <cstring>
using namespace std;

#define SZ(x) ((int)(x).size())
typedef pair<int,int> pii;
const int MAX_N = 1e6 +6;
int prime[MAX_N];

void build() {
    prime[0] = prime[1] = 1;
    for (int i=2;MAX_N>i;i++) {
        if (prime[i] == 0) {
            prime[i]=i;
            for (long long j=i*1LL*i;MAX_N>j;j+=i) {
                prime[j] = i;
            }
        }
    }
}

vector<pii> get_prime_divisor(int x) {
    vector<pii> ret;
    while (x!=1) {
        pii tmp;
        tmp.first = prime[x];
        int cnt=0;
        int pp=prime[x];
        while (x%pp==0) {
            x/=pp;
            cnt++;
        }
        tmp.second = cnt;
        ret.emplace_back(tmp);
    }
    return ret;
}

vector<int> get_divisor(int x) {
    vector<pii> prime_divisor=get_prime_divisor(x);
    int sz=SZ(prime_divisor);
    queue<pii> que;
    que.push({1,0});
    vector<int> ret;
    while (!que.empty()) {
        pii p=que.front();
        que.pop();
        if (p.second == sz) {
            ret.emplace_back(p.first);
            continue;
        }
        int t=1;
        for (int i=0;prime_divisor[p.second].second>=i;i++) {
            que.push(make_pair(p.first*t,p.second+1));
            t*=prime_divisor[p.second].first;
        }
    }
    return ret;
}

int dp[MAX_N];

const int MAGIC = 30;

void doo(int id) {
    vector<int> ret=get_divisor(id);
    int cnt[MAGIC];
    memset(cnt,0,sizeof(cnt));
    for (int i:ret) {
        if (i==id) continue;
        if (dp[i] == -1) doo(i);
        cnt[dp[i]]=1;
    }
    for (int i=0;MAGIC>i;i++) {
        if (!cnt[i]) {
            dp[id] = i;
            break;
        }
    }
}

int main () {
    build();
    int T;
    scanf("%d",&T);
    memset(dp,-1,sizeof(dp));
    dp[1] = 0;
    while (T--) {
        int n;
        scanf("%d",&n);
        int ans=0;
        for (int i=1;n>=i;i++) {
            int h;
            scanf("%d",&h);
            if (dp[h] != -1) ans ^= dp[h];
            else {
                doo(h);
                ans ^= dp[h];
            }
        }
        if (ans) puts("1");
        else puts("2");
    }
}

2017年9月6日星期三

(Hackerrank) Balanced Forest

https://www.hackerrank.com/challenges/balanced-forest/problem

Treap + 啟發式合併

#include <iostream>
#include <cstdio>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <algorithm>
using namespace std;

typedef long long LL;
const LL INF = 1e17 + 6;
const int MAX_P = 1e6 + 6;

struct Treap {
    static Treap mem[MAX_P];
    Treap *lc,*rc;
    LL key;
    int pri,sz;
    Treap(){
        
    }
    Treap(LL _key) : key(_key),pri(rand()),sz(1),lc(NULL),rc(NULL) {
        
    }
} Treap::mem[MAX_P],*ptr=Treap::mem;

int Sz(const Treap* t) {
    return t?t->sz:0;
}

void pull(Treap* t) {
    if (!t) return;
    t->sz = Sz(t->lc) + Sz(t->rc) + 1;
}

Treap* merge(Treap* a,Treap* b) {
    if (!a || !b) return a?a:b;
    else if (a->pri > b->pri) {
        a->rc=merge(a->rc,b);
        pull(a);
        return a;
    }
    else {
        b->lc=merge(a,b->lc);
        pull(b);
        return b;
    }
}

void split(Treap* t,LL k,Treap* &a,Treap* &b) {
    if (!t) a=b=NULL;
    else if (t->key <= k) {
        a=t;
        split(t->rc,k,a->rc,b);
        pull(a);
    }
    else {
        b=t;
        split(t->lc,k,a,b->lc);
        pull(b);
    }
}

bool ffind(Treap* &t,LL x) {
    Treap *tl,*tr;
    split(t,x-1,tl,t);
    split(t,x,t,tr);
    bool ret=(Sz(t)!=0);
    t=merge(tl,merge(t,tr));
    return ret;
}

const int MAX_N = 5e4 +6;

vector<int> edg[MAX_N];
LL a[MAX_N];
LL sz[MAX_N];
LL ans;

void dfs1(int id,int par) {
    sz[id] = a[id];
    for (int i:edg[id]) {
        if (i!=par) {
            dfs1(i,id);
            sz[id] += sz[i];
        }
    }
}

void addd(Treap* &t,LL val) {
    Treap *tl;
    split(t,val,tl,t);
    t=merge(merge(tl,new(++ptr)Treap(val)),t);
}

void dell(Treap* &t,LL val) {
    Treap *tl,*tr;
    split(t,val-1,tl,t);
    split(t,val,t,tr);
    t=merge(merge(tl,t->lc),merge(t->rc,tr));
}

int n;
LL tot=0;

Treap* root;

LL get_ans(LL x,LL n_2x) {
    if (x<n_2x) return INF;
    else return x-n_2x;
}

void dfs2(int id,int par) {
    //sz[id] --> x
    //see have 2*x or tot-x
    if (ffind(root,2*sz[id])) {
        ans = min(ans,get_ans(sz[id],tot-2*sz[id]));
    }
    if (ffind(root,tot-sz[id])) {
        ans = min(ans,get_ans(sz[id],tot-2*sz[id]));
    }
    //sz[id] --> tot-2*x
    //see have tot-x
    if ((tot-sz[id])%2==0) {
        LL x=(tot-sz[id])/2;
        if (ffind(root,tot-x)) {
            ans = min(ans,get_ans(x,tot-2*x));
        }
    }
    addd(root,sz[id]);
    for (int i:edg[id]) {
        if (i!=par) {
            dfs2(i,id);
        }
    }
    dell(root,sz[id]);
}

void split_by_sz(Treap* t,int k,Treap* &a,Treap* &b) {
    if (!t) a=b=NULL;
    else if (Sz(t->lc) + 1 <= k) {
        a=t;
        split_by_sz(t->rc,k-Sz(t->lc)-1,a->rc,b);
        pull(a);
    }
    else {
        b=t;
        split_by_sz(t->lc,k,a,b->lc);
    }
}

void ddfs(Treap* &a,Treap* t) {
    LL now=t->key;
    //now --> x
    //find x or tot-2*x
    if (ffind(a,now)) {
        ans = min(ans,get_ans(now,tot-2*now));
    }
    if (ffind(a,tot-2*now)) {
        ans = min(ans,get_ans(now,tot-2*now));
    }
    //now --> tot-2*x;
    //find x
    if ((tot-now)%2 == 0) {
        LL x=(tot-now)/2;
        if (ffind(a,x)) {
            ans = min(ans,get_ans(x,tot-2*x));
        }
    }
    if (t->lc) ddfs(a,t->lc);
    if (t->rc) ddfs(a,t->rc);
}

void mmerge(Treap* &a,Treap* &b) {
    ddfs(a,b);
    while(Sz(b)) {
        Treap* t;
        split_by_sz(b,1,t,b);
        Treap *tl;
        split(a,t->key-1,a,tl);
        a=merge(merge(a,t),tl);
    }
}

Treap* sagiri[MAX_N];

void dfs3(int id,int par) {
    Treap* ret=NULL;
    vector<Treap*> v;
    for (int i:edg[id]) {
        if (i!=par) {
            dfs3(i,id);
            Treap* rett=sagiri[i];
            if (Sz(rett) > Sz(ret)) {
                swap(rett,ret);
            }
            if (rett != NULL)v.push_back(rett);
        }
    }
    for (auto i:v) {
        mmerge(ret,i);
    }
    addd(ret,sz[id]);
    sagiri[id] = ret;
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        ptr=Treap::mem;
        scanf("%d",&n);
        for (int i=0;n>=i;i++) {
            edg[i].clear();
        }
        for (int i=1;n>=i;i++) {
            scanf("%lld",&a[i]);
        }
        for (int i=1;n-1>=i;i++) {
            int x,y;
            scanf("%d %d",&x,&y);
            edg[x].push_back(y);
            edg[y].push_back(x);
        }
        ans = INF;
        dfs1(1,1);
        root=NULL;
        tot=sz[1];
        dfs2(1,1);
        dfs3(1,1);
        if (ans == INF) ans=-1;
        printf("%lld\n",ans);
    }
}

2017年9月1日星期五

(Hackerrank) Kitty's Calculations on a Tree [重心剖分]

https://www.hackerrank.com/challenges/kittys-calculations-on-a-tree

重心剖分 (centroid decomposition)

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pii;
const int MAX_N = 2e5 + 6;
const int MAX_P = 19;
const LL mod = 1e9 + 7;

vector<int> edg[MAX_N];
int dis[MAX_P][MAX_N];
bool visit[MAX_N];

struct Cen {
    int par;
    int depth;
    pii val_v_av;  //first --> val, second --> minus
    pii val_v;
} cen[MAX_N];

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

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

#define SZ(x) ((int)(x).size())

int get_cen(int id) {
    v.clear();
    dfs2(id);
    int tot=SZ(v);
    int cen=-1;
    for (int i:v) {
        if (max(mx[i],tot-sz[i]) <= tot/2) {
            cen=i;
        }
        visit[i]=false;
    }
    return cen;
}

void dfs3(int id,int par,int cen_depth,int dist)  {
    dis[cen_depth][id] = dist;
    for (int i:edg[id]) {
        if (!visit[i] && i!=par) {
            dfs3(i,id,cen_depth,dist+1);
        }
    }
}

void dfs(int id,int cen_par,int cen_depth) {
    int ccen=get_cen(id);
    dfs3(ccen,ccen,cen_depth,0);
    cen[ccen]={cen_par,cen_depth,{0,0},{0,0}};
    visit[ccen]=1;
    for (int i:edg[ccen]) {
        if (!visit[i]) dfs(i,ccen,cen_depth+1);
    }
}

pii operator+(const pii &p1,const pii &p2) {
    return make_pair(p1.first+p2.first,p1.second+p2.second);
}

pii operator-(const pii &p1,const pii &p2) {
    return make_pair(p1.first-p2.first,p1.second-p2.second);
}

pii operator+=(pii &p1,const pii &p2) {
    p1 = p1 + p2;
    return p1;
}

pii operator-=(pii &p1,const pii &p2) {
    p1 = p1 - p2;
    return p1;
}

void Pure(pii &p) {
    p.first = (p.first%mod + mod) % mod;
    p.second = (p.second%mod + mod) % mod;
}

void addd(LL x) {
    LL p=x;
    while (p!=-1) {
        cen[p].val_v += {x,0};
        cen[p].val_v_av += {x*dis[cen[p].depth][x],0};
        if (cen[p].par != -1) {
            int par=cen[p].par;
            cen[p].val_v -= {0,x};
            cen[p].val_v_av -= {0,x*dis[cen[par].depth][x]};
        }
        Pure(cen[p].val_v);
        Pure(cen[p].val_v_av);
        p=cen[p].par;
    }
}

void dell(LL x) {
    LL p=x;
    while (p!=-1) {
        cen[p].val_v -= {x,0};
        cen[p].val_v_av -= {x*dis[cen[p].depth][x],0};
        if (cen[p].par != -1) {
            int par=cen[p].par;
            cen[p].val_v += {0,x};
            cen[p].val_v_av += {0,x*dis[cen[par].depth][x]};
        }
        Pure(cen[p].val_v);
        Pure(cen[p].val_v_av);
        p=cen[p].par;
    }
}

LL query(LL x) {
    LL ret=0;
    LL v=0;
    LL v_av=0;
    int p=x;
    while (p!=-1) {
        v += cen[p].val_v.first;
        v_av += cen[p].val_v_av.first;
        ret += x*v_av;
        ret %= mod;
        ret += x*dis[cen[p].depth][x]*v;
        ret %= mod;
        v = cen[p].val_v.second;
        v_av = cen[p].val_v_av.second;
        p=cen[p].par;
    }
    return ret;
}

LL pow(LL a,LL n,LL mod) {
    if (n==0) return 1;
    else if (n==1) return a;
    LL ret=pow(a,n/2,mod);
    ret*=ret;
    ret%=mod;
    if (n&1) {
        ret*=a;
        ret%=mod;
    }
    return ret;
}

int main () {
    int n,q;
    scanf("%d %d",&n,&q);
    for (int i=1;n-1>=i;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        edg[a].push_back(b);
        edg[b].push_back(a);
    }
    dfs(1,-1,0);
    while (q--) {
        int k;
        scanf("%d",&k);
        vector<int> v;
        while (k--) {
            int x;
            scanf("%d",&x);
            v.push_back(x);
        }
        for (int i:v) addd(i);
        LL ans=0;
        for (int i:v) {
            ans += query(i);
            ans%=mod;
        }
        for (int i:v) dell(i);
        printf("%lld\n",(ans*pow(2,mod-2,mod) + mod)%mod);
    }
}

2017年8月28日星期一

(Hackerrank) Coprime Paths [樹上莫隊]

https://www.hackerrank.com/challenges/coprime-paths

樹上莫隊

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cmath>
using namespace std;

typedef long long LL;
const int MAX_N = 25006;
const int MAX_P = 1e7 + 1;
const int MAX_Q = 15;
int prime[MAX_P];

void addd(int x,LL val);
void subb(int x,LL val);

struct P {
    int n;
    int p[3];
    int tot;
    void input() {
        scanf("%d",&n);
        tot=0;
        while (n != 1) {
            int pp=prime[n];
            p[tot++] = pp;
            while (n%pp==0) n/=pp;
        }
    }
    void add() {
        for (int i=0;(1<<tot)>i;i++) {
            int sz=0;
            int xx=1;
            for (int j=0;tot>j;j++) {
                if (((1<<j)&i) != 0) {
                    sz++;
                    xx *= p[j];
                }
            }
            if (sz == 0) continue;
            else if (sz%2 == 0) addd(xx,1);
            else addd(xx,-1);
        }
    }
    void sub() {
        for (int i=0;(1<<tot)>i;i++) {
            int sz=0;
            int xx=1;
            for (int j=0;tot>j;j++) {
                if (((1<<j)&i) != 0) {
                    sz++;
                    xx *= p[j];
                }
            }
            if (sz == 0) continue;
            else if (sz%2 == 0) subb(xx,1);
            else subb(xx,-1);
        }
    }
} p[MAX_N];

void build() {
    prime[0] = prime[1] = 1;
    for (int i=2;MAX_P>i;i++) {
        if (prime[i] == 0) {
            prime[i] = i;
            for (LL j=i;MAX_P>j;j+=i) {
                prime[j] = i;
            }
        }
    }
}

vector<int> G[MAX_N];
stack<int,vector<int> > st;
int B;  //block size
int block[MAX_N],b_cnt;  //block[x] --> block id of x
int dfn[MAX_N],dfs_time; //dfn[i] --> time that dfs(i)
int depth[MAX_N];
int pa[MAX_N];
int pin[MAX_N],pout[MAX_N];
int stamp;

#define SZ(x) ((int)(x).size())

void dfs(int u,int cur_depth,int par) {
    pin[u] = ++stamp;
    pa[u] = par;
    depth[u] = cur_depth;
    dfn[u] = dfs_time++;
    int buttom = SZ(st);
    for (int v:G[u]) {
        if (v==par) continue;
        dfs(v,cur_depth+1,u);
        if (SZ(st) - buttom >= B) {
            while (SZ(st) != buttom) {
                block[st.top()] = b_cnt;
                st.pop();
            }
            b_cnt++;
        }
    }
    st.emplace(u);
    pout[u] = ++stamp;
}

void make_block(int root,int n) {
    B=sqrt(n);
    b_cnt = dfs_time = 0;
    dfs(root,1,root);
    while (SZ(st) != 0) {
        block[st.top()] = b_cnt-1;
        st.pop();
    }
}

int cnt[MAX_P];

struct QUERY {
    int u,v,id;
    void give_val(int _u,int _v,int _id) {
        u=_u;
        v=_v;
        if (dfn[u] > dfn[v]) swap(u,v);
        id=_id;
    }
    bool operator<(const QUERY &b) {
        if (block[u] != block[b.u]) return block[u] < block[b.u];
        return dfn[v] < dfn[b.v];
    }
} query[MAX_N];

int ans[MAX_N];

int lca[MAX_Q][MAX_N];

void pre_lca(int n) {
    for (int i=0;MAX_Q>i;i++) {
        for (int j=1;n>=j;j++) {
            if (!i) lca[i][j] = pa[j];
            else lca[i][j] = lca[i-1][lca[i-1][j]];
        }
    }
}

bool is_anc(int son,int par) {
    return pin[par] <= pin[son] && pout[son] <= pout[par];
}

int get_lca(int u,int v) {
    if (depth[u] > depth[v]) swap(u,v);
    if (is_anc(v,u)) return u;
    for (int i=MAX_Q-1;i>=0;i--) {
        if (!is_anc(v,lca[i][u])) {
            u=lca[i][u];
        }
    }
    return lca[0][u];
}

#define minus sagiri

LL tot_sz;
LL minus;

void addd(int x,LL val) {
    if (cnt[x] >= 1) {
        minus -= val*(cnt[x])*(cnt[x]-1)/2;
        cnt[x]++;
        minus += val*(cnt[x])*(cnt[x]-1)/2;
    }
    else {
        cnt[x]++;
    }
}

void subb(int x,LL val) {
    if (cnt[x] >= 2) {
        minus -= val*(cnt[x])*(cnt[x]-1)/2;
        cnt[x]--;
        minus += val*(cnt[x])*(cnt[x]-1)/2;
    }
    else {
        cnt[x]--;
    }
}

void add(P x) {
    tot_sz++;
    x.add();
}

void sub(P x) {
    tot_sz--;
    x.sub();
}

bool in_set[MAX_N];

void flip (int x) {
    if (in_set[x]) sub(p[x]);
    else add(p[x]);
    in_set[x] ^= 1;
}

void move(int a,int b) {
    int lca=get_lca(a,b);
    for (;a!=lca;a=pa[a]) flip(a);
    for (;b!=lca;b=pa[b]) flip(b);
}

int main () {
    build();
    int n,q;
    scanf("%d %d",&n,&q);
    for (int i=1;n>=i;i++) {
        p[i].input();
    }
    for (int i=1;n-1>=i;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    make_block(1,n);
    pre_lca(n);
    for (int i=1;q>=i;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        query[i].give_val(a,b,i);
    }
    sort(query+1,query+q+1);
    int u=1,v=1;
    tot_sz = minus = 0;
    for (int i=1;q>=i;i++) {
        int uu=query[i].u,vv=query[i].v;
        move(u,uu);
        move(v,vv);
        u=uu;
        v=vv;
        int lca=get_lca(u,v);
        add(p[lca]);
        ans[query[i].id] = tot_sz*(tot_sz-1)/2 + minus;
        sub(p[lca]);
    }
    for (int i=1;q>=i;i++) {
        printf("%d\n",ans[i]);
    }
}

(Hackerrank) Demanding Money

https://www.hackerrank.com/challenges/borrowing-money

很精湛的拆點作法

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

typedef long long LL;
typedef pair<LL,LL> pii;
const int MAX_N = 35;
const int MAGIC = 20;

int weight[MAX_N];
bool adj[MAX_N][MAX_N];
pii dp[(1<<14)];

bool check(vector<int> v) {
    for (int i=0;v.size()>i;i++) {
        for (int j=0;v.size()>j;j++) {
            if (adj[v[i]][v[j]]) return false;
        }
    }
    return true;
}

int main () {
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=0;n>i;i++) {
        scanf("%d",&weight[i]);
    }
    for (int i=1;m>=i;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        --a;
        --b;
        adj[a][b] = adj[b][a] = 1;
    }
    if (n <= 20) {
        int mx=0;
        int mx_cnt=0;
        for (int i=0;(1<<n)>i;i++) {
            vector<int> v;
            int tot=0;
            for (int j=0;n>j;j++) {
                if (((1<<j)&i) != 0) {
                    v.push_back(j);
                    tot += weight[j];
                }
            }
            if (check(v)) {
                if (tot > mx) {
                    mx=tot;
                    mx_cnt=1;
                }
                else if (tot==mx) {
                    mx_cnt++;
                }
            }
        }
        printf("%d %d\n",mx,mx_cnt);
    }
    else {
        int nn=n-MAGIC;
        for (int i=0;(1<<nn)>i;i++) {
            vector<int> v;
            for (int j=0;nn>j;j++) {
                if (((1<<j)&i) != 0) {
                    v.push_back(j+MAGIC);
                }
            }
            int nnn=v.size();
            for (int ii=0;(1<<nnn)>ii;ii++) {
                vector<int> vv;
                int tot=0;
                for (int jj=0;nnn>jj;jj++) {
                    if (((1<<jj)&ii) != 0) {
                        vv.push_back(v[jj]);
                        tot += weight[v[jj]];
                    }
                }
                if (check(vv)) {
                    if (tot > dp[i].first) {
                        dp[i].first = tot;
                        dp[i].second = 1;
                    }
                    else if (tot == dp[i].first) {
                        dp[i].second++;
                    }
                }
            }
        }
        int mx=0;
        LL mx_cnt=0;
        int nnnn=20;
        for (int i=0;(1<<nnnn)>i;i++) {
            vector<int> v;
            int tot=0;
            for (int j=0;nnnn>j;j++) {
                if (((1<<j)&i) != 0) {
                    v.push_back(j);
                    tot += weight[j];
                }
            }
            if (check(v)) {
                int mask=0;
                for (int j=MAGIC;n>j;j++) {
                    bool okayy=true;
                    for (int ii=0;v.size()>ii;ii++) {
                        if (adj[j][v[ii]]) okayy=false;
                    }
                    if (okayy == true) mask += (1<<(j-MAGIC));
                }
                LL cnt = max(1LL,dp[mask].second);
                tot += dp[mask].first;
                if (tot > mx) {
                    mx=tot;
                    mx_cnt=cnt;
                }
                else if (tot==mx) {
                    mx_cnt+=cnt;
                }
            }
        }
        printf("%d %lld\n",mx,mx_cnt);
    }
}

2017年8月18日星期五

(Sky OJ) 154. DAY 4 PH. 字串雜湊

https://pc2.tfcis.org/sky/index.php/problem/view/154/

很奇怪的min cut XD

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

typedef long long LL;

struct Dinic {
    static const int MAX_N = 4e4 + 6;
    struct Edge {
        LL to,cap,rev;
    };
    vector<Edge> edg[MAX_N];
    int n,s,t;
    void init(int _n,int _s,int _t) {
        n=_n;
        s=_s;
        t=_t;
        for (int i=0;n+1>=i;i++) {
            edg[i].clear();
        }
    }
    #define SZ(x) ((int)(x).size())
    void add_edge(int from,int to,int cap) {
        edg[from].push_back({to,cap,SZ(edg[to])});
        edg[to].push_back({from,0,SZ(edg[from])-1});
    }
    int iter[MAX_N],level[MAX_N];
    void BFS() {
        queue<int> que;
        memset(level,-1,sizeof(level));
        level[s] = 0;
        que.push(s);
        while (!que.empty()) {
            int t=que.front();
            que.pop();
            for (Edge &e:edg[t]) {
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[t] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    LL dfs(int id,LL flow) {
        if (id == t) return flow;
        for (int &i=iter[id];SZ(edg[id])>i;i++) {
            Edge &e=edg[id][i];
            if (e.cap > 0 && level[e.to] == level[id] + 1) {
                int ret=dfs(e.to,min(flow,e.cap));
                if (ret>0) {
                    e.cap -= ret;
                    edg[e.to][e.rev].cap += ret;
                    return ret;
                }
            }
        }
        return 0;
    }
    static const LL INF = 1e15 + 7;
    LL flow() {
        LL ret=0;
        while (1) {
            BFS();
            if (level[t] == -1) break;
            memset(iter,0,sizeof(iter));
            LL tmp=0;
            while ((tmp = dfs(s,INF)) > 0) {
                ret += tmp;
            }
        }
        return ret;
    }
} dinic;

typedef long long LL;
typedef vector<LL> vint;
const int MAX_N = 106;
const LL mod = 71234;
const LL INF = 1e9 +7;
int v[144];

vint dp[MAX_N];
vint mn[MAX_N];
vint edg[MAX_N];
int deg[MAX_N];
bool visit[MAX_N];
#define SZ(x) ((int)(x).size())
vint dp2[MAX_N];
int ppre[MAX_N];

int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >>n >>m;
    for (int i='a';'z'>=i;i++) {
        cin >>v[i];
    }
    for (int i=1;n>=i;i++) {
        dp[i].push_back(INF);
        string s;
        cin >> s;
        LL pre=0;
        int sz=0;
        for (int j=0;s.size()>j;j++) {
            pre *= (j);
            pre += v[s[j]];
            pre %= mod;
            if (SZ(s) % (j+1) == 0) {
                dp[i].push_back(pre);
                sz++;
            }
        }
        ppre[i] = ppre[i-1] + sz;
    }
    int s=0,t=ppre[n] + 1;
    dinic.init(t,s,t);
    for (int i=1;n>=i;i++) {
        int first=ppre[i-1];
        dinic.add_edge(s,first+1,INF);
        for (int j=1;SZ(dp[i])>j;j++) {
            if (j==SZ(dp[i]) - 1) dinic.add_edge(first+j,t,dp[i][j]);
            else dinic.add_edge(first+j,first+j+1,dp[i][j]);
        }
    }
    for (int i=1;m>=i;i++) {
        int x,y;
        cin >> x >> y;
        int firstx=ppre[x-1],firsty=ppre[y-1];
        for (int j=1;min(SZ(dp[x]),SZ(dp[y])) > j;j++) {
            dinic.add_edge(firstx+j,firsty+j,INF);
        }
    }
    cout<<dinic.flow()<<'\n';
}

訂閱：文章 (Atom)

2017年9月7日 星期四

2017年9月6日 星期三

2017年9月1日 星期五

2017年8月28日 星期一

2017年8月18日 星期五

2017年9月7日星期四

2017年9月6日星期三

2017年9月1日星期五

2017年8月28日星期一

2017年8月18日星期五