重庆day3

（前排膜拜qr大佬）

第一题，签到题，观察到图只能是几个环，每次改变能把两个环合成一个大环，所以先求出原始的环，把环看成点跑最小生成树就行了

第二题，看到不同行不影响，同列也不影响，只要分别求每行跟每列的方案数和总和，乘一下系数，加起来就行了；

求每行跟每列的方案数和总和，用dp，设f[i][j]表示前i个，有j个R没匹配上的方案数，g[i][j]是总和，当不放，f[i][j]=f[i-1][j],g[i][j]=g[i-1][j]

若放，当前是L，则f[i][j]=f[i-1][j+1](j+1),g[i][j]=(g[i-1][j+1]+f[i-1][j+1]a[])(j+1);若当前是R，则f[i][j]=f[i-1][j-1],g[i][j]=g[i-1][j-1]+f[i-1][j-1]a[]

第三题，没懂

第四题，先把能确定的确定了，接下来随便填，在一步步推下去

证明正确：若不正确，则在这步之前这步就会被证明不正确，所以当一步操作能执行时，一定正确