题意:
给定一段代码,让模仿出来他的代码缩进风格。缩进风格由三个数字 $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(""); } }