7.26 Test——DS2

小咪咪 2021-10-30 06:24 146阅读 0赞

**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。

**【样例数据】**

<table> 
 <tbody> 
 <tr> 
 <td> japari1.in </td> 
 <td> japari1.out </td> 
 </tr> 
 <tr> 
 <td> 3 4 1 2 1 2 1 3 2 2 2 1 4 1 3 3 -1 2 2 2 2 3 1 3 </td> 
 <td> SUGOI </td> 
 </tr> 
 <tr> 
 <td> japari2.in </td> 
 <td> japari2.out </td> 
 </tr> 
 <tr> 
 <td> 4 6 2 4 0 0 2 1 3 2 4 3 2 1 4 2 1 4 4 9 1 3 2 -2 2 4 2 5 3 1 4 3 4 4 </td> 
 <td> TANOSHI SUGOI </td> 
 </tr> 
 </tbody> 
</table>

**【样例解释】**

在第一个样例中，三个区域的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序，这才几个月没打树剖就出错了

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
 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]];
 else
 top[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);
 else
 Add(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);
 else
 Cover(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);
 else
 ret += 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"<<endl;
 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;
 }

japari

**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取模。

**【样例数据】**

<table> 
 <tbody> 
 <tr> 
 <td> monokuma.in </td> 
 <td> monokuma.out </td> 
 </tr> 
 <tr> 
 <td> 4 2 1 2 3 4 3 3 3 3 </td> 
 <td> 144190851 </td> 
 </tr> 
 </tbody> 
</table>

**【样例解释】**

答案是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\]萌萌哒][Bzoj4569_ _Scoi2016]

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

代价：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
 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;
 }

monokuma

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次事件后初音最少需要准备多少葱。

**【样例数据】**

<table style="border-collapse:collapse;border:none;"> 
 <tbody> 
 <tr> 
 <td style="width:213pt;border:solid 1pt;"> cruise.in </td> 
 <td style="width:213.05pt;border:solid 1pt;border-left:none;"> cruise.out </td> 
 </tr> 
 <tr> 
 <td style="width:213pt;border:solid 1pt;border-top:none;"> 5 8 1 2 1 3 2 4 2 5 1 0 0 1 0 5 4 2 1 2 5 3 2 </td> 
 <td style="width:213.05pt;border-top:none;border-left:none;border-bottom:solid 1pt;border-right:solid 1pt;"> 3 2 2 1 0 0 0 2 </td> 
 </tr> 
 </tbody> 
</table>

**【数据范围】**

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

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

解析：

没搞出来， 先CV一波Solution

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

复杂度O(mlogn + nlogn)。

代码鸽了

![loading.gif][]

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

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/1556107342934a0eb5ea8dd44eae41df.png
[Bzoj4569_ _Scoi2016]: https://www.lydsy.com/JudgeOnline/problem.php?id=4569
[loading.gif]: /images/20211029/2369551c40164a2fbd00c2e4c538c68d.png