7.26 Test——DS2

T1:

加帕里的聚会

256MB / 1s ; japari.cpp / c / pas / in / out

【题目描述】

加帕里公园里有n个区域，n-1条道路将它们连接到了一起，形成了一个树的结构。开始时，第i个区域有Ai个friends，但是由于砂之星的作用，有时从x区域到y区域的简单路径上的所有区域的friends数量都会增加v，有时从x区域到y区域的简单路径上所有区域的friends数量都会变成v。

有时，从x区域到y区域的简单路径上所有区域的friends想要聚会，聚会时需要从所有参加聚会的friends中选择一部分作为staff。加帕里的friends都很喜欢质数，因此她们希望staff和非staff的参与者的数量都是质数。

请你告诉她们，每次聚会是否存在一种方案满足她们的要求。

【输入格式】

第一行两个整数n,m，表示friends数量和事件数量。

接下来一行n个数，第i个数表示Ai。

接下来n-1行，每行2个数x,y，表示x和y之间有一条无向道路。

接下来m行，每行第一个整数opt表示事件类型。

若opt=1，接下来三个整数x,y,v，表示从x区域到y区域的简单路径上的所有区域的friends数量都增加v。

若opt=2，接下来三个整数x,y,v，表示从x区域到y区域的简单路径上的所有区域的friends数量都变为v。

若opt=3，接下来两个整数x,y，表示从x区域到y区域的简单路径上的所有区域的friends进行聚会。

【输出格式】

对于每个3事件，若可以让staff和非staff的数量都为质数，输出一行SUGOI，否则输出一行TANOSHI。

【样例数据】

【样例解释】

在第一个样例中，三个区域的friends数量依次为4、2、0，询问的friends和为6，可以分成两组，每组的friends数量都为3。

在第二个样例中，四个区域的friends数量依次为2、5、5、5，第一个询问的friends和为17，无法分成两组。第二个询问的friends和为5，可以分为两组，每组的friends数量分别为2、3。

【数据范围】

对于30%的数据，n,m≤5000。

对于另30%的数据，对于i＞1，第i个区域与第i-1个区域直接相连。

对于100%的数据，1≤n,m≤100000，1≤x,y≤n，一直满足0≤Ai,S≤10000000。在增加事件中v可能为负数。

解析：

　　签到题，标准树剖， 但我写挂了，一看代码，发现我没有统计子树大小，相当于我得到了一个普通的dfs序，这才几个月没打树剖就出错了

　代码：

#include
using namespace std;
typedef long long ll;
const int maxn = 100005, inf = (1<<30);template<class T>
inline void read(T &re)
{T f=1;char c;while((c=getchar())&&(c<'0'||c>'9'))if(c=='-')f=-1;re=c-'0';while((c=getchar())&&c>='0'&&c<='9')re = (re<<3) + (re<<1) + c - '0';re*=f; 
}int n, m, a[maxn], ednum;vector<int> G[maxn];int root, tot;
struct seg_tree{int ls, rs;int sum, cov, add;
}tr[maxn<<2];int dep[maxn], top[maxn], pos[maxn], f[maxn], son[maxn], d[maxn], siz[maxn], cnt;int pri[maxn*10], num;
bool prime[maxn*100];void Euler()
{for(int i = 2; i <= 10000000; ++i){if(!prime[i])pri[++num] = i;for(int j = 1; j <= num; ++j){if(i * pri[j] > 10000000)    break;prime[i * pri[j]] = 1;if(i % pri[j] == 0)    break;}}
}void dfs1(int x)
{siz[x] = 1;for(unsigned int i = 0; i < G[x].size(); ++i){int id = G[x][i];if(id == f[x])    continue;dep[id] = dep[x] + 1;f[id] = x;dfs1(id);if(siz[id] > siz[son[x]])son[x] = id;siz[x] += siz[id];}
}void dfs2(int x)
{pos[x] = ++cnt;d[cnt] = a[x];if(son[f[x]] == x)top[x] = top[f[x]];elsetop[x] = x;if(son[x])dfs2(son[x]);for(unsigned int i = 0; i < G[x].size(); ++i){int id = G[x][i];if(id == f[x] || id == son[x])    continue;dfs2(id);}
}void update(int x)
{int l = tr[x].ls, r = tr[x].rs;tr[x].sum = tr[l].sum + tr[r].sum;
}void build(int &x, int l, int r)
{x = ++tot;tr[x].cov = -inf;if(l == r){tr[x].sum = d[l];return ;}int mid = (l + r)>>1;build(tr[x].ls, l, mid);build(tr[x].rs, mid + 1, r);update(x);
}void spread(int x, int L, int mid, int R)
{int l = tr[x].ls, r = tr[x].rs;if(tr[x].cov != -inf){tr[l].sum = (mid - L + 1) * tr[x].cov;tr[r].sum = (R - mid) * tr[x].cov;tr[l].cov = tr[r].cov = tr[x].cov;tr[l].add = tr[r].add = 0;tr[x].cov = -inf;}if(tr[x].add){tr[l].sum += (mid - L + 1) * tr[x].add;tr[r].sum += (R - mid) * tr[x].add;tr[l].add += tr[x].add;tr[r].add += tr[x].add;tr[x].add = 0;}
}void Add(int x, int l, int r, int L, int R, int v)
{if(l <= L && R <= r){tr[x].sum += v * (R - L + 1);tr[x].add += v;return ;}int mid = (L + R)>>1;spread(x, L, mid, R);if(l <= mid)Add(tr[x].ls, l, r, L, mid, v);if(mid < r)Add(tr[x].rs, l, r, mid + 1, R, v);update(x);
}void Cover(int x, int l, int r, int L, int R, int v)
{if(l <= L && R <= r){tr[x].sum = v * (R - L + 1);tr[x].cov = v;tr[x].add = 0;return ;}int mid = (L + R)>>1;spread(x, L, mid, R);if(l <= mid)Cover(tr[x].ls, l, r, L, mid, v);if(mid < r)Cover(tr[x].rs, l, r, mid + 1, R, v);update(x);
}int Query(int x, int l, int r, int L, int R)
{if(l <= L && R <= r)return tr[x].sum;int mid = (L + R)>>1;spread(x, L, mid, R);int ret = 0;if(l <= mid)ret += Query(tr[x].ls, l, r, L, mid);if(mid < r)ret += Query(tr[x].rs, l, r, mid + 1, R);update(x);return ret;
}void work1(int u, int v, int x)
{while(top[u] != top[v]){if(dep[top[u]] > dep[top[v]]){Add(root, pos[top[u]], pos[u], 1, n, x);u = f[top[u]];}else{Add(root, pos[top[v]], pos[v], 1, n, x);v = f[top[v]];}}if(dep[u] < dep[v])Add(root, pos[u], pos[v], 1, n, x);elseAdd(root, pos[v], pos[u], 1, n, x);
}void work2(int u, int v, int x)
{while(top[u] != top[v]){if(dep[top[u]] > dep[top[v]]){Cover(root, pos[top[u]], pos[u], 1, n, x);u = f[top[u]];}else{Cover(root, pos[top[v]], pos[v], 1, n, x);v = f[top[v]];}}if(dep[u] < dep[v])Cover(root, pos[u], pos[v], 1, n, x);elseCover(root, pos[v], pos[u], 1, n, x);
}int work3(int u, int v)
{int ret = 0;while(top[u] != top[v]){if(dep[top[u]] > dep[top[v]]){ret += Query(root, pos[top[u]], pos[u], 1, n);u = f[top[u]];}else{ret += Query(root, pos[top[v]], pos[v], 1, n);v = f[top[v]];}}if(dep[u] < dep[v])ret += Query(root, pos[u], pos[v], 1, n);elseret += Query(root, pos[v], pos[u], 1, n);return ret;
}bool check(int x)
{if(x <= 3)    return 0;if(!(x&1))    return 1;x -= 2;return !prime[x];
}int main()
{freopen("japari.in", "r", stdin);freopen("japari.out", "w", stdout);Euler();read(n);read(m);for(int i = 1; i <= n; ++i)read(a[i]);for(int i = 1; i < n; ++i){int x, y;read(x);read(y);G[x].push_back(y);G[y].push_back(x);}dfs1(1);//cout<<"hahahahaha"<dfs2(1);build(root, 1, n);for(int i = 1; i <= m; ++i){int opt, u, v;read(opt);read(u);read(v);if(opt == 1){int x;read(x);work1(u, v, x);}else if(opt == 2){int x;read(x);work2(u, v, x);}else{int res = work3(u, v);printf("%s\n", check(res)? "SUGOI": "TANOSHI");}}return 0;
}

T2:

黑白熊的密码

256MB / 1s ; monokuma.cpp / c / pas / in / out

【题目描述】

苗木诚发现了脱出装置，它可以帮助所有人逃脱希望之峰学园。但是要想使用它，必须输入一个十进制的n位数密码（没有前导0）。为了让游戏变得更加有趣，黑白熊提供了m条信息，其中第i条信息指出这个数的第Li位到Ri位和第li位到ri位完全相同。

苗木诚决定随机选择一个满足要求的n位数输入。请你告诉他他碰对密码的概率是多少。

【输入格式】

第一行两个整数n,m，表示数的位数和黑白熊提供的信息数。

接下来m行，每行四个正整数Li,Ri,li,ri。

【输出格式】

输出一行一个整数，表示苗木诚碰对密码的概率，对998244353取模。

【样例数据】

【样例解释】

答案是1/90在模998244353意义下的值。

【数据范围】

对于30%的数据，n,m≤2000。

对于100%的数据，1≤n,m≤100000，1≤Li≤Ri≤n，1≤li≤ri≤n，且保证Ri-Li=ri-li。

解析：

　　原题：Bzoj4569: [Scoi2016]萌萌哒

　　并查集好题， 考试的时候我只写了暴力维护每个点的并查集的算法， 30pts。1e5的数据范围显然需要一个log的优化， 以方便快速地维护并查集，发现在单点维护并查集时，许多点都被访问了多次，这样很不优，于是在并查集中维护连续的点，即一段区间，在最后把标记下放给小一级的区间，最终可以下放到单点， 区间长度与在st表中一样， 都是2^k，这样就做到了O（nlogn）的时间复杂度

　代价：

#include
using namespace std;
typedef long long ll;
const int maxn = 100005;
const ll mod = 998244353;template<class T>
inline void read(T &re)
{T f=1;char c;while((c=getchar())&&(c<'0'||c>'9'))if(c=='-')f=-1;re=c-'0';while((c=getchar())&&c>='0'&&c<='9')re = (re<<3) + (re<<1) + c - '0';re*=f; 
}int n, m, tot, f[maxn*20], res, pw[20], timer, mp[maxn*20], id[20][maxn];
ll ans = 1;ll qpow(ll x, ll y)
{ll ret = 1;while(y){if(y&1)ret = ret * x % mod;x = x * x % mod;y>>=1;}return ret;
}int Find(int x)
{return x == f[x]? x: f[x] = Find(f[x]);
}int main()
{freopen("monokuma.in", "r", stdin);freopen("monokuma.out", "w", stdout);read(n);read(m);pw[0] = 1;for(int i = 1; i <= 18; ++i)pw[i] = pw[i-1] * 2;for(int i = 1; i <= n; ++i)for(int j = 0; j <= 18 && i + pw[j] - 1 <= n; ++j){id[j][i] = ++timer;mp[timer] = i;f[timer] = timer;}for(int i = 1; i <= m; ++i){int l1, r1, l2, r2;read(l1);read(r1);read(l2);read(r2);for(int j = 18; j >= 0; --j)if(l1 + pw[j] - 1 <= r1){f[Find(id[j][l1])] = Find(id[j][l2]);l1 += pw[j];l2 += pw[j];}}for(int j = 18; j; --j)for(int i = 1; i + pw[j] - 1 <= n; ++i){int k = Find(id[j][i]), s = mp[k];f[Find(id[j-1][i])] = Find(id[j-1][s]);f[Find(id[j-1][i+pw[j-1]])] = Find(id[j-1][s+pw[j-1]]);}for(int i = 1; i <= n; ++i)if(Find(id[0][i]) == id[0][i])res++;ans = 1LL * 9;ans = ans * qpow(1LL * 10, 1LL * (res - 1)) % mod;printf("%lld", qpow(ans, mod - 2));return 0;
}

T3：

初音未来的巡游

128MB / 1s ; cruise.cpp / c / pas / in / out

【题目描述】

Miku决定在n个地点中选择一些地点进行巡游。这n个地点由n-1条道路连接，两两之间有且仅有一条路径可以互相到达。Miku希望在这些道路中选择一些放上葱，使得Miku可以选择一种方式只经过有葱的道路而巡游完所有她选择的地点（一条道路可以被多次经过，起点任选）。

Miku想知道她至少需要准备多少葱。由于她的巡游计划可能更改，她希望你能在更改后即时回答她的疑问。

【输入格式】

第一行两个整数n,m，表示地点数和事件数。

第2至n行，每行两个整数x,y，表示地点x和地点y之间有一条无向道路。

接下来一行n个0/1数，若第i个数为1则表示i号地点初始时被选，为0则表示不选。

接下来一行m个整数，依次表示修改事件。第i个数Ai表示Ai号地点的状态发生变化，即若当前被选则改为不选，当前不选则改为被选。

【输出格式】

输出m行，第i行一个整数表示第i次事件后初音最少需要准备多少葱。

【样例数据】

【数据范围】

对于30%的数据，n,m≤3000。对于另30%的数据，开始时所有地点都不选，保证修改操作的地点当前是不选状态。

对于100%的数据，1≤n,m≤200000，1≤x,y,Ai≤n。

解析：

　　 没搞出来， 先CV一波Solution

可以证明答案的两倍为按DFS序排序后相邻两个选择点的距离和加上首尾点的距离，则预处理LCA，使用set维护选择的点，进行修改时根据DFS序的前驱和后继点更新答案即可。

复杂度O(mlogn + nlogn)。

　代码鸽了

转载于:https://www.cnblogs.com/Joker-Yza/p/11253108.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！