长度为 的字符串 描述了 个人的性别,如果第 个字符是 M
则第 个人的性别为 male
,否则如果字符是 F
则性别为 female
。
如果 个人性别是交替的,则输出 Yes
,否则输出 No
。
#include <bits/stdc++.h>
using namespace std;
int N;
string S;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
cin >> S;
bool flag = true;
for (int i = 1; i < S.length(); i++)
if (S[i] == S[i - 1])
flag = false;
if (flag)
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
有一个八行八列的棋盘,行编号为 1,2,3,4,5,6,7,8
,列编号为 a,b,c,d,e,f,g,h
。棋盘的每个格子都由此唯一编号(从下往上数的第三行第四列为 d3
)。
给定一个仅有 .
与 *
构成的八行八列的字符画,保证 *
只有一个。输出这个 *
的位置编号。
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
for (int i = 8; i >= 1; i--)
{
for (int j = 0; j <= 7; j++)
{
char c;
cin >> c;
if (c == '*')
cout << (char)('a' + j) << i << "\n";
}
}
return 0;
}
给定包含 个数的序列 (),求是否存在 使得 。
排序后每个数二分找或者用 set
存出现过的数都可以。
#include <bits/stdc++.h>
using namespace std;
int n, x;
int a[212345];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> x;
if (x < 0)
x = -x;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++)
{
if (binary_search(a + 1, a + i + 1, a[i] - x))
{
cout << "Yes\n";
return 0;
}
}
cout << "No\n";
return 0;
}
set
#include <bits/stdc++.h>
using namespace std;
int n, x;
int a[212345];
set<int> s;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> x;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
s.insert(a[i]);
if (s.find(a[i] + x) != s.end() ||
s.find(a[i] - x) != s.end())
{
cout << "Yes\n";
return 0;
}
}
cout << "No\n";
return 0;
}
给定正整数 与 ,求满足下列条件的最小的 ,如果不存在则输出 :
数据范围:
如果确定了 ,那么显然 ,但是如果这样暴力枚举所有可能的 ,时间复杂度是 的,行不通。
此时可以人为加上限制条件,不妨令 ,这样 的上限就是 了,可以行得通。
#include <bits/stdc++.h>
using namespace std;
long long n, m, ans;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
ans = -1;
for (long long a = 1; a <= n; a++)
{
long long b = (m + a - 1) / a; // ceil(m/a);
if (b <= n)
{
if (ans == -1)
ans = a * b;
else
ans = min(ans, a * b);
}
if (a > b)
break;
}
cout << ans << "\n";
return 0;
}
给定一个包含 个数的序列 ,保证 。
Taka 与 Aoki 两个人要玩 轮游戏,对于第 轮游戏,他们会按照下面的步骤进行:
如果 轮后,写在黑板上的是 ,那么 Taka 就赢了,否则 Aoki 赢了。
如果两个人都足够聪明,请输出 Taka 会赢多少局。
.
如果按 建图。由于 是可以任意给的,所以只有当 处在一个环上时才能保证最终能走到。那么答案就时最终处于环上的点的数量。
注意到这里的图比较特殊,每个点的出度都为 ,所以简单搜一下就好了。
#include <bits/stdc++.h>
using namespace std;
int n, ans;
int a[212345];
int dfn[212345], dfsTot;
void dfs(int x, int st)
{
if (dfn[x] != 0)
{
if (dfn[x] > st)
ans += dfsTot - dfn[x] + 1;
return;
}
if (!dfn[x])
dfn[x] = ++dfsTot;
dfs(a[x], st);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
// i -> a[i]
for (int i = 1; i <= n; i++)
cin >> a[i];
dfsTot = 0;
ans = 0;
for (int i = 1; i <= n; i++)
{
if (!dfn[i])
{
// 从 i 号点开启一轮 (dfsTot, ~) 的 dfs
dfs(i, dfsTot);
}
}
cout << ans << "\n";
return 0;
}
给定两个序列:、。
Taka 被允许进行下面的任意次(包括 次)
选择三个互不相同的 以内的数 。
交换 与 ,并交换 与 。
如果存在一种方法使最终 与 相等,就输出 Yes
,否则输出 No
。
显然必要条件是 与 排序后相同。
那么此时进行一次 的调动后 不变, 与 交换了,显然可以对 进行任意调动,问题总时有解的。
进行一次 的操作后,只看这三个位置的话,实际上达成的效果是:
对于 来说,有一个数对的前后顺序变换了 ,对于 来说,所有三个数对的前后顺序都变换了 、、。
那么假设初始时 、 的逆序对数量奇偶性相同,那么变换后还是相同,否则无论怎么变换,奇偶性都不同。所以逆序对数量的奇偶性相同是必要条件。
那么有了这两个条件后充分吗?其实确实是充分的,两个序列不要求都是从小到大的,只要相对位置正确就好。因此可以考虑按照 从小到大的顺序去调整 。
那么考虑上面的变换,不妨令 ,考虑到相对位置的变换,把变换后的 也调整为有序的话,可以视作是:
也每次操作后为 不变, 进行了一个任意三个数的轮换(注意不是三个数的任意调换位置,而是第一个数变到了第三个数,后两个数往前挪一步)。而如果 的逆序对数量为偶数个,则必然可以通过这样的三个数轮换变为 个(可以思考一下怎么用三轮换来排序)。所以是充分的。
#include <bits/stdc++.h>
using namespace std;
int n;
int a[212345], b[212345];
int t[212345];
int lowbit(int x)
{
return x & -x;
}
void add(int pos)
{
for (int i = pos; i <= n; i += lowbit(i))
t[i]++;
}
int query(int pos)
{
int res = 0;
for (int i = pos; i >= 1; i -= lowbit(i))
res += t[i];
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
long long cntA, cntB;
// 输入 a[] 并计算逆序对
cntA = 0;
for (int i = 1; i <= n; i++)
t[i] = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
add(a[i]);
cntA += i - query(a[i]); // 之前出现的大于 a[i] 的数量
}
// 输入 b[] 并计算逆序对
cntB = 0;
for (int i = 1; i <= n; i++)
t[i] = 0;
for (int i = 1; i <= n; i++)
{
cin >> b[i];
add(b[i]);
cntB += i - query(b[i]); // 之前出现的大于 a[i] 的数量
}
// 排序后检查
bool flag = ((cntA % 2) == (cntB % 2));
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; i++)
if (a[i] != b[i])
{
cout << "No\n";
return 0;
}
for (int i = 2; i <= n; i++)
if (a[i] == a[i - 1])
{
cout << "Yes\n";
return 0;
}
if (flag)
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
给定一个 个点的凸包 逆时针顺序给出每个点:。
次询问,每次询问一个点 ,判断该点在凸包内(IN
)、凸包上(ON
)还是凸包外(OUT
)。
对于每个询问点,画一条线( 或 ),找到这条线与凸包的交点,判断点与线段的关系。这题可以直接从左往右或者从上往下扫完。
钦定一个点,对凸包所有其他点做一条向量,对于每个询问的点,二分判断属于哪个区域,然后再来判断是否在这个区域的三角形内即可。
以后补。