[高斯消元][模拟][比赛补题][×] codeforces gym 101412 B Stylish

题目链接

题意:

给定一段代码,让模仿出来他的代码缩进风格。缩进风格由三个数字 $R C S$ 确定,分别代表到当前位置有多少个未封闭的圆括号/花括号/方括号 ,然后每多一个 $R/C/S$ 的话,多出来的缩进数是确定的。现在要求用学习到的代码风格对新的一段没有缩进的代码进行缩进,输出每行缩进的空格数。数据范围行数 $N\le 80$ , 每行最多80个字符。

题解:

显然难点在于能不能用已经学到的经验来推断出来现在该缩进多少。把所有 $(r,c,s)$ 的三元组看成一组向量,等于说新的向量能不能被之前出现过的表示出来,也就是是否线性相关。那么我们只需要用高斯消元去解就行了,如果有唯一解那么一定是可以被表示出来的,这是后这个就能解出来了,如果不是的话就把这个新的向量插进去作为一个新的基。

这个题当时的问题就在于没有一个好的高斯消元板子。。。于是很正经的去找了一个好的板子TAT

wa点:没注意到题目说RCS最多只有20个最少至少有1个。。。这个限制导致了在某些情况下方程解不出来但是仍然可以确定RCS的数值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
const ll MOD=1000000007;
const ll maxn=500+7;
const double eps=1e-12;

//Guassian 
double a[maxn][maxn];
int equ,var;//equ个方程,var个变量
double x[maxn];//解集
bool free_x[maxn];
 
int sgn(double x)
{
    return (x>eps)-(x<-eps);
}
// 高斯消元法解方程组(Gauss-Jordan elimination).(0表示无解,1表示唯一解,大于1表示无穷解,并返回自由变元的个数)
int Gauss()
{
    //equ=n,var=n;//多少个方程,多少个变量
    int i,j,k;
    int max_r; // 当前这列绝对值最大的行.
    int col; // 当前处理的列.
    double temp;
    int free_x_num;
    int free_index;
    // 转换为阶梯阵.
    col=0; // 当前处理的列.
    memset(free_x,true,sizeof(free_x));
    for(k=0;k<equ&&col<var;k++,col++)
    {
        max_r=k;
        for(i=k+1;i<equ;i++)
        {
            if(sgn(fabs(a[i][col])-fabs(a[max_r][col]))>0)
                max_r=i;
        }
        if(max_r!=k)
        { // 与第k行交换.
            for(j=k;j<var+1;j++)
                swap(a[k][j],a[max_r][j]);
        }
        if(sgn(a[k][col])==0)
        { // 说明该col列第k行以下全是0了,则处理当前行的下一列.
            k--; continue;
        }
        for(i=k+1;i<equ;i++)
        { // 枚举要删去的行.
            if (sgn(a[i][col])!=0)
            {
                temp=a[i][col]/a[k][col];
                for(j=col;j<var+1;j++)
                {
                    a[i][j]=a[i][j]-a[k][j]*temp;
                }
            }
        }
    }
 
    for(i=k;i<equ;i++)
    {
        if (sgn(a[i][col])!=0)
            return 0;
    }
    if(k<var)
    {
        for(i=k-1;i>=0;i--)
        {
            free_x_num=0;
            for(j=0;j<var;j++)
            {
                if (sgn(a[i][j])!=0&&free_x[j])
                    free_x_num++,free_index=j;
            }
            if(free_x_num>1) continue;
            temp=a[i][var];
            for(j=0;j<var;j++)
            {
                if(sgn(a[i][j])!=0&&j!=free_index)
                    temp-=a[i][j]*x[j];
            }
            x[free_index]=temp/a[i][free_index];
            free_x[free_index]=0;
        }
        return var-k;
    }
 
    for (i=var-1;i>=0;i--)
    {
        temp=a[i][var];
        for(j=i+1;j<var;j++)
        {
            if(sgn(a[i][j])!=0)
                temp-=a[i][j]*x[j];
        }
        x[i]=temp/a[i][i];
    }
    return 1;
}


int base[3][maxn+1],bcnt;

void setMat(int cur[]){
    equ=3,var=bcnt;
    for(int i=0;i<3;++i){
        for(int j=0;j<bcnt;++j){
            a[i][j]=base[j][i];
        }
    }
    for(int i=0;i<3;++i)
        a[i][bcnt]=cur[i],x[i]=free_x[i]=0;
}

void insert(int cur[]){
    if(bcnt==3) return ;
    setMat(cur);
    int sg=Gauss();
    if(bcnt==0||sg!=1){
        for(int i=0;i<4;i++){
            base[bcnt][i]=cur[i];
        }
        bcnt++;
    }
}

int getans(int cur[]){
    setMat(cur);
    int sg=Gauss();
    if(sg>1) while(1);
    if(sg!=1){
        return -1;
    }
    else{
        int res=0;
        double dres=0.0;
        for(int i=0;i<bcnt;++i){
            dres+=x[i]*base[i][3];//error2
        }
        res=(int)(dres+0.5);
        if(res<0) return -1;
        return res;
    }
}

int cur[2][500],pre;
char tmp[500];

void init(){
    pre=0;
    bcnt=0;
    memset(base,0,sizeof(base));
}

int main(){
    // freopen("test_.in","r",stdin);
    // freopen("2.txt","w",stdout);
    int p,q,r,c,s,w,len,flag;
    while(scanf(" %d %d",&p,&q)==2&&p){
        init();
        r=c=s=0;
        while(p--){
            flag=1,w=0;
            scanf(" %s",tmp);
            len=strlen(tmp);
            for(int i=0;i<len;++i){
                if(tmp[i]=='.'){
                    w+=flag;
                }
                else{
                    flag=0;
                    if(tmp[i]=='('){
                        r++;
                    }else if(tmp[i]==')'){
                        r--;
                    }else if(tmp[i]=='{'){
                        c++;
                    }else if(tmp[i]=='}'){
                        c--;
                    }else if(tmp[i]=='['){
                        s++;
                    }else if(tmp[i]==']'){
                        s--;
                    }else continue;
                }
            }
            cur[pre^1][0]=r,cur[pre^1][1]=c,cur[pre^1][2]=s,cur[pre][3]=w;
            if(w){
                int n0=0,sum=0;
                for(int i=0;i<3;i++){
                    n0+=cur[pre][i];
                }
                if(n0*20==cur[pre][3]){
                    int a[4];
                    for(int i=0;i<3;i++){
                        if(cur[pre][i]==0) continue;
                        memset(a,0,sizeof(a));
                        a[i]=1,a[3]=20;
                        insert(a);                        
                    }
                }
                else if(n0==cur[pre][3]){
                    int a[4];
                    for(int i=0;i<3;i++){
                        if(cur[pre][i]==0) continue;
                        memset(a,0,sizeof(a));
                        a[i]=1,a[3]=1;
                        insert(a);                        
                    }
                }else 
                    insert(cur[pre]);
            }
                
            pre^=1;
        }
        r=c=s=pre=0;memset(cur,0,sizeof(cur));
        int ff=0;
        while(q--){
            scanf(" %s",tmp);
            len =strlen(tmp);
            for(int i=0;i<len;++i){
                if(tmp[i]=='('){
                    r++;
                }else if(tmp[i]==')'){
                    r--;
                }else if(tmp[i]=='{'){
                    c++;
                }else if(tmp[i]=='}'){
                    c--;
                }else if(tmp[i]=='['){
                    s++;
                }else if(tmp[i]==']'){
                    s--;
                }else continue;
            }
            cur[pre^1][0]=r,cur[pre^1][1]=c,cur[pre^1][2]=s;
            if(ff==0)
                printf("0 "),ff=1;
            else
                printf("%d ",getans(cur[pre]));
            pre^=1;
        }
        puts("");
    }
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据