# 演算法課程題解 - 暴力與窮舉 2

# UVa 541
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?541
## 解法 by baie
### 想法
輸出要求的三種狀況分別為
1. 矩陣已等價
2. 矩陣更改一點可等價
3. 矩陣不可等價

直接窮舉過整個矩陣，如果各行列皆等價則為狀況1，否則如果未等價的(行<=1)和(列<=1)，即為狀況2，否則為狀況3
### 程式碼

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	bool a[110][110];
	int b[110][2];
	while(cin>>n&&n)
	{
		memset(b,0,sizeof(b));
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				cin>>a[i][j];
				if(a[i][j]) b[i][0]++,b[j][1]++;
			}
		}
		int x = 0,y = 0;
		bool w = 0;
		for(int i=1;i<=n&&!w;i++)
		{
			if(b[i][0]%2&&!x) x = i;
			else if(b[i][0]%2&&x) w = 1;
			if(b[i][1]%2&&!y) y = i;
			else if(b[i][1]%2&&y) w = 1;
		}
		if(w) cout<<"Corrupt"<<endl;
		else if(x&&y) cout<<"Change bit ("<<x<<","<<y<<")"<<endl;
		else cout<<"OK"<<endl;
	}
	return 0;
}

### 時間複雜度
時間複雜度為$O(n^2)$

# UVa 498
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?498
## 解法 by baie
### 想法
倒序計算多項式可以直接延用上一次的X值，不用每次再重新計算X次方
### 程式碼

#include<bits/stdc++.h>
using namespace std;

long long int a[1000000],b[1000000],ans[1000000];
int main()
{
	string s,s1;
	while(getline(cin,s))
	{
		getline(cin,s1);
		stringstream ss;
		int n,k=0,w=0,e=0;
		long long int x,y,sum;
		ss << s;
		while(ss >> n)
			a[k++] = n;
		ss.clear(),ss.str("");
		ss << s1;
		while(ss >> n)
			b[w++] = n;
		for(int i=0;i<w;i++)
		{
			y = b[i],x = b[i], sum = a[k-1];
			for(int j=k-2;j>=0;j--)
			{
				sum += a[j] * x;
				x *= y; 
			}
			ans[i] = sum;
		}
		cout<<ans[0];
		for(int i=1;i<w;i++) cout<<" "<<ans[i];
		cout<<endl;
	}
	return 0;
}

### 時間複雜度
n為最大次方，時間複雜度為$O(nm)$
# UVa 11059
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?11059
## 解法 by baie
### 想法
窮舉所有的連續數字乘積取最大
### 程式碼

#include<bits/stdc++.h>
using namespace std;

int main()
{
	long long int n,k=0,a[20];
	while(cin>>n)
	{
		k++;
		for(int i=0;i<n;i++) cin>>a[i];
		long long int mx = 0,sum = 0;
		for(int i=0;i<n;i++)
		{
			sum = a[i];
			mx = max(sum,mx);
			for(int j=i+1;j<n;j++)
			{
				sum = sum * a[j];
				mx = max(sum,mx);	
			}
		} 
		cout<<"Case #"<<k<<": The maximum product is "<<mx<<'.'<<"\n\n";
	}
	return 0;
}

### 時間複雜度
時間複雜度為$O(n^2)$
# ZJ b840
## 題目
https://zerojudge.tw/ShowProblem?problemid=b840

## 解法 by tim25871014
### 想法
有效率的演算法有很多種，這邊提供最直接最暴力但是非常慢的作法。

### AC code

#include<iostream>
using namespace std;
int a[21][21];

int sum(int u, int d, int l, int r) {
    int ans = 0;
    for(int i=u;i<=d;i++) for(int j=l;j<=r;j++) ans += a[i][j];
    return ans;
}

int main() {
    int n;
    cin >> n;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) {
        cin >> a[i][j];
    }
    int ans = 0;
    for(int u=0;u<n;u++) for(int d=u;d<n;d++) {
        for(int l=0;l<n;l++) for(int r=l;r<n;r++) {
            ans = max(ans, sum(u, d, l, r));
        }
    }
    cout << ans << endl;
}

### 時間複雜度
$O(n^6)$

###### tags: `SCIST 演算法 題解`