第二周题解

2026-02-05
0
0
26分钟

第A题

思路:先找R1的最大值,再去遍历找R2.

#include<bits/stdc++.h>

using i64 = long long;
int n;
std::vector<int> d , c;
void update(int x)
{
	int tim = 1;
	while(x <= n && x != 1)
	{
		d[x] = tim;
		x *= x;
		c[x] = tim;
		tim++;
	}
	if(x == 1)
		d[x] = x;
}

struct ma
{
	int w;
	int d3;
	int d4;
};

bool cmp(ma x , ma y)
{
	return x.d3 <= y.d3;
}

bool cmp1(double x , double y)
{
	return x <= y;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::pair<int , int> d1 , d2;
	std::cin >> d1.first >> d1.second >> d2.first >> d2.second;
	int n;
	std::cin>>n;
	int r1 = 0 , r2 = 0;
	std::vector<ma> me(n);
	for(int i = 0;i < n;i++)
	{
		int x , y;
		std::cin>> x >> y;
		me[i].d3 = (x - d1.first) * (x - d1.first) + (y - d1.second) * (y - d1.second);
		me[i].d4 = (x - d2.first) * (x - d2.first) + (y - d2.second) * (y - d2.second);
		
	}
	std::sort(me.begin() , me.end() , cmp);
	int ans = me[n - 1].d3;
	r2 = 0;
	for(int i = n - 1;i >= 0;i--)
	{
		r2 = std::max(r2 , me[i].d4);
		if(i == 0)
		{
			ans = std::min(ans , r2);
			continue;
		}
		ans = std::min(ans , me[i - 1].d3 + r2);
	}
	std::cout<< ans <<"\n";
	
	return 0;
}

第B题

思路:直接dfs即可

#include<bits/stdc++.h>

using i64 = long long;

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n , m;
	std::cin>> n >> m;
	std::vector<std::vector<int>> ma(n , std::vector<int>(m , -1));
	for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < m;j++)
		{
			std::cin>> ma[i][j];
		}
	}
	int dx[4] = {1 , -1 , 0 , 0} , dy[4] = {0 , 0 , 1 , -1};
	std::vector<std::vector<int>> dg(n , std::vector<int>(m , -1));
	auto dfs = [&](auto self , int x , int y) -> int
	{
		dg[x][y] = 1;
		int cnt = 0;
		for(int i = 0;i < 4;i++)
		{
			int xx = x + dx[i] , xy = y + dy[i];
			if(xx >= 0 && xx < n && xy >= 0 && xy < m && ma[xx][xy] < ma[x][y])
			{
				if(dg[xx][xy] != -1)
				{
					cnt = std::max(cnt , dg[xx][xy]);
				}
				else
				{
					cnt = std::max(cnt , self(self , xx , xy));
				}
			}
		}
		dg[x][y] += cnt;
		return dg[x][y];
	};
	int ans = 0;
	for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < m;j++)
		{
			if(dg[i][j] != -1)
			{
				ans = std::max(ans , dg[i][j]);
			}
			else
			{
				ans = std::max(ans , dfs(dfs , i , j));
			}
		}
	}
	std::cout<< ans << "\n";
	
	
	
	
	
	
	return 0;
}

第C题

思路:依旧dfs, 但需注意w是水.......

#include<bits/stdc++.h>

using i64 = long long;
int n , m;
std::vector<std::string> ma;
std::vector<std::vector<int>> me;
int dx[8] = {1 , -1 , 0 , 0 , 1 , -1 , 1 , -1};
int dy[8] = {0 , 0 , -1 , 1 , 1 , 1 , -1 , -1};

void update(int x , int y)
{
	if(me[x][y] == 1)
		me[x][y] = -1;
	for(int i = 0;i < 8;i++)
	{
		int xx = x + dx[i] , xy = y + dy[i];
		if(xx >= 0 && xx < n && xy >= 0 && xy < m && me[xx][xy] == 1)
		{
			update(xx , xy);
		}
		else
			continue;
	}
//	if(x < 0 || x >= n || y < 0 || y >= m || me[x][y] == -1)
//		return;
//	me[x][y] = -1;
//	for(int i = 0;i < 8;i++)
//		update(x + dx[i] , y + dy[i]);
}


int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin>> n >> m;
	ma.resize(n);
	me.resize(n , std::vector<int>(m , -1));
	for(int i = 0;i < n;i++)
	{
		std::cin>> ma[i];
		for(int j = 0;j < m;j++)
		{
			if(ma[i][j] == 'W')
				me[i][j] = 1;
		}
	}
	int ans = 0;
	for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < m;j++)
		{
			if(me[i][j] == 1)
			{
				ans ++;
				update(i , j);
			}
		}
	}
	std::cout<< ans <<"\n";
	
	
	
	
	
	
	
	return 0;
}

第D题

思路:遍历,从1开始,找到1的位置,然后向后推找2...的位置,直到封闭,然后继续操作

#include<bits/stdc++.h>

using i64 = long long;


int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t;
	std::cin >> t;
	while(t--)
	{
		
		int n;
		std::cin>> n;
		std::vector<int> a(n + 1 , 0) , b(n + 1 , 0);
		for(int i = 1;i <= n;i++)
		{
			std::cin >> a[i];
			b[a[i]] = i;
		}
		int ans = 0;
		for(int i = 1;i <= n;i++)
		{
			if(b[i] == i)
				continue;
			else
			{
				int be = i , ed = b[i];
				for(int j = be + 1 ; j <= ed;j++)
				{
					if(b[j] > ed)
						ed = b[j];
				}
				i = ed;
				ans += ed - be + 1;
			}
			
		}
		std::cout<< ans << "\n";
	}
	
	
	
	
	
	
	
	return 0;
}

第E题

思路:dfs

#include<bits/stdc++.h>

using i64 = long long;


int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n , m;
	std::cin >> n >> m;
	std::vector<std::string> a(n);
	std::vector<std::vector<int>> ma(n , std::vector<int>(m , 0));
	for(int i = 0;i < n;i++)
		std::cin>> a[i];
	int dx[4] = {0 , 0 , -1 , 1} , dy[4] = {-1 , 1 , 0 , 0};
	
	auto dfs = [&](auto self , int x , int y) -> bool
	{
		ma[x][y] = 1;
		bool dg = 0;
		if(x == n - 1 && y == m - 1)
			return 1;
		for(int i = 0;i < 4;i++)
		{
			int xx = x + dx[i] , xy = y + dy[i];
			if(xx >= 0 && xx < n && xy >= 0 && xy < m && a[xx][xy] == '.' && !ma[xx][xy])
			{
				if(self(self , xx , xy))
					dg = 1;
			}
		}
		return dg;
	};
	
	if(dfs(dfs , 0 , 0))
		std::cout<< "Yes" << "\n";
	else
		std::cout<< "No" << "\n";
	
	
	
	
	return 0;
}

第F题

思路:先求前缀和再依次求总和

#include<bits/stdc++.h>

using i64 = long long;


int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n;
	std::cin>> n;
	std::vector<i64> a(n + 1 , 0) , sum(n + 1 , 0);
	for(int i = 1;i <= n;i++)
	{
		std::cin>> a[i];
		sum[i] = a[i] + sum[i - 1];
	}
	i64 ans = 0;
	for(int i = 1;i <= n;i++)
	{
		ans += (sum[n] - sum [i]) * a[i];
	}
	std::cout<< ans << "\n";
	
	
	
	
	return 0;
}

第G题

思路:我看的题解,根据异或和总小于和得出结论:全部异或即可.......

#include<bits/stdc++.h>

using i64 = long long;


int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n;
	std::cin>> n;
	std::vector<i64> a(n);
	for(int i = 0;i < n;i++)
		std::cin>> a[i];
	i64 ans = 0;
	for(int i = 0;i < n;i++)
	{
		ans ^= a[i];
	}
	std::cout<< ans <<"\n";
	
	
	
	
	return 0;
}

H

思路:先特判t,然后除2即可

#include<bits/stdc++.h>

using i64 = long long;


int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n;
	std::cin>> n;
	int t = 1 , ans = 0;
	while(t < n)
		t *= 2;
	if(t == n)
	{
		std::cout<< n << " 0" << "\n";
		return 0;
	}
	else
		std::cout<< t << " ";
	int i = 0;
	while(n > 0)
	{
		t /= 2;
		n %= t;
		i++;
	}
	std::cout<< i << "\n";
	
	
	
	return 0;
}

I

思路:我当时确实没思路,去看了题解,发现依旧是dfs........

#include<bits/stdc++.h>

using i64 = long long;
int r , n;
std::vector<int> a(100 , 0);

void dfs(int x)
{
	if(x > r)
	{
		for(int i = 1;i <= r;i++)
		{
			std::cout<< std::setw(3) << a[i];
		}
		std::cout<< "\n";
		return;
	}
	for(int  i = a[x - 1] + 1;i <= n;i++)
	{
		a[x] = i;
		dfs(x + 1);
	}
}


int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin>> n >> r;
	dfs(1);
	
	
	
	
	return 0;
}

J

思路:2进制分法加普通背包

#include<bits/stdc++.h>

using i64 = long long;

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int N , T;
	std::cin>> N >> T;
	std::vector<std::pair<int , int>> a(N);
	for(int i = 0;i < N;i++)
		std::cin>> a[i].first >> a[i].second;
	std::vector<double> d(T + 1 , 0.0);
	for(int i = 0;i < N;i++)
	{
		int c = a[i].first , e = 1;
		double on = (double)a[i].second / a[i].first;
		while(c >= e)	
		{
			double mo = e * on;
			c -= e;
			for(int j = T;j;j--)
			{
				if(j >= e)
					d[j] = std::max(d[j] , d[j - e] + mo);
			}
			e *= 2;
		}
		if(c)
		{
			for(int j = T;j;j--)
			{
				if(j >= c)
					d[j] = std::max(d[j] , d[j - c] + c * on);
			}
		}
	}
	std::cout << std::fixed << std::setprecision(2) << d[T] << "\n";
	
	
	
	
	return 0;
}

K

思路:二分查找即可

#include<bits/stdc++.h>

using i64 = long long;

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int m , n;
	std::cin>> m >> n;
	std::vector<int> f(m) , na(n);
	for(int i = 0;i < m;i++)
		std::cin>> f[i];
	for(int i = 0;i < n;i++)
		std::cin>> na[i];
	i64 ans = 0;
	std::sort(f.begin() , f.end());
	for(int i = 0;i < n;i++)
	{
		int l = 0 , r = m - 1 , mid = (l + r) >> 1 , pos = m;
		while(l <= r)
		{
			if(f[mid] < na[i])
			{
				l = mid + 1;
			}
			else
			{
				r = mid - 1;
				pos = mid;
			}
			mid = (l + r) >> 1;
		}
		int cnt = 1e9;
		if(pos < m)
			cnt = std::min(cnt , std::abs(na[i] - f[pos]));
		if(pos > 0)
			cnt = std::min(cnt , std::abs(na[i] - f[pos - 1]));

		ans += cnt;
	}
	std::cout<< ans <<"\n";
	
	
	
	
	return 0;
}

L

思路:先大再小依次排,然后平方输出

#include<bits/stdc++.h>

using i64 = long long;

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n;
	std::cin>> n;
	std::vector<i64> j(n) , s(n);
	for(int i = 0;i < n;i++)
	{
		std::cin>> j[i];
	}
	std::sort(j.begin() , j.end());
	i64 ans = 0 , k = 0;
	for(int i = 0;i < (n + 1) / 2;i++)
	{
		s[k] = j[n - 1 - i];
		k++;
		if(k < n)
		{
			s[k] = j[i];
			k++;
		}
	}
	i64 st = 0;
	for(int i = 0 ; i < n;i++)
	{
		ans += (st - s[i]) * (st - s[i]);
		st = s[i];
	}
	std::cout<< ans << "\n";
//	for(int i = 0;i < n;i++)
//		std::cout<< s[i] << " \n"[i == n - 1];
//	
	
	
	
	
	return 0;
}

如果觉得文章对你有用，请随意赞赏

第二周题解

评论