要是k有s位二进制1,1)之间为新鲜边)

难题链接: 标题链接

老C的任务

【SinGuLaRiTy-1014】 Copyright (c) SinGuLaRiTy 2017. All Rights
Reserved.

题意:假使一个数二进制n有k位1,那么f1[n]
= k,假设k有s位二进制1,那么f2[n] = f1[k] = s.
 如此往复,直到fx[n] =
1,此时的x正是n的”K值“,以往须要[L,R]内的”K值“为X的数有多少个。(1<=L<=翼虎<=10^18)

难点大体:

敬重贰个二维平面,先河给出一些点及其权.多次打听有个别矩形内的权和.
n,m <= 100000

对于具有的主题材料:Time Limit:1s  |  Memory:256 MB

解法:首先能够见见10^18最多独有67人左右的数,所以我们只需管理1~61之间每一个数有多少个1,就能够见道1~61之间每种数”K值“是有一些。

题解:

签到题.
CDQ水一水.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
    x=0;static char ch;static bool flag;flag = false;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    while(x=(x<<1)+(x<<3)+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
const int maxn = 100010;
const int maxm = maxn;
struct Node{
    int x,y;
    int type,val,id;
    Node(){}
    Node(const int &a,const int &b,
     const int &c,const int &d,const int &e){
        x = a;y = b;type = c;val = d;id = e;
    }
}q[maxn*6];
#define lowbit(x) (x&-x)
int n,m,mxlim;
ll c[maxn*6];int vis[maxn*6],T;
inline void modify(int x,ll d){
    for(;x <= mxlim;x += lowbit(x)){
        if(vis[x] == T) c[x] += d;
        else c[x] = d,vis[x] = T;
    }
}
inline ll query(int x){
    ll ret = 0;
    for(;x;x-=lowbit(x)) if(vis[x] == T) ret += c[x];
    return ret;
}
int qcnt = 0;ll ans[maxm];
void solve(int l,int r){
    if(l == r) return ;
    int mid = l+r >> 1;
    solve(l,mid);solve(mid+1,r);
    ++ T;rg i = l,j = mid+1,k = l;
    static Node tmp[maxn*6];
    while(i <= mid || j <= r){
        if(i > mid || (j <= r && q[j].x < q[i].x)){
            if(q[j].type == 2){
            ans[q[j].id] += query(q[j].y)*q[j].val;
            }
            tmp[k++] = q[j++];
        }else{
            if(q[i].type == 1) modify(q[i].y,q[i].val);
            tmp[k++] = q[i++];
        }
    }
    rep(i,l,r) q[i] = tmp[i];
    return ;
}
struct num{
    int x,y,val;
}p[maxn];
struct number{
    int x1,y1,x2,y2;
}nu[maxm];
int b[maxn*6],cnt;
int main(){
    read(n);read(m);
    rg x,y,v;
    rep(i,1,n){
        read(p[i].x);read(p[i].y);read(p[i].val);
        b[++cnt] = p[i].y;
    }
    rg xx,yy;
    rep(i,1,m){
        read(x);read(y);read(xx);read(yy);
        b[++cnt] = y;b[++cnt] = yy;
        if(x > xx) swap(x,xx);
        if(y > yy) swap(y,yy);
        nu[i].x1 = x;nu[i].y1 = y;
        nu[i].x2 = xx;nu[i].y2 = yy;
    }
    sort(b+1,b+cnt+1);
    rep(i,1,n){
        p[i].y = lower_bound(b+1,b+cnt+1,p[i].y) - b;
        x = p[i].x;y = p[i].y;v = p[i].val;
        q[++qcnt] = Node(x,y,1,v,0);
    }
    rep(i,1,m){
        y = lower_bound(b+1,b+cnt+1,nu[i].y1) - b;
        yy = lower_bound(b+1,b+cnt+1,nu[i].y2) - b;
        x = nu[i].x1;xx = nu[i].x2;
        q[++qcnt] = Node(xx,yy,2,1,i);
        q[++qcnt] = Node(x-1,yy,2,-1,i);
        q[++qcnt] = Node(xx,y-1,2,-1,i);
        q[++qcnt] = Node(x-1,y-1,2,1,i);
    }
    mxlim = cnt;
    solve(1,qcnt);
    rep(i,1,m){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

第一题:完美系列

下一场就将求[L,R]中间的个数形成求[1,R]-[1,L-1],所以我们只需数出对于每种数n,[1,n]中间有多少个数的”K值“为X就可以。

题目: 老 C 的方块

【标题陈述】

给你四个长短为n(1<=n<=100,000)的当然数数列,当中每贰个数都低于等于10亿,现在给您三个k,表示您最多能够去除k类数。数列中一样的数字被称作一类数。设该数列中级知识分子足全体的数字也就是的延续子类别被称呼完美体系,你的职分正是经过删数使得该数列中的最长完美种类尽量长。

对此二进制来说,可以如此搜索出来:

标题大要:

给定多个这样的Lacrosse行C列网格图:加粗边称为特殊边
图片 1
概念若出现下列意况本质一样的意况则非法.
图片 2
于今加以网格图内什么格子是存在的及其被去除的代价共n个
最小化使得网格图合法的代价.
R,C,n <= 100000

【输入】

第一行四个整数N,K。

接下来N行,每行1个整数,表示第i个数。

比方说<=101001,要满足有k个1的数的个数,那么大家从高位往低位扫,扫到第三个1,那么未来有三种状态:

题解:

着眼全数非法的状态.
我们开采其实便是独辟蹊径边两端不能都有大小超越2的四连块.(不通过特别边)
据此大家得以列出一些事关:
一经将标题中提交的网格图的行列看成横纵坐标轴:(即(1,1)和(2,1)之间为非凡边)
笔者们能够博得这么的涉嫌:

对此非常边(3,2) – (4,2)来讲.
假定要那条优异边合法,那么必须是两侧不可能何况涵盖大小超越2的四连块.
这就是说只要大家删除(3,2)大概(4,2)那是必然知足的.
下边就是不删除(3,2)可能(4,2)的情景,那么我们领略:
依旧全体刨除(3,1),(2,2),(3,3),要么全体剔除(4,1),(5,2),(4,3).
接下来大家开采大家得以对网格图举办三色染色:创设最小割模型.
一经大家将(3,1),(2,2),(3,3)染成浅绿灰那么(4,1),(5,2),(4,3)一定是紫罗兰色.
然后将具有在奇特边两边的点染成红棕.
能够创设最小割模型:

图片 3

浅紫边为除去相应格子的代价,藤黄均为inf,海水绿边为特别边两边的独家的代价的异常的小值.
跑最小割就能够.

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
    x=0;char ch;bool flag = false;
    while(ch=getchar(),ch<'!'); if(ch == '-') ch=getchar(),flag = true;
    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
typedef pair<int,int> pa;
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
struct Edge{
    int to,next,cap;
}G[maxn*10];
int head[maxn],cnt = 1;
void add(int u,int v,int c){
    G[++cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt;
    G[cnt].cap = c;
}
inline void insert(int u,int v,int c){
    add(u,v,c);add(v,u,0);
}
#define v G[i].to
int dis[maxn],q[maxn],l,r,S,T;
bool bfs(){
    memset(dis,-1,sizeof dis);
    l = 0;r = -1;q[++r] = S;
    dis[S] = 0;
    while(l <= r){
        int u = q[l++];
        for(int i = head[u];i;i=G[i].next){
            if(dis[v] == -1 && G[i].cap != 0){
                dis[v] = dis[u] + 1;
                q[++r] = v;
            }
        }
    }return dis[T] != -1;
}
int dfs(int u,int f){
    if(u == T || f == 0) return f;
    int ret = 0;
    for(int i = head[u];i;i=G[i].next){
        if(dis[v] == dis[u] + 1 && G[i].cap){
            int x = dfs(v,min(f,G[i].cap));
            f -= x;ret += x;
            G[i].cap -= x;
            G[i^1].cap += x;
            if(f == 0) break;
        }
    }return ret;
}
inline int dinic(){
    int ret = 0;
    while(bfs()) ret += dfs(S,inf);
    return ret;
}
#undef v
inline bool ca(int x,int y){
    int id = (x + 1) >> 1;
    if(id & 1) return (y&1) == 1;
    else return (y & 1) == 0;
}
inline bool cb(int x,int y){
    int id = (x + 1) >> 1;
    if(id & 1){
        if((y & 1) == 1) return false;
        return (x & 1) == 1;
    }else{
        if((y & 1) == 0) return false;
        return (x & 1) == 0;
    }
}
inline bool cc(int x,int y){
    int id = (x + 1) >> 1;
    if(id & 1){
        if((y & 1) == 1) return false;
        return (x & 1) == 0;
    }else{
        if((y & 1) == 0) return false;
        return (x & 1) == 1;
    }
}
int d1[3][2] = {{-1,0},{0,1},{0,-1}};
int d2[3][2] = {{1,0},{0,1},{0,-1}};
map<pa,int>mp;
struct Node{
    int x,y,w;
}p[maxn];
int main(){
    int C,R,n;read(C);read(R);read(n);
    S = maxn - 5;T = S + 1;
    rep(i,1,n){
        read(p[i].x);read(p[i].y);read(p[i].w);
        mp[make_pair(p[i].x,p[i].y)] = i;
        if(cb(p[i].x,p[i].y)) insert(S,i,p[i].w);
        if(cc(p[i].x,p[i].y)) insert(i,T,p[i].w);
    }
    rep(i,1,n){
        if( (p[i].x & 1) && ca(p[i].x,p[i].y) 
            && (mp.count(make_pair(p[i].x+1,p[i].y)))){
            rg j = mp[make_pair(p[i].x+1,p[i].y)];
            if(p[i].y & 1){
                insert(i,j,min(p[i].w,p[j].w));
                rep(k,0,2){
                    rg nx = p[i].x + d1[k][0];
                    rg ny = p[i].y + d1[k][1];
                    if(!mp.count(make_pair(nx,ny))) continue;
                    insert(mp[make_pair(nx,ny)],i,inf);
                }
                rep(k,0,2){
                    rg nx = p[j].x + d2[k][0];
                    rg ny = p[j].y + d2[k][1];
                    if(!mp.count(make_pair(nx,ny))) continue;
                    insert(j,mp[make_pair(nx,ny)],inf);
                }
            }else{
                insert(j,i,min(p[i].w,p[j].w));
                rep(k,0,2){
                    rg nx = p[i].x + d1[k][0];
                    rg ny = p[i].y + d1[k][1];
                    if(!mp.count(make_pair(nx,ny))) continue;
                    insert(i,mp[make_pair(nx,ny)],inf);
                }
                rep(k,0,2){
                    rg nx = p[j].x + d2[k][0];
                    rg ny = p[j].y + d2[k][1];
                    if(!mp.count(make_pair(nx,ny))) continue;
                    insert(mp[make_pair(nx,ny)],j,inf);
                }
            }
        }
    }
    int ans = dinic();
    printf("%d\n",ans);
    return 0;
}

【输出】

最长的精细入微类别的长短。

1.此处放1:那么就相当于求<=1001时放k-1个1的数的个数

老 C 的键盘

【样例数据】

样例输入 样例输出

9 1

2

7

3

7

7

3

7

5

7

4

 

 

 

 

 

 

 

 

 

 

 

 

2.此处放0:那么后边就随便放了,为C[5][k]

主题素材大体:

有多个n的排列对于各个地点i,给出[i/2]与i地方上的数的分寸关系,求只怕的排列数.
n <= 100

【STD Code】

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
int ans;
int kind[200000];
struct node
{
    int value;
    int pos;
};
node data[200000];
int cmp_value(node a,node b)
{
    return a.value<b.value;
}
int cmp_origin(node a,node b)
{
    return a.pos<b.pos;
}
int main()
{
    int n,k;
    int t,now,contain,l;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
      scanf("%d",&data[i].value);
      data[i].pos=i;
    }
    sort(data+1,data+n+1,cmp_value);
    now=1;
    t=data[1].value;
    for(int i=1;i<=n;i++)
        if(data[i].value==t)
            data[i].value=now;
        else
        {
            now+=1;
            t=data[i].value;
            data[i].value=now;
        }
    sort(data+1,data+n+1,cmp_origin);
    contain=0;
    l=1;
    for(int i=1;i<=n;i++)
    {
        if((kind[data[i].value]==0)&&(contain<=k))
        {
            contain+=1;
            kind[data[i].value]+=1;
            ans=max(ans,kind[data[i].value]);
        }
        else if((kind[data[i].value]==0)&&(contain>k))
        {
            kind[data[i].value]+=1;
            kind[data[l].value]-=1;
            while(kind[data[l].value]!=0)
            {
                l+=1;
                kind[data[l].value]-=1;
            }
            l+=1;
            ans=max(ans,kind[data[i].value]);
        }
        else
        {
            kind[data[i].value]+=1;
            ans=max(kind[data[i].value],ans);
        }
    }
    printf("%d",ans);
    return 0;
}

因而这么递归的检索就可得出答案,也可以用DP做。

题解:

轻松窥见实际上那是一棵树.
大家把那棵树建出来,那么今后改成一给定一棵树,树上的边表示的老爹和儿子的轻重关系.
大家着想树归 : 设\(f[i][j]\)表示在以i为根的子树内根作为排行为j的值出现的排列数.
那就是说难题就在于状态的联合更新了.
对于八个\(f[u][]\)要将外甥的情景\(f[v][]\)合併进来,大家第一分意况研究:

  • u的值必须 > v的值:
    咱俩想像成五个排列举办合併.
    大家精通大家不可能不满足的规范即v在u的前边.
    那就是说大家枚举一下急需有微微排在u的近日就能够.
    由于需求保障相对顺序不产生变化,所以将n个数插到m个数中的方案即:\(C_{n+m-1}^m\)
    但是由于此处照旧前边能插,要么后边能插,即哪天都多一个足以插的岗位,
    故此其实这里插入的方案数为\(C_{n+m}^m\)
    那般大家列出转移方程:
    \[f[u][j+k] +=
    C_{j-1+k}^{k}C_{s_u-j+s_v-k}^{s_v-k}*f[u][j]\sum_{i=1}^kf[v][i]\]

  • u的值必须 < v的值:
    对应地列出方程:
    \[f[u][j+k-1] +=
    C_{j-1+k-1}^{k-1}C_{s_u-j+s_v-(k-1)}^{s_u-j}*f[u][j]\sum_{i=k}^nf[v][i]\]

预管理前缀后缀和可以将sigma消掉.

流言那样做复杂度是\(O(n^2\log
n)\)的..笔者也不清楚为什么..

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
    x=0;static char ch;static bool flag;flag = false;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    while(x=(x<<1)+(x<<3)+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
const int maxn = 128;
const int mod = (1e9 + 7);
struct Edge{
    int to,next,type;
}G[maxn<<1];
int head[maxn],cnt;
void add(int u,int v,int d){
    G[++cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt;
    G[cnt].type = d;
}
int C[maxn][maxn];
inline void prework(int n){
    C[0][0] = 1;
    rep(i,1,n) rep(j,0,n){
        C[i][j] = C[i-1][j];
        if(j != 0) C[i][j] += C[i-1][j-1];
        if(C[i][j] >= mod) C[i][j] -= mod;
    }
}
int f[maxn][maxn],pre[maxn][maxn],suf[maxn][maxn];
inline void init(){
    memset(head,0,sizeof head);
    cnt = 0;
}
int siz[maxn],n;
#define v G[i].to
void dfs(int u,int fa){
    siz[u] = 1;
    for(int i = head[u];i;i=G[i].next){
        if(v == fa) continue;
        dfs(v,u);siz[u] += siz[v];
    }
    rep(i,2,n) f[u][i] = 0;
    f[u][1] = 1;
    rg s = 1;
    static int g[maxn];
    for(int i = head[u];i;i=G[i].next){
        if(v == fa) continue;
        rep(j,1,s+siz[v]) g[j] = 0;
        if(G[i].type == -1){
            rep(j,1,s) rep(k,1,siz[v]){
                g[j+k-1] += 1LL*C[j+k-2][k-1]*C[s-j+siz[v]-k+1][s-j]%mod*f[u][j]%mod*suf[v][k]%mod;
                if(g[j+k-1] >= mod) g[j+k-1] -= mod;
            }
        }else{
            rep(j,1,s) rep(k,1,siz[v]){
                g[j+k] += 1LL*C[j+k-1][k]*C[s-j+siz[v]-k][s-j]%mod*f[u][j]%mod*pre[v][k]%mod;
                if(g[j+k] >= mod) g[j+k] -= mod;
            }
        }
        rep(j,1,s + siz[v]) f[u][j] = g[j];
        s += siz[v];
    }
    rep(i,1,n){
        pre[u][i] = pre[u][i-1] + f[u][i];
        if(pre[u][i] >= mod) pre[u][i] -= mod;
    }
    per(i,n,1){
        suf[u][i] = suf[u][i+1] + f[u][i];
        if(suf[u][i] >= mod) suf[u][i] -= mod;
    }
    return ;
}
#undef v
inline void work(){
    init();read(n);
    rg u,v;char ch;
    rep(i,2,n){
        u = i>>1;
        while(ch=getchar(),ch<'!');
        v = i;
        if(ch == '<') add(u,v,-1),add(v,u,1);
        else add(u,v,1),add(v,u,-1);
    }
    dfs(1,1);
    int ans = 0;
    rep(i,1,n){
        ans += f[1][i];
        if(ans >= mod) ans -= mod;
    }
    printf("%d\n",ans);
}
int main(){
    int T;T = 1;
    prework(100);
    while(T--) work();
    return 0;
}

 【标题深入分析】

别的先不说,看到只有100000个数字,数据范围却是一千000000,就认证大家先是要对那些行列进行离散化。在这里,能够开一个结构体,定义五个值:value和pos,value代表值,pos表示这几个数原来在体系的哪五个任务,先用一回sort对value进行排序,改造值的高低(约等于离散化的焦点操作),接着再来二次sort,按pos排序,以此将系列的岗位排布还原为原来的体系。

上面,大家就来走访那道题的为主思路:设置三个“移动窗口”。约等于说,定义三个变量:L,XC90,来记录只怕答案的潜在区间。在最开始,我们将L,奥迪Q5早先化为0,即L,智跑将从连串的最左端开首向右扫描。由于标题中有供给“仅能去除k类数”,那么,当窗口刚刚早先移动时,我们得以先保持L不动,使PAJERO右移,与此同一时候,不断更新在该窗口内部存款和储蓄器在的数的花色(当然,你也要算出此时的最优解),当种类到达k+1种时,就注脚当前距离已经塞满啦,此时要想继续使窗口移动,将在使L+=1,更新之后,再让PAJERO+=1……就那样类推,不断使窗口移动下去,直到扫描至体系末端,此时的答案就是成套连串中的完美类别的最优解了。

代码:

第二题:岛屿

图片 4图片 5

【标题陈述】

 给你一张r*c(1<=r,c<=50)的地形图,有’S’,’X’,’.’二种地形,全数剖断相邻与行动都以四连通的。大家设’X’为陆地,一个’X’连通块为多个岛礁,’S’为浅水,’.’为深水。当中一共有n个小岛(n<=15),刚初始你能够减低在任一一块陆地上,在陆地上能够走路,在浅水里能够游泳。並且陆地和浅水之间能够并行通行。但不管如何都不能走到深水。你今后供给通过行动和游泳使得你把装有的小岛都经过一遍。问最少要由此多少次浅水区?标题保险有解。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;

int Count(ll state) {
    int cnt = 0;
    while(state) {
        if(state & 1LL) cnt++;
        state >>= 1;
    }
    return cnt;
}
int WEI(ll state) {
    int cnt = 0;
    while(state) {
        cnt++;
        state >>= 1;
    }
    return cnt;
}
ll C[100][100];
int in[67];

void init()
{
    C[0][0] = 1;
    for(int i = 1; i < 90; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        }
    }
    memset(in,0,sizeof(in));
    in[1] = 0;
    for(int i=2;i<=61;i++)
        in[i] = in[Count(i)]+1;
}
int X;

ll get(ll state,int cnt) {
    if(state < 0) return 0;
    int len = WEI(state);
    if(len < cnt) return 0;   // not enough
    if(cnt == 0)  return 1;   // no demand
    return get(state-(1LL<<(len-1)),cnt-1) + C[len-1][cnt];
}

ll getsum(ll R,ll L) {
    ll ans = 0;
    for(int i=1;i<=61;i++)
        if(in[i]+1 == X) ans += get(R,i)-get(L-1,i);
    return ans;
}

int main()
{
    init();
    int i,j;
    ll L,R;
    while(scanf("%lld%lld%d",&L,&R,&X)!=EOF && L+R+X)
    {
        ll ans = 0;
        if(X == 0 && L == 1LL) { puts("1"); continue; }
        if(X == 1 && L == 1LL) ans--;  //1's binary code is 1, but 1 is not in (X==1)
        ans += getsum(R,L);
        cout<<ans<<endl;
    }
    return 0;
}

【输入】

首先行四个整数福睿斯,C

接下去第有Evoque行,每行C列个字符,为’X’,’S’,’.’

View Code

【输出】

一个大背头,表示遍历完全部的小岛最小要游过些微次浅水区。

 

【样例数据】

 样例输入 样例输出 

5 4

XX.S

.S..

SXSS

S.SX

..SX

3

 

 

 

 

 

 

 

 

【STD Code】

#include<cstring>
#include<cstdio>
#include<queue>

#define MAXN 55
#define Size 20
#define MAXM 400010
#define INF 0x3f3f3f3f

using namespace std;

int sx[4]={0,0,1,-1};
int sy[4]={1,-1,0,0};

int r,c,num;
char s[MAXN];
char a[MAXN][MAXN];
int land[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dist[Size][Size],dis[MAXN][MAXN];

struct hp
{
    int x;
    int y;
};
struct hq
{
    int has_been;
    int island;
};
hp st[Size][MAXN];

queue <hp> q;
queue <hq> p;

int tot[Size];
int f[MAXM][Size];
int goal,ans;
bool atp[MAXM][Size];

inline void dfs(int x,int y,int num)
{
    land[x][y]=num;
    tot[num]+=1;
    st[num][tot[num]].x=x;
    st[num][tot[num]].y=y;
    for(int i=0;i<4;++i)
    {
        int nowx=x+sx[i];
        int nowy=y+sy[i];
        if(nowx>0&&nowx<=r&&nowy>0&&nowy<=c&&a[nowx][nowy]=='X'&&!land[nowx][nowy])
            dfs(nowx,nowy,num);
    }
}

void spfa(int island)
{
    memset(vis,0,sizeof(vis));
    memset(dis,0x7f,sizeof(dis));
    while(!q.empty())
        q.pop();
    for(int i=1;i<=tot[island];i++)
    {
        vis[st[island][i].x][st[island][i].y]=true;
        dis[st[island][i].x][st[island][i].y]=0;
        q.push((hp){st[island][i].x,st[island][i].y});
    }
    while(!q.empty())
    {
        hp now=q.front();
        q.pop();
        vis[now.x][now.y]=false;
        hp next;
        for(int i=0;i<4;++i)
        {
            next.x=now.x+sx[i];
            next.y=now.y+sy[i];
            if(next.x>0&&next.x<=r&&next.y>0&&next.y<=c&&a[next.x][next.y]!='.')
                if(a[next.x][next.y]=='S')
                {
                    if(dis[next.x][next.y]>dis[now.x][now.y]+1)
                    {
                        dis[next.x][next.y]=dis[now.x][now.y]+1;
                        if(!vis[next.x][next.y])
                        {
                            vis[next.x][next.y]=true;
                            q.push((hp){next.x,next.y});
                        }
                    }
                }
                else
                {
                    if(dis[next.x][next.y]>dis[now.x][now.y])
                    {
                        dis[next.x][next.y]=dis[now.x][now.y];
                        if(!vis[next.x][next.y])
                        {
                            vis[next.x][next.y]=true;
                            q.push((hp){next.x,next.y});
                        }
                    }
                    dist[island][land[next.x][next.y]]=min(dist[island][land[next.x][next.y]],dis[next.x][next.y]);
                }
            else
                continue;
        }
    }
}

int main()
{
    scanf("%d%d\n",&r,&c);
    for(int i=1;i<=r;++i)
    {
        gets(s);
        for(int j=1;j<=c;++j)
          a[i][j]=s[j-1];
    }
    num=0;
    for(int i=1;i<=r;++i)
        for(int j=1;j<=c;++j)
        {
            if(a[i][j]=='X'&&!land[i][j])
                dfs(i,j,++num);
        }
    memset(dist,0x7f,sizeof(dis));
    for(int i=1;i<=num;++i)
        spfa(i);
    memset(f,0x7f,sizeof(f));
    while(!p.empty()) p.pop();
    for(int i=0;i<num;++i)
    {
        p.push((hq){1<<i,i+1});
        atp[1<<i][i+1]=true;
        f[1<<i][i+1]=0;
    }
    while(!p.empty())
    {
        hq now=p.front();
        p.pop();
        atp[now.has_been][now.island]=false;
        for(int i=0;i<num;i++)
            if(f[now.has_been|(1<<i)][i+1]>f[now.has_been][now.island]+dist[now.island][i+1])
            {
                f[now.has_been|(1<<i)][i+1]=f[now.has_been][now.island]+dist[now.island][i+1];
                if(!atp[now.has_been+(1<<i)][i+1])
                    p.push((hq){now.has_been+(1<<i),i+1});
            }
    }
    for(int i=0;i<num;i++)
        goal+=(1<<i);
    ans=INF;
    for(int i=1;i<=num;i++)
        ans=min(ans,f[goal][i]);
    printf("%d\n",ans);
    return 0;
}

【标题深入分析】

那道题要使用“状态压缩DP”。

作者们须要把每二个小岛当做一个节点,求出每三个岛礁之间的最短路线distance,那样一来,大家其实就获取了三个图。接下来,大家就足以用多少个DP数组f[state][i]来代表近来的动静,个中的state为三个14位的二进制数,表示小岛的访谈标记,i表示最近滞留在第多少个岛礁(此前未达到过的)。

那就是说,我们就足以博得那样三个递推式:f[state][i]=f[state'(第i位清零)=min(state^(1<<i))][j]+distance(i,j)。

 

Time: 2017-03-21

相关文章