A – TLD (abc339 A)
题目大意
给一个网址,问它的后缀是多少。
解题思路
找到最后的’.’的位置,然后输出后面的字符串即可。
python
可以一行。
神奇的代码
print(input().split('.')[-1])
B – Langton’s Takahashi (abc339 B)
题目大意
二维网格,上下左右相连,左上原点。初始全部为白色,位于原点,面朝上。
进行(n)次操作,每次操作,将当前格子颜色黑白反转,然后
- 如果原来是白色,则顺时针旋转(90)度,前进一个格子。
- 如果原来是黑色,则逆时针旋转(90)度,前进一个格子。
解题思路
网格大小只有(100 times 100), (n)为 (1000),每步模拟的复杂度是 (O(1)),因此直接模拟即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int h, w, n;
cin >> h >> w >> n;
vector> tu(h, vector(w));
int x = 0, y = 0, dir = 0;
array dx = {-1, 0, 1, 0};
array dy = {0, 1, 0, -1};
while (n--) {
tu[x][y] ^= 1;
if (tu[x][y] == 0) {
dir = (dir - 1 + 4) % 4;
} else {
dir = (dir + 1 + 4) % 4;
}
x = (x + dx[dir] + h) % h;
y = (y + dy[dir] + w) % w;
}
for (auto& i : tu) {
for (auto& j : i)
cout
C – Perfect Bus (abc339 C)
题目大意
公交车,经过很多公交站,依次给定每个公交站时公交车的变化人数,由于初始时公交车人数不知道,问最后公交车可能人数的最小值。注意途中不能有负数的人。
解题思路
最小化最终的人数相当于最小化最开始的公交车人数。
可以先假设一开始(0)人,然后模拟经过这些公交站的上下人数变化,维护最小值。
如果最小值(min ,说明期间有公交车人数小于 (0),即假定开始人数(0)不合法,太少了,需要更多的人,多多少呢?就是多(-min)人就足够了,这样最小值就是(0),符合题目要求了。
如果(min> 0),说明开始(0)人已经足够了,但又不能更小,因此最后的结果即为答案了。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
LL minn = 0;
LL sum = 0;
while (n--) {
int x;
cin >> x;
sum += x;
minn = min(minn, sum);
}
LL ans = sum - minn;
cout
D – Synchronized Players (abc339 D)
题目大意
二维网格,有障碍物,两个人。
问最小的操作数,使得两人位于同一个格子。
操作为:选定上下左右一个方向,使两人均往同方向移动一格。如果目的地是障碍物或出界,则不动。
解题思路
网格大小只有(60 times 60),两人所处位置的状态数只有 (60^4 = 10^7 ,此即为朴素搜索的复杂度上限,因此直接(BFS)即可。
神奇的代码
#include
using namespace std;
using LL = long long;
const int inf = 1e9 + 7;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector tu(n);
for (auto& i : tu)
cin >> i;
array dx = {0, 0, 1, -1};
array dy = {1, -1, 0, 0};
typedef array s;
queue q;
vector dis(n * n * n * n, inf);
s st;
int cnt = 0;
for (int i = 0; i = 0 && x = 0 && y w + 1) {
dis[v] = w + 1;
q.push({nx1, ny1, nx2, ny2});
}
if (nx1 == nx2 && ny1 == ny2) {
ans = dis[v];
break;
}
}
if (ans != -1)
break;
}
cout
E – Smooth Subsequence (abc339 E)
题目大意
给定一个数组(a)和一个数(D),删去若干个数,使得剩余数俩俩差不超过(D)。
问删去个数的最小值。
解题思路
考虑当前这个数(a_r),如果要保留它,我们则要找到左边也保留的数(a_l),且它们的差值不超过(D),且 ([l+1,…,r-1])都要删去。
发现只用考虑上一个保留数在哪,这是个非常简洁的状态,且具有递归性,所以一个朴素的 (dp[i] = max_{j
朴素转移是(O(n^2)),其中转移复杂度是 (O(n))。
考虑优化转移。
注意到转移条件是一个经典的二维偏序问题,因此用线段树维护转移即可。下标是(a_j),值是(dp[j])。
即当前(dp[j])求出来后,将 (dp[j])插入到线段树里,即将 (a_j)位置的值赋予 (dp[j])。
这样在求(dp[i])时,线段树里的值都是 (j 的 (dp[i])的值,自然满足第一个 (j 的条件,因为线段树的下标是 (a_j),而 (|a_j – a_i| leq D)相当于一个区间 ([a_i – D, a_i + D]),要求的就是这个区间的(dp)最大值,因为线段树维护的就是(dp[j]),故区间查询最大值、单点修改即可。
神奇的代码
#include
using namespace std;
using LL = long long;
const int N = 5e5 + 10;
class segment {
#define lson (root > 1;
build(lson, l, mid);
build(rson, mid + 1, r);
maxx[root] = max(maxx[lson], maxx[rson]);
}
void update(int root, int l, int r, int pos, int val) {
if (l == r) {
maxx[root] = val;
return;
}
int mid = (l + r) >> 1;
if (pos rr)
return 0;
if (ll > 1;
int ans = 0;
if (ll mid)
ans = max(ans, query(rson, mid + 1, r, ll, rr));
return ans;
}
} sg;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, d;
cin >> n >> d;
vector a(n);
for (auto& x : a)
cin >> x;
int maxa = ranges::max(a);
sg.build(1, 1, maxa);
int ans = 0;
for (int i = 0; i
F – Product Equality (abc339 F)
题目大意
给定(n)个数 (a_i),问 ((i,j,k))的数量,使得 (a_i times a_j = a_k)。
注意 (a_i leq 10^{1000})
解题思路
因为(n leq 1000),不考虑(a_i)大小的话,可以先统计(cnt[i])表示值为 (i)的数量,然后 花 (O(n^2))枚举 (i,j),计算 (a_i times a_j),则对应的 (k)的数量即为 (cnt[a_i times a_j])。
而由于 (a_i)很大, (a_i times a_j)的计算比较棘手,就算用 FFT
也有(1000)的常数, (O(n^3))过不了。
怎么办呢?考虑如何避免大数的计算,一个常用的手法就是取模。
如果(a_i times a_j = a_k),那么也有 ((a_i % mo times a_j % mo) % mo = a_k % mo)。
如果我们将模数 (mo=1e9 + 7)之类的数,那么取模后的结果就完全可以进行相乘,然后用上述的 (O(n^2))枚举。
但是有可能原本不同的值取模后变成相同的值,注意相乘的结果个数是 (O(10^6)),模数(O(1e9))的话, 可能会出现的概率有点高,因此可以取两个模数,即双hash
的方式。
这个想法跟(2021ICPC)济南的一题,给了行列式的绝对值,问其符号是正是负的解决方法是一样的,同样数很大不能直接算出,但由于正负的取模结果是不一样的,因此也是取模后计算比较。
神奇的代码
#include
using namespace std;
using LL = long long;
const LL mo1 = 954169327;
const LL mo2 = 906097321;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector a(n);
for (auto& i : a)
cin >> i;
auto mod1 = [&](string s) {
LL ret = 0;
for (auto& i : s) {
ret = ret * 10 + (i - '0');
ret %= mo1;
}
return ret;
};
auto mod2 = [&](string s) {
LL ret = 0;
for (auto& i : s) {
ret = ret * 10 + (i - '0');
ret %= mo2;
}
return ret;
};
vector b1(n), b2(n);
map cnt1;
map cnt2;
for (int i = 0; i
G – Smaller Sum (abc339 G)
题目大意
给定(n)个数 (a_i),回答 (q)个询问。
每次询问给定 (l, r, x),求(sum_{l leq i leq r & a_i leq x} a_i)
强制在线。
解题思路
如果可以离线的话,莫队可以解决。
但这里强制在线,注意到求和式子同样是一个二维偏序问题。
我们可以先把上式拆成两式相减:
]
这个的形式就跟(E)题的转移式一模一样,只是这里是求和,E题的求最大值。
因此可以用线段树求解,下标是(a_i),值也是 (a_i)。
但这里需要保存,维护了([1,l-1])状态的线段树和([1,r])状态的线段树 ,因此需要可持久化线段树,即主席树维护即可。
每次询问就两棵历史版本的线段树的一个区间查询的差就是答案。
时间复杂度是(O(qlog max a_i))
主席树板子是贴的,贴贴快乐
神奇的代码
#include
using namespace std;
using LL = long long;
const int M = 1e6 + 8;
const int ls = 1e9;
namespace tree {
#define mid ((l + r) >> 1)
#define lson l, mid
#define rson mid + 1, r
const int MAGIC = M * 30;
struct P {
LL sum;
int ls, rs;
} tr[MAGIC] = {{0, 0, 0}};
int sz = 1;
int N(LL sum, int ls, int rs) {
if (sz == MAGIC)
assert(0);
tr[sz] = {sum, ls, rs};
return sz++;
}
int ins(int o, int x, LL v, int l = 1, int r = ls) {
if (x r)
return o;
const P& t = tr[o];
if (l == r)
return N(t.sum + v, 0, 0);
return N(t.sum + v, ins(t.ls, x, v, lson), ins(t.rs, x, v, rson));
}
LL query(int o, int ql, int qr, int l = 1, int r = ls) {
if (ql > r || l > qr)
return 0;
const P& t = tr[o];
if (ql > n;
vector a(n);
for (auto& x : a)
cin >> x;
vector root(n);
for (int i = 0; i > q;
LL ans = 0;
while (q--) {
LL l, r, x;
cin >> l >> r >> x;
l ^= ans;
r ^= ans;
x ^= ans;
--l, --r;
ans = tree::query(root[r], 1, x);
if (l)
ans -= tree::query(root[l - 1], 1, x);
cout
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net