A.Love Story

題意:

給定n個長度為10的字串，問其與codeforces字串的對應下標字母不同的個數，

分析:

對于每個字串從前往后依次和“codeforces”對應字符比較然后統計不同字母數即可

code:

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

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	string s = "codeforces";
	
	int t;
	cin >> t;
	
	while (t --)
	{
		string s2;
		cin >> s2;
		
		int cnt = 0;
		for (int i = 0; i < 10; i ++)
			if (s2[i] != s[i])
				cnt ++;
		
		cout << cnt << endl;	
	} 
	
	return 0;
}

B. Blank Space

題意:

給定長度為n的陣列，問連續相鄰為0的最大長度

分析:

維護一個全域最大長度res，和當前連續序列的長度cnt，從前往后掃描序列，若當前元素為0則更新cnt,否則更新res并重置cnt為0

code:

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

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t;
	cin >> t;
	
	while (t --)
	{
		int n;
		cin >> n;
		
		int res = 0, cnt = 0; 
		for (int i = 0; i < n; i ++)
		{
			int a;
			cin >> a;
			
			if (a == 0)
				cnt ++;
			else
			{
				res = max(res, cnt);
				cnt = 0;
			}
		}
		
		res = max(res, cnt);
		
		cout << res << endl;
	} 
	
	return 0;
}

C. Mr. Perfectly Fine

題意：

給定n個二元組，第一個數為花費，第二個是一個長度為2的01串，第一位為1表示含有1技能，第二位為1表示含有2技能，問最少需要花費多少才能獲得這兩個技能即用最少的花費得到字串11？

分析：

由于“00，01，10，11”分別表示“0，1，2，3”，所以為了方便處理我直接用數字表示字串，
首先預處理排個序，優先按花費從小到大排序，若花費相同則按技能數值從大到小排序（能優先得到3自然不需要用1和2來湊）
然后我們考慮以下情況：①第一次選到3②第一次選到1③第一次選到2，這三種情況誰先發生并有解，誰就是最優解，

code:

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

const int N = 2e5 + 5;
struct Book
{
	int t, skill;
}book[N];

bool cmp(Book A, Book B)
{
	if (A.t != B.t)
		return A.t < B.t;
	else
		return A.skill > B.skill;
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n;
		cin >> n;
		
		for (int i = 0; i < n; i ++)
		{
			string s;
			cin >> book[i].t >> s;
			int skill = 0;
			if (s == "00")
				skill = 0;
			else if (s == "01")
				skill = 1;
			else if (s == "10")
				skill = 2;
			else
				skill = 3;
			book[i].skill = skill; 
		}
		
		sort(book, book + n, cmp);
		
		int res = 0x3f3f3f3f;
		bool a = false, b = false, c = false;
		for (int i = 0; i < n; i ++)
		{
			if (book[i].skill == 0)
				continue;
				
			if (a && b && c)
				break;
			
			if (book[i].skill == 3)
			{
				if (!a)
				{
					res = min(res, book[i].t);
					a = true;
					break;
				}
			}
			
			if (book[i].skill == 1)
			{
				if (!b)
				{
					for (int j = i + 1; j < n; j ++)
					{
						if (book[j].skill == 2)
						{
							res = min(res, book[i].t + book[j].t);
							break;
						}
					}
					b = true;
				}
			}
			
			if (book[i].skill == 2)
			{
				if (!c)
				{
					for (int j = i + 1; j < n; j ++)
					{
						if (book[j].skill == 1)
						{
							res = min(res, book[i].t + book[j].t);
							break;
						}
					}
					c = true;
				}
			}
		}
		
		if (res == 0x3f3f3f3f)
			cout << -1 << endl;
		else
			cout << res << endl;
	} 
	
	return 0;
}

D. Gold Rush

題意:

給你兩個數n和m，n可以拆成兩個數a和b，需要滿足：a + b = n，且其中一個數a（或b）需為另一個數b（或a）的2倍，問是否能拆出m來，

分析：

首先得明確如果n能按題目劃分則n必須得是3的倍數，然后dfs搜索一下所有劃分方案看是否有解即可

code：

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

const int N = 2e5 + 5;

bool dfs(int n, int m)
{
	if (n == m)
		return true;
	
	if (n % 3 != 0)
		return false;
	int a = n / 3;
	int b = a * 2;
	
	if (a == m || b == m)
		return true;
	
	if (m > b)
		return false;
	else
	{
		if (dfs(b, m))
			return true;
		else if (m > a)
			return false;
		
		if (dfs(a, m))
			return true;
	}
	
	return false;
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n, m;
		cin >> n >> m;
		
		if (dfs(n, m))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	} 
	
	return 0;
}

E. The Lakes

題意:

給定n * m的地圖，每個點都有一個非負數的權值，定義湖泊區域為不包含值為0的連通區域(上下左右任意聯通即可)，問其中點權值和最大的湖泊區域所對應的值為多少，

分析：

經典的flood-fill模型，可以用bfs做也可以用dfs做，

code:

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

#define x first
#define y second

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1010;
int g[N][N];
bool st[N][N];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int n, m;

LL bfs(int sx, int sy)
{
	queue<PII> q;
	LL res = g[sx][sy];
	q.push({sx, sy});
	st[sx][sy] = true;
	
	while (q.size())
	{
		auto t = q.front();
		q.pop();
		
		int x = t.x, y = t.y;
		
		for (int i = 0; i < 4; i ++)
		{
			int x1 = x + dx[i], y1 = y + dy[i];
			
			if (x1 < 0 || x1 > n || y1 < 0 || y1 > m || g[x1][y1] == 0 || st[x1][y1])
				continue;
				
			res += g[x1][y1];
			st[x1][y1] = true;
			q.push({x1, y1});
		}
	}
	
	return res;
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		cin >> n >> m;
		
		LL res = 0;
		for (int i = 0; i < n; i ++)
		{
			for (int j = 0; j < m; j ++)
			{
				cin >> g[i][j];
				st[i][j] = false;
			}
		}
		
		for (int i = 0; i < n; i ++)
		{
			for (int j = 0; j < m; j ++)
			{
				if (g[i][j] == 0 || st[i][j])
					continue;
				res = max(res, bfs(i, j));
			}
		}
		
		cout << res << endl;
	} 
	
	return 0;
}

F. Forever Winter

題意:

給定一個雪花圖，問滿足這個圖要求的x和y是多少？
1.1個點連接著x個其他的點，
2.這x個點又分別連接著y個點，

分析:

找規律，我們可以發現，設度為1的結點總數為n，則n = x * y，于是我們可以用unordered_map記錄所有存在的度數，列舉n的因數x,y，若度數x和度數y + 1存在或者度數y和度數x + 1存在，則x和y就是滿足要求的解，

code:

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

#define x first
#define y second

typedef pair<int, int> PII;
typedef long long LL;

const int N = 210;
int d[N];

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n, m;
		cin >> n >> m;
		unordered_map<int, bool> mp;
		memset(d, 0, sizeof d);
		
		while (m --)
		{
			int a, b;
			cin >> a >> b;
			
			d[a] ++, d[b] ++;
		}
		
		int cnt = 0;
		for (int i = 1; i <= n; i ++)
		{
			if (d[i] == 1)
				cnt ++;
			mp[d[i]] = true;
		}
		
		for (int i = 2; i * i <= cnt; i ++)
		{
			if (cnt % i == 0)
			{
				int j = cnt / i;
				
				if (mp[i] && mp[j + 1])
				{
					cout << i << " " << j << endl;
					break;
				}
				else if (mp[i + 1] && mp[j])
				{
					cout << j << " " << i << endl;
					break;
				}
			}
		}
	} 
	
	return 0;
}

G. Hits Different

題意:

給你2023行數，第i行有i個數，如果一個數被“擊倒”，則會影響上面與其相鄰的數（也會被“擊倒”），影響會一直向上擴散，問被擊倒的這些數的和為多少，

分析:

①首先分析，擊中一個數n它會影響到哪些數？這里可以找規律，可以發現數字是和層數相關的：第i層[l,r]將會影響到第i - 1層的[l - i, r - i + 1]，當然這里要注意邊界，第i層的數n應當滿足：i * (i - 1) / 2 + 1 <= n <= i * (i + 1) / 2，所以設L = l - i, R = r - i + 1, I = i - 1;那么L = max(L, I * (I - 1) / 2 + 1), R = min(R, I * (I + 1) / 2)，
②既然知道會影響哪些數，那么怎么求和呢？快速求一個區間的和我們自然想到用前綴和來處理，
③最后分析如何確定一個數所在的層數，根據上面分析第i層的數n應當滿足：i * (i - 1) / 2 + 1 <= n <= i * (i + 1) / 2，可以通過看n是否滿足 floor * (floor + 1) / 2的二段性來二分查找，

code:

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

typedef unsigned long long LL;

const int N = 1e6 + 5;
LL s[N];

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	for (LL i = 1; i < N; i ++)
		s[i] = s[i - 1] + i * i;
		
	int t;
	cin >> t;
	
	while (t --)
	{
		LL n;
		cin >> n;
		
		int l = 1, r = 2023;
		while (l < r)
		{
			int mid = l + r >> 1;
			if (n <= mid * (mid + 1) / 2)
				r = mid;
			else
				l = mid + 1;
		}
		int p = r;
		
		LL res = n * n;
		l = r = n;
		while (p > 1)
		{
			l = l - p;
			r = r - p + 1;
			p --;
			r = min(r, p * (p + 1) / 2);
			l = max(l, p * (p - 1) / 2 + 1);
			res += s[r] - s[l - 1];
		}
		
		cout << res << endl;
	}
	
	return 0;
}

H. Don't Blame Me

題意:

給定n個數，問有多少種子序列相與，結果的二進制中有k個1，

分析:

由于0 <= n <= 63,63已經是6位1了因此再怎么相與也不會超過63，所以我們可以先求出所有子序列相與結果為0-63的所有方案，然后從0-63中選出二進制有k個1的方案，其方案數之和即為答案，“求從n個數里選一些數使其相與結果為m的方案數”，這就是一個類01背包問題，
狀態：f[i][j]表示從前i個數中選一些數，使其相與結果為j的方案數，
轉移：
①不選第i個數：f[i][j] += f[i - 1][j];
②選第i個數: f[i][j & a[i]] += f[i - 1][j];
因為已知a & b = c，并不能推出c & b = a，所以②不能寫成f[i][j] += f[i - 1][j & a[i]];

code:

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

typedef long long LL;

const int N = 2e5 + 5, M = 65, mod = 1e9 + 7;
LL f[N][M];
int a[N];

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n, k;
		cin >> n >> k;
		
		for (int i = 1; i <= n; i ++)
			cin >> a[i];
			
		for (int i = 1; i <= n; i ++)
			for (int j = 0; j <= 63; j ++)
				f[i][j] = 0;
		
		for (int i = 1; i <= n; i ++)
		{
			f[i][a[i]] = 1;
			
			for (int j = 0; j <= 63; j ++)
			{
				f[i][j] = (f[i][j] + f[i - 1][j]) % mod;
				f[i][j & a[i]] = (f[i][j & a[i]] + f[i - 1][j]) % mod;	
			}	
		} 
		
		LL res = 0;
		for (int i = 0; i <= 63; i ++)
		{
			int m = i, len = 0;
			
			while (m)
			{
				if (m & 1)
					len ++;
				m >>= 1;
			}
			
			if (len == k)
				res = (res + f[n][i]) % mod;
		}
		
		cout << res << endl;
	}
	
	return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/551924.html

標籤：其他

上一篇：GPS北斗衛星時間同步系統助力電力自動化網路系統

下一篇：返回列表

Codeforces Round 871 (Div. 4)

A.Love Story

題意:

分析:

code:

B. Blank Space

題意:

分析:

code:

C. Mr. Perfectly Fine

題意：

分析：

code:

D. Gold Rush

題意:

分析：

code：

E. The Lakes

題意:

分析：

code:

F. Forever Winter

題意:

分析:

code:

G. Hits Different

題意:

分析:

code:

H. Don't Blame Me

題意:

分析:

code: