B. Pleasant Pairs
链接
我们通过控制i来枚举ai*t-j的方法来确定有多少个满足条件的结果.用一个res来记录最后有多少满足条件的结果就可以了
#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 = 2 * 100005;
int a[N];
signed 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 res = 0;
for (int i = 1; i <= n; i++) {//外层循环先枚举a[i]
for (int j = a[i] - i; j <= n; j = j + a[i]) //直接使用a[i]满足的条件来枚举a[j],例如a[i]-i,a[i]*2-i,这种
if (i < j && a[i] * a[j] == i + j) { //每次向后跳a[i],直接枚举
res++;//如果满足条件就让结果加1
}
}
cout << res << '\n';//打印结果
}
return 0;
}
B1. Palindrome Game (easy version)
链接
B1. Palindrome Game (easy version)
这是一个典型的贪心例题,当0的个数为偶数时因为ALICE先走所以BOB可以控制结果当剩余最后两个0的时候都让ALICE支付变成1,这样bob就赢了
当0的个数为奇数的时候,当n>=3的时候因为ALICE先走ALICE走了最中间的那个之后就相当于时偶数的情况bob先走这样ALICE就可以控制比赛让自己赢,注意一下当0的个数为1的时候特殊判断一下赢的人为bob
#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 = 2 * 100005;
signed main () {
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n;
cin >> s;
int num_1 = 0, num_0 = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '1') {
num_1++;
} else {
num_0++;
}
}//统计0的个数
if (num_0 == 1) { //当0的个数为1的时候特殊判断一下
cout << "BOB" << '\n';
continue;
}
if (num_0 % 2 == 0) {//0的个数为偶数的时候bob赢
// if ((num_0 / 2) % 2 == 0) {
// cout << "DRAW" << '\n';
// } else if ((num_0 / 2) % 2 == 1) {
cout << "BOB" << '\n';
// }
} else { //0的个数为大于1的奇数的时候ALICE赢
cout << "ALICE" << '\n';
}
}
return 0;
}
B. Collecting Packages
链接
这个题是一个模拟的问题我们先根据经过顺序进行排序,然后直接模拟就可以每次模拟的时候判断一下会不会向下和向左走就可以了
#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;
struct data {
int x, y;
};
//第一次写的排序方法有问题
//二元组直接进行排序
bool cmp(struct data a, struct data b) {
//先排横坐标再排纵坐标
if (a.x != b.x) {//如果横坐标不相等,就直接排序
return a.x < b.x;
} else {//如果横坐标相等就按照纵坐标排序
return a.y < b.y;
}
}
struct data a[1005];
signed main () {
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].x >> a[i].y;
}
sort(a, a + n, cmp);
// for (int i = 0; i < n; i++) {
// cout << a[i].x << ' ' << a[i].y << '\n';
//
// }
int flag = 1;
struct data start;
start.x = 0, start.y = 0;
string res;
for (int i = 0; i < n; i++) {
if (start.y > a[i].y || start.x > a[i].x) {//如果当时移动到的`位置是大于该移动的横坐标金和纵坐标的话,就直接失败跳出循环
flag = 0;
break;
}
if (start.x < a[i].x) {//如果当前横坐标小于a[i].x模拟走过去
int cnt = a[i].x - start.x;
while (cnt--) {
res = res + 'R';
}
start.x = a[i].x;
}
if (start.y < a[i].y) {//如果当前横坐标小于a[i].y模拟走过去
int cnt = a[i].y - start.y;
while (cnt--) {
res = res + 'U';
}
start.y = a[i].y;
}
}
if (flag == 0) {//打印结果
no;
} else {
yes;
cout << res << '\n';
}
}
return 0;
}
C. Division by Two and Permutation
链接
将a数组里面的数一直向下取整当元素a[i]一直向下取整的时候.当小于等于n的时候将这个数标记为yes,如果一个数因为前面的数一直都变成true了导致一直除以2变成了0,这样肯定就会出现一个数的空缺,是绝对不可能变成yes的如果没有出现这种情况就直接打印yes
#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;
int st[60];
int a[60] = {false};
signed main () {
//ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);//先排序
memset(st, false, sizeof st);//初始化st数组
int flag = 1;
for (int i = 0; i < n; i++) {
//如果第一次就在n以为的话
if (a[i] <= n && st[a[i] == false]) {
st[a[i]] = true;//将st数组标记为yes
} else {
while (1) {
//如果大于n的话
if (a[i] <= n && st[a[i]] == false) {
st[a[i]] = true;
break;
} else {
a[i] = a[i] / 2;//每次除以2向下取整,如果a[i]小于n就直接标记为ture
}
if (a[i] == 0) {//如果a[i]==0的话肯定是no
flag = 0;
break;
}
}
}
}
//根据flag来打印结果
if (flag == 1) {
yes;
} else {
no;
}
}
return 0;
}