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;
}