B.Prefix Code(字典树)
题意：给出一系列数字，长度均小于
，问是否有一个数是其他数的前缀？
题解：Trie树模板题。记录单词的终末，前缀包含的单词个数即可。若一个点是单词终末且前缀包含单词个数
，则输出No。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int T[maxn][12];
int num[maxn];
int isend[maxn];
int tot=1;
void init()
{
for(int i=0;i<=tot;i++)
{
memset(T[i],0,sizeof(T[i]));
num[i]=isend[i]=0;
}
tot=1;
}
void add(char * s)
{
int l=strlen(s+1);
int rt=1;
for(int i=1;i<=l;i++)
{
if(T[rt][s[i]-'0']==0)
{
T[rt][s[i]-'0']=++tot;
rt=tot;
}
else
rt=T[rt][s[i]-'0'];
num[rt]++;
}
isend[rt]=1;
}
char s[15];
int main()
{
int t;
int caseN=0;
scanf("%d",&t);
while(t--)
{
init();
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
add(s);
}
int flag=1;
for(int i=1;i<=tot;i++)
{
if(isend[i]&&num[i]>1)
{
flag=0;
break;
}
}
if(flag)printf("Case #%d: Yes\n",++caseN);
else printf("Case #%d: No\n",++caseN);
}
} D.Spanning Tree Removal（构造）
题意：给定一个
阶的完全图，每次操作是从图中移除一棵生成树的所有边，问最多能进行多少次这样的操作？输出操作次数和每次移除的生成树的边。
题解：阶完全图共有%2F2&preview=true)
条边，一棵生成树有
条边，很容易猜到能进行
次操作，接下来就是如何构造的问题。类似于双指针，一个在
，另一个为
，
连接
连接
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
scanf("%d",&t);
int caseN=0;
while(t--)
{
int n;
scanf("%d",&n);
int k=n/2;
printf("Case #%d: %d\n",++caseN,k);
for (int i = 1; i <= k; ++i){
for (int j = i+1; j <= i + k; ++j) printf("%d %d\n",i,j);
for (int j = 1; j <= n-k-1; ++j) printf("%d %d\n",i+k,(i+k+j) % n == 0 ? n : (i + k + j) % n );
}
}
return 0;
} E.Cave Escape（生成树）
题意：给定一个
的格子矩阵，其中有一个格子是起点，一个格子是终点。从起点开始移动，每次能移动到有相邻边的格子中，每个格子都有一个权值
,若从点
移动到点
，且点未被访问过，则可以获得
的收益，若移动到终点，可以选择先不出去，继续在图上乱走，问如何可以使得走出终点后获得得收益最大？(只需要输出最大收益即可)
题解：不管起点在哪里，因为权值都为正数，我们要让收益最大，肯定尽量每个点都访问一遍，然后才是最大的值，所以我们可以直接建图，然后跑一遍生成树(最大),因为要让每个点访问一次。正解的话存图是把权值作为索引，然后从大到小一次枚举；一般的做法可以卡过去。
正解（运行时间： 893 ms 占用内存：186444K）：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int mod = 1e9 + 7;
typedef long long ll;
typedef pair<int, int> pii;
int val[maxn][maxn], fa[maxn * maxn], x[maxn * maxn];
int cnt, n, m;
struct Edge
{
int u, v, w;
bool operator<(const Edge &C) const
{
return w > C.w;
}
} E[2 * maxn * maxn];
int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
ll kruskal()
{
ll ans = 0;
int tot = 0;
for (int i = 0; i < cnt; i++)
{
int u = E[i].u;
int v = E[i].v;
int w = E[i].w;
int a = find(u);
int b = find(v);
if (a != b)
{
fa[b] = a;
ans += w;
tot++;
}
if (tot == n * m - 1)
break;
}
return ans;
}
int main()
{
int t;
int caseN = 0;
scanf("%d", &t);
while (t--)
{
int s, a, b, c, p;
scanf("%d%d%d%d%d%d", &n, &m, &s, &s, &s, &s);
scanf("%d%d%d%d%d%d", &x[1], &x[2], &a, &b, &c, &p);
fa[1] = 1;
fa[2] = 2;
for (int i = 3; i <= n * m; i++)
{
fa[i] = i;
x[i] = (a * x[i - 1] + b * x[i - 2] + c) % p;
}
cnt = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
val[i][j] = x[(i - 1) * m + j];
if (!val[i][j])
continue;
if (i > 1 && val[i - 1][j])
E[cnt++] = Edge{(i - 1) * m + j, (i - 2) * m + j, val[i][j] * val[i - 1][j]};
if (j > 1 && val[i][j - 1])
E[cnt++] = Edge{(i - 1) * m + j, (i - 1) * m + j - 1, val[i][j] * val[i][j - 1]};
}
}
sort(E, E + cnt);
printf("Case #%d: %lld\n", ++caseN, kruskal());
}
return 0;
} 一般做法（运行时间： 1731 ms 占用内存：36156K）：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int mod = 1e9 + 7;
typedef long long ll;
typedef pair<int, int> pii;
int val[maxn][maxn], fa[maxn * maxn], x[maxn * maxn];
vector<pair<int, int>> V[10005];
int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main()
{
int t;
int caseN = 0;
scanf("%d", &t);
while (t--)
{
for (int i = 0; i <= 10000; i++)
V[i].clear();
int n, m, s, a, b, c, p;
scanf("%d%d%d%d%d%d", &n, &m, &s, &s, &s, &s);
scanf("%d%d%d%d%d%d", &x[1], &x[2], &a, &b, &c, &p);
fa[1] = 1;
fa[2] = 2;
for (int i = 3; i <= n * m; i++)
{
fa[i] = i;
x[i] = (a * x[i - 1] + b * x[i - 2] + c) % p;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
val[i][j] = x[(i - 1) * m + j];
if (!val[i][j])
continue;
if (i > 1 && val[i - 1][j])
V[val[i][j] * val[i - 1][j]].push_back(make_pair((i - 1) * m + j, (i - 2) * m + j));
if (j > 1 && val[i][j - 1])
V[val[i][j] * val[i][j - 1]].push_back(make_pair((i - 1) * m + j, (i - 1) * m + j - 1));
}
}
ll res = 0;
int tot = 0;
for (int i = 10000; i >= 0; i--)
{
for (auto j : V[i])
{
int u = j.first;
int v = j.second;
int a = find(u);
int b = find(v);
if (a != b)
{
fa[b] = a;
res += 1ll * i;
tot++;
}
if (tot == n * m - 1)
break;
}
if (tot == n * m - 1)
break;
}
printf("Case #%d: %lld\n", ++caseN, res);
}
return 0;
} F.A Simple Problem On A Tree（树剖）
可以参考这一篇博客地址
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
typedef long long ll;
typedef pair<int, int> pii;
int n, m, a[maxn];
vector<int> g[maxn];
int f[maxn], dep[maxn], son[maxn], sz[maxn];
int top[maxn], id[maxn];
ll w[maxn];
ll mul[maxn << 2], add[maxn << 2];
ll sum1[maxn << 2], sum2[maxn << 2], sum3[maxn << 2];
int dfn;
void init()
{
dfn = 0;
for (int i = 0; i <= n; i++)
{
son[i] = 0;
g[i].clear();
}
}
void dfs1(int u, int fa)
{
f[u] = fa;
dep[u] = dep[fa] + 1;
sz[u] = 1;
for (auto v : g[u])
{
if (v == fa)
continue;
dfs1(v, u);
sz[u] += sz[v];
if (sz[son[u]] < sz[v])
son[u] = v;
}
}
void dfs2(int u, int tp)
{
top[u] = tp;
id[u] = ++dfn;
w[dfn] = a[u];
if (son[u])
dfs2(son[u], tp);
for (auto v : g[u])
{
if (v == f[u] || v == son[u])
continue;
dfs2(v, v);
}
}
void solve(int rt, ll x, ll y, int len)
{
if (x != 1)
{
ll x2 = x * x % mod;
ll x3 = x2 * x % mod;
sum1[rt] = sum1[rt] * x % mod;
sum2[rt] = sum2[rt] * x2 % mod;
sum3[rt] = sum3[rt] * x3 % mod;
mul[rt] = mul[rt] * x % mod;
add[rt] = add[rt] * x % mod;
}
if (y != 0)
{
ll y2 = y * y % mod;
ll y3 = y2 * y % mod;
sum3[rt] = (sum3[rt] + 1ll * len * y3 % mod) % mod;
sum3[rt] = (sum3[rt] + 3ll * y * sum2[rt] % mod) % mod;
sum3[rt] = (sum3[rt] + 3ll * y2 * sum1[rt] % mod) % mod;
sum2[rt] = (sum2[rt] + 1ll * len * y2 % mod) % mod;
sum2[rt] = (sum2[rt] + 2ll * y * sum1[rt] % mod) % mod;
sum1[rt] = (sum1[rt] + 1ll * len * y % mod) % mod;
add[rt] = (add[rt] + y) % mod;
}
}
void pushup(int rt)
{
sum1[rt] = (sum1[rt << 1] + sum1[rt << 1 | 1]) % mod;
sum2[rt] = (sum2[rt << 1] + sum2[rt << 1 | 1]) % mod;
sum3[rt] = (sum3[rt << 1] + sum3[rt << 1 | 1]) % mod;
}
void pushdown(int rt, int len)
{
solve(rt << 1, mul[rt], add[rt], len - (len >> 1));
solve(rt << 1 | 1, mul[rt], add[rt], len >> 1);
mul[rt] = 1;
add[rt] = 0;
}
void build(int l, int r, int rt)
{
mul[rt] = 1;
add[rt] = 0;
if (l == r)
{
sum1[rt] = w[l] % mod;
sum2[rt] = w[l] * w[l] % mod;
sum3[rt] = w[l] * w[l] % mod * w[l] % mod;
return;
}
int mid = l + r >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
pushup(rt);
}
void update(int rt, int L, int R, int l, int r, int x, int y)
{
if (L <= l && r <= R)
{
solve(rt, x, y, r - l + 1);
return;
}
pushdown(rt, r - l + 1);
int mid = l + r >> 1;
if (L <= mid)
update(rt << 1, L, R, l, mid, x, y);
if (mid < R)
update(rt << 1 | 1, L, R, mid + 1, r, x, y);
pushup(rt);
}
ll query(int rt, int l, int r, int L, int R)
{
if (L <= l && r <= R)
return sum3[rt] % mod;
pushdown(rt, r - l + 1);
int mid = l + r >> 1;
ll res = 0;
if (L <= mid)
res = (res + query(rt << 1, l, mid, L, R)) % mod;
if (mid < R)
res = (res + query(rt << 1 | 1, mid + 1, r, L, R)) % mod;
pushup(rt);
return res;
}
void updRange(int u, int v, int x, int y)
{
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]])
swap(u, v);
update(1, id[top[u]], id[u], 1, n, x, y);
u = f[top[u]];
}
if (dep[u] > dep[v])
swap(u, v);
update(1, id[u], id[v], 1, n, x, y);
}
ll qRange(int u, int v)
{
ll res = 0;
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]])
swap(u, v);
res = (res + query(1, 1, n, id[top[u]], id[u])) % mod;
u = f[top[u]];
}
if (dep[u] > dep[v])
swap(u, v);
res = (res + query(1, 1, n, id[u], id[v])) % mod;
return res;
}
int main()
{
int t;
int caseN = 0;
scanf("%d", &t);
while (t--)
{
printf("Case #%d:\n", ++caseN);
scanf("%d", &n);
init();
for (int i = 1; i < n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
dfs1(1, 0);
dfs2(1, 1);
build(1, n, 1);
scanf("%d", &m);
for (int i = 0; i < m; i++)
{
int op, u, v, w;
scanf("%d%d%d", &op, &u, &v);
if (op == 1)
{
scanf("%d", &w);
updRange(u, v, 0, w);
}
else if (op == 2)
{
scanf("%d", &w);
updRange(u, v, 1, w);
}
else if (op == 3)
{
scanf("%d", &w);
updRange(u, v, w, 0);
}
else if (op == 4)
printf("%lld\n", qRange(u, v));
}
}
return 0;
} H.Tree Partition（二分+贪心）
题意：给出一棵点权树，一个树的大小定义为所有点的权值和。问将一棵树切
次分为
棵子树，如何分割才能使所有树的大小的最大值最小，求出最小值？
题解：首先权值最大的块，最小。我们可以想到二分。然后看是否能够满足。我们对于每个点，假设子树都是小于当前二分的值mid，对于当前点，如果把全部子树加上都是合法的，那么肯定直接加上即可。如果全部加上不合法，肯定就需要丢弃一些子树。肯定贪心丢掉最大的子树，直到合法。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
typedef long long ll;
typedef pair<int, int> pii;
struct Edge
{
int v, next;
} E[maxn];
int head[maxn], tot;
int n, k, flag, cnt;
ll w[maxn], sum[maxn];
void addedge(int u, int v)
{
E[tot].v = v;
E[tot].next = head[u];
head[u] = tot++;
}
void init()
{
fill(head, head + n + 1, -1);
fill(sum, sum + n + 1, 0);
tot = 0;
}
void dfs(int u, int fa, ll x)
{
sum[u] = w[u];
if (sum[u] > x || flag == 0)
{
flag = 0;
return;
}
for (int i = head[u]; ~i; i = E[i].next)
{
int v = E[i].v;
if (v == fa)
continue;
dfs(v, u, x);
sum[u] += sum[v];
}
if (sum[u] > x)
{
vector<ll> V;
for (int i = head[u]; ~i; i = E[i].next)
{
int v = E[i].v;
if (v == fa)
continue;
V.push_back(sum[v]);
}
sort(V.begin(), V.end());
while (sum[u] > x)
{
cnt++;
sum[u] -= V.back();
V.pop_back();
}
}
if (cnt > k - 1)
{
flag = 0;
return;
}
}
bool check(ll x)
{
flag = 1;
cnt = 0;
dfs(1, 0, x);
return flag;
}
int main()
{
int t;
int caseN = 0;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &k);
init();
for (int i = 1; i < n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
for (int i = 1; i <= n; i++)
scanf("%lld", &w[i]);
ll l = 0, r = 1e14 + 5ll;
while (l < r)
{
ll mid = (l + r) >> 1ll;
if (check(mid))
r = mid;
else
l = mid + 1;
}
printf("Case #%d: %lld\n", ++caseN, l);
}
return 0;
} K.Color Graph（二分图+枚举）
题意：给定一个简单图，点个数
，删去部分边后，使得该图中无边数为奇数得环，问剩下的边数最大为多少？
题解：如果一个图中无奇数边的环，那么这个图一定是个二分图。只要枚举二分图的左部，统计所有从左部到右部的边个数，答案就是枚举出的所有边数的最大值。(因为最优解一定也是一个二分图，所以一定会被枚举到)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef pair<int,int> edge;
vector<edge>G;
bool flag[20];
int main()
{
int t;
int caseN=0;
scanf("%d",&t);
while(t--)
{
G.clear();
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G.push_back({u,v});
}
int ans=0;
for(int i=0;i<(1<<n);i++)
{
for(int j=1;j<=n;j++)
{
if(i&1<<j-1)
flag[j]=1;
else flag[j]=0;
}
int tmp=0;
for(auto i:G)
if(flag[i.first]^flag[i.second])
tmp++;
ans=max(ans,tmp);
}
printf("Case #%d: %d\n",++caseN,ans);
}
} 
京公网安备 11010502036488号