首页 > 代码库 > UVALive 4255 Guess

UVALive 4255 Guess

2024-07-06 04:18:57   231人阅读

这道题目让我学到了很多

一道不走寻常路的题目，给定一串数列的 和 的正负号，即假设数列 为  a1,a2,a3.....an，则一致了 Sij的正负号或者是否等于0，Sij代表了 从 ai 到 aj的和。要你求出任意一种序列，满足题目给定的Sij条件

确实是看了白书上的思路都还不太知道怎么写，然后看了LRJ的代码才知道原来还可以如此实现

很容易联系到前缀和sum，也就是说我们现在 得到了 sum[i]-sum[j] (j<i) 的正负号情况，要求满足情况的数列，那我们如果能得到满足情况的 sum[],那数列的每个数岂不就是

sum[i]-sum[i-1],那就是说我们得到合理的sum值，就相当于得到了最终结果

LRJ的思路是用拓补排序，。。。哎，以前写过裸的拓补排序，但是一到这种关键题目，就联想不起来可以这样搞，即，我们根据已经得到的sum[i]-sum[j]的正负号，得到 sum[i]和sum[j]的相对大小关系，当然还有个sum[0]=0作为对照，根据大小关系来进行建边，则，进行一次拓补排序就可以轻松把sum进行排序，其实说到底，只要sum排好了序，问题就解了，前面所有的都是为这个做铺垫，。。。既然把sum从小到大  或者 从大到小 排了序，就手动 把 1-n负责给他们呗，然后他们一相减就是合理的数列值了

题目里面有0，就代表某两个前缀和相等，在代码里用了 并查集合并 进行优化，不仅节省时间，还省去了处理相等的情况。

确实学到了好多，本来有点无所下手，这道题目首先，根据题目给的条件联想，要得到最终结果，其实是先得到前缀和的结果，因为题目给的就是和之间的大小关系，肯定要联想到前缀和的，不然不可能直接得到结果。其次拓补排序这种很实用的算法，也要懂得利用起来

 

其实我刚刚说了，所有处理的目的就是给 前缀和进行排序，前缀和顺序出来了，结果就出来了，所以也有人直接在读入的时候，读到+就对前面的sum--，读到+就对后面的--，这样sum的相对大小也可以出来。尽管没证明，好像这样做也可以，因为在扫第一行的时候，就把 sum1和其他sum的相对大小关系求出来了，然后扫第二行，就把sum2和除sum1以外的大小也求出来了，以此类推。。。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n;
char ch[60],S[15][15];
int f[20];
int findset(int x){
    if (x!=f[x]){
       return f[x]=findset(f[x]);
    }
    return x;
}
int G[15][15];
int c[15],cnt,topo[15];
bool dfs(int u)
{
    c[u]=-1;
    for (int v=0;v<=n;v++) if (G[u][v]){
        if (c[v]<0) return false;
        else  if (!c[v] && !dfs(v)) return false;
    }
    c[u]=1;
    topo[cnt--]=u;
    return true;
}
bool toposort()
{
    cnt=n;
    memset(c,0,sizeof c);
    for (int i=0;i<=n;i++) if (!c[i])
        if (!dfs(i)) return false;
    return true;
}
int sum[15];
int main()
{
    int t;
    scanf("%d",&t);
    while (t--){
        scanf("%d%s",&n,ch);
        for (int i=0;i<=n;i++) f[i]=i;
        int tmp=0;
        for (int i=1;i<=n;i++)
            for (int j=i;j<=n;j++){
                S[i][j]=ch[tmp++];
                if (S[i][j]==‘0‘){
                    f[findset(j)]=i-1;
                }
            }
        memset(G,0,sizeof G);
        for (int i=1;i<=n;i++)
           for (int j=i;j<=n;j++){
           if (S[i][j]==‘-‘) G[findset(j)][findset(i-1)]=1;
           else if (S[i][j]==‘+‘) G[findset(i-1)][findset(j)]=1;
        }
        toposort();
        //for (int i=0;i<=n;i++) cout<<topo[i]<<endl;
        for (int i=0;i<=n;i++) sum[topo[i]]=i;
        for (int i=1;i<=n;i++){
            sum[i]=sum[f[i]];
            if (i>1) printf(" ");
            printf("%d",sum[i]-sum[i-1]);
        }
        printf("\n");
    }
    return 0;
}

 


联系
我们