A - Easy $h$-index
后缀扫一下
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 200010 int n;
ll arr[N]; inline int work()
{
ll sum = ;
for (int i = n; i >= ; --i)
{
sum += arr[i];
if (sum >= i) return i;
}
return ;
} int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%lld", arr + i);
printf("%d\n", work());
}
return ;
}
B - Higher $h$-index
题意：有n个小时的工作量，在一篇paper上工作x小时，就能得到$a \cdot x$ 次引用，每增加一篇paper ，前面的paper 引用次数就+1 ，求h-index
思路：给每一篇paper一个小时，那么arr[]相当于 011111111111 一共有 a + n - 1 个1
然后要满足不等式$a + n - 1 - h + 1 >= h$
化简后便是 $h <= \frac{a + n}{2}$
#include <bits/stdc++.h>
using namespace std; #define ll long long ll a, b; int main()
{
while (scanf("%lld%lld", &a, &b) != EOF)
{
printf("%lld\n", (a + b) / );
}
return ;
}
C - Just $h$-index
题意：给n个paper,给出每个paper的引用次数，每次询问给出 l, r 求只有这个区间内的paper有效，有h-index
思路：主席树维护，二分h 复杂度$O(n * log(n)^2)$
#include <bits/stdc++.h>
using namespace std; #define N 100010
#define M N * 30
#define ll long long int n, q, u, v;
int arr[N];
int T[N], L[M], R[M], C[M], tot; inline int build(int l, int r)
{
int root = tot++;
C[root] = ;
if (l < r)
{
int mid = (l + r) >> ;
L[root] = build(l, mid);
R[root] = build(mid + , r);
}
return root;
} inline int update(int root, int pos)
{
int newroot = tot++, tmp = newroot;
C[newroot] = C[root] + ;
int l = , r = n;
while (l < r)
{
int mid = (l + r) >> ;
if (pos <= mid)
{
L[newroot] = tot++, R[newroot] = R[root];
newroot = L[newroot], root = L[root];
r = mid;
}
else
{
L[newroot] = L[root], R[newroot] = tot++;
newroot = R[newroot], root = R[root];
l = mid + ;
}
C[newroot] = C[root] + ;
}
return tmp;
} inline int query(int left_root, int right_root, int pos)
{
int res = ;
int l = , r = n;
while (l < r)
{
int mid = (l + r) >> ;
if (pos <= mid)
{
left_root = L[left_root];
right_root = L[right_root];
r = mid;
}
else
{
res += C[L[left_root]] - C[L[right_root]];
left_root = R[left_root];
right_root = R[right_root];
l = mid + ;
}
}
return res;
} int main()
{
while (scanf("%d%d", &n, &q) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d", arr + i);
tot = ; T[n + ] = build(, n);
for (int i = n; i >= ; --i) T[i] = update(T[i + ], arr[i]);
for (int i = , u, v; i <= q; ++i)
{
scanf("%d%d", &u, &v);
int l = , r = v - u + , ans;
while (r - l >= )
{
int mid = (l + r) >> ;
int tot = v - u + - query(T[u], T[v + ], mid);
if (tot >= mid)
{
ans = mid;
l = mid + ;
}
else
r = mid - ;
}
printf("%d\n", ans);
} }
return ;
}
D - Circular Coloring
留坑。
E - From Tree to Graph
题意：给出一棵树 定义$f_i[u] = 去掉点u后的联通分量个数$ 定义$z_i = f_i(0) \oplus f_i(1) \oplus ... \oplus f_i(n - 1)$
$x_i = (a \cdot x_{i - 1} + b \cdot y_{y - 1} + z_{i - 1}) \pmod n$
$y_i = (b \cdot x_{i - 1} + a \cdot y_{i - 1} + z_{i - 1}) \pmod n$
求 $x_m, y_m$
思路：先求出$z_0$ 刚开始的联通分量个数就是每个点的出入度，然后根据异或性质，异或两次相当于消除，每次假如一条边必定形成一个环，然后并查集缩点
#include <bits/stdc++.h>
using namespace std; #define N 10010 struct Edge
{
int to, nx;
inline Edge() {}
inline Edge(int to, int nx) : to(to), nx(nx) {}
}edge[N << ]; int n, m, a, b, x, y, ans;
int head[N], pos, sz[N];
int rmq[N << ], F[N << ], P[N], fa[N], deep[N], cnt;
int pre[N]; struct ST
{
int mm[N << ];
int dp[N << ][];
inline void init(int n)
{
mm[] = -;
for (int i = ; i <= n; ++i)
{
mm[i] = ((i & (i - )) == ) ? mm[i - ] + : mm[i - ];
dp[i][] = i;
}
for (int j = ; j <= mm[n]; ++j)
{
for (int i = ; i + ( << j) - <= n; ++i)
{
dp[i][j] = rmq[dp[i][j - ]] < rmq[dp[i + ( << (j - ))][j - ]] ? dp[i][j - ] : dp[i + ( << (j - ))][j - ];
}
}
}
inline int query(int a, int b)
{
if (a > b) swap(a, b);
int k = mm[b - a + ];
return rmq[dp[a][k]] <= rmq[dp[b - ( << k) + ][k]] ? dp[a][k] : dp[b - ( << k) + ][k];
}
}st; inline void Init()
{
memset(head, -, sizeof head);
memset(sz, , sizeof sz);
pos = ; cnt = ; ans = ;
for (int i = ; i <= n; ++i) pre[i] = i;
} inline void addedge(int u, int v)
{
edge[++pos] = Edge(v, head[u]); head[u] = pos;
} inline void DFS(int u)
{
F[++cnt] = u;
rmq[cnt] = deep[u];
P[u] = cnt;
for (int it = head[u]; ~it; it = edge[it].nx)
{
int v = edge[it].to;
if (v == fa[u]) continue;
fa[v] = u; deep[v] = deep[u] + ;
DFS(v);
F[++cnt] = u;
rmq[cnt] = deep[u];
}
} inline void init_lca(int root, int node_num)
{
fa[root] = ; deep[] = ;
DFS(root);
st.init( * node_num - );
} inline int query_lca(int u, int v)
{
return F[st.query(P[u], P[v])];
} inline int find(int x)
{
if (pre[x] != x)
pre[x] = find(pre[x]);
return pre[x];
} inline void join(int x, int y)
{
x = find(x);
if (deep[fa[x]] <= deep[y] || fa[x] == ) return;
ans ^= sz[fa[x]] ^ (sz[fa[x]] - );
--sz[fa[x]];
pre[x] = fa[x];
join(fa[x], y);
} inline void Run()
{
while (scanf("%d%d%d%d%d%d", &n, &m, &a, &b, &x, &y) != EOF)
{
Init();
for (int i = , u, v; i < n; ++i)
{
scanf("%d%d", &u, &v); ++u, ++v; ++sz[u], ++sz[v];
addedge(u, v); addedge(v, u);
}
init_lca(, n);
for (int i = ; i <= n; ++i) ans ^= sz[i];
for (int i = ; i <= m; ++i)
{
int nx = (a * x + b * y + ans) % n;
int ny = (b * x + a * y + ans) % n;
x = nx, y = ny;
join(x + , query_lca(x + , y + ));
}
printf("%d %d\n", x, y);
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ;
}
F - Sorting
公式化简，结构体排序
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 1010 struct node
{
int id;
ll a, b, c, sum;
inline void scan(int _id)
{
scanf("%lld%lld%lld", &a, &b, &c);
sum = a + b;
id = _id;
}
inline bool operator < (const node &r) const
{
ll t1 = sum * r.c, t2 = r.sum * c;
return t1 < t2 || t1 == t2 && id < r.id;
}
}arr[N]; int n; int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) arr[i].scan(i);
sort(arr + , arr + + n);
for (int i = ; i <= n; ++i) printf("%d%c", arr[i].id," \n"[i == n]);
}
return ;
}
G - String Transformation
题意：给出一个串a和串b，每次可以在串a中添加 {"aa", "bb", "abab"} 问能否将串a变成串b
思路：显然 两个串的c的数量不同是不可以变的 然后以c为间隔，分成若干个间隔，每个间隔里面的a,b差值不为偶数也是没法变
#include<bits/stdc++.h> using namespace std; const int maxn = 1e4 + ; int a1[maxn], b1[maxn], c1[maxn];
int a2[maxn], b2[maxn], c2[maxn];
char str1[maxn], str2[maxn]; int main()
{
while(~scanf("%s", str1 + ))
{
scanf("%s", str2 + );
int n = strlen(str1 + );
int m = strlen(str2 + );
int cnt1 = ;
for(int i = ; i <= n; ++i)
{
cnt1 += (str1[i] == 'c');
}
int cnt2 = ;
for(int i = ; i <= m; ++i)
{
cnt2 += (str2[i] == 'c');
}
if(cnt1 != cnt2)
{
puts("No");
continue;
}
c1[] = c2[] = ;
cnt1 = cnt2 = ;
for(int i = ; i <= n; ++i)
{
a1[i] = a1[i - ] + (str1[i] == 'a');
b1[i] = b1[i - ] + (str1[i] == 'b');
if(str1[i] == 'c')
{
c1[cnt1++] = i;
}
}
c1[cnt1++] = n;
for(int i = ; i <= m; ++i)
{
a2[i] = a2[i - ] + (str2[i] == 'a');
b2[i] = b2[i - ] + (str2[i] == 'b');
if(str2[i] == 'c')
{
c2[cnt2++] = i;
}
}
c2[cnt2++] = m;
bool flag = true;
for(int i = ; i < cnt1; ++i)
{
if((a1[c1[i]] - a1[c1[i - ]]) % != (a2[c2[i]] - a2[c2[i - ]]) % || (b1[c1[i]] - b1[c1[i - ]]) % != (b2[c2[i]] - b2[c2[i - ]]) % )
{
flag = false;
}
}
puts(flag ? "Yes" : "No");
}
return ;
}
H - Infinity
留坑。
I - Longest Increasing Subsequence
题意：给出n个数，有若干个数是0，定义$F[i]$ 为将所有0变成i后的最长上升子序列长度 求$\sum_{i = 1}^{i = n} i \cdot F[i]$
思路：预处理出$dp[], dp2[]$ $dp[i]$表示以$i$结尾的最长上升子序列长度，$dp2[i]$ 表示以$i$开头的最长上升子序列长度
我们考虑$F[i] = (Minlen, Minlen + 1)$
我们先求出 去掉所有0的最长上升子序列长度 然后考虑 $dp[i] + dp2[j] = m$ 并且 $[i, j]$ 中有0存在 并且 $arr[i] < arr[j]$ 那么
$x \in [arr[i] + 1, arr[j] - 1]$ 的时候 $F[x] = len + 1$
#include <bits/stdc++.h>
using namespace std; #define N 100010
#define INF 0x3f3f3f3f
#define ll long long int n, m;
int dp[N], dp2[N], arr[N], brr[N], a[N]; inline void LIS()
{
int len = ; brr[] = ;
for (int i = ; i <= n; ++i)
{
if (arr[i] == ) continue;
int pos = lower_bound(brr + , brr + + len, arr[i]) - brr;
if (pos > len) ++len;
dp[i] = pos; brr[pos] = arr[i];
}
m = len; len = ; brr[] = ;
for (int i = n; i >= ; --i)
{
if (arr[i] == ) continue;
int pos = lower_bound(brr + , brr + + len, -arr[i]) - brr;
if (pos > len) ++len;
dp2[i] = pos; brr[pos] = -arr[i];
}
} inline void Run()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d", arr + i); LIS();
memset(a, , sizeof a); memset(brr, 0x3f, sizeof brr); brr[] = ;
int now = ;
for (int i = ; i <= n; ++i)
{
if (arr[i] == )
{
for (int j = now + ; j < i; ++j)
{
brr[dp[j]] = min(brr[dp[j]], arr[j]);
}
now = i;
continue;
}
if (now && brr[m - dp2[i]] < arr[i])
{
a[brr[m - dp2[i]] + ]++;
a[arr[i]]--;
}
}
if (now && brr[m] != INF)
{
a[brr[m] + ]++;
}
for (int i = ; i <= n; ++i) a[i] += a[i - ];
ll ans = ;
for (int i = ; i <= n; ++i) ans += (ll)i * (m + (a[i] ? : ));
printf("%lld\n", ans);
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ;
}
J - Vertex Cover
题意：有n个点，标号为0 - n - 1每个点的权值就是$2_i$ i 为标号，alice 任意选择一种边集，bob选择一种权值和最小的边际覆盖它的边集，覆盖的定义为alice中每条边中至少有一个点在bob的边集当中，并且权值和为k
思路：因为权值为2的幂，所以如果bob存在一种选择满足要求，只有一种，那就是k
那么相当于固定bob的选择，找alice有多少种选择被bob覆盖
从左往右扫，如果遇到一个点是0，那么这个点可以和前面的1连一条边
如果遇到一个点是1，那么这个点至少要在前面选择一个没有选的点相连，其他点可连可不连，所有可能性相乘
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define MOD 1000000007
#define N 100010 ll Bit[N]; inline void Init()
{
Bit[] = ;
for (int i = ; i <= ; ++i) Bit[i] = (Bit[i - ] << ) % MOD;
} int n;
char s[N]; int main()
{
Init();
while (scanf("%d", &n) != EOF)
{
scanf("%s", s);
int len = strlen(s);
ll ans = ; int k = n - len, cnt = ;
for (int i = ; i < len; ++i, ++k)
{
if (s[i] == '')
{
ans = (ans *(Bit[k] - Bit[cnt] + MOD) % MOD) % MOD;
++cnt;
}
else
{
ans = (ans * Bit[cnt]) % MOD;
}
}
printf("%lld\n", ans);
}
return ;
}
K - 2018
题意：给出a, b, c, d, 找出有多少个二元组(x, y) 满足 $ x \cdot y \equiv 0 \pmod 2018$
思路：显然，2018只能拆成1009 * 2
那么只要在(a, b) 中有多少1009 倍数 2008倍数 然后计算 注意去重
#include <bits/stdc++.h>
using namespace std; #define ll long long ll x, y;
ll a, b, c, d; int main()
{
while (scanf("%lld%lld%lld%lld", &a, &b, &c, &d) != EOF)
{
ll ans = ; x = (b / ) - ((a - ) / );
y = (d - c + );
ans += x * y; x = (d / ) - ((c - ) / );
y = (b - a + );
ans += x * y; x = (b / ) - ((a - ) / );
y = (d / ) - ((c - ) / );
ans -= x * y; x = (((b / ) + ) / ) - ((((a - ) / ) + ) / );
y = ((d / ) - ((c - ) / )) - ((d / ) - ((c - ) / ));
ans += x * y; x = (((d / ) + ) / ) - ((((c - ) / ) + ) / );
y = ((b / ) - ((a - ) / )) - ((b / ) - ((a - ) / ));
ans += x * y; printf("%lld\n", ans);
}
return ;
}