A. Marathon
输入三个数字,判断有几个比第一个数字大
#include <bits/stdc++.h>
using namespace std;
void solve(){
int a, b, cnt = 0;
cin >> a;
for(int i = 0; i < 3; i ++ )
{
cin >> b;
if(b > a) cnt ++ ;
}
cout << cnt << endl;
}
int main()
{
freopen("test.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _t = 1;
cin >> _t;
while(_t -- ){
solve();
}
return 0;
}
B. All Distinct
用set存不同个数,如果要删除的个是偶数,就输出set.size();否则,输出set.size() - 1;
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
set<int> se;
for(int i = 0; i < n; i ++ )
{
int x;
cin >> x;
se.insert(x);
}
int res = se.size();
cout << ((n - res) & 1 ? res - 1 : res) << endl;
}
int main()
{
freopen("test.in", "r", stdin);
int _t;
cin >> _t;
while(_t--)
{
solve();
}
return 0;
}
C. Where's the Bishop?
找主教的位置,题目说出主教的位置不在棋盘边缘故统计每一行#的个数,如果当前行是1,而上下两行是2,就在当前行
遍历一遍寻找y坐标即可
#include<bits/stdc++.h>
using namespace std;
char g[8][8];
void solve()
{
int cnt[8] = {0};
for(int i = 0; i < 8; i ++ )
{
cin >> g[i];
for(int j = 0; j < 8; j ++ )
{
if(g[i][j] == '#')
cnt[i] ++ ;
}
}
for(int i = 0; i < 8; i ++ )
{
if(i == 0 || i == 7) continue;
if(cnt[i] == 1 && cnt[i - 1] == 2 && cnt[i + 1] == 2)
{
for(int j = 0; j < 8; j ++ )
{
if(g[i][j] == '#')
cout << i + 1 << " " << j + 1 << endl;
}
}
}
}
int main()
{
freopen("test.in", "r", stdin);
int _t;
cin >> _t;
while(_t--)
{
solve();
}
return 0;
}
D. The Clock
直接模拟这个过程
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int h, m, t;
scanf("%d:%d %d", &h, &m, &t);
int h1 = h, m1 = m;
int x = t / 60, y = t % 60;
int cnt = 0;
do
{
if(h % 10 == m / 10 && m % 10 == h / 10)
cnt ++ ;
if(m + y >= 60)
{
h = (h + x + 1) % 24;
m = (m + y) % 60;
}
else
{
h = (h + x) % 24;
m = (m + y) % 60;
}
// cout << h << " " << m << endl;
} while (h != h1 || m != m1);
cout << cnt << endl;
}
int main()
{
freopen("test.in", "r", stdin);
int _t;
cin >> _t;
while(_t--)
{
solve();
}
return 0;
}
E. Binary Deque
删去最少的数,使得数组和为k先找到如果左区间定为0,和为k的话,右区间在哪,如果大于数组长度了,说明无解
找到左右区间,进行双指针更新答案
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n, k;
cin >> n >> k;
int a[n];
int sum = 0;
int res = 0;
for (int i = 0; i < n; i++)
cin >> a[i];
int l = 0, r = -1;
for (int i = 0; i < n; i++)
{
sum += a[i];
if (sum == k)
{
r = i;
}
if (sum > k)
break;
}
if (r == -1)
{
cout << -1 << endl;
return;
}
res = max(res, r - l + 1);
while (r >= l && r < n)
{
r++;
sum += a[r];
while (sum > k)
{
sum -= a[l];
l++;
}
res = max(res, r - l + 1);
}
cout << n - res << endl;
}
int main()
{
freopen("test.in", "r", stdin);
int _t;
cin >> _t;
while (_t--)
{
solve();
}
return 0;
}
F. 3SUM
因为题目只在乎模十后的数,我们就只用模十后的数,模十后相同的数我们最多存3个这样数组中最多也就30个数,直接n^3暴力求解
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
vector<int> a;
vector<int> cnt(10, 0);
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
if (cnt[x % 10] < 3)
{
a.push_back(x % 10);
cnt[x % 10] ++ ;
}
}
n = a.size();
for(int i = 0; i < n; i ++ )
for(int j = i + 1; j < n; j ++ )
for(int k = j + 1; k < n; k ++ )
if((a[i] + a[j] + a[k]) % 10 == 3)
{
cout << "YES" << endl;
return;
}
cout << "NO" << endl;
}
int main()
{
freopen("test.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _t = 1;
cin >> _t;
while (_t--)
{
solve();
}
return 0;
}
G. 2^Sort
找到一个长度为k+1的子数组,满足每个元素小于下一个元素的两倍
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n, k;
cin >> n >> k;
vector<int> a(n);
for(int i = 0; i < n; i ++ ) cin >> a[i];
int cur = 1, cnt = 0;
for(int i = 0; i < n - 1; i ++ )
{
if(a[i] < a[i + 1] * 2)
{
cur ++ ;
cnt += (cur >= k + 1);
}
else cur = 1;
}
cout << cnt << endl;
}
int main()
{
freopen("test.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _t = 1;
cin >> _t;
while(_t -- ){
solve();
}
return 0;
}
H. Gambling
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
map<int, vector<int>> mp;
for(int i = 1; i <= n; i ++ )
{
int x;
cin >> x;
mp[x].push_back(i);
}
int l, r, ans, maxv = 0;
for(auto [x, a] : mp)
{
int t = -2e9, pos;
for(int i = 0; i < a.size(); i ++ )
{
if(a[i] - 2 * i > t)
{
t = a[i] - 2 * i;
pos = a[i];
}
int now = 2 * i - a[i] + t + 1;
if(now > maxv)
{
maxv = now;
ans = x;
l = pos;
r = a[i];
}
}
}
cout << ans << " " << l << " " << r << endl;
}
int main()
{
freopen("test.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _t = 1;
cin >> _t;
while(_t -- ){
solve();
}
return 0;
}