2016-2017 CT S03E07: Codeforces Trainings Season 3 Episode 7
2024-08-20 12:46:49
A. Yet Another Problem with Strings
题意：
给出$n$个字符串$S_i$，要求支持两种操作：
- 在第$i$个字符串后增加一个字符$c$
- 给出一个字符串$T$，询问是否有一个串$S_i$是$T$的子串。
强制在线，保证$\sum S_i, \sum T \leq 2 \cdot 10^5$
思路：
考虑暴力做法即枚举每个$S_i$然后询问$T$中的每个等长的子串是否等于$S_i$。
但是一个小优化是可以把所有长度相同的$S_i$放在一起做，用std::map记录哈希值。
并且注意到$\sum S_i \leq 2 \cdot 10^5$，所以所有的$S_i$只有$\sqrt{2 \cdot 10^5}$种长度。
暴力即可。
B. Pen Pineapple Apple Pen
Solved.
题意：将一个序列合并成一个数。
思路：分类讨论一下， 水。
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + ; char str[maxn]; bool solve()
{
int len = strlen(str + );
if(len == ) return true;
while(len % == ) len = len >> ;
if(len != ) return false;
len = strlen(str + );
for(int i = ; i <= len; i += ) if(str[i] != 'P' && str[i + ] != 'P') return false;
return true;
} int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%s", str + );
puts(solve() ? "YES" : "NO");
}
return ;
}
C. Stickmen
Solved.
题意：找有几个小人
思路：枚举$i, j$两个点作为中间那条线的端点， 再枚举公共点计算贡献。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1e9 + ;
const int maxn = 1e3; int n, m;
ll fac[maxn];
ll inv[maxn];
ll invfac[maxn];
int du[maxn];
int mp[maxn][maxn]; void Init()
{
fac[] = inv[] = invfac[] = ;
fac[] = inv[] = invfac[] = ;
for(int i = ; i < maxn; ++i)
{
fac[i] = fac[i - ] * i % MOD;
inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
invfac[i] = invfac[i - ] * inv[i] % MOD;
}
} ll C(int n, int m)
{
if(n < || m < ) return ;
if(m > n) return ;
return fac[n] * invfac[m] % MOD * invfac[n - m] % MOD;
} int merge(int x, int y)
{
int res = ;
for(int i = ; i <= n; ++i) if(mp[x][i] == && mp[y][i] == ) res++;
return res;
} int main()
{
Init();
while(~scanf("%d %d", &n, &m))
{
memset(mp, , sizeof mp);
memset(du, , sizeof du);
for(int i = , x, y; i <= m; ++i)
{
scanf("%d %d", &x, &y);
du[x]++, du[y]++;
mp[x][y] = mp[y][x] = ;
}
ll ans = ;
for(int i = ; i <= n; ++i) for(int j = ; j <= n; ++j) if(mp[i][j] && i != j)
{
int x = du[i] - , y = du[j] - ;
int same = merge(i, j);
ans = (ans + C(x, ) * C(y, ) % MOD)% MOD; ans = (ans - C(x - , ) * C(y - , ) % MOD * same % MOD) % MOD;
ans = (ans + C(x - , ) * C(same, ) % MOD) % MOD;
}
printf("%lld\n", ans);
}
return ;
}
D. Strange Queries
Solved.
题意：询问$i \in [L_1, R_1],j \in [L_2, R_2] 有多少对(i, j) 使得 a_i = a_j$
思路：$f[i][j]表示第i个块对前j个块的贡献，f2[i][j]表示a_i对前j个块的贡献$
$整块整块处理，边边角角处理$
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 50010
#define S 150
#define unit 450
int n, a[N], q;
int pos[N], posl[unit], posr[unit];
ll f[unit][unit], f2[N][unit];
int cnt[N]; int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) pos[i] = (i - ) / S + ;
for (int i = ; i <= n; ++i)
{
if (i == || pos[i] != pos[i - ])
posl[pos[i]] = i;
// cout << i << " " << pos[i] << endl;
posr[pos[i]] = i;
// printf("%d %d\n", posl[pos[i]], posr[pos[i]]);
}
// for (int i = 1; i <= n; ++i) cout << i << " " << pos[i] << endl;
// for (int i = 1; i <= n; ++i)
// printf("%d %d\n", posl[pos[i]], posr[pos[i]]);
memset(f, , sizeof f);
memset(f2, , sizeof f2);
memset(cnt, , sizeof cnt);
for (int i = ; i <= n; ++i) scanf("%d", a + i);
for (int i = ; i <= pos[n]; ++i)
{
for (int j = posl[i]; j <= posr[i]; ++j)
++cnt[a[j]];
for (int j = ; j <= n; ++j)
{
f[i][pos[j]] += cnt[a[j]];
f2[j][i] += cnt[a[j]];
}
for (int j = posl[i]; j <= posr[i]; ++j)
--cnt[a[j]];
}
for (int i = ; i <= pos[n]; ++i)
for (int j = ; j <= pos[n]; ++j)
f[i][j] += f[i][j - ];
for (int i = ; i <= n; ++i)
for (int j = ; j <= pos[n]; ++j)
f2[i][j] += f2[i][j - ];
scanf("%d", &q);
int l[], r[];
while (q--)
{
for (int i = ; i < ; ++i)
scanf("%d%d", l + i, r + i);
if (pos[l[]] == pos[r[]])
{
swap(l[], l[]);
swap(r[], r[]);
}
ll res = ;
if (pos[l[]] == pos[r[]])
{
if (pos[l[]] == pos[r[]])
{
for (int i = l[]; i <= r[]; ++i)
++cnt[a[i]];
for (int i = l[]; i <= r[]; ++i)
res += cnt[a[i]];
for (int i = l[]; i <= r[]; ++i)
--cnt[a[i]];
}
else
{
int L = pos[l[]] + ;
int R = pos[r[]] - ;
for (int i = l[]; i <= r[]; ++i)
{
res += f2[i][R] - f2[i][L - ];
++cnt[a[i]];
}
for (int i = l[]; i <= posr[pos[l[]]]; ++i)
res += cnt[a[i]];
for (int i = posl[pos[r[]]]; i <= r[]; ++i)
res += cnt[a[i]];
for (int i = l[]; i <= r[]; ++i)
--cnt[a[i]];
}
}
else
{
int L[] = {pos[l[]] + , pos[l[]] + };
int R[] = {pos[r[]] - , pos[r[]] - };
for (int i = L[]; i <= R[]; ++i)
res += f[i][R[]] - f[i][L[] - ];
for (int i = l[]; i <= posr[pos[l[]]]; ++i)
{
res += f2[i][R[]] - f2[i][L[] - ];
++cnt[a[i]];
}
for (int i = posl[pos[r[]]]; i <= r[]; ++i)
{
res += f2[i][R[]] - f2[i][L[] - ];
++cnt[a[i]];
}
for (int i = l[]; i <= posr[pos[l[]]]; ++i)
{
res += f2[i][R[]] - f2[i][L[] - ];
res += cnt[a[i]];
}
for (int i = posl[pos[r[]]]; i <= r[]; ++i)
{
res += f2[i][R[]] - f2[i][L[] - ];
res += cnt[a[i]];
}
for (int i = l[]; i <= posr[pos[l[]]]; ++i)
--cnt[a[i]];
for (int i = posl[pos[r[]]]; i <= r[]; ++i)
--cnt[a[i]];
}
printf("%lld\n", res);
}
}
return ;
}
E. Bravebeart
Solved.
题意：给出n个人和n匹马， 每个人和每匹马都有自己的能力值， 每个人选择一匹马， 那么每个人的权值就是个人能力值乘上马的权值， 求是否存在一种方案， 使得第一个人的权值最大。
思路：排序， 水
#include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + ; int n;
int w[maxn], h[maxn]; bool solve(int tmp)
{
for(int i = n - ; i >= ; --i)
{
if(w[i] * h[n - - i + ] >= tmp) return false;
}
return true;
} int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(int i = ; i <= n; ++i) scanf("%d", w + i);
for(int i = ; i <= n; ++i) scanf("%d", h + i);
int tmp = w[];
w[] = INF;
sort(w + , w + + n);
sort(h + , h + + n);
tmp *= h[n];
puts(solve(tmp) ? "YES" : "NO");
}
return ;
}
F. GukiZ Height
Solved.
题意：$f_i = f_{i - 1} + a_{(i - 1) \% n +1}, g_i = h - \frac{i \cdot (i + 1)}{2}, 求最小的i 使得 f_i >= g_i$
思路：枚举每个余数， 那么分为周期为0和周期>=1， 对于后面一种情况， 二分周期。
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 100010
int n;
ll h, a[N];
ll sum[N]; bool check(ll x, int remind)
{
ll day = x * n + remind;
return h - (day * (day + )) / <= sum[n] * x + sum[remind];
} int main()
{
while (scanf("%d%lld", &n, &h) != EOF)
{
sum[] = ;
for (int i = ; i <= n; ++i) scanf("%lld", a + i);
for (int i = ; i <= n; ++i) sum[i] = sum[i - ] + a[i];
ll ans = (ll)1e18;
for (int i = ; i <= n; ++i) if(sum[i] >= h - (i * (i + ) / )) ans = min(ans, 1ll * i);
for (int i = ; i <= n; ++i)
{
ll l = , r = (2e9 + ) / n, res = -;
while (r - l >= )
{
ll mid = (l + r) >> ;
// cout << i << " " << mid << endl;
if (check(mid, i))
{
r = mid - ;
res = mid;
}
else
l = mid + ;
}
// cout << i << " " << res << endl;
if (res != -)
ans = min(ans, res * n + i);
}
printf("%lld\n", ans);
}
return ;
}
I. Prime Moving
Solved.
题意：将素数$a$通过某系列变化得到素数$b$, 每次变化可以加上或减去一个素数， 同时结果要求是素数。
思路：将2作为中间点， 各种分类
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int S = ; ll mult_mod(ll a, ll b, ll c)
{
a %= c;
b %= c;
ll ret = ;
ll tmp = a;
while(b)
{
if(b & )
{
ret += tmp;
if(ret > c) ret -= c;
}
tmp <<= ;
if(tmp > c) tmp -= c;
b >>= ;
}
return ret;
} ll pow_mod(ll a, ll n, ll mod)
{
ll ret = ;
ll tmp = a % mod;
while(n)
{
if(n & ) ret = mult_mod(ret, tmp, mod);
tmp = mult_mod(tmp, tmp, mod);
n >>= ;
}
return ret;
} bool check(ll a, ll n, ll x, ll t)
{
ll ret = pow_mod(a, x, n);
ll last = ret;
for(int i = ; i <= t; ++i)
{
ret = mult_mod(ret, ret, n);
if(ret == && last != && last != n - ) return true;
last = ret;
}
if(ret != ) return true;
else return false;
} bool is_Prime(ll n)
{
if(n < ) return false;
if(n == ) return true;
if((n & ) == ) return false;
ll x = n - ;
ll t = ;
while((x & ) == ) { x >>= ; ++t; }
srand(time(NULL));
for(int i = ; i < S; ++i)
{
ll a = rand() % (n - ) + ;
if(check(a, n, x, t)) return false;
}
return true;
} ll a, b; void solve()
{
if(a == )
{
if(is_Prime(b - ))
{
printf("%lld->%lld\n", a, b);
return ;
}
if(is_Prime(b + ))
{
printf("%lld->%lld->%lld\n", a, b + , b);
return ;
}
}
else
{
if(b == a + )
{
printf("%lld->%lld\n", a, b);
return ;
}
if(b == a + && is_Prime(a + ))
{
if(is_Prime(a - ) && is_Prime(b - ))
{
puts("Poor Benny");
return ;
}
else
{
printf("%lld->%lld->%lld\n", a, a + , b);
return ;
}
}
if(is_Prime(a - ))
{
if(is_Prime(b - ))
{
printf("%lld->%lld->%lld\n", a, 2ll, b);
return ;
}
if(is_Prime(b + ))
{
if(is_Prime(a + ) && is_Prime(b - ))
{
puts("Poor Benny");
return ;
}
else
{
printf("%lld->%lld->%lld->%lld\n", a, 2ll, b + , b);
return ;
}
}
}
if(is_Prime(a + ))
{
if(is_Prime(b - ))
{
printf("%lld->%lld->%lld->%lld\n", a, a + , 2ll, b);
return ;
}
if(is_Prime(b + ))
{
printf("%lld->%lld->%lld->%lld->%lld\n", a, a + , 2ll, b + , b);
return ;
}
}
}
puts("Unlucky Benny");
} int main()
{
while(~scanf("%lld %lld", &a, &b))
{
solve();
}
return ;
}
J. Valentina and the Gift Tree
Upsolved
题意：给出一棵树，询问$a -> b的简单路径上组成的序列的最大子段和$
思路：把一条简单路径拆成两条链，单独处理，一条链上用树链剖分处理，合并的时候注意左右端点怎么接
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 100010
#define D 20
#define INF 0x3f3f3f3f3f3f3f3f
int n, q, g[N];
vector <int> G[N]; int sze[N], top[N], fa[D][N], son[N], p[N], fp[N], deep[N], cnt;
void DFS(int u)
{
sze[u] = ;
for (int i = ; i < D; ++i)
fa[i][u] = fa[i - ][fa[i - ][u]];
for (auto v : G[u]) if (v != fa[][u])
{
fa[][v] = u;
deep[v] = deep[u] + ;
DFS(v);
sze[u] += sze[v];
if (!son[u] || sze[v] > sze[son[u]]) son[u] = v;
}
} void gettop(int u, int sp)
{
top[u] = sp;
p[u] = ++cnt;
fp[cnt] = u;
if (!son[u]) return;
gettop(son[u], sp);
for (auto v : G[u]) if (v != fa[][u] && v != son[u])
gettop(v, v);
} namespace SEG
{
struct node
{
ll lmax, rmax, Max, sum;
node () {}
void init()
{
lmax = rmax = Max = sum = -INF;
}
node operator + (const node &other) const
{
node res; res.init();
if (lmax == -INF || rmax == -INF)
return other;
if (other.lmax == -INF || other.rmax == -INF)
return *this;
res.sum = sum + other.sum;
res.lmax = max(lmax, sum + other.lmax);
res.rmax = max(other.rmax, other.sum + rmax);
res.Max = max(Max, other.Max);
res.Max = max(res.Max, rmax + other.lmax);
return res;
}
}a[N << ], ans[], tmp;
void build(int id, int l, int r)
{
a[id].init();
if (l == r)
{
a[id].lmax = a[id].rmax = a[id].sum = a[id].Max = g[fp[l]];
return;
}
int mid = (l + r) >> ;
build(id << , l, mid);
build(id << | , mid + , r);
a[id] = a[id << ] + a[id << | ];
}
void query(int id, int l, int r, int ql, int qr)
{
if (qr < ql || ql <= || qr <= ) return;
if (l >= ql && r <= qr)
{
tmp = tmp + a[id];
return;
}
int mid = (l + r) >> ;
if (ql <= mid) query(id << , l, mid, ql, qr);
if (qr > mid) query(id << | , mid + , r, ql, qr);
}
} int lca(int u, int v)
{
while (top[u] != top[v])
{
if (deep[top[u]] < deep[top[v]]) swap(u, v);
u = fa[][top[u]];
}
if (deep[u] > deep[v]) swap(u, v);
return u;
} int kth(int u, int k)
{
for (int i = ; i < D; ++i)
if ((k >> i) & )
u = fa[i][u];
return u;
} void query(int u, int v, int vis)
{
SEG::ans[vis].init();
while (top[u] != top[v])
{
if (deep[top[u]] < deep[top[v]]) swap(u, v);
SEG::tmp.init();
SEG::query(, , n, p[top[u]], p[u]);
SEG::ans[vis] = SEG::tmp + SEG::ans[vis];
u = fa[][top[u]];
}
if (deep[u] > deep[v]) swap(u, v);
SEG::tmp.init();
SEG::query(, , n, p[u], p[v]);
SEG::ans[vis] = SEG::tmp + SEG::ans[vis];
} int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) G[i].clear();
memset(son, , sizeof son); cnt = ; deep[] = ;
for (int i = , u, v; i < n; ++i)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = ; i <= n; ++i) scanf("%d", g + i);
deep[] = ; fa[][] = ;
DFS(); gettop(, ); SEG::build(, , n);
//if (n == 10) return 0;
scanf("%d", &q);
int a, b;
while (q--)
{
scanf("%d%d", &a, &b);
if (deep[a] > deep[b]) swap(a, b);
int Lca = lca(a, b);
if (a == Lca)
query(a, b, );
else
{
query(Lca, a, );
query(kth(b, deep[b] - deep[Lca] - ), b, );
swap(SEG::ans[].lmax, SEG::ans[].rmax);
SEG::ans[] = SEG::ans[] + SEG::ans[];
}
printf("%lld\n", SEG::ans[].Max);
}
}
return ;
}
LCA
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1e9 + ;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5 + ; const int DEG = ; struct Edge {
int to, nxt;
Edge() {}
Edge(int to, int nxt) :to(to), nxt(nxt) {}
}edge[maxn << ]; struct node {
ll lmax, rmax, ans, sum;
node()
{
sum = ;
lmax = rmax = ans = -INFLL;
}
node(ll tmp)
{
lmax = rmax = ans = sum = tmp;
}
node operator + (const node &other) const
{
node res;
res.sum = sum + other.sum;
res.lmax = max(lmax, sum + other.lmax);
res.rmax = max(other.rmax, other.sum + rmax);
res.ans = max(max(ans, other.ans), rmax + other.lmax);
return res;
}
}; int n, m;
ll arr[maxn];
int head[maxn], tot;
node res[maxn][DEG];
int fa[maxn][DEG];
int deg[maxn]; void Init()
{
tot = ;
memset(fa, -, sizeof fa);
memset(head, -, sizeof head);
} void addedge(int u, int v)
{
edge[tot] = Edge(v, head[u]); head[u] = tot++;
edge[tot] = Edge(u, head[v]); head[v] = tot++; } void BFS(int root)
{
queue<int>q;
deg[root] = ;
res[root][] = node(arr[root]);
fa[root][] = root;
q.push(root);
while (!q.empty())
{
int tmp = q.front();
q.pop();
for (int i = ; i < DEG; ++i)
{
fa[tmp][i] = fa[fa[tmp][i - ]][i - ];
res[tmp][i] = res[tmp][i - ] + res[fa[tmp][i - ]][i - ];
}
for (int i = head[tmp]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
if (v == fa[tmp][]) continue;
deg[v] = deg[tmp] + ;
fa[v][] = tmp;
res[v][] = node(arr[v]);
q.push(v);
}
}
} node LCA(int u, int v)
{
if (deg[u] > deg[v]) swap(u, v);
int hu = deg[u], hv = deg[v];
int tu = u, tv = v;
node ansu, ansv;
for (int det = hv - hu, i = ; det; det >>= , ++i)
{
if (det & )
{
ansv = ansv + res[tv][i];
tv = fa[tv][i];
}
}
for (int i = DEG - ; i >= ; --i)
{
if (fa[tu][i] == fa[tv][i]) continue;
ansu = ansu + res[tu][i];
ansv = ansv + res[tv][i];
tu = fa[tu][i];
tv = fa[tv][i];
}
while (tu != tv)
{
ansu = ansu + res[tu][];
ansv = ansv + res[tv][];
tu = fa[tu][];
tv = fa[tv][];
}
swap(ansv.lmax, ansv.rmax);
return ansu + res[tu][] + ansv;
} void RUN()
{
while (~scanf("%d", &n))
{
Init();
for (int i = , u, v; i < n; ++i)
{
scanf("%d %d", &u, &v);
addedge(u, v);
}
for (int i = ; i <= n; ++i) scanf("%lld", arr + i);
BFS();
int q;
scanf("%d", &q);
for (int qq = , u, v; qq <= q; ++qq)
{
scanf("%d %d", &u, &v);
printf("%lld\n", LCA(u, v).ans);
}
}
} int main()
{
#ifdef LOCAL_JUDGE
freopen("Text.txt", "r", stdin);
#endif // LOCAL_JUDGE RUN(); #ifdef LOCAL_JUDGE
fclose(stdin);
#endif // LOCAL_JUDGE
return ;
}
最新文章
- iOS dealloc 不被调用的问题
- 解决hibernate删除时的异常
- DELL服务器系统安装
- VpnService
- Android ActionBar的Overlay模式如何不遮盖顶部内容的问题
- Redis指令文档
- shell抓取
- 图片以BLOB存储在后台数据库中,Android客户端要进行读取显示
- poj 3348 Cows 求凸包面积
- 一些Wifi破解姿势
- Delphi调用Android的.so文件（转）
- 重写equals和hashCode
- 微信小程序教学第二章（含视频）：小程序中级实战教程之预备篇 - 封装网络请求及 mock 数据
- if；脚本中退出语句：exit 数字，用$?查时为exit设置的数字，此数字为程序执行完后的返回数据，可以通过此方法自动设定
- C#之Winform跨线程访问控件
- DX11 Without DirectX SDK--06 DirectXMath数学库
- 活代码LINQ——06
- Code First下迁移数据库更改
- JQ JS复制到剪贴板
- Java代码中获取Json的key值