要开学了
ABC341
A - Print 341
题意：
输出n个10最后输出1
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cout << "10";
}
cout << 1 << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}
B - Foreign Exchange
思路：
模拟交换
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
vector<int> v(n + 1);
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
int t = v[i + 1] / a;
v[i + 2] += t * b;
}
cout << v[n] << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}
C - Takahashi Gets Lost
思路：
这题范围很小，遍历每个点模拟一下就行，复杂度是O(H * W * N)
#include <bits/stdc++.h>
using namespace std;
#define int long long
char arr[505][505];
bool vis[505][505];
void solve() {
int r, c, n;
cin >> r >> c >> n;
string s;
cin >> s;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> arr[i][j];
}
}
auto check =[&] (int x, int y) {
bool ok = 1;
for (auto c : s) {
// cout << x << " " << y << endl;
int tx, ty;
if(c == 'L') {
tx = x;
ty = y - 1;
}
else if(c == 'R') {
tx = x;
ty = y + 1;
}
else if(c == 'U') {
tx = x - 1;
ty = y;
}
else {
tx = x + 1;
ty = y;
}
// cerr << tx << " " << ty << "**\n";
if(arr[tx][ty] == '.') {
x = tx;
y = ty;
}
else {
ok = 0;
break;
}
}
if(ok) {
vis[x][y] = 1;
}
};
int ans = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if(arr[i][j] == '.') {
check(i, j);
}
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if(arr[i][j] == '.' && vis[i][j]) {
// cout << i << " " << j << endl;
ans++;
}
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}
D - Only one of two
题意：
给n，m，k，求第k个数，这个数的要求是只能被n和m其中的一个整除。
思路：
这个题我没有找到规律，但是给一个数很容易就能确定是第几个数，这个数量是递增的，所以我们可以用二分的方法
在0 - max(n, m) * k中找到。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int x, int y)
{
int c;
while(y)
{
c = x;
x = y;
y = c % y;
}
return x;
}
int lcm(int x, int y)
{
return x * y / gcd(x, y);
}
void solve() {
int n, m, k;
cin >> n >> m >> k;
int _lcm = lcm(n, m);
int l1 = 0, r1 = max(n, m) * k ;
while(l1 < r1) {
int mid = (l1 + r1) >> 1;
int num = mid / n + mid / m - 2 * (mid / _lcm);
if(num < k) {
l1 = mid + 1;
}
else {
r1 = mid;
}
}
if(l1 / n + l1 / m - 2 * (l1 / _lcm) == k) {
cout << l1 << endl;
return ;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}
$num = \frac{n}{a} + \frac{n}{b} - \frac{2n}{lcm} $
这个判断方法我叫他容斥（不知道对不对）
E - Alternating String
题意：
给n长度的字符串，有两种操作
- $1 , l , r$ 将$l$ 到$r$的1变成0，0变成1
- $2 , l , r$ ，查询子串l到r，如果是连续的10或者01就是好串否则就是坏串。
思路：
区间操作和区间查询，很明显的一个线段树题
起初我想用线段树直接模拟，下层向上层传递的要求是左边字符串和右边的字符串都是好串，然后左边的最右边的字符和右边最左边的字符不同。
我折腾了两个多小时，没有A。
我又开始观察这个字符串的特点，如果一段字符串反转了，那么他的好坏性质不会发生改变，改变的只能是最左边和最右边的字符。这个性质类似于差分。
再想想，题目要求的好串是相邻字符不同，这不就是差分每一位都是1？
维护差分的线段树：
- 反转操作只反转 $l$ 和 $r + 1$ ，特殊的，如果 $l$ 是1不反转
- 查询操作查询$l + 1 -> r$ 因为 $l$ 的差分值与前一个有关，只要查询的结果是$r - l$ 就是好串
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
int arr[maxn];
int brr[maxn];
struct Node {
int l, r;
int lazy;
int sum;
}tree[maxn << 2];
void push_up(int u) {
tree[u].sum = (tree[u << 1].sum + tree[u << 1 | 1].sum);
}
void push_down(int u) {
if(tree[u].lazy) {
tree[u << 1].lazy = !tree[u << 1].lazy;
tree[u << 1 | 1].lazy = !tree[u << 1 | 1].lazy;
tree[u << 1].sum = tree[u << 1].r - tree[u << 1].l + 1 - tree[u << 1].sum;
tree[u << 1 | 1].sum = tree[u << 1 | 1].r - tree[u << 1 | 1].l + 1 - tree[u << 1 | 1].sum;
tree[u << 1].lazy = 0;
}
}
void build_tree(int u, int l, int r) {
tree[u].l = l, tree[u].r = r;
if(l == r) {
tree[u].sum = brr[l];
return ;
}
int mid = (l + r) >> 1;
build_tree(u << 1, l, mid);
build_tree(u << 1 | 1, mid + 1, r);
push_up(u);
}
void fz(int u, int l, int r) {
// cerr << u << endl;
if(tree[u].l >= l && tree[u].r <= r) {
tree[u].sum = tree[u].r - tree[u].l + 1 - tree[u].sum;
tree[u].lazy = !tree[u].lazy;
return ;
}
push_down(u);
int mid = (tree[u].l + tree[u].r) >> 1;
if(mid >= l) {
fz(u << 1, l, r);
}
if(mid < r) {
fz(u << 1 | 1, l, r);
}
push_up(u);
}
int query(int u, int l, int r) {
if(tree[u].l >= l && tree[u].r <= r) {
return tree[u].sum;
}
push_down(u);
int mid = (tree[u].l + tree[u].r) >> 1;
int res = 0;
if(mid >= l) {
res += query(u << 1, l, r);
}
if(mid < r) {
res += query(u << 1 | 1, l, r);
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
char c;
cin >> c;
if(c == '1') {
arr[i] = 1;
}
}
brr[1] = 1;
for (int i = 2; i <= n; i++) {
brr[i] = (arr[i] != arr[i - 1]);
}
build_tree(1, 1, n);
// cerr << "OK1\n";
for (int i = 0; i < m; i++) {
int op, l, r;
cin >> op >> l >> r;
if(op == 1) {
if(l != 1) {
fz(1, l, l);
}
if(r != n) {
fz(1, r + 1, r + 1);
}
}
else {
if(l == r) {
cout << "Yes\n";
}
else {
int t = query(1, l + 1, r);
if(t == r - l) {
cout << "Yes\n";
}
else {
cout << "No\n";
}
}
}
}
return 0;
}