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