题解 | #2024牛客寒假算法基础集训营2#
Tokitsukaze and Bracelet
https://ac.nowcoder.com/acm/contest/67742/A
A - Tokitsukaze and Bracelet
思路：
- 简单多次判断问题
以下是代码部分
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, t;
ios::sync_with_stdio(false);
cin>>t;
while(t--){
n = 0;
int a,b,c;
cin>>a>>b>>c;
if(a >= 150)n++;
if(a == 200)n++;
if(b >= 34)n++;
if(b == 45)n++;
if(c >= 34)n++;
if(c == 45)n++;
cout<<n<<'\n';
}
}
B - Tokitsukaze and Cats
思路：
- 简单枚举判断题
以下是代码部分
#include <bits/stdc++.h>
using namespace std;
bool mp[310][310];
int main() {
ios::sync_with_stdio(false);
int n, m, k, sum = 0;
cin >> n >> m >> k;
//输入猫的坐标
for(int i = 1; i <= k; i ++)
{
int x, y;
cin >> x >> y;
mp[x][y] = true;
}
//枚举判断猫旁边是否有猫
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
if(mp[i][j])
{
if(mp[i - 1][j])
sum ++;
if(mp[i + 1][j])
sum ++;
if(mp[i][j - 1])
sum ++;
if(mp[i][j + 1])
sum ++;
mp[i][j] = false;
}
cout << k * 4 - sum << endl;
return 0;
}
D-Tokitsukaze and Slash Draw
思路：
以下是代码部分
E-Tokitsukaze and Eliminate (easy)
思路：
- 从后往前遍历，简单模拟便可
- cnt用来考虑剩余的颜色相同的状况
以下是代码部分
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int main() {
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t --)
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int flag = a[n], ans = 0, cnt = 0;
for(int i = n; i >= 1; i --)
{
//如果不同
if(a[i] != flag)
{
cnt = 0;
ans ++;
flag = a[i - 1];//更新末尾的颜色
}
//如果相同
else
cnt ++;
}
cout << ans + cnt << endl;
}
return 0;
}
F-Tokitsukaze and Eliminate (hard)
思路:
- 找到每个颜色的最大坐标值
- 比较每个颜色的最大坐标值，选出其中最小的，去掉坐标大于等于这个值的。
- 更新，循环往复
以下是代码部分，代码参考来源——出题人题解 Solution1
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
//用来记录每种颜色的坐标
vector<int> pos[N];
int main()
{
ios::sync_with_stdio(false);
int t, n, ans;
cin >> t;
while(t --)
{
cin >> n;
//记得清除pos[i], 避免上一轮的数据干扰
for(int i = 1; i <= n; i ++)
cin >> a[i], pos[i].clear();
//把每组颜色的坐标存储起来
for(int i = 1; i <= n; i ++)
pos[a[i]].push_back(i);
//初始化maxn， maxn代表颜色中最大坐标的最小值
int maxn = n;
//统计需要选择是数量
ans = 0;
//找到所有颜色中最大坐标的最小值，并存储于maxn中
for(int i = 1; i <= n; i ++)
if((int)pos[i].size())
maxn = min(maxn, pos[i].back());
// now用来表示目前的颜色中的最大坐标的最小值
// pre表示上一次的最大坐标的最小值
int now = maxn, pre = n;
while(pre >= 1)
{
ans ++;
maxn = now;
for(int i = pre; i >= now; i --)
{
//把坐标比i大的都砍掉
pos[a[i]].pop_back();
//寻找下一个所有颜色当中最大坐标的最小值
if((int)pos[a[i]].size())
maxn = min(maxn, pos[a[i]].back());
}
//更新pre和now的值
pre = now - 1;
now = maxn;
}
cout << ans << '\n';
}
return 0;
}
I-Tokitsukaze and Short Path (plus)
思路：
- 数学找规律题，比较简单
- 防止TLE，使用前缀和快速查询数组连续段的值
以下是代码部分
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
ll G[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t, n;
cin >> t;
while(t --)
{
ll sum = 0;
cin >> n;
//输入
for(int i = 1; i <= n; i ++) cin >> G[i];
//从小到大排序
sort(G + 1, G + n + 1);
// 前缀和
for(int i = 1; i <= n; i ++)
G[i] += G[i - 1];
//应题目要求，做加法
for(int i = 1; i <= n; i ++)
sum += G[n] - G[i];
//注意倍数关系
cout << sum * 4 << endl;
}
return 0;
}
J-Tokitsukaze and Short Path (minus)
思路：
- 想走最短路径，不同于I题，此题可以绕路，但最多只能多走一个节点
- 当
大于
，就应该绕路了。
以下是代码部分
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
ll G[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t, n;
cin >> t;
while(t --)
{
ll sum = 0;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> G[i];
sort(G + 1, G + n + 1);
for(int i = 2; i < n; i ++)
if(G[i] > 2 * G[1])
G[i] = 2 * G[1];
for(int i = 1; i < n; i ++)
sum += G[i] * 2 * (n - i);
cout << sum * 2 << endl;
}
return 0;
}
K-Tokitsukaze and Password (easy)
思路：
- 暴力枚举
以下是代码部分，代码参考来源——牛客288141082号
#include<bits/stdc++.h>
using namespace std;
string s, temp;
set<int> st;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t, n, y;
cin >> t;
while(t --)
{
st.clear();
cin >> n >> s >> y;
char a, b, c, d, _;
for(a = '0'; a <= '9'; a ++)
for(b = '0'; b <= '9'; b ++)
for(c = '0'; c <= '9'; c ++)
for(d = '0'; d <= '9'; d ++)
for(_ = '0'; _ <= '9'; _ ++)
{
if(a == b || a == c || a == d || b == c || b == d || c == d)
continue;
temp = s;
for(auto &x : temp)
{
if(x == 'a') x = a;
else if(x == 'b') x = b;
else if(x == 'c') x = c;
else if(x == 'd') x = d;
else if(x == '_') x = _;
}
if(n > 1 && temp[0] == '0')
continue;
int out = stoi(temp);
if(out <= y && !(out % 8))
st.insert(out);
}
cout << st.size() << '\n';
}
return 0;
}
投递游卡等公司10个岗位 >