DATE #:202409010
ITEM #:DOC
WEEK #:TUESDAY
DAIL #:捌月初捌
``` “不白”“不净”“不能”“不悟” ```TAGS
<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=2624325722&auto=0&height=66" width="330"></iframe> < BGM = "和光 - 闫东炜" > < theme = oi-contest > < [NULL] > < [空] > < [空] >
A. SpireRound#1 红裤衩
时间限制: 1 s 内存限制: 512 MB 测评类型: 传统型
题目背景
战士哥拿到了腐化树枝。 Cu.
题目描述
战士哥手中有\(n\)张牌，依次编号为\(1\dots n\)。
战士哥捡到了一根树枝，但是这根树枝是通人性的。它对战士哥的手牌有不同的喜爱度，用 INT 范围内的整数\(a_i,i\in [1,n]\)表示。
战士哥每回合可以出若干次牌，前提是满足树枝的要求：当且仅当对于某个位置\(i\in[2,n-1]\)满足$a_i=\dfrac{a_{i-1}+a_{i+1}}{2} \(时，他可以打出并消耗第i\)i$张牌，之后其余的牌自动向前填补空位。
战士哥手中有一张“悔恨”诅咒牌，在回合结束时，每有一张手牌就失去 1 点生命。因此他希望他的手牌尽可能少。请你告诉他，他出牌后的手牌数量最小是多少。
输入格式
第一行，一个正整数 \(T\)，表示数据组数。之后对于每组数据：
- 第一行，一个正整数 \(n\)；
- 第二行，\(n\) 个整数 \(a_1,\cdots,a_n\)。
输出格式
对于每组数据，输出一行，一个正整数，表示答案。
样例
样例一
样例输入
3 5 1 2 3 4 5 7 1 3 5 6 7 8 10 3 1 1 1样例输出
2 4 2样例解释
对于第一组数据 \([1,2,3,4,5]\)，依次删除 \(2,4,3\) 即可。
对于第二组数据 \([1,3,5,6,7,8,10]\)，依次删除 \(3,7,8\) 即可。
对于第三组数据 \([1,1,1]\)，删除中间的 \(1\) 即可。
样例二
见下发文件。
数据范围
本题共 20\(20\) 组测试点，各 5\(5\) 分。
对于所有数据，\(1 \le T\le 10^3\)，\(\sum n\le 3\cdot 10^5\)，\(a_i\) 在 INT32 范围内。
测试点编号 \(n\le\) \(\sum n\le\) 特殊性质 \(1\sim 3\) \(15\) \(400\) \(4\sim 6\) \(a_i=i\) \(7\sim 8\) \(1\le a_i\le 3\) \(9\sim 12\) \(300\) \(10^3\) \(13\sim 16\) \(3\cdot 10^3\) \(10^4\) \(17\sim 20\) 无
首先考虑转化题意，我们设原数列为\(a\),那么题意可以转化如下：
将\(a\)的差分数组求出，记作\(d\)那么当相邻的两个值相等时(即\(d_i=d_{i+1}\))，我们可以将其合并成为\(2\times d_i\)求合并后最短数列长度
题目的转化是巧妙且显然与原题相同的
那么就会有如下这样的结论：
正数只能和正数合并，负数同理，多个0可以合并成同一个
下面我们定义所有操作均在差分后数组\(d\)上讨论
注意到每次合并是一个乘二的过程，而纵观整个数列，一个值最多只能乘上2的\(log_2V\)次方，总共只有\(log\)次，所以数据范围并不大，我们可以将这\(log\)次乘方预处理出来
因此，我们就可以根据这个很好的性质展开需要的DP了
再对\(d\)进行一下操作，得到以下两个数组:\(dit，base\)关系为:\(dit_i = lowbit(d_i),base_i \times 2^{dit_i} = d_i\)
我们设:\(g_{i,j}\)表示从\(x+1\)到\(i\),这段区间被我们合并成了\(base_i\times 2^j\),那么\(g_{i,j}\)等于\(x\)
同时我们设:\(f_{i}\)表示前\(i\)个数中合并的最小方案数
所以DP方程就理所应当的被推了出来
\[g_{i,j} = \begin{cases} i-1(j=dit_i)\\ g_{g_{i,j-1},j-1}(j>dit_i\&\&base_{g_{i,j-1}}\&\&[g_{i,j-1}]\&\&[g_{g_{g_i,j-1},j-1}]) \end{cases} \]\[f_i = min_{j}(g_{i,j}+1) \]复杂度优美可过
//2024.9.10
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define int long long
#define itn long long
constexpr int oo = 300005;
int t,n,num[oo];itn d[oo],cnt[oo];
itn f[oo][35],g[oo];
__inline int calc(int l,int r){
if (d[l]==0) return 1;
for_each(f+l,f+r+1,[](int *it){fill_n(it,35,-1);});
f[l][cnt[l]]=l-1;
for (int i=l+1;i<=r;i++){
f[i][cnt[i]]=i-1;
for (int j=cnt[i]+1;j<=32;j++){
if (f[f[i][j-1]][j-1]==-1) break;
f[i][j]=f[f[i][j-1]][j-1];
if (f[i][j]<l) break;
}
}
fill(g+l,g+r+1,numeric_limits<int>::max());
g[l-1]=0;
for (int i=l;i<=r;i++)
for (int j=0;j<=32;j++)
if (~f[i][j])g[i]=min(g[i],g[f[i][j]]+1);
return g[r];
}
main(void){
//fre();
cin.tie(nullptr)->ios::sync_with_stdio(false);
cin >> t;while(t--){cin >> n;
for (int i=1;i<=n;i++) cin >> num[i];
for (int i=1;i<n;i++) d[i]=num[i+1]-num[i];
for (int i=1;i<n;i++){
cnt[i]=0;
while (d[i]&&!(d[i]&1)){cnt[i]++;d[i] >>= 1;}
}
int last=1,out=0;
for (int i=1;i<n-1;i++)
if (d[i]!=d[i+1]){out+=calc(last,i);last=i+1;}
out += calc(last,n-1);
cout << out+1 << '\n';
}
cout << flush;exit (0);
}
B. SpireRound#1 观者
时间限制: 4 s 内存限制: 512 MB 测评类型: 传统型
题目背景
观者是一位好姑娘。 Cute.
题目描述
观者手中拿着一张地图。地图的内容是一个\(n\)个点\(m\)条边的有向图。
观者希望经过更多的房间（即地图上的点）。她想知道，从每个房间出发，最多能经过多少房间。为了方便观者理解你的方案，地图的每条边上都带有一个字符，字符用一个数字表示。你需要在所有满足条件（即经过的房间数最多）的方案中，选择走过的边的字符构成的字符串的字典序最小的方案。
输入格式
第一行两个整数 \(n,m\) ，表示有向图的结点个数和边数。
接下来 \(m\) 行，每行三个整数 \(x,y,w\) ，表示有一条从 \(x\) 连向 \(y\) 的边，上面有字符 \(w\) 。
输出格式
为了避免过量的输出，如果观者经过的房间数量没有上限，请输出
Infinity；否则，假设方案走过的边的字符依次为 \(w_1,w_2,\dots,w_k\) ，输出\(\sum^k_{i=1}w_i\times 29^i\pmod {998244353}\)。对于每个询问，输出一行，表示答案。
样例
样例一
样例输入
5 6 1 2 0 2 1 0 3 4 2 4 5 3 4 5 1 3 5 1样例输出
Infinity Infinity 899 29 0数据范围
对于所有数据，\(1\le n\le 10^6,1\le m \le 10^6,0\le {\_\_}\le 10^9\)。
测试点编号 \(n\le\) \(m\le\) 特殊性质 \(1\sim 4\) \(1000\) \(1000\) \(5\sim 8\) 所有字符相等 \(9\sim 12\) 所有字符互不相等 \(13\sim 16\) \(200000\) \(200000\) \(17\sim 20\) 无
首先缩点，将有自环的点和点数 \(\ge 2\) 的连通块标记，走到这些标记就可以在里面无限循环。
然后整张图变成了一个 DAG，在 DAG 的反图上拓扑排序即可求出所有的 \(\tt {Infinity}\) 点。
因为要经过最多房间，所以对这个 DAG 建一个最长路 DAG。
因为边的长度都为 \(1\)，整张图被分成了若干层。
我们没办法维护所有串来比较大小，但是对于字典序，假如前面某一位已经确定大小关系，后面再怎么也不能改变这个关系。
假设我们将每一层的串按照字典序排序，记 \(x\) 号点在其所在层的排名为 \(r_x\)。
对于第 \(i\) 层 \(s\) 点到第 \(i+1\) 层 \(t\) 点的一条边 \(w\)，将 \(w\) 作为第一关键字，\(r_s\) 作为第二关键字对第 \(i+1\) 层的点排序得到该层的 \(r\) 数组。哈希值在排序时就可以处理出来了。
时间复杂度瓶颈在排序，为 \(O(n\log n)\)。
//2024.9.10
//by white_ice
#include <bits/stdc++.h>
using namespace std;
const int oo=1e6 + 10;
const int mod=998244353;
int n,m;
int in[oo],ans[oo],dis[oo],to[oo],num[oo];
int head[oo],tot;
int dfn[oo],low[oo],tim;
int stk[oo],top,scc[oo],siz[oo],cnt;
bool vis[oo],flag[oo];
struct node{int u,v,num,nxt;}st[oo],e[oo];
struct edge{int v,num;
bool operator < (const edge &b) const{return num < b.num;}
};vector <edge> g[oo];
int add(int x) {return x>=mod?x-mod:x;}
int mul(int x,int y) {return 1ll*x*y%mod;}
void add(int x,int y,int z){
st[++tot]=(node){x,y,z,head[x]};
head[x]=tot;
}
void tarjan(int x){
dfn[x]=low[x]=++tim;
stk[++top]=x,vis[x]=1;
for(int i=head[x],y;i;i=st[i].nxt){
if((y=st[i].v)==x) flag[x]=1;
if(!dfn[y=st[i].v]) tarjan(y),low[x]=min(low[x],low[y]);
else if(vis[y]) low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
int k;cnt++;
do{ k=stk[top--];
if(flag[x]) siz[cnt]=2;
vis[k]=0,scc[k]=cnt,siz[cnt]++;
}while(x != k);
}
}
bool check(int x,int y,int wi){
while(x&&y&&wi==num[y]) wi=num[x],x=to[x],y=to[y];
return wi < num[y];
}
void topo(){
queue <int> q;
memset(ans,-1,sizeof(ans));
for(int i=1;i<=cnt;++i)
if(!in[i]&&siz[i]==1) q.push(i),ans[i]=0;
while(!q.empty()){
int x=q.front();q.pop();
if(siz[x] > 1) continue;
if(ans[x]==-1) ans[x]=mul(29,add(num[x] + ans[to[x]]));
sort(g[x].begin(),g[x].end());
for(auto v : g[x]){
int y=v.v,wi=v.num;
if(dis[y] < dis[x] + 1) dis[y]=dis[x] + 1,to[y]=x,num[y]=wi;
else if(dis[y]==dis[x] + 1){
if(check(x,y,wi)) num[y]=wi,to[y]=x;
}
if(!(--in[y])) q.push(y);
}
}
}
main(void){
cin >> n >> m;
for(int i=1;i<=m;++i){
int u,v,num;
cin >> u >> v >> num;
add(u,v,num),e[i]=(node){u,v,num};
}
for(int i=1;i<=n;++i)
if(!dfn[i]) tarjan(i);
for(int i=1;i<=m;++i){
int x=e[i].u,y=e[i].v;
if(scc[x] != scc[y]){
in[scc[x]]++;
g[scc[y]].push_back((edge){scc[x],e[i].num});
}
}
topo();
for(int i=1;i<=n;++i){
if(ans[scc[i]]==-1)printf("Infinity\n");
else printf("%d\n",ans[scc[i]]);
}
exit (0);
}
C. SpireRound#1 万物一心
时间限制: 1 s 内存限制: 512 MB 测评类型: 传统型
题目背景
故障机器人的核心丢了。 yix.
题目描述
机器人的电路由\(n\)个芯片和\(n-1\)条导线组成，任意两个芯片之间有一条导线路径联通。所有导线都因受损而断开了，如果修复第\(i\)条导线，会获得\(c_i\)点 Wu。
假设机器人的核心在第\(h\)个芯片，他将要选择\(k\)个芯片，并修复最少的导线，使得\(k\)个芯片与核心之间导通。他希望这一过程中获得的 Wu 最多，请你对每个\(h\)分别计算这个最大值。
输入格式
第一行，两个正整数 \(n,k\)。
之后 \(n-1\) 行，每行两个正整数 \(u_i,v_i\) 和一个非负整数 \(c_i\)。
输出格式
共 \(n\) 行，第 \(h\) 行一个非负整数，表示对应的答案。
样例
样例一
样例输入
11 3 1 2 5 2 3 3 2 6 5 3 4 4 3 5 2 1 7 6 7 8 4 7 9 5 1 10 1 10 11 1样例输出
28 28 28 32 30 32 28 32 32 29 30样例二
见下发文件，该样例符合子任务 \(4\) 的限制。
数据范围
对于所有数据，\(1\le k\le n\le 10^5\)，\(0\le c_i\le 10^9\)。
共 25 个测试点。
编号 特殊限制 测试点数量 \(1\) \(n\le 18\) \(1\) \(2\) \(n\le 200\)，k≤20\(k\le 20\) \(4\) \(3\) \(n\le 2000\) \(5\) \(4\) \(k=1\) \(5\) \(5\) \(10\)
肯定先选叶子。
第一次选最长链
然后扣掉这条链，再选最长链，然后接着扣掉，选最长链……
考虑长剖剖出来一些链，然后选前 k\(k\) 大即可。
换根的话只有 \(O(1)\) 条链发生变化，记录最长次长链即可。
维护链的数据结构应该是可删对顶堆。
注意要么换根还原要么版本回退，比较难写。
代码太难写了还没调出来
D. SpireRound#1 华丽收场
时间限制: 1 s 内存限制: 512 MB 测评类型: 传统型
题目背景
这次经历并没有华丽收场，事实上，它草草地结束了，仿佛什么也没有开始一样。不太恰当的时间与不太恰当的将来。唉。 Jane.
题目描述
静默猎手吸取教训，决定先解决掉这个数学问题，再尝试华丽收场。
我们知道，求任意图的最大独立集是一类 NP 完全问题，目前还没有准确的多项式算法，但是有许多多项式复杂度的近似算法。
猎手使用的算法是：
- 对于一个 \(n\) 个点的无向图，先等概率随机一个 \(1\ldots n\) 的排列 \(p[1\ldots n]\)。
- 维护答案集合 \(S\) ，一开始 \(S\) 为空集，之后按照 \(i=1\ldots n\) 的顺序，检查 \(\{p[i]\}\cup S\) 是否是一个独立集，如果是的话就令 \(S=\{p[i]\}\cup S\)。
- 最后得到一个独立集 \(S\) 作为答案。
猎手现在想知道，对于给定的一张图，这个算法的正确率。输出答案对 \(998244353\) 取模。
输入格式
第一行两个非负整数 \(n,m\) 表示给定的图的点数和边数。
接下来 \(m\) 行，每行有两个正整数 \((u,v) (u\neq v)\) 描述这张图的一条无向边。
输出格式
输出正确率，答案对 \(998244353\) 取模。
样例
样例一
样例输入
3 2 1 2 2 3样例输出
665496236样例解释
这张图的最大独立集显然为 \(2\)，可以发现只有 \(p[1]=2\) 时会得出 \(S=\{2\}\)，否则都是 \(S=\{1,3\}\)，所以答案是 \(\frac{2}{3}\)。
数据范围
对于 \(10\%\) 的数据，有\(1\leq n\leq 9\)。
对于 \(30\%\) 的数据，有\(1\leq n\leq 13\)。
对于 \(50\%\) 的数据，有\(1\leq n\leq 17\)。
另有 \(10\%\) 的数据，满足给定的图是一条链。
另有 \(10\%\) 的数据，满足给定的图是一棵树。
对于 \(100\%\) 的数据，有\(1\leq n\leq 20\)，\(0\leq m\leq \frac{n\times (n-1)}{2}\)，保证给定的图没有重边和自环。
原题是https://www.luogu.com.cn/problem/P5492 [PKUWC2018]随机算法
//2024.9.10
//by white_ice
//D. SpireRound#1 华丽收场
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define int long long
#define itn long long
constexpr int oo = 23;
constexpr int op = (1<<20)+5;
constexpr int mod = 998244353;
int n,m;
itn cnts,ix[op],pset[oo],cnt[op],siz[op];
int maxs,f[op],inv[oo],out;
bool vis[op];
main(void){
//fre();
int x,y;
cin >> n >> m;
while (m--){
cin >> x >> y;
pset[x]|=1<<y-1,pset[y]|=1<<x-1;
}
vis[0]=1;cnts=1<<n;
for (int i=1;i<=n;i++) ix[1<<i-1]=i;
for (int s=1;s<cnts;s++){
int t=s^(s&-s),i=ix[s&-s];
if (vis[t]) vis[s]=!(t&pset[i]);
cnt[s]=siz[s]=siz[t]+1;
if (vis[s]) maxs=max(maxs,siz[s]);
for (int i=1;i<=n;i++)
if (s&pset[i]) cnt[s]++;
}
f[0]=inv[1]=1;
for (int i=2;i<=n;i++)
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for (int s=1;s<cnts;s++){
if (!vis[s]) continue;
for (int i=1;i<=n;i++){
if (!((s>>i-1)&1)) continue;
int t=s^(1<<i-1);
f[s]=(f[t]*inv[n-cnt[t]]+f[s])%mod;
}
if (siz[s]==maxs) out=(out+f[s])%mod;
}
cout << out << endl;
exit (0);
}