2023年9月30日
Acwing5266 队列
题目大意
问你，n加在三个数上，看最后三个数能不能相等。
题目理解
先把三个数都变成最大的，然后最后的n如果是3的倍数且大于等于0即可
代码实现
void solve()
{
ll n, a, b, c;
cin >> a >> b >> c >> n;
ll k = max(a, max(b, c));
if(k > a) n -= (k - a);
if(k > b) n -= (k - b);
if(k > c) n -= (k - c);
if(n % 3 == 0 && n >= 0) cout << "YES" << endl;
else cout << "NO" << endl;
return;
}
Acwing5267 合格数
题目理解
- 先用差分，把所有的
l和r区间都加一遍 - 然后前缀和差分数组，就可以得到所有的值出现的次数
- 如果出现的次数大于
k，那就标记上，存在一个数组里记为1 - 然后对新数组前缀和，处理询问即可
代码实现
const int N = 2e5 + 10;
int a[N];
int b[N];
void solve()
{
int n, k, q;
cin >> n >> k >> q;
for(int i = 1; i <= n; i++)
{
int l, r;
cin >> l >> r;
a[l]++;
a[r + 1]--;
}
for(int i = 1; i <= N - 5; i++)
{
a[i] += a[i - 1];
if(a[i] >= k) b[i] = 1;
}
for(int i = 1; i <= N - 5; i++)b[i] += b[i - 1];
for(int i = 1; i <= q; i++)
{
int l, r;
cin >> l >> r;
cout << b[r] - b[l - 1] << endl;
}
return;
}
Div.3 Round888 A Escalator Conversations
题目大意
有m个台阶每个台阶的高度是i * k，然后一个主角的身高是h，还有另外n个人，然后他们站在不同的台阶，问身高可以相同的有多少个人
题目理解
- 枚举主角在的每一个台阶
- 枚举每一个台阶的时候，其他
n个人是否可以站在其他的台阶上，与主角当前的身高相同，如过相同，标记这个人 - 最后求和即可
代码实现
const int N = 110;
bool st[N];
void solve()
{
int n, m, k, h;
int res = 0;
cin >> n >> m >> k >> h;
int a[N];
for (int i = 1; i <= n; i++)
cin >> a[i];
memset(st, 0, sizeof st);
for(int i = 1; i <= m; i++)
{
int p = h + i * k;
for(int j = 1; j <= n; j++)
{
for(int q = 1; q <= m; q++)
{
if(a[j] + q * k == p && q != i) st[j] = true;
}
}
}
for(int i = 1; i <= n; i++) if(st[i]) res++;
cout << res << endl;
return;
}
Div.3 Round888 Parity Sort
题目大意
只可以偶数和偶数交换，奇数和奇数交换，问可否把序列变为升序。
题目理解
- 对于偶数排序
- 对于奇数排序
- 然后原来的序列，是奇数就放奇数，是偶数就放偶数
- 最后看序列是不是升序即可
代码实现
const int N = 2e5 + 10;
int a[N];
void solve()
{
int n;
cin >> n;
vector<int> p,q;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
if(a[i] % 2) p.push_back(a[i]);
else q.push_back(a[i]);
}
sort(p.begin(), p.end());
sort(q.begin(), q.end());
for(int i = 1, j = 0, k = 0; i <= n; i++)
{
if(a[i] % 2) a[i] = p[j++];
else a[i] = q[k++];
}
bool flag = true;
for(int i = 2; i <= n; i++)
if(a[i] < a[i - 1])
{
flag = false;
break;
}
if(flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
Atocder ABC322 A FirstABC2
题目大意
第一个ABC串的下标是多少？
题目理解
枚举即可，没有-1
代码实现
void solve()
{
int n;
string s;
cin >> n;
cin >> s;
int flag = -1;
for(int i = 0; i <= n - 3; i++)
if(s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C')
{
flag = i + 1;
break;
}
cout << flag;
return;
}
Atcoder ABC322 B Prefix and Suffix
题目大意
问m是n的前缀还是后缀？前缀1后缀2都是0，都不是3
题目理解
直接写个check判断前后缀即可
代码实现
void solve()
{
cin >> n >> m;
string s1, s2;
cin >> s1 >> s2;
if(check_f(s1, s2) && check_b(s1, s2)) cout << 0;
else if(check_f(s1, s2)) cout << 1;
else if(check_b(s1, s2)) cout << 2;
else cout << 3;
return;
}
Atocder ABC322 C Festival
题目大意
有n天，放m天烟花，并且告诉你第几天放，问第i天距离下一次放烟花还要多久
题目理解
用队列存一下，然后每次减就行，相同就pop
代码实现
void solve()
{
int n, m;
cin >> n >> m;
queue<int> q;
for(int i = 1; i <= m; i++)
{
int b;
cin >> b;
q.push(b);
}
for(int i = 1; i <= n; i++)
{
cout << q.front() - i << endl;
if(q.front() == i) q.pop();
}
return;
}