高斯消元+叉积求面积+记忆化搜索

P3389 【模板】高斯消元法

模板采用高斯-约旦消元法
步骤如下：
1.选择一个尚未被选择过的，且为该列的最大系数的未知数作为主元，进行整行交换。
2.再将这一列的其他系数通过行初等变换都变为0。具体做法:该系数除以主元，再用每一行中每一列的值减去这个值乘上求得每一行算出的系数。
3.每一列都这个重复步骤，最后每一行都只存在一个系数和值。做出运算得出值。

#include 
#define endl '\n'
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define PII pair<int,int>

using namespace std;
const int N =1e2+5;
const int inf=1e18;
const int mod=1e9+7;
int n;
double d[N][N];
void guess()
{
    for(int i=1;i<=n;i++)   //枚举列项
    {
        int mx=i;
        for(int j=i+1;j<=n;j++)   //选出该列的最大系数
        {
            if(abs(d[j][i])>abs(d[mx][i]))
                mx=j;
        }
        for(int j=1;j<=n+1;j++)
            swap(d[i][j],d[mx][j]);
        if(!d[i][i])    //最大值为0说明该列都为0，无解
        {
            cout<<"No Solution"<<endl;return;
        }
        for(int j=1;j<=n;j++)
        {
            if(j!=i)
            {
                double tmp=d[j][i]/d[i][i];
                for(int k=i;k<=n+1;k++)
                {
                    d[j][k]-=d[i][k]*tmp;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
        cout<<fixed<<setprecision(2)<<d[i][n+1]/d[i][i]<<endl;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)
            cin>>d[i][j];
    guess();
}
signed main()
{
    ios;
    //int T;cin>>T;
    //while(T--)
    solve();
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

Matrix Equation

抄了大佬们的一个高斯消元求自由元的板子。

#include 
#define endl '\n'
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define PII pair<int,int>

using namespace std;
const int N =2e2+5;
const int inf=1e18;
const int mod=998244353;
int n,id;
int A[N][N],B[N][N];
int a[N][N];

int qpow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
int x[N];       //解集
int freeX[N];   //自由变元
//equ:方程个数 var:变量个数
int Gauss(int equ, int var)
{
    for(int i = 1; i <= var; i++)
    {
        x[i] = 0;
        freeX[i] = 0;
    }
    int col = 1;//当前处理的列
    int num = 0;//自由变元的序号
    int row;//当前处理的行
    for(row = 1; row <= equ && col <= var; row++, col++) //枚举当前处理的行
    {
        int maxRow = row;//当前列绝对值最大的行
        for(int i = row + 1; i <= equ; i++) //寻找当前列绝对值最大的行
        {
            if(abs(a[i][col]) > abs(a[maxRow][col]))
                maxRow = i;
        }
        if(maxRow != row) //与第row行交换
        {
            for(int j = row; j <= var + 1; j++)
                swap(a[row][j], a[maxRow][j]);
        }
        if(a[row][col] == 0) //col列第row行以下全是0，处理当前行的下一列
        {
            freeX[num++] = col;//记录自由变元
            row--;
            continue;
        }
        for(int i = row + 1; i <= equ; i++)
        {
            if(a[i][col] != 0)
            {
                for(int j = col; j <= var + 1; j++) //对于下面出现该列中有1的行，需要把1消掉
                {
                    a[i][j] ^= a[row][j];
                }
            }
        }
    }
    /*求解*/
    //无解：化简的增广阵中存在(0,0,...,a)这样的行，且a!=0
    for (int i = row; i <= equ; i++)
        if (a[i][col] != 0)
            return -1;

    //无穷解: 在var*(var+1)的增广阵中出现(0,0,...,0)这样的行
    if (row <= var)//返回自由变元数
        return var - row+1;//自由变元有var-k个

    //唯一解: 在var*(var+1)的增广阵中形成严格的上三角阵
    for (int i = var ; i >= 1; i--) {//计算解集
        x[i] = a[i][var];
        for (int j = i + 1; j <=var; j++)
            x[i] ^= (a[i][j] && x[j]);
    }
    return 0;
}

void solve()
{
    cin>>n;
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++)
            cin>>A[i][j];
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++)
            cin>>B[i][j];
    int ans=0;
    for(int k=1; k<=n; k++)
    {
        memset(a,0,sizeof a);
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
                a[i][j]=A[i][j];
            if(B[i][k]) a[i][i]^=1;
        }
        ans+=max(0ll,Gauss(n,n));
    }
    cout<<qpow(2,ans)%mod<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
    solve();
    return 0;
}




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

F. Icebergs

逆时针对两个点进行叉乘累加，最后取绝对值再除以2为多边形的面积。
此外，题目中没有要求，先不要考虑给出点的顺时针、逆时针顺序。

#include 
#define endl '\n'
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define PII pair<int,int>

using namespace std;
const int N =1e6+5;
const int inf=1e18;
const int mod=1e9+7;
int n,m;
struct Node{
	double x, y;
	double operator ^ (const Node &b) const{
		return x * b.y - y * b.x;
	}
};

vector<Node> e;
void solve()
{
    cin>>n;
    double ans=0;
    for(int i=1; i<=n; i++)
    {
        e.clear();
        cin>>m;
        int lx=inf,rx=0,by=inf,ty=0;
        for(int j=1; j<=m; j++)
        {
            int x,y;
            cin>>x>>y;
            e.push_back({x,y});
        }
        e.push_back({e[0].x,e[0].y});
        double area=0;
        for(int i=1; i<e.size(); i++)
        {
            area+=(e[i-1]^e[i]);
        }
        ans+=abs(area)/2;
    }
    cout<<(int)(ans)<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
    solve();
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

D1. Zero-One (Easy Version)

如果对应位置不一样的数目为奇数，是不存在变换方案的；此外，若只好有一对相邻位置不同的，在x和2*y中取最小值即可；若有偶数前提下有多对，肯定选y值不相邻交换才是最优的

#include
#define int  long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
int n,x,y;
string s1,s2;
void solve()
{
    cin>>n>>x>>y>>s1>>s2;
    s1=" "+s1;s2=" "+s2;
    int g=0,flag=0;
    for(int i=1;i<=n;i++)
        if(s1[i]!=s2[i]) g++;
    if(g%2)
    {
        cout<<-1<<endl;return;
    }
    for(int i=1;i<n;i++)
    {
        if(s1[i]!=s2[i]&&s1[i+1]!=s2[i+1])
        {
            if(g==2)
            {
                flag=1;
                break;
            }
        }
    }
    if(flag)
        cout<<min(x,2*y)<<endl;
    else
        cout<<(g/2)*y<<endl;
}
signed main()
{
    //ios;
    int T;cin>>T;
    while(T--)
        solve();
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

D2. Zero-One (Hard Version)

在D1的条件下，加上几组特判和记忆化搜索。
题解：非常棒的大佬题解

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int inf=1e18;
const int N=5e3+5;
const int mod=1e9+7;
int n,x,y,dp[N][N];
string s1,s2;
vector<int>e;
int cal(int l,int r)
{
    if(l+1==r) return min(2*y,x);
    else
        return min(y,(r-l)*x);
}
int dfs(int l,int r)
{
    if(l>r) return 0;
    if(dp[l][r]!=-1) return dp[l][r];
    int res=inf;
    res=min(res,dfs(l+1,r-1)+cal(e[l],e[r]));
    res=min(res,dfs(l+2,r)+cal(e[l],e[l+1]));
    res=min(res,dfs(l,r-2)+cal(e[r-1],e[r]));
    dp[l][r]=res;
    return dp[l][r];
}
void solve()
{
    e.clear();
    cin>>n>>x>>y>>s1>>s2;
    s1=" "+s1;s2=" "+s2;
    for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j]=-1;
    for(int i=1;i<=n;i++)
        if(s1[i]!=s2[i]) e.push_back(i);
    if(e.size()%2)
    {
        cout<<-1<<endl;return;
    }
    if(e.size()==0)
    {
        cout<<0<<endl;return;
    }
    else if(e.size()==2)
    {
        if(e[0]+1==e[1]) cout<<min(2*y,x)<<endl;
        else cout<<min(y,(e[1]-e[0])*x)<<endl;
        return;
    }
    else if(x>=y)
    {
        cout<<(e.size()/2)*y<<endl;return;
    }
    cout<<dfs(0,e.size()-1)<<endl;
}
signed main()
{
    //ios;
    int T;cin>>T;
    while(T--)
        solve();
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68