A - Plural Form
签到题（
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
system("pause");
#endif
}
char s[N];
inline void solve()
{
cin >> s;
int n = strlen(s);
if(s[n-1] == 's')
s[n] = 'e', s[n + 1] = 's';
else
s[n] = 's';
cout << s;
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf("%d", &Test);
while (Test--)
{
solve();
if (Test)
putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
B - Go to Jail
签到题）
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
system("pause");
#endif
}
pair<int, int> p[N];
bool yes[N];
inline void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> p[i].first >> p[i].second;
if (p[i].first == p[i].second)
yes[i] = 1;
}
for (int i = 1; i <= n - 2; ++i)
{
if (yes[i] && yes[i + 1] && yes[i + 2])
return puts("Yes"), void();
}
puts("No");
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf("%d", &Test);
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
C - A x B + C
我写得比较麻烦......
可以把 $C$ 移到右边去，变成 $A\times B = N-C$，然后只需要枚举右边，左边可以用因数个数公式，分解质因数之后求出来即可。
不过好像只需要枚举 $A\times B$ 就行了......
时间复杂度：$\mathcal{O}(N\ln N)$.
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 1000050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
system("pause");
#endif
}
int n;
ll ans;
int vis[N], pri[N], tot;
void shaipri(int lim)
{
for (int i = 2; i <= lim; ++i)
{
if (!vis[i])
vis[i] = i, pri[++tot] = i;
for (int j = 1; j <= tot && i * pri[j] <= lim; ++j)
{
vis[i * pri[j]] = pri[j];
if (i % pri[j] == 0)
break;
}
}
}
inline void solve()
{
cin >> n;
for (int c = 1; c < n; ++c)
{
ll now = n - c;
ll tmp = 1;
while (now > 1)
{
ll cnt = 1;
int nowpri = vis[now];
while (now % nowpri == 0)
now /= nowpri, cnt++;
tmp *= cnt;
}
ans += tmp;
}
cout << ans;
}
int main()
{
TIME__START = clock();
int Test = 1;
shaipri(1000000);
// scanf("%d", &Test);
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
D - Leaping Tak
一个很简单的 $dp$.
直接设 $dp(n)$ 表示走到第 $n$ 个格子的方案数，那么就有
$$
dp(i)=\sum\limits_{j\in S}dp(i-j)
$$
初始条件 $dp(1)=1$。然后这个递推式是一段一段的和，所以可以直接维护一个前缀和即可。
时间复杂度 $\mathcal{O}(nk)$.
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
system("pause");
#endif
}
int n, k;
ll dp[N], sum[N];
int l[N], r[N];
inline void solve()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= k; ++i)
scanf("%d%d", &l[i], &r[i]);
dp[1] = sum[1] = 1;
for (int i = 2; i <= n; ++i)
{
for (int j = 1; j <= k; ++j)
dp[i] += (sum[max(0, i - l[j])] - sum[max(0, i - r[j] - 1)]) % mod, dp[i] %= mod, dp[i] += mod, dp[i] %= mod;
sum[i] = (sum[i - 1] + dp[i]) % mod;
}
cout << dp[n];
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf("%d", &Test);
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
E - Sequence Sum
注意到 $M\le 10^5$，也就是说循环节的大小也不会超过 $M$。
然后这个循环实际上构成了一棵基环树，跑到环上去了就是 $x$ 开始循环了，所以只需要找到循环节，中间一大段可以直接算，边界再单独处理一下即可。
时间复杂度 $\mathcal{O}(M)$.
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
system("pause");
#endif
}
vector<int> r;
ll n;
int x, m;
map<int, int> vis;
inline void solve()
{
scanf("%lld%d%d", &n, &x, &m);
int initx = x;
int tot = 1;
ll ans = 0;
while (tot <= n)
{
ans += x;
vis[x] = tot;
r.push_back(x);
x = 1ll * x * x % m;
tot++;
if (vis.count(x))
break;
}
if (tot == n + 1 || vis.count(0))
return printf("%lld", ans), void();
ll sum = 0;
int sz = r.size();
for (int i = vis[x] - 1; i < sz; ++i)
sum += r[i];
ans = 0;
for (int i = 0; i < vis[x] - 1; ++i)
ans += r[i];
n -= vis[x] - 1;
sz -= vis[x] - 1;
ans += sum * (n / sz);
int re = n % sz;
for (int i = vis[x] - 1; i < re + vis[x] - 1; ++i)
ans += r[i];
cout << ans;
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf("%d", &Test);
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
F - Simplified Reversi
维护两棵线段树，分别是横着的和竖着的，这一列或者这一行最上 / 最左的白棋的位置。每次查询就先查询这个位置，设为 $pos$，那么黑棋总数就减去 $pos-2$。之后再修改，对行操作就对列进行区间修改（注意修改的时候一定要取最小值），对列操作就对行进行区间修改。
这样，模拟一下这个过程，答案就出来了。
时间复杂度 $\mathcal{O}(Q\log N)$.
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
system("pause");
#endif
}
int n;
struct segtree
{
struct T
{
int val;
int lazy;
int l, r;
} t[N << 2];
inline void pushup(int id) { t[id].val = min(t[ls].val, t[rs].val); }
inline void pushdown(int id)
{
if (t[id].lazy)
{
t[ls].val = t[id].lazy, t[rs].val = t[id].lazy;
t[ls].lazy = t[rs].lazy = t[id].lazy;
t[id].lazy = 0;
}
}
void build(int l, int r, int id)
{
t[id].l = l, t[id].r = r;
if (l == r)
return t[id].val = n, void();
int mid = (l + r) >> 1;
build(l, mid, ls), build(mid + 1, r, rs);
pushup(id);
}
void change(int L, int R, int id, int val)
{
int l = t[id].l, r = t[id].r;
if (L <= l && r <= R)
{
if (t[id].val > val)
{
t[id].val = val;
t[id].lazy = val;
}
return;
}
pushdown(id);
int mid = (l + r) >> 1;
if (R <= mid)
change(L, R, ls, val);
else if (L > mid)
change(L, R, rs, val);
else
{
change(L, mid, ls, val);
change(mid + 1, R, rs, val);
}
pushup(id);
}
int query(int pos, int id)
{
int l = t[id].l, r = t[id].r;
if (l == r)
return t[id].val;
pushdown(id);
int mid = (l + r) >> 1;
if (pos <= mid)
return query(pos, ls);
else
return query(pos, rs);
}
} heng, shu;
int Q;
inline void solve()
{
scanf("%d%d", &n, &Q);
heng.build(1, n, 1), shu.build(1, n, 1);
ll sum = (n - 2ll) * (n - 2);
while (Q--)
{
int op, x;
scanf("%d%d", &op, &x);
if (op == 1)
{
int pos = shu.query(x, 1);
sum -= (pos - 2);
heng.change(1, pos, 1, x);
}
else
{
int pos = heng.query(x, 1);
sum -= (pos - 2);
shu.change(1, pos, 1, x);
}
}
printf("%lld\n", sum);
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf("%d", &Test);
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
Comments NOTHING