C 给定一张 $n$ 个点 $m$ 个边的图，现在构成一张 $n^2$ 个点的新图，每个点是一个二元组 $(a,b)$ ,其中，新图中点 $(a,b) , (c,d)$ 有边当且仅当 原图中 $a,c ; b,d$ 有边，求新图中连通块个数
观察新图中两点间有边的条件：在原图中的两个点 $i,j$ 分别向其相邻的点走一步，到达点 $u,v$ ，那么新图中连边 $(i,j)\rightarrow (u,v)$
考虑单一连通块内部：对于任意点对 $(u,v)$ 可将两点均向中间缩，最后有两种情况：
$u,v$ 重合：路径长偶数
$u,v$ 位于边两端：路径长奇数
那么，原图的连通块在新图中会形成一个或两个连通块
可以得出神奇的结论：
对于一个原图中的独立点 $u$ ，新图的 $(u,v)$ 与 $(v,x)$ 均为独立的点 $( v\in n )$ 。故设原图中独立点数量为 $single$ ，那么独立点对答案的贡献就是 $single\times n+(n-single)\times single$
对于原图中的无奇环联通块，可以与任一联通块组成新图的两个不同联通块。设这种联通块有 $c$ 个，其两两组合对答案的贡献为 $c\times c\times 2$
对于原图中的有奇环联通块，可以与任一联通块组成新图的一个联通块（若与它组合的是无奇环联通块，则两个）。设这种联通块有 $d$ 个，则它对答案的贡献就是 $d*\times (d+c\times 2)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 const int N=2e5 +100 ;int head[N],ver[N<<1 ],Next[N<<1 ],tot;int fa[N],Size[N],n,m,cnt[2 ];PII circle[N]; int num; bool parity[N],odd[N];int single; ll ans;inline void add (int u,int v) int find (int x) return fa[x]==x ? x : fa[x]=find (fa[x]);}void dfs (int x,int fath) parity[x]=parity[fath]^1 ; for (rei i=head[x];i;i=Next[i]){ rei y=ver[i]; if (y==fath) continue ; dfs (y,x); } } int main () scanf ("%d%d" ,&n,&m); for (rei i=1 ;i<=n;++i) fa[i]=i,Size[i]=1 ; for (rei i=1 ,u,v;i<=m;++i){ scanf ("%d%d" ,&u,&v); if (find (u)!=find (v)){ add (u,v),add (v,u); u=find (u),v=find (v); fa[u]=v,Size[v]+=Size[u];} else circle[++num]=mk (u,v); } for (rei i=1 ;i<=n;++i) if (fa[i]==i) dfs (i,0 ); for (rei i=1 ;i<=num;++i) if (parity[ circle[i].first ]==parity[ circle[i].second ]) odd[ find (circle[i].first) ]=1 ; for (rei i=1 ;i<=n;++i){ if (fa[i]!=i) continue ; if (Size[i]==1 ) ++single,ans+=n; else ++cnt[ odd[i] ]; } ans+=(ll) (n-single)*single + (ll) 2 *cnt[0 ]*cnt[0 ] + (ll) cnt[1 ]*(cnt[1 ]+2 *cnt[0 ]); printf ("%lld\n" ,ans); getchar (),getchar (); return 0 ; }
D
有 $n$ 个机器排成一排，每个装置有 $A,B$ 两种状态，一小球从左侧进入该系统。其中 $A$ 使球反弹回原方向，$B$ 无作用，球经过一个装之后装置状态将改变，给定初始状态，求 $k$ 个小球经过后装置最终状态
先看小一点的情况：
第一个是 $A$ ：球弹回去，第一个变成 $B$
第一个是 $B$ ：球继续，如果后面还有 $A$ 则会撞上之前经过的 $B$ 变成的 $A$ 而弹回去
可以发现对于一次滚球：删去序列第一个，序列整体取反，末尾加上一个 $A$ 可以完成
再考虑 $k$ ，由于删除-取反-添加 的操作，整个字符串逐渐从后向前变成 $ABAB…或BABA…$ 的形态
而在 $k>n$ 时，对于 $ABAB…$ 奇数次会变为 $BABA…$ ，偶数次不变，对于 $BABA…$ 形态不会改变
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 const int N=4e5 +100 ;int n,k,num[N],st;char s[N];int main () scanf ("%d%d" ,&n,&k); scanf ("%s" ,s+1 ); for (rei i=1 ;i<=n;++i) num[i]=s[i]-'A' ; st=num[1 ]; rei pos=1 ,cnt=0 ; while (k--){ if (!st) st^=1 ,num[pos]^=1 ; else ++pos,++cnt,st=num[pos],st^=(cnt&1 ); if (pos>n) break ; } if (pos<=n){ for (rei i=pos;i<=n;++i) putchar ('A' +(num[i]^(cnt&1 ))); rei t=pos-1 ,c=(cnt-1 )&1 ; while (t--) putchar ('A' +c),c^=1 ; } else { if ((cnt-1 )&1 ) for (rei i=1 ;i<=n;++i) putchar ('A' +(i&1 )); else { putchar ('A' +(k&1 )); for (rei i=1 ;i<n;++i) putchar ('A' +(i&1 )); } } getchar (),getchar (); return 0 ; }
E
定义一个数是“递增的”，当且仅当对于它的任意相邻的两位都有左边小于等于右边。给定一个数 $n\leq 10^{500000}$ 求其最少可以被表示为一个递增的数之和
考虑找到一个数时递增的充要条件
定义一个数纯一数，如果其所有数码都为 $1$ ， 显然其可被写成 $\frac{1}{9}(10^n-1)$ 的形式。那么一个数时递增的当且仅当它是不超过 $9$ 个纯一数的和，由于 $0$ 也可以被写成该形式，定义纯一数都表示为 $9$ 个形如 $\frac{1}{9}(10^n-1)$ 的数的和
于是 $x=\frac{1}{9}(10^{n_1}-1) + …+\frac{1}{9}(10^{n_9}-1)\ \Leftrightarrow \ 9x+9=10^{n_1}+…+10^{n_9}$
$\therefore$ $9x+9$ 的数码和一定为 $9$
现在需要判断 $n$ 是多少递增数的和，需要算出 $9n$ ，然后加上 $9k$ 其中 $k$ 是答案
假设 $n$ 是 $k$ 个递增数的和， $9\times (n+k)$ 就是不超过 $9k$ 个 $10$ 的幂的和，从而数码和 $\leq 9\times k$ ，反之亦能推出，故这是充要条件
问题转化为：求最小的 $k$ 使 $9(n+k)$ 的数码和 $\leq 9\times k$
对于这种高精的题，尝试直接枚举，以利用均摊复杂度
枚举 $k$ ，每次对 $9n$ 加 $9$ ，加法过程中维护数码和，答案不会超过 $\lg n+O(1)$ ，均摊复杂度为 $O(k+\lg n)=O(\log n)$
压位减小常数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 const int N=5e5 +100 ,BASE=1e8 ;int n,s[N],f[10000 ],cur,dsum,ans,len;char str[N],tok[9 ];inline int digit_sum (int x) return f[x/10000 ]+f[x%10000 ];}int main () tok[8 ]=0 ; for (rei i=1 ;i<10000 ;++i) f[i]=f[i/10 ]+i%10 ; scanf ("%s" ,str); len=strlen (str); for (rei i=1 ;i*8 <=len;++i) memcpy (tok,str+(len-i*8 ),8 ),s[n++]=strtol (tok,NULL ,10 ); if (len&7 ) memcpy (tok,str,len&7 ),tok[len&7 ]=0 ,s[n++]=strtol (tok,NULL ,10 ); for (rei i=0 ;i<n+2 ;++i) cur=s[i]*9 +cur,s[i]=cur%BASE,cur/=BASE,dsum+=digit_sum (s[i]); for (ans=1 ;;++ans){ dsum-=digit_sum (*s),*s+=9 ; rei i; for (i=0 ;s[i]>=BASE;++i) dsum+=digit_sum (s[i]-=BASE)-digit_sum (s[i+1 ]++); dsum+=digit_sum (s[i]); if (dsum<=9 *ans){ printf ("%d\n" ,ans); goto done;} } done: getchar (),getchar (); return 0 ; }
F
有一条分成 $n$ 段的铁路共有 $n+1$ 个站台，标号为 $0\sim N$ ，其中铁路 $i$ 连接站台 $i-1,i$ ，长度为 $a_i$ ，铁路分为单向双向两种，需要制定一个时间表，满足：
所有火车要么正向要么反向，中途不能掉头
所有火车速度 $1$ 单位，且保持匀速
所有正向，反向火车发车间隔均为 $k$ 且在站 $i$ 上的停靠时间只与 $i$ 有关
对于任意一条单向铁路，不能有正向反向火车在非站台的地方相遇
求一个时间表，使正向火车 $0\sim n$ 的时间加上反向火车 $n\sim 0$ 的时间总合(包括停靠时间)最小
把铁路放在数轴上考虑，每个站台 $i$ 都有坐标 $x_i=a_1+a_2+…+a_i$ ，且将时间模 $k$ ，在 $\pmod k$ 的范围下讨论
先考虑无解：
一段单项铁路长度 $l>\frac{k}{2}$ 时无解：$\pmod k$ 意义下两个长度 $>\frac{k}{2}$ 的区间并相交，显然正反向列车行车区间相交则无解； 反之，若所有长度 $l\leq \frac{k}{2}$ 则一定有解。
设 $p_0$ 时正向列车发车时刻， $p_i$ 时列车在站台 $i$ 的停靠时间，则正向列车在铁路 $i$ 上的行车区间为 $[p_0+p_1+…+p_{i-1}+x_{i-1} \ ,\ p_0+p_1+…+p_{i-1}+x_i]$
简记 $P_n=\sum_{i=1}^n p_i$ 则区间 $\mathcal{P_i}=[P_{i-1}+x_{i-1}\ ,\ P_{i-1}+x_i]$
而对于反向列车，将整个过程倒过来，设 $-n_0$ 为到达时刻， $n_i$ 为停靠时间，$N_n=\sum_{i=1}^n n_i$ ，则区间 $\mathcal{N_i}=[-N_{i-1}-x_i\ ,\ -N_{i-1}-x_{i-1}]$
考虑环上区间 $[l_1,r_1],[l_2,r_2]$ 不交的充要条件，为 $l_1\in [r_2,l_1+l_2-r_1]$
$\therefore$ 列车不碰撞的条件转化为表达式： $P_{i-1}+x_{i-1}\in [-N_{i-1}-x_{i-1}\ ,\ -N_{i-1}+x_{i-1}-2x_i] \Leftrightarrow P_{i-1}+N_{i-1}\in[-2x_{i-1}\ ,\ -2x_i]$
再考虑最终答案，若不计停靠时间显然为 $2\times x_n$ ，所以需要最小化停靠时间之和 $\sum_{i=1}^{n-1} (p_i+n_i)$
将上述不碰撞区间看为 $R_i$ ，转化为一般问题：
若干个区间 $R_1,R_2,…,R_n$ 有一个 $\pmod k$ 意义下的数 $x$ ，且初值任意。需要核实的移动 $x$ 使其落入 $R_i$ 中，仅能正向移动，且模 $k$ ，求最小化移动距离
当起点固定，有贪心：能不移就不移，否则移至区间左端点
由于不知道起点，考虑 $\text{dp}$ ，$f_{i,x}$ 表示前 $i$ 个区间，从最有七点移动到已知终点 $x$ 所需最小总距离
设 $j$ 是最大的使 $x\notin R_j$ 的 $j$ ，整个过程的最后一步就是将 $x$ 从 $R_j$ 的右端点移回 $x$
$f_{i,x}=f_{j,r_j}+\left(x∸r_j\right)$ ，其中 $a∸b$ 表示 $a-b$ 取 $\pmod k$ 的最小非负剩余
添加区间时依次求出 $f_{1,r_1},f_{2,r_2},…,f_{n,r_n}$ ，最后的位置一定是某个区间的左端点，将所有左端点带入 $x$ 询问即可
最后，考虑如何找到最大的 $j$ 使 $x\notin R_j$ 的 $j$ 最大
对于每个 $x$ ,设 $pre_x=j$ ，考虑操作对 $pre$ 的影响
每一次操作相当于对不在 $[l_i,r_i]$ 的所有数 $e$ 令 $pre_e=i$
这可以看成区间赋值，而查询只需要单点查询，然后就会用到珂朵莉树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 const int N=1e5 +100 ;int n,m,T;ll x[N],f[N],ans=LLONG_MAX; PII seg[N]; bool directed[N];inline void down (ll &x,const ll y) 0 ;}inline int fix (ll x) return x%=T,x+=x>>63 &T;}namespace CTree{ map<int ,int > C; void init () emplace (0 ,-1 ),C.emplace (T,-1 );} map<int ,int >::iterator split (int pos) { map<int ,int >::iterator it=C.lower_bound (pos),jt=it; return it->first==pos ? it : C.emplace_hint (it,pos,(--jt)->second); } void modify (int l,int r,int v) map<int ,int >::iterator it=split (l),jt=split (r); C.erase (it,jt),C.emplace (l,v); } inline int query (int h) return (--C.upper_bound (h))->second;} } int main () rei j,L,R; scanf ("%d%d" ,&n,&T); for (rei i=1 ;i<=n;++i) if (scanf ("%lld%d" ,x+i,&j),directed[i]=j&1 ){ if (2 *x[i]>T) return puts ("-1" ),0 ; x[i]+=x[i-1 ],seg[m++]=mk (L=fix (-2 *x[i-1 ]),R=fix (-2 *x[i])); } else x[i]+=x[i-1 ]; CTree::init (); for (rei i=0 ;i<m;++i){ std::tie (L,R)=seg[i],j=CTree::query (R); f[i]=(~j ? f[j]+fix (R - seg[j].second) : 0 ); L<=R ? (CTree::modify (0 ,L,i),CTree::modify (R+1 ,T,i)) : (CTree::modify (R+1 ,L,i)); } for (const PII &e : CTree::C){ if (e.first>=T) continue ; if (!~e.second){ ans=0 ;break ;} down (ans,f[e.second]+fix (e.first-seg[e.second].second)); } printf ("%lld\n" ,ans+2 *x[n]); getchar (),getchar (); return 0 ; }