Toyota Programming Contest 2023#7（AtCoder Beginner Contest 328）

A. Not Too Hard

题意：

将给定的数列\(a\)中数值小于\(x\)的数累加。

解题思路:

模拟。

代码:

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

void solve()
{
	int n,x;
	cin >> n >> x;
	vector<int> s(n + 1);
	ll ans = 0;
	for(int i = 1;i<=n;i++)
	{
		cin >> s[i];
		if(s[i] <= x)
		{
			ans += s[i];
		}
	}
	cout<< ans;
}

int main()
{
	int t = 1;
//	cin >> t;
	while(t --)
	{
		solve();
	}
	return 0;
}

B. 11/11

题意：

设定一年的月数和各个月的天数，看一年中有多少天第\(i\)月第\(j\)号，的\(i,j\)是由一个数字组成。例如1月11日、2月2日。

解题思路:

暴力。找到由相同数字组成的月份，然后再该月份中找相同数字组成的日期。

代码:

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

void solve()
{
	int n;
	cin >> n;
	vector<int> d(n + 1);
	for(int i = 1;i<=n;i++)
	{
		cin >> d[i];
	}
	ll cnt = 0;
	for(int i = 1;i<=n;i++)
	{
		bool f = true;
		int t = i;
		int z = i % 10;
		while(t)
		{
			int y = t % 10;
			t /= 10;
			if(y != z)
			{
				f = false;
				break;
			}
		}
		if(!f)
		{
			continue;
		}
		for(int j = 1;j<=d[i];j++)
		{
			int x = j;
			bool f = true;
			while(x)
			{
				int t = x % 10;
				x /= 10;
				if(t != z)
				{
					f = false;
					break;
				}
			}
			if(f)
			{
//				cout << i <<' ';
//				cout << j <<endl;
				cnt ++;
			}
		}
	}
	cout << cnt;
}

int main()
{
	int t = 1;
//	cin >> t;
	while(t --)
	{
		solve();
	}
	return 0;
}

C Consecutive

题意：

给定一个字符串，有多组询问，每组询问为从\(l_i\)到\(r_i\)之间有多少个两两连续的字符短串。

例如\(aaa\)，这个字符中就有两个字符短串。\(aabcc\)中有两个\(aa,cc\)。

解题思路:

前缀和。

代码:

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

void solve()
{
	int n,q;
	cin >> n >> q;
	string s;
	cin >> s;
	s = ' ' + s;
	vector<int> d(n + 10);
	for(int i = 2;i<=n;i++)
	{
		if(s[i] == s[i-1])
		{
			d[i] = 1;
		}
		d[i] += d[i-1];
//		cout << i << "fdsafasdfasd" << d[i]<<endl;
	}

	while(q--)
	{
		int l,r;
		cin >> l >> r;
		ll ans = 0;
		cout << d[r] - d[l] << endl;
	}
}

int main()
{
	int t = 1;
//	cin >> t;
	while(t --)
	{
		solve();
	}
	return 0;
}

D. Take ABC

题意：

给定一个字符串，从左往右看，遇到\(ABC\)就删，然后从左往右看，直到所有\(ABC\)删完。

解题思路:

栈。从左到右找到一个删一个。

代码:

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

void solve()
{
	string s;
	cin >> s;
	string ans;
	for(auto c : s)
	{
		ans += c;
		if(ans.size() >= 3 && ans.substr(ans.size()-3,3) == "ABC")
		{
			ans.pop_back();
			ans.pop_back();
			ans.pop_back();
		}
	}
	cout << ans << endl;
}

int main()
{
	int t = 1;
//	cin >> t;
	while(t --)
	{
		solve();
	}
	return 0;
}

E. Modulo MST

题意：

给一个图，求最小生成树。此处最小指的是树边权求和后模\(k\)后最小。

解题思路:

数据量小。暴力枚举所有构造的可行方案。取最小值即可。

简单图这里最多\(26\)条边，我们最多从中取\(7\)条，\(C_{26}^7 = 657800\) 。

注意点:

树中边数为点数减一
用排列枚举组合数：\(C_a^b\)。我们开一个长度为\(a\)的数组，最后\(b\)个位置设为\(1\)，表示取，其余位置设为\(0\)，表示不取。\(next_permutation\)即可。
并查集合并时，让序号大的合并到小的上，最后根节点为1。

代码:

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

struct edge
{
	ll a,b,w;
	bool operator < (edge t)
	{
		return w < t.w;
	}
	
};

void solve()
{
	ll n,m,k;
	cin >> n >> m >>k;
	vector<edge> e(m + 1);
	for(int i = 1;i<=m;i++)
	{
		cin >> e[i].a >> e[i].b >> e[i].w;
	}
	vector<ll> p(n + 1);
	auto find =[&](auto self,int u) -> int
	{
		if(u != p[u])
		{
			p[u] = self(self,p[u]);
		}
		return p[u];
	};
	auto merge =[&](int a,int b) 
	{
		int pa = find(find,a);
		int pb = find(find,b);
		if(pa == pb)
		{
			return;
		}
		if(pa < pb)
		{
			swap(pa,pb);
		}
		p[pa] = pb;
	};
	vector<int> a(m + 1);
	for(int i = m - n + 2;i <= m;i++)
	{
		a[i] = 1;
//		cout << i << ' ' << a[i] << endl;
	}
	ll ans = 1e18;
	auto check =[&]()
	{
		for(int i = 1;i<=n;i++)
		{
			// ÕâÀïÒ»¶¨ÊÇfind(p[i])
			if(find(find,p[i]) != 1)
			{
				return false;
			}
		}
		return true;
	};
	do{
		for(int i = 1;i<=n;i++)
		{
			p[i] = i;
		}
		ll res = 0;
		for(int i = 1;i<=m;i++)
		{
			if(a[i])
			{
				res = (res + e[i].w) % k;
				merge(e[i].a,e[i].b);
			}
		}
		if(check())
		{
			ans = min(ans,res);
		}
	}while(next_permutation(a.begin() + 1,a.end()));
	cout << ans << endl;
}

int main()
{
	int t = 1;
//	cin >> t;
	while(t --)
	{
		solve();
	}
	return 0;
}