ACM-ICPC 2018 沈阳赛区网络预赛 wu-kan

Made In Heaven

Astar 求 K 短路。

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
typedef int ll;
const ll INF=1e9;
struct Graph
{
    struct Vertex
    {
        vector<int> a,b;//相关出边和入边编号
        //int siz,dep,top,dfn;//树链剖分中使用,依次代表子树节点数、深度、所在链的顶端节点、dfs序
    };
    struct Edge
    {
        int from,to;
        ll dist/*,cap*/;//边长、容量,图论算法使用
    };
    vector<Vertex> v;//点集
    vector<Edge> e;//边集
    Graph(int n):v(n) {}
    void add(const Edge &ed)
    {
        //if(ed.from==ed.to)return;//如果有需要请拆点
        v[ed.from].a.push_back(e.size());
        v[ed.to].b.push_back(e.size());
        e.push_back(ed);
    }
};
struct Dijkstra:Graph
{
    vector<ll> d;
    Dijkstra(int n):Graph(n) {}
    void ask(int s)
    {
        d.assign(v.size(),INF);
        priority_queue<pair<ll,int> > q;
        for(q.push(make_pair(d[s]=0,s)); !q.empty();)
        {
            ll dis=-q.top().first;
            int u=q.top().second;
            if(q.pop(),d[u]<dis)continue;
            for(int i=0,k,to; i!=v[u].a.size(); ++i)
                if(k=v[u].a[i],to=e[k].to,
                        d[to]>d[u]+e[k].dist)
                {
                    d[to]=d[u]+e[k].dist;
                    q.push(make_pair(-d[to],to));
                }
        }
    }
};
struct Astar:Dijkstra
{
    vector<ll> ans;
    Astar(int n):Dijkstra(n) {}
    void ask(int s,int t,int k,int T)
    {
        Dijkstra::ask(s);
        ans.assign(k,INF);
        if(d[t]==INF)return;
        vector<int> cnt(v.size(),0);
        priority_queue<pair<ll,int> > q;
        for(q.push(make_pair(-d[t],t)); cnt[s]<k&&!q.empty();)
        {
            ll dis=-q.top().first;
            int u=q.top().second;
            if(u==s)ans[cnt[s]]=dis;
            if(dis>T)return;
            if(q.pop(),++cnt[u]>k)continue;
            for(int i=0,k; i<v[u].b.size(); ++i)
                k=v[u].b[i],q.push(make_pair(d[u]-d[e[k].from]-e[k].dist-dis,e[k].from));
        }
    }
};
int main()
{
    for(int n,m,s,e,k,t; ~scanf("%d%d%d%d%d%d",&n,&m,&s,&e,&k,&t);)
    {
        Astar g(n+1);
        for(int u,v,w; m--;)
        {
            scanf("%d%d%d",&u,&v,&w);
            g.add({u,v,w});
        }
        g.ask(s,e,k,t);
        printf(g.ans[k-1]>t?"Whitesnake!\n":"yareyaredawa\n");
    }
}

Fantastic Graph

转换一下变成一个有源汇上下界网络流模型。

#include<cstdio>
#include<vector>
using namespace std;
typedef int ll;
const ll INF=1e9;
struct Graph
{
    struct Vertex
    {
        vector<int> a/*,b*/;//相关出边和入边编号
        //int siz,dep,top,dfn;//树链剖分中使用,依次代表子树节点数、深度、所在链的顶端节点、dfs序
    };
    struct Edge
    {
        int from,to;
        ll /*dist,*/cap;//边长、容量,图论算法使用
    };
    vector<Vertex> v;//点集
    vector<Edge> e;//边集
    Graph(int n):v(n) {}
    void add(const Edge &ed)
    {
        //if(ed.from==ed.to)return;//如果有需要请拆点
        v[ed.from].a.push_back(e.size());
        //v[ed.to].b.push_back(e.size());
        e.push_back(ed);
    }
};
struct ISAP:Graph
{
    ll flow;
    vector<ll> f;
    vector<int> h,cur,gap;
    ISAP(int n):Graph(n) {}
    void add(Edge ed)
    {
        Graph::add(ed);
        swap(ed.from,ed.to),ed.cap=0;
        Graph::add(ed);
    }
    ll dfs(int s,int u,int t,ll r)
    {
        if(r==0||u==t)return r;
        ll _f,_r=0;
        for(int &i=cur[u],k; i<v[u].a.size(); ++i)
            if(k=v[u].a[i],h[u]==h[e[k].to]+1)
            {
                _f=dfs(s,e[k].to,t,min(r-_r,e[k].cap-f[k]));
                f[k]+=_f,f[k^1]-=_f,_r+=_f;
                if(_r==r||h[s]>=v.size())return _r;
            }
        if(!--gap[h[u]])h[s]=v.size();
        return ++gap[++h[u]],cur[u]=0,_r;
    }
    void ask(int s,int t)
    {
        h.assign(v.size(),0);
        cur.assign(v.size(),0);
        gap.assign(v.size()+2,0);
        /*for(deque<int> q(h[t]=gap[t]=1,t); !q.empty(); q.pop_front())//可选预处理
            for(int i=0,u=q.front(),k,to; i<v[u].a.size(); ++i)
                if(to=e[v[u].a[i]].to,!h[to])
                    ++gap[h[to]=h[u]+1],q.push_back(to);*/
        for(f.assign(e.size(),flow=0); h[s]<v.size();)
            flow+=dfs(s,s,t,INF);
    }
};
int main()
{
    for(int n,m,k,l,r,kase=0; ~scanf("%d%d%d",&n,&m,&k);)
    {
        ISAP g((n+m)*2+9);
        scanf("%d%d",&l,&r);
        for(int i=0,u,v; i<k; ++i)
        {
            scanf("%d%d",&u,&v);
            v+=n;
            g.add({2*u+1,2*v,1});
        }
        int s=2*(n+m+1),t=s+1,ss=t+1,tt=ss+1;
        g.add({t,s,INF});
        for(int i=1; i<=n; ++i)
            g.add({s,2*i,INF});
        for(int i=n+1; i<=n+m; ++i)
            g.add({2*i+1,t,INF});
        for(int i=1; i<=n+m; ++i)
        {
            g.add({2*i,2*i+1,r-l});
            g.add({ss,2*i+1,l});
            g.add({2*i,tt,l});
        }
        g.ask(ss,tt);
        printf("Case %d: %s\n",++kase,g.flow==(n+m)*l?"Yes":"No");
    }
}

Spare Tire

#include<cstdio>
#include<vector>
#define mul(a,b,m) ((a)*(b)%(m))
using namespace std;
typedef long long ll;
const ll M=1e9+7;
ll n,m,ans1,ans2,INV[9];
vector<ll> fac;
void getfac(ll n)
{
    fac.clear();
    for(ll i=2; i*i<=n; ++i)
        if(n%i==0)
            for(fac.push_back(i); n%i==0;)n/=i;
    if(n>1)fac.push_back(n);
}
ll pow(ll a,ll b,ll m)
{
    ll r=1;
    for(a%=m; b; b>>=1,a=mul(a,a,m))
        if(b&1)r=mul(r,a,m);
    return r;
}
void dfs(ll cur,ll num,ll val)
{
    if(cur==fac.size())
    {
        if(val!=1)
        {
            ll t=n/val,k=mul(mul(t*(t+1)/2%M,num%2?M-1:1,M),val,M);
            if(ans1+=k,ans1>=M)ans1-=M;
            if(ans2+=mul(mul(mul(k,(t*2+1),M),INV[3],M),val,M),ans2>=M)ans2-=M;
        }
        return;
    }
    dfs(cur+1,num,val),dfs(cur+1,num+1,val*fac[cur]);
}
int main()
{
    for(ll i=0; i<9; ++i)INV[i]=pow(i,M-2,M);
    while(~scanf("%lld%lld",&n,&m))
    {
        ans1=n*(n+1)/2%M;
        ans2=ans1*(2*n+1)%M*INV[3]%M;
        getfac(m);
        dfs(0,0,1);
        printf("%lld\n",(ans1+ans2)%M);
    }
}

Lattice’s basics in digital electronics

做了一遍就不想再做一遍的沙雕大模拟…为了模拟而模拟。字典树跑掉。

#include<cstdio>
using namespace std;
const int NPOS=-1,N=200009<<2;
struct AhoCorasick
{
    struct Node
    {
        int ch[2],val;
        int &to(char c)
        {
            return ch[c-'0'];
        }
        Node():val(NPOS)
        {
            ch[0]=ch[1]=0;
        }
    } v[N];
    int siz;
    AhoCorasick():siz(1) {}
    void add(char s[],int val)
    {
        int u=0;
        for(int i=0; s[i]; u=v[u].to(s[i++]))
            if(!v[u].to(s[i]))
            {
                v[u].to(s[i])=siz;
                v[siz++]=Node();
            }
        v[u].val=val;
    }
};
char stak[N],data[N];
int t,kase=0,m,n;
int main()
{
    for(scanf("%d",&t); t--;)
    {
        scanf("%d%d",&m,&n);
        AhoCorasick ac;
        for(int i=0,c; i<n; ++i)
        {
            scanf("%d%s",&c,data);
            ac.add(data,c);
        }
        scanf("%s",stak);
        int len=0,siz=0;
        for(int i=0; stak[i]; ++i)
        {
            stak[i]='0'<=stak[i]&&stak[i]<='9'?stak[i]-'0':
                    'a'<=stak[i]&&stak[i]<='z'?stak[i]-'a'+10:
                    stak[i]-'A'+10;
            len+=4;
            for(int j=1; j<=4; ++j)data[len-j]='0'+stak[i]%2,stak[i]/=2;
        }
        for(int i=0,cnt; i+8<len; i+=9)
        {
            for(int j=cnt=0; j<8; ++j)if(data[i+j]=='1')++cnt;
            if(cnt%2!=(data[i+8]=='0'?1:0))continue;
            for(int j=0; j<8; ++j)stak[siz++]=data[i+j];
        }
        for(int i=0,u=0,cnt=0; i<siz; ++i)
            if(ac.v[u=ac.v[u].to(stak[i])].val!=NPOS)
            {
                printf("%c",ac.v[u].val);
                u=0;
                if(++cnt==m)break;
            }
        printf("\n");
    }
}

Supreme Number

#include<stdio.h>
#include<string.h>
char s[127];
int t,n,kase,a[]=
{
    1,2,3,5,7,
    11,13,17,23,31,
    37,53,71,73,113,
    131,137,173,311,317
};
int main()
{
    for(scanf("%d",&t); t--;)
    {
        scanf("%s",s);
        if(strlen(s)>3)n=318;
        else sscanf(s,"%d",&n);
        for(int i=19; ~i; --i)
            if(a[i]<=n)
            {
                printf("Case #%d: %d\n",++kase,a[i]);
                break;
            }
    }
}