B. Sort the Array
链接
这个题原本也是不会然后看了别人的题解,以及学长给了一个思路
学长给的思路就是找到最长的可以翻转的区间然后把这个区间翻转过来,然后在判断一遍是不是满足题目要求,满足就打印结果
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
const int N = 100008;
int a[N];
signed main () {
int n;
map<int, int> mp;
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
int flag = 1;
for (int i = 1; i <= n - 1; i++) {
if (a[i] > a[i + 1]) {
flag = 0;
break;
}
}
if (flag == 1) {
cout << "yes" << '\n';
cout << 1 << ' ' << 1 << '\n';
return 0;
}//还是先不进行操作之前进行判断,满足操作打印1 1
int l = -1;
int r = -1;
for (int i = 1; i <= n - 1; i++) {
if (a[i] > a[i + 1]) {
l = i;//找到最左边的点
break;
}
}
for (int i = n; i >= 2; i--) {
if (a[i] < a[i - 1]) {
r = i;//找到最右边的点
break;
}
}
reverse(a + l, a + r + 1);//翻转
flag = 1;
for (int i = 1; i <= n - 1; i++) {
if (a[i] > a[i + 1]) {
flag = 0;
break;
}
}//再次判断
if (flag == 1) {//打印结果
cout << "yes" << '\n';
cout << l << ' ' << r << '\n';
return 0;
} else {
cout << "no" << '\n';
}
// cout<<a[i]<<' ';
//
// }
return 0;
}
官方的题解就是先对数组进行从1到n的一个映射,然后用下标来判断,然后和上面的操作相同,打印结果
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
const int N = 100008;
int a[N], b[N];
signed main () {
int n;
map<int, int> mp;
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &b[i]);
a[i] = b[i];//读入数据并且让a数组和b数组相同
}
sort(b + 1, b + n + 1);//对b数组排序
for (int i = 1; i <= n; i++) {
mp[b[i]] = i;//对b[i]映射到下标
}
for (int i = 1; i <= n; i++) {
a[i] = mp[a[i]];//然后将映射的结果赋值给a,这样a数组就构造好了
}
// for(int i=1;i<=n;i++){
// cout<<a[i]<<' ';
//
// }
int flag = 1;
for (int i = 1; i <= n; i++) {
if (a[i] != i) {
flag = 0;
}
}//先判断一下不用操作是不是可以满足条件
if (flag == 1) {
cout << "yes" << '\n';
cout << 1 << ' ' << 1 << '\n';
return 0;//如果满足打印1 1
}
//否则
int l = -1;
for (int i = 1; i <= n; i++) {
if (a[i] != i) {
l = i;//找到第一个和i不同的数就退出
break;
}
}
int r = -1;
for (int i = n; i >= 1; i--) {
if (a[i] != i) {//倒着寻找最后一个和i不同的数
r = i;
break;
}
}
flag = 1;
reverse(a + l, a + r + 1);//翻转这个区间
for (int i = 1; i <= n; i++) {//判断一下
if (a[i] != i) {
flag = 0;
break;
}
}
if (flag == 1) {//flag=1打印yes和区间信息
cout << "yes" << '\n';
cout << l << ' ' << r << '\n';
} else {
cout << "no" << '\n';
}
return 0;
}
B. Worms
链接
这个题是个很明显的二分查找,需要先对数组进行前缀和处理然后再使用二分查找
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
const int N = 100008;
int a[N], b[N], s[N];
signed main () {
int n, m;
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
s[i] = s[i - 1] + a[i];//前缀和处理
}
scanf("%lld", &m);//m次查找
while (m--) {
int x;
scanf("%lld", &x);
int l = 0, r = n + 1;
while (l + 1 != r) {
int mid = (l + r) / 2;
if (s[mid] < x) {//分界线为小于x
l = mid;
} else {
r = mid;
}
}
//因为要查找x所在的区间的话
cout << r << '\n';//返回r
}
}
C. K-th Not Divisible by n
链接
这个题,用数学知识简单的推导一下
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
const int N = 100008;
void solve() {
int n, k;
cin >> n >> k;
int ans;
if (k % (n - 1) == 0) {//如果k%(n-1)为0的话
ans = (k / (n - 1)) + k;//ans
//(k / (n - 1))为需要补的数字,因为如果按照这种情况加上k % (n - 1) == 0,会多加一个之母
cout << ans - 1 << '\n';//打印ans-1
} else {
ans = (k / (n - 1)) + k;//否则直接打印ans就可以
cout << ans << '\n';
}
}
signed main () {
int t;
cin >> t;
while (t) {
solve();
t--;
}
return 0;
}
B. Polycarp Training
链接
先对数组进行排序然后用ans(初始化为1)变量来从数组第一元素开始判断,判断ans<=a[i]..如果满足条件的话,就让ans++,继续判断最后ans-1(因为ans初始化为1)就是需要打印的值
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
const int N = 200008;
int a[N];
signed main () {
int n;
scanf("%lld", &n);
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
sort(a, a + n);//排序
int ans = 1;//初始化ans为1
for (int i = 0; i < n; i++) {
if (a[i] >= ans) {
ans++;//满足条件ans++
}
}
cout << ans - 1 << '\n';//打印结果
return 0;
}