C 小红的循环移位
思路：
一个数是不是四的倍数，只用看最后两位是否能够整除4即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"
void solve()
{
string s;
cin>>s;
string t=s;
if(s.size()==1){
int tmp=s.back()-'0';
if(tmp%4==0) cout<<0<<endl;
else cout<<-1<<endl;
}
else{
int cnt=0;
int tmp=(s[s.size()-2]-'0')*10+s.back()-'0';
if(tmp%4==0){
cout<<cnt<<endl;
return ;
}
for(int i=0;i<s.size();i++){
cnt++;
t.push_back(s[i]);
int tmp=(t[t.size()-2]-'0')*10+t.back()-'0';
if(tmp%4==0){
cout<<cnt<<endl;
return ;
}
}
cout<<-1<<endl;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
t = 1;
// cin >> t;
while (t--)
{
solve();
}
system("pause");
return 0;
}
D 小红的好串
思路：
容易知道，好串的组成一定是类似于多个连续的 r r r 和多个连续的 e e e 和多个连续的 d d d 组成，且这三部分的长度尽可能相同，但由于 r − l + 1 r-l+1 r−l+1 会出现不能整除三的情况，所以无法判断余数应该放在哪一部分最合适，所以暴力的去跑余数处于哪个部分即可。最后考虑如何快速查询，使用前缀和预处理出区间信息即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 998244353;
const int maxv = 4e6 + 5;
#define endl "\n"
void solve()
{
int n,q;
cin>>n>>q;
vector<int> sr(n+5),se(n+5),sd(n+5);
string s;
cin>>s;
s=" "+s;
for(int i=1;i<=n;i++){
sr[i]=sr[i-1]+(s[i]=='r');
se[i]=se[i-1]+(s[i]=='e');
sd[i]=sd[i-1]+(s[i]=='d');
}
while(q--){
int l,r;
cin>>l>>r;
int ans=r-l+1;
int len=r-l+1;
if(len<3){
cout<<0<<endl;
continue;
}
vector<int> p;
int x=len%3,len1,len2,len3;
if(x==0){
len1=len/3,len2=len/3,len3=len/3;
}
else if(x==1){
len1=len/3+1,len2=len/3,len3=len/3;
}
else len1=len/3+1,len2=len/3+1,len3=len/3;
p.push_back(len1),p.push_back(len2),p.push_back(len3);
sort(p.begin(),p.end());
do{
int res=0,c1=0,c2=0;
for(int i=0;i<3;i++){
if(i==0){
c1=l,c2=c1+p[i]-1;
res+=c2-c1+1-(sr[c2]-sr[c1-1]);
}
else if(i==1){
c1=l+p[i-1],c2=c1+p[i]-1;
res+=c2-c1+1-(se[c2]-se[c1-1]);
}
else{
c1=l+p[i-1]+p[i-2],c2=r;
res+=c2-c1+1-(sd[c2]-sd[c1-1]);
}
}
ans=min(ans,res);
}while(next_permutation(p.begin(),p.end()));
cout<<ans<<endl;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
t = 1;
// cin >> t;
while (t--)
{
solve();
}
system("pause");
return 0;
}
E,F 小红的树上赋值
思路：
首先把每个红色子树的独立块给处理出来，什么叫独立块，即，对于每一个以红色节点为根的子树而言，其内部没有任何的红色节点，这样祖宗节点的红色子树赋值不会影响他的子节点。
进而考虑如何赋值，我们可以使用一个
s
u
m
sum
sum 记录当前总和，若总和大于 0 ，则给当前节点赋
r
r
r ，若小于 0 ，则赋值
l
l
l，最后再进行动态调整即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"
int n;
string s;
vector<int> e[N];
void add(int u,int v)
{
e[u].push_back(v);
e[v].push_back(u);
}
vector<int> c[N];
int ans[N];
void dfs(int x,int fa,int last)
//last参数必须传在函数中，不能开在全局，因为孩子中若存在红色节点则会直接进行更新，无法处理出独立块了
{
if(s[x]=='R') last=x;
c[last].push_back(x);
for(auto u: e[x]){
if(u!=fa) dfs(u,x,last);
}
}
void solve()
{
int l,r;
cin>>n>>l>>r;
cin>>s;
s=" "+s;
for(int i=1;i<=n-1;i++){
int u,v;
cin>>u>>v;
add(u,v);
}
dfs(1,-1,0);
for(auto u :c[0]) ans[u]=r>abs(l)? r: l;
for(int i=1;i<=n;i++){
if(s[i]=='R'){
ll sum=0;
for(auto x :c[i]){
if(sum>=0){
sum+=l;
ans[x]=l;
}
else{
sum+=r;
ans[x]=r;
}
}
if(sum>0){
for(auto x: c[i]){
if(ans[x]>0){
if(sum>=r){
ans[x]=0,sum-=r;
}
else{
ans[x]-=sum;
break;
}
}
}
}
else if(sum<0){
for(auto x: c[i]){
if(ans[x]<0){
if(sum<=l){
ans[x]=0,sum-=l;
}
else{
ans[x]-=sum;
break;
}
}
}
}
}
}
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
t = 1;
// cin >> t;
while (t--)
{
solve();
}
system("pause");
return 0;
}
