25.3.13刷题

P2670 扫雷问题

https://www.luogu.com.cn/problem/P2670

题解

入门题

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

const int N = 105;
char a[N][N];
int ans;
int m, n;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == '*') {
				cout << '*';
				continue;
			}
			if (a[i - 1][j] == '*') ans++;
			if (a[i - 1][j + 1] == '*') ans++;
			if (a[i][j + 1] == '*')ans++;
			if (a[i + 1][j + 1] == '*') ans++;
			if (a[i + 1][j] == '*') ans++;
			if (a[i + 1][j - 1] == '*')ans++;
			if (a[i][j - 1] == '*')ans++;
			if (a[i - 1][j - 1] == '*')ans++;
			cout << ans;
			ans = 0;
		}
		cout << endl;
	}

	return 0;
}

使用方向数组 dx dy

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

const int N = 105;
char a[N][N];
int dx[8] = { 0,0,1,1,1,-1,-1,-1 }, dy[8] = { -1,1,-1,0,1,-1,0,1 };//方向数组
int ans=0;
int m, n;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == '*') {
				cout << '*';
			}
			else {
				for (int k = 0; k < 8; k++) {
					int x = i + dx[k], y = j + dy[k];
					if (x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] == '*') ans++;
				}
				cout << ans;
				ans = 0;
			}
			
		}
		cout << endl;
	}

	return 0;
}

P1563 玩具谜题

https://www.luogu.com.cn/problem/P1563

题解

模拟，朝内向左和朝外向右一样，朝内向右和朝外向左一样。模拟转圈。

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

const int N = 100001;
int a[N];
string name[N];
int n, m, x, y;
int t = 1;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> a[i] >> name[i];
	for (int i = 1; i <= m; i++) {
		cin >> x >> y;
		if (a[t] == x) t -= y;
		else t += y;
		if (t <= 0) t += n;
		else if (t > n) t -= n;
	}
	cout << name[t];

	return 0;
}

P1601 A+B Problem (高精)

https://www.luogu.com.cn/problem/P1601

题解

高精度加法，模板题。

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

vector<int>add(vector<int>&a,vector<int>&b)
{
	vector<int> c;
	int t=0;
	for(int i=0;i<a.size()||i<b.size();i++)
	{
		if(i<a.size()) t+=a[i];
		if(i<b.size()) t+=b[i];
		c.push_back(t%10);
		t/=10;
	}
	if(t) c.push_back(1);
	return c;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	string A,B;
	cin>>A>>B;
	vector<int> a,b;
	for(int i=A.length()-1;i>=0;i--) a.push_back(A[i]-'0');
	for(int i=B.length()-1;i>=0;i--) b.push_back(B[i]-'0');
	vector<int>ans=add(a,b);
	for(int i=ans.size()-1;i>=0;i--) cout<<ans[i];
	
	return 0;
}

P1303 A*B Problem

https://www.luogu.com.cn/problem/P1303

题解

高精度乘法，模板题。

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

vector<int>mul(vector<int>& a, vector<int>& b)
{
	vector<int> c(a.size()+b.size());
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < b.size(); j++)
		{
			c[i + j] += a[i] * b[j];
		}
	}
	for(int i=0,t=0;i<c.size();i++)
	{
		t += c[i];
		c[i] = t % 10;
		t /= 10;
	}
	while (c.size() > 1 && c.back() == 0) c.pop_back();
	return c;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	string A, B;
	cin >> A >> B;

	vector<int> a, b;
	for (int i = A.length() - 1; i >= 0; i--) a.push_back(A[i] - '0');
	for (int i = B.length() - 1; i >= 0; i--) b.push_back(B[i] - '0');

	vector<int>ans = mul(a, b);
	for (int i = ans.size() - 1; i >= 0; i--) cout << ans[i];

	return 0;
}

P1009 阶乘之和

https://www.luogu.com.cn/problem/P1009

题解

高精度乘法 和 高精度加法

//阶乘之和
#include<bits/stdc++.h>
using namespace std;

int n;

vector<int>add(const vector<int>& a, const vector<int>& b)
{
	vector<int>c;
	int t = 0;
	for (int i = 0; i < a.size() || i < b.size(); i++)
	{
		if (i < a.size()) t += a[i];
		if (i < b.size()) t += b[i];
		c.push_back(t % 10);
		t /= 10;
	}
	if (t) c.push_back(1);
	return c;
}

vector<int>mul(vector<int>& a, vector<int>& b)
{
	vector<int> c(a.size() + b.size());
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < b.size(); j++)
			c[i + j] += a[i] * b[j];
	}
	for (int i = 0,t=0; i < c.size(); i++)
	{
		t += c[i];
		c[i] = t % 10;
		t /= 10;
	}
	while (c.size() > 1 && c.back() == 0) c.pop_back();
	return c;
}

vector<int> jiecheng(int n)
{
	vector<int>ans = {1};
	vector<int>c;
	for (int i = 1; i <= n; i++)
	{
		c.clear();
		int p = i;
		while (p > 0)
		{
			c.push_back(p % 10);
			p /= 10;
		}
		ans = mul(c, ans);
	}
	return ans;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	vector<int>ans = { 0 };
	for (int i = 1; i <= n; i++)
	{
		ans = add(ans, jiecheng(i));
	}
	for (int i = ans.size() - 1; i >= 0; i--) cout << ans[i];

	return 0;
}