DQS DQS

NOIP2015解题报告

in 算法,NOIPread (134) 文章转载请注明来源!

还是老样子。不说具体步骤,只说新的心得体会。看具体题解请移步我的CSDN

神奇的幻方

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int maps[233][233];

int main()
{
    int n;
    scanf("%d",&n);
    int x = 1,y = n + 1 >> 1,tot = 1;
    while(tot <= n * n)
    {
        maps[x][y] = tot ++;
        if(x == 1 && y != n)
            x = n,y ++;
        else if(y == n && x != 1)
            y = 1,x --;
        else if(x == 1 && y == n)
            x ++;
        else
        {
            if(x - 1 >= 1 && y + 1 <= n && maps[x - 1][y + 1] == 0)
                x --,y ++;
            else
                x ++;
        }
    }
    for(int i = 1;i <= n;i ++,puts(""))
        for(int j = 1;j <= n;j ++)
            printf("%d ",maps[i][j]);
    return 0;
}

信息传递

这个题我考场上用tarjan求scc水过的,然后就再也没有理过…
这次写了一种新做法:由于是n点n单向边并且每个点的出度只有一个,所以一定是一个或多个图,图是边指向父节点的有向树上根节点所连出的边指向一个节点。这样可以直接dfs,有以下两种情况:

  1. 遍历到了当前栈中的节点。
  2. 遍历到了已遍历过但不在栈中的节点(也就是之前搜过,不是这次搜到的)。

对第二种情况直接舍弃,因为答案一定已经统计过了。
对第一种情况,可以记一个当前点到搜索树的根节点的距离$d_i$,若当前点是u,下一个点是v,则答案是$d_u-d_v+1$。
时间复杂度还是$O(n)$。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int SZ = 200010;

int ans = SZ,to[SZ],dis[SZ];
bool vis[SZ],ins[SZ];

void dfs(int u)
{
    if(vis[u]) return ;
    vis[u] = 1;
    int v = to[u];
    if(ins[v])
    {
        //if(dis[u] - dis[v] + 1 < 0) return ;
        ans = min(ans,dis[u] - dis[v] + 1);
        return ;
    }
    ins[u] = 1;
    dis[v] = dis[u] + 1;
    dfs(v);
    ins[u] = 0;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
        scanf("%d",&to[i]);
    for(int i = 1;i <= n;i ++)
        if(!vis[i])
            dis[i] = 1,dfs(i);
    printf("%d",ans);
    return 0;
}

斗地主

我已经说过了这个题我不会去写第二遍

跳石头

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int SZ = 100010;

int L,n,m,a[SZ];

int check(int d)
{
    int ans = 0,l = 0;
    for(int i = 1;i <= n;i ++)
    {
        if(a[i] - l < d)
            ans ++;
        else
            l = a[i];
    }
    return ans;
}

int div()
{
    int l = -1,r = L + 1;
    while(r - l > 1)
    {
        int mid = l + r >> 1;
        if(check(mid) < m)
            l = mid;
        else
            r = mid;
    }
    return r;
}

int main()
{
    scanf("%d%d%d",&L,&n,&m);
    for(int i = 1;i <= n;i ++)
        scanf("%d",&a[i]);
    a[++ n] = L;
    printf("%d",div());
    return 0;
}

子串

这次我换了一个状态表示,并自己成功写对了方程式(一年了,真不容易…)。
设$dp[i][j][k][0/1]$表示a串前i个,b串前j个,分成k份,不包括/包括 第i个字符的总方案数。
状态转移方程和我blog的差不多,也很简单,就不写了。

值得注意的是,我写了两种优化:第一个是滚动数组,只要在i或i-1后面加&1即可,非常简单。
第二个是类似01背包的倒序循环,这个是我以前讲过的。但我这次总是无限WA,非常郁闷…最后发现,错引在不光j和k需要倒序,0/1也要倒序才合法,真是太坑了……所以以后还是写滚动数组吧2333

滚动数组

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

const int mod = 1000000007;

char a[1010],b[210];
int dp[2][210][210][2];

int main()
{
    int n,m,K;
    scanf("%d%d%d%s%s",&n,&m,&K,a + 1,b + 1);
    dp[0][0][0][0] = 1;
    for(int i = 1;i <= n;i ++)
    {
        dp[i & 1][0][0][0] = 1;
        for(int j = 1;j <= m;j ++)
            for(int k = 1;k <= K;k ++)
            {
                if(a[i] == b[j])
                    dp[i & 1][j][k][1] = ((dp[i - 1 & 1][j - 1][k][1] + dp[i - 1 & 1][j - 1][k - 1][1]) % mod + dp[i - 1 & 1][j - 1][k - 1][0]) % mod;
                if(a[i] != b[j])
                    dp[i & 1][j][k][1] = 0;
                dp[i & 1][j][k][0] = (dp[i - 1 & 1][j][k][0] + dp[i - 1 & 1][j][k][1]) % mod;
            }
    }
    printf("%d",(dp[n & 1][m][K][0] + dp[n & 1][m][K][1]) % mod);
    return 0;
}

倒序循环

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

const int mod = 1000000007;

char a[1010],b[210];
int dp[210][210][2];

int main()
{
    int n,m,K;
    scanf("%d%d%d%s%s",&n,&m,&K,a + 1,b + 1);
    dp[0][0][0] = 1;
    for(int i = 1;i <= n;i ++)
    {
        dp[0][0][0] = 1;
        for(int j = m;j >= 1;j --)
            for(int k = K;k >= 1;k --)
            {
                dp[j][k][0] = (dp[j][k][0] + dp[j][k][1]) % mod;
                if(a[i] == b[j])
                    dp[j][k][1] = ((dp[j - 1][k][1] + dp[j - 1][k - 1][1]) % mod + dp[j - 1][k - 1][0]) % mod;
                if(a[i] != b[j])
                    dp[j][k][1] = 0;
            }
    }
    printf("%d",(dp[m][K][0] + dp[m][K][1]) % mod);
    return 0;
}

运输计划

这个题印象很深刻,大体思路几乎全记着,立马就开始写了。后来SB错层出不穷非常郁闷……不过可算最后写对了。
我写的是二分+lca的做法,明天写一个树剖玩玩。
(更新:树剖的做法其实是在剖完的数组上差分,和树上差分没什么区别)

思路几乎和之前一样,就不赘述。
说一下主要的卡常技巧(这方法好像不卡常UOJ过不了):

  1. 算差分时要求和,换成拓扑排序累加,不用dfs
  2. 手动读入
  3. 提前算好LCA
  4. 对询问路径按权值排序,可提前break

写到这发现我好像原来写过?!算了不管了,卡常才是这个题的精髓。

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

const int SZ = 300010;

int head[SZ],nxt[SZ << 1];
int deep[SZ],anc[SZ][22],cnt[SZ],dist[SZ],cost[SZ],n,m,MAXN = 0,MAXE = 0,topo[SZ];

struct edge
{
    int t,d;
}l[SZ << 1];

struct edge2
{
    int u,v,d,lca;
}p[SZ];

bool cmp(edge2 a,edge2 b)
{
    return a.d > b.d;
}


void build(int f,int t,int d)
{
    static int tot = 1;
    l[++ tot] = (edge){t,d};
    nxt[tot] = head[f];
    head[f] = tot;
}

void dfs_lca(int u,int fa,int d)
{
    dist[u] = d;
    deep[u] = deep[fa] + 1;
    anc[u][0] = fa;
    for(int i = 1;anc[u][i - 1];i ++)
        anc[u][i] = anc[anc[u][i - 1]][i - 1];
    for(int i = head[u];i;i = nxt[i])
    {
        int v = l[i].t;
        if(v == fa) continue;
        cost[v] = l[i].d;
        dfs_lca(v,u,d + l[i].d);
    }
}

int ask_lca(int u,int v)
{
    if(deep[u] < deep[v]) swap(u,v);
    if(deep[u] > deep[v])
    {
        int d = deep[u] - deep[v];
        for(int i = 0;i <= 19;i ++)
            if(1 << i & d)
                u = anc[u][i];
    }
    if(u != v)
    {
        for(int i = 19;i >= 0;i --)
            if(anc[u][i] != anc[v][i])
                u = anc[u][i],v = anc[v][i];
        return anc[u][0];
    }
    return u;
}

bool check(int d)
{
    memset(cnt,0,sizeof(cnt));
    int t = 0;
    for(int i = 1;i <= m;i ++)
        if(p[i].d > d)
        {
            int u = p[i].u,v = p[i].v,lca = p[i].lca;
            cnt[u] ++,cnt[v] ++,
            cnt[lca] -= 2;
            t ++;
        }
        else
            break;
    for(int i = n;i >= 1;i --)
    {
        int u = topo[i];
        cnt[anc[u][0]] += cnt[u];
    }
    for(int i = 1;i <= n;i ++)
        if(cnt[i] == t && p[1].d - cost[i] <= d)
            return true;
    return false;
}

int div()
{
    int l = -1,r = 300000001;
    while(r - l > 1)
    {
        int mid = l + r >> 1;
        if(check(mid))
            r = mid;
        else
            l = mid;
    }
    return r;
}

int read()
{
    bool flag = 0;
    int n = 0;
    char a = getchar();
    while(a < '0' || a > '9')
        { if(a == '-') flag = 1; a = getchar(); }
    while('0' <= a && a <= '9')
        n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

void get_topo()
{
    queue<int> q;
    q.push(1);
    while(q.size())
    {
        int u = q.front(); q.pop();
        topo[++ topo[0]] = u;
        for(int i = head[u];i;i = nxt[i])
        {
            int v = l[i].t;
            if(v != anc[u][0])
                q.push(v);
        }
    }
}


int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n - 1;i ++)
    {
        int a = read(),b = read(),c = read();
        build(a,b,c); build(b,a,c); MAXE = max(MAXE,c);
    }
    dfs_lca(1,0,0); get_topo();
    for(int i = 1;i <= m;i ++)
    {
        p[i].u = read(), p[i].v = read();
        p[i].lca = ask_lca(p[i].u,p[i].v);
        p[i].d = dist[p[i].u] + dist[p[i].v] - dist[p[i].lca] * 2;
        MAXN = max(MAXN,p[i].d);
    }
    sort(p + 1,p + 1 + m,cmp);
    printf("%d\n",div());
    return 0;
}
jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

算法NOIP
最后由DQS修改于2017-07-08 23:26
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆