终于打了一场CF,不知道为什么我会去打00:05的CF比赛……
不管怎么样,这次打的很好!拿到了Div. 2选手中的第一名,成功上紫!
以后还要再接再厉!
题意:
一个合法的字符串可以这样生成:
初始是一个空串,然后小 A 同学往这个串中加入若干(大于零)个字符\(\texttt{a}\),然后小 B 同学往这个串的末尾加入若干(大于零)个字符\(\texttt{b}\),最后小 C 同学往这个串的末尾加入一些字符\(\texttt{c}\),但要满足\(\texttt{c}\)的个数等于\(\texttt{a}\)的个数或\(\texttt{b}\)的个数。
问一个字符串是否是合法的。
题解:
模拟,注意细节。
#include<bits/stdc++.h> char str[10000]; int i,n,A,B,C; int main(){ scanf("%s",str); n=strlen(str); if(str[0]!='a') {puts("NO"); return 0;} for(i=0;i<n;++i) if(str[i]=='a') ; else break; A=i; if(i==n||str[i]!='b') {puts("NO"); return 0;} for(;i<n;++i) if(str[i]=='b') ; else break; if(i==n||str[i]!='c') {puts("NO"); return 0;} B=i-A; for(;i<n;++i) if(str[i]=='c') ; else break; if(i!=n) {puts("NO"); return 0;} C=n-B-A; if(C!=A&&C!=B) {puts("NO"); return 0;} puts("YES"); return 0; }
题意:
有两个长度都为\(n\)的数组\(A\)和\(B\),定义误差\(E=\sum_{i=1}^{n}(A_i-B_i)^2\)。
你需要对数组\(A\)执行恰好\(k_1\)次操作,对数组\(B\)执行恰好\(k_2\)次操作。一次操作即让数组中的一个数加一,或者减一。
问执行完操作后的最小误差\(E\)。
题解:
数组的每一位都是独立的。对于某一位\(A_i,B_i\),对这一位执行操作可以让\((A_i-B_i)^2=|A_i-B_i|^2\)变大,或者变小。
显然变大是不合算的,所以计算出\(C_i=|A_i-B_i|\),不论是对\(A\)还是对\(B\)的操作都是一样的,可以让\(C_i\)加一或者减一,但是不能减到负数。
而\(C_i\)越大,对它减一的收益就越大,所以每次贪心选取最大的\(C_i\)减去一。我使用了优先队列来加快速度,尽管暴力可过。
#include<bits/stdc++.h> #define F(i,a,b) for(int i=a;i<=(b);++i) #define ll long long using namespace std; int n,A,B; int a[100001],b[100001]; priority_queue<int> pq; ll Ans=0; int main(){ scanf("%d%d%d",&n,&A,&B); A+=B; F(i,1,n) scanf("%d",a+i); F(i,1,n) scanf("%d",b+i); F(i,1,n) a[i]=abs(a[i]-b[i]), pq.push(a[i]); F(i,1,A){ int x=pq.top(); pq.pop(); if(x>0) pq.push(x-1); else pq.push(1); } int x; F(i,1,n) x=pq.top(), Ans+=(ll)x*x, pq.pop(); printf("%lld",Ans); return 0; }
题意:
对于一个数组,将这个数组的所有非空子序列写下,然后删掉满足:最大值与最小值的差大于等于\(d\)的子序列。
最后剩下了\(X\)个子序列。
请你给出原序列的一种合法排列。
题解:
考虑这样构造:
\(\overset{k_1}{\overbrace{x,\cdots,x}},\overset{k_2}{\overbrace{x+d,\cdots,x+d}},\overset{k_3}{\overbrace{x+2d,\cdots,x+2d}},\cdots\)。
这样的目的是让任意包含两个不同的数的子序列会被删掉,留下的只有包含相同数的。
这样最终剩下的子序列有多少个呢?通过一些简单的计算,我们得到答案:
\(\sum 2^{k_i}-1\)。
得到了这个,发现两组个数分别为\(k_i\)和\(1\)的数,会对答案产生\(2^{k_i}\)的贡献。
那么把\(X\)二进制拆分一下即可。
#include<bits/stdc++.h> #define F(i,a,b) for(int i=a;i<=(b);++i) #define ll long long int X,d,cnt; ll now=1; ll b[100001]; int main(){ scanf("%d%d",&X,&d); if(X&1) {b[++cnt]=now; now+=d;} int x=1; X>>=1; while(X){ if(X&1){ for(int i=1;i<=x;++i) b[++cnt]=now; now+=d; b[++cnt]=now; now+=d; } X>>=1; ++x; } printf("%d\n",cnt); F(i,1,cnt) printf("%lld ",b[i]); return 0; }
题意:
给你一个无限层的满二叉树(无限层也不考虑是完全还是满了2333)。
这个满二叉树的节点上有值,而且一个节点的左儿子的值是这个节点的值乘以2,右儿子的值是这个节点的值乘2加1。
你有三个操作:
①把值为X的节点所在层的所有节点的值往右循环移动K位。
②把值为X的节点所在层的所有节点往右循环移动K位,子树也一起移动。
③问值为X的节点走到根的路径上的值的序列。
请执行这些操作,并回答结果。
题解:
发现初始一个节点的值可以很轻松算出来,其实就是线段树上的节点的编号,很有规律。
因为\(X\)在long long范围,所以深度大于62的都是假的节点。
考虑暴力维护每一层循环移动的位数。再做做数学加加减减就完事了。
#include<bits/stdc++.h> #define F(i,a,b) for(int i=a;i<=(b);++i) #define dF(i,a,b) for(int i=a;i>=(b);--i) #define ll long long int n; ll lev[64]; inline int hibit(ll x){ int ans=-1; while(x) x>>=1, ++ans; return ans; } inline void shift(int lv,ll k){lev[lv]+=k&((1ll<<lv)-1);lev[lv]&=((1ll<<lv)-1);} int main(){ scanf("%d",&n); F(i,1,n){ int t; ll x,k; scanf("%d%lld",&t,&x); if(t==1){ scanf("%lld",&k); shift(hibit(x),k); } if(t==2){ scanf("%lld",&k); F(j,hibit(x),61) shift(j,k<<(j-hibit(x))); } if(t==3){ int lv=hibit(x); ll y=(x-(1ll<<lv)+lev[lv])&((1ll<<lv)-1); dF(j,lv,0) printf("%lld ",((y-lev[j])&((1ll<<j)-1))+(1ll<<j)), y>>=1; puts(""); } } return 0; }
题意:
对于一棵树,假设有一条简单路径\(u_1 \rightarrow u_2 \rightarrow u_3 \rightarrow \dots u_{m-1} \rightarrow u_{m}\)。
定义它的交替函数:\(A(u_{1},u_{m}) = \sum\limits_{i=1}^{m} (-1)^{i+1} \cdot V_{u_{i}}\)。
一条路径也可以有\(0\)条边,即\(u_1=u_m\)。
请计算所有不同路径的交替函数值的总和。答案对\(10^9+7\)取模。
题解:
考虑对于每一个点计算自己的贡献。
为了好处理,把树变成以1为根的有根树。
再考虑一个点的贡献:显然只有经过这个点的路径才会有贡献,即起点在这个点的一个子树(父亲连接的也算作一个子树),终点在其他子树的路径。
而对于一个路径,显然该点在奇数位贡献为正数,否则是负数。假设当前点为\(u\)。
对于起点在某一个大小为\(siz\)的子树中的\(v\)点,这个点在\(u\)的贡献就是\((-1)^{dis_{v,u}}\times (n-siz)\)。
\(n-siz\)即为终点可以在的位置的个数,只要不在同一个子树就可以。
发现只要\(v\)在同一个子树,最后乘的\(n-siz\)都是相同的。考虑把前面的也合并起来。
那么以\(u\)为根建树,\(u\)直接相连的每一个子树\(T\)都定义一个函数\(f(T)=\sum_{v\in T}(-1)^{dep_v}\)。
当\(v\)为\(T\)的根时,\(dep_v=0\),之后每一层\(dep\)就多一。
这个函数有什么意义呢?发现\(f(T)\)正好就是刚刚的\((-1)^{dis_{v,u}}\)的总和的相反数。
那就是说子树\(T\)对\(u\)的贡献次数是\(-f(T)\times (n-siz_T)=-f(T)\cdot n+f(T)\cdot siz_T\)。
但是还漏了一种起点就是\(u\)本身的情况,那样会多贡献正好\(n\)次。
那就是说,总贡献是\((1-\sum f(T))\cdot n+\sum f(T)\cdot siz_T\)。
那\(siz_T\)通过DFS比较好算,考虑一下\(f(T)\)如何求出。
假如已经以\(u\)为根了,那么\(f(T)\)可以递归计算:\(f(T)=1-\sum f(G)\),其中\(G\)是与\(T\)直接相连的子树。
这和刚刚的公式是一样的结构,也就是说总贡献为\(f(T_u)\cdot n+\sum f(T)\cdot siz_T\),\(T_u\)即以\(u\)为根的整棵树。
但是这样还不够,因为要通过DFS计算答案,就必须指定一个点为根,比如\(1\)号点。
那么这时还能统计出每个\(u\)的每个\(f(T)\)吗?
考虑以\(1\)为根时的每个\(f(T)\),那么以\(u\)为根时,\(f(T_u)\)就等于\(f(1)\)或者\(-f(1)\)。当\(u\)的深度是偶数(1的深度为0)时,就是\(f(1)\),否则取相反数。
而对于\(u\)的\(f(T)\)呢?对于\(u\)的儿子的\(f(T)\),值不变,但是\(u\)还有一个指向父亲的\(T\),其实这个\(f(T)\)就等于\(f(T_u)\)【这个指的是以1为根的】减去\(f(T_u)\)【这个指的是以u为根的,即上面算出来的\(f(1)\)或相反数】。
那么一次DFS求出siz、dep和f值,第二次DFS直接求答案即可。
#include<bits/stdc++.h> #define F(i,a,b) for(int i=a;i<=(b);++i) #define eF(i,u) for(int i=h[u];i;i=nxt[i]) #define ll long long int Mod=1000000007; int n,q; int val[200001]; int h[200001],nxt[400001],to[400001],tot; inline void ins(int x,int y){nxt[++tot]=h[x];to[tot]=y;h[x]=tot;} int f[200001],siz[200001],dep[200001]; ll Ans; void DFS(int u,int fa){ f[u]=1; dep[u]=dep[fa]+1; siz[u]=1; eF(i,u) if(to[i]!=fa) DFS(to[i],u), f[u]-=f[to[i]], siz[u]+=siz[to[i]]; } void D2(int u,int fa){ eF(i,u) if(to[i]!=fa){ D2(to[i],u); Ans=((Ans+(ll)f[to[i]]*siz[to[i]]%Mod*val[u]%Mod)%Mod+Mod)%Mod; } if(fa!=0) Ans=((Ans+(ll)(((dep[u]&1)?-f[1]:f[1])+f[u])*(n-siz[u])%Mod*val[u]%Mod)%Mod+Mod)%Mod; } int main(){ int x,y; scanf("%d",&n); F(i,1,n) scanf("%d",val+i); F(i,2,n) scanf("%d%d",&x,&y), ins(x,y), ins(y,x); DFS(1,0); F(i,1,n) if(dep[i]&1) Ans+=(ll)f[1]*val[i]; else Ans-=(ll)f[1]*val[i]; Ans=(Ans%Mod+Mod)%Mod; Ans=Ans*n%Mod; D2(1,0); printf("%lld\n",Ans); return 0; }
题意:
给定一个有向图,边有边权。
问最长的路径,满足条件:边权逐个严格增加,并且边的顺序是读入时的顺序。
只要回答长度即可。
题解:
用\(dp[i][j]\)表示走到节点\(i\),并且最后的边权为\(j\)时的最长路径长度。
有转移:\(dp[i][j]=max(dp[k][l])+1,(l\leq k\to i)\)。
但是还要边的顺序是读入时的顺序。
那可以边读入边转移:读入\(u\to v=w\)时,可以转移\(dp[v][w]=max(dp[u][l])+1,(l\leq w)\)。
但是dp[i][j]存储的状态太多了,而且处理最大值也很吃力。
但是发现能转移的状态很少,而最大值是一个区间。
于是用动态开点的线段树解决这个问题。不需要离散化。
【也可以树状数组,因为求得是前缀】
#include<bits/stdc++.h> #define F(i,a,b) for(int i=a;i<=(b);++i) using namespace std; int n,m,Ans; int a[100001],b[100001]; int u[100001],v[100001],w[100001]; int f[100001]; int dat[8000001],ls[8000001],rs[8000001],cnt; int Maxi(int rt,int l,int r,int a,int b){ if(a>b) return 0; if(r<a||b<l) return 0; if(a<=l&&r<=b) return dat[rt]; if(!ls[rt]) ls[rt]=++cnt; if(!rs[rt]) rs[rt]=++cnt; int mid=l+r>>1; return max(Maxi(ls[rt],l,mid,a,b),Maxi(rs[rt],mid+1,r,a,b)); } void Ins(int rt,int l,int r,int p,int x){ if(l==r) {dat[rt]=x; return;} if(!ls[rt]) ls[rt]=++cnt; if(!rs[rt]) rs[rt]=++cnt; int mid=l+r>>1; if(p<=mid) Ins(ls[rt],l,mid,p,x); else Ins(rs[rt],mid+1,r,p,x); dat[rt]=max(dat[ls[rt]],dat[rs[rt]]); } int main(){ scanf("%d%d",&n,&m); cnt=n; F(i,1,m) scanf("%d%d%d",u+i,v+i,w+i), ++w[i]; F(i,1,m){ f[i]=Maxi(u[i],1,100001,1,w[i]-1)+1; Ins(v[i],1,100001,w[i],f[i]); } F(i,1,m) Ans=max(Ans,f[i]); printf("%d",Ans); return 0; }