AtCoder Beginner Contest 167 题解
A - Registration
题意:
给两个仅由小写字母构成的字符串AB，问B是否是在A上添加一个小写字母构成的。思路:
直接判断即可，保险起见多写了些特判。
int main()
{
IOS;
string s1, s2;
cin >> s1 >> s2;
int i;
for (i = 0; i < s1.size(); i++)
{
if (s1[i] != s2[i])
break;
}
if (i == s1.size() && s2.size() - 1 == s1.size() && s2[i] >= 'a' && s2[i] <= 'z')
cout << "Yes";
else
cout << "No";
return 0;
}
B - Easy Linear Programming
题意:
给定放在一堆的、权值为1 0 -1的三种牌，现在从牌堆中取k张牌，求能获得的最大权值总和。思路:
暴力模拟即可。
int main()
{
IOS;
ll a[3],k;
cin>>a[0]>>a[1]>>a[2]>>k;
int ans=0;
for(int i=0;i<3;i++)
{
if(a[i]<=k)
{
ans+=a[i]*(1-i);
k-=a[i];
}else
{
ans+=k*(1-i);
k=0;
}
}
cout<<ans;
return 0;
}
C - Skill Up
题意:
给定n本书，每种书都有m种知识，给定书的价值和读书所能获得的知识，问至少需要花费多少才能使获得的m种知识，每一种都大于x思路:
dfs实在是不熟练，于是花了快半个小时写了一波bfs。。但是看这个题榜单过的超级快，估计有更简单的做法吧*
题目给定n，m都小于12，故直接使用bfs枚举所有可能的书本组合，判断最小花费即可。
struct node
{
ll c;
ll a[15];
} s[15];
ll vis[15], ans[15];
ll n, m, x;
struct node2
{
ll num;
ll ans[15];
ll vis[15];
ll cnt;
};
bool check(node2 top)
{
for (ll i = 0; i < m; i++)
{
if (top.ans[i] < x)
return false;
}
return true;
}
ll minn = 999999999;
void bfs()
{
queue<node2> q;
node2 ss;
ss.num = 0, ss.cnt = 0;
for (ll i = 0; i < n; i++)
{
ss.ans[i] = 0;
ss.vis[i] = 0;
}
q.push(ss);
node2 top;
while (!q.empty())
{
top = q.front();
if (check(top))
{
minn = min(minn, top.num);
}
q.pop();
for (ll i = top.cnt; i < n; i++)
{
if (!top.vis[i])
{
node2 temp;
for (ll j = 0; j < n; j++)
temp.vis[j] = top.vis[j];
temp.vis[i] = 1;
temp.num = top.num + s[i].c;
for (ll j = 0; j < m; j++)
temp.ans[j] = top.ans[j] + s[i].a[j];
temp.cnt = i;
q.push(temp);
}
}
}
}
int main()
{
IOS;
cin >> n >> m >> x;
for (ll i = 0; i < n; i++)
{
cin >> s[i].c;
for (ll j = 0; j < m; j++)
cin >> s[i].a[j];
}
bfs();
if (minn != 999999999)
cout << minn;
else
cout << -1;
return 0;
}
D - Teleporter
题意:
给定n个城市，和k次操作，一个人从第一个城市开始，每次可以从当前城市传送到当前城市的值所指向的城市，问k次操作后这个人在哪思路:
再一次被OI大佬清晰且简短的代码折服。。*
观察题目发现，因为城市之间可以互相传送，故这个人可能传送中途中陷入到一个环内，那么只需要判断坏的大小和初始位置，将k%(环的大小)即为位置
const ll N = 2e5 + 5;
int n, a[N], v[N], cnt, f[N];
ll k;
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
int x = 1;
do
{
v[x] = 1;
if (cnt == k)
{
cout << x;
return 0;
}
f[cnt++] = x;
x = a[x];
} while (!v[x]);
k -= cnt;
cnt = 0;
do
{
v[x] = 2;
f[cnt++] = x;
x = a[x];
} while (v[x]!=2);
cout << f[k % cnt];
return 0;
}
F - Bracket Sequencing
题意:
给n个由 “(” , “)” 构成的字符串，问能否把这些字符串串联起来，构成括号相互匹配的序列。思路:
绝世好题！！我最开始还以为要用什么复杂的算法 一看题解 ORZ*
- 先将输入的字符串中的已经形成匹配的括号删掉，之后剩余的无非就是三种："(((..."、"...)))"、"...)))(((..."，那么就可以将左右括号映射为单独的数字，从而降低复杂度。
- 统计这些字符串中左右括号的数量，再将这些字符串按照左右括号的数量进行分类
- 分类后进行排序，目的是使排序后能够尽可能构成题目要求的序列
- 排序后即为已经符合题目要求的字符串，判断这个字符串是否符合题意用栈模拟即可（我这里是直接实现了一个类似栈的做法）
const int N = 1e6 + 5;
string s;
struct str
{
int l, r;
} a[N], b[N];
bool cmp2(str a,str b)// 使这个序列中不能匹配的‘(’尽可能在前面
{
return a.l>b.l;
}
bool cmp1(str a,str b)// 使这个序列中不能匹配的‘)’尽可能在前面
{
return a.r<b.r;
}
int main()
{
IOS;
int n;
cin >> n;
int at = 0, bt = 0;
for (int i = 0; i < n; i++)
{
cin >> s;
int ln = 0, rn = 0;
for (int j = 0; s[j]; j++)
{
if (s[j] == '(')
ln++;
else if (s[j] == ')'&&ln>0)
ln--;
else
rn++;
}
if (ln >= rn)
a[at++] = (str){ln, rn};
else
b[bt++] = (str){ln, rn};
}
sort(a,a+at,cmp1);
sort(b,b+bt,cmp2);
int suml=0;
for(int i=0;i<at;i++)//判断a+b这个长字符串是否题意，类似栈。
{
if(suml<a[i].r)
{
cout<<"No";
return 0;
}
suml-=a[i].r;
suml+=a[i].l;
}
for(int i=0;i<bt;i++)
{
if(suml<b[i].r)
{
cout<<"No";
return 0;
}
suml-=b[i].r;
suml+=b[i].l;
}
if(suml==0)
cout<<"Yes";
else
cout<<"No";
return 0;
}
查看26道真题和解析
投递华为等公司10个岗位