2025.3.3

Educational Codeforces Round 175 (Rated for Div. 2)

C. Limited Repainting(二分)

题意

给出一个字符串a由“R”B“组成，不同位置对应一个惩罚值。存在一个初始全为”R“的字符串b，可以最多进行k次操作，选择b中连续区间R->B,B->R.最终罚分为a,b不匹配的位置中最大一个罚分。求可以得到的最小罚分是多少。

思路

起初,试图找规律,未果。看到标签“二分”，虽有初步判断，仍思路不明，惭愧。二分难于check，此check难于区间不定。check(x),即，凡>x者，必变。B相连，操作数为一。遇R且>x,不可变，分离变化区间或是复变此处，操作皆需+1，因而此无需多虑。凡遇之，皆+1即可。若k次即可完成操作便return1；

代码

const int N=1e6+10;
int n,k,a[N];
string s;
bool check(int x)
{int c=k,flag=0;fir(i,0,n-1){if(s[i]=='R'&&a[i]>x)flag=0;else{if(s[i]=='B'&&a[i]>x&&flag==0){if(c==0) return false;c--,flag=1;		} 		  }}return true;
}
void solve()
{cin>>n>>k;cin>>s;fir(i,0,n-1)cin>>a[i];int l=0,r=1e9;while(l<r){int mid=(l+r)/2;if(check(mid)) r=mid;else l=mid+1;}cout<<l<<'\n';
}

点击了解更多二分二分答案（模板+例题+代码）_二分答案模板-CSDN博客

D. Tree Jumps(树形结构、dp)

题意

节点1为根，1可以和与他的相邻子节点组成序列。其他节点只能和与他不在一层，且不是子节点的组成序列。求一共多少从1开始的序列。

例：

这个样例输入

7
1 2 2 1 4 5

输出 8

分别是$[1][1]、[1,2][1,2]、[1,2,7][1,2,7]、[1,2,7,6][1,2,7,6]，[1,5][1,5]，[1,5,3][1,5,3]，[1,5,3,6][1,5,3,6]和[1,5,4][1,5,4]$

思路

思考规律，树形结构，少不了递推。可以发现以p点结尾的序列数，可以由上一层连向它，然而不能是父节点及父父节点，所以只需g【p】=sum—g【 f [ i ]】

-首先用f数组存放父节点，还需要知道父节点多少个序列，所以用g来存放每个节点的序列数。

上一层的总和递推下一层，所以要分层计算，用二维vector类型**v，存放每一层的节点。**层数如何得知呢？用数组d来计算d[i]=d[f[i]]+1。想知道每一层所有节点的序列数，就用sum不断清零、累加。每个节点的序列总和便是answer.

代码

const int N=1e6+10;
int n,a[N],f[N],d[N],g[N],mod=998244353;//f:父节点，d:结点深度,g:某节点的序列总数
void solve()
{int ans=1,sum=0;//ans 答案，sum 每层总和cin>>n;vector<int> v[n+5];//存放某层结点fir(i,2,n){cin>>f[i];//输入结点i的父节点d[i]=d[f[i]]+1;//深度=父节点+1v[d[i]].push_back(i);//结点i存入d[i]层if(f[i]==1) ans++,g[i]=1,sum++;}for(int i=2;v[i].size();i++){for(int x:v[i]){g[x]=sum,g[x]=(g[x]-g[f[x]]+mod)%mod;//该结点的序列数=上一层-父节点ans=(ans+g[x])%mod;}sum=0;for(int x:v[i]) sum=(sum+g[x])%mod;//计算该层总序列}cout<<ans<<'\n';return ;
}

注意：减法取模，需要+mod，防止出现负数