Codeforces刷题题解（思维+数构+字符串）
https://codeforces.com/contest/1583/problem/B1.B. Omkar and Heavenly Tree
题意：
建一个树有n个点,n-1条边,有m个限制,a直接连b,中间不能有c。
思路：
用set先把1~n连起来,然后把中间b删去,也就是把限制都删掉,找到一个根可以连到其它所有点,然后把set的头作为根,之后所有除根以外的点都直接连上根。
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
void ZB1()
{
int n,m;
cin>>n>>m;
set<int>s;
for(int i=1;i<=n;i++)
{
s.insert(i);
}
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
s.erase(b);//找根节点的过程，存在一个点到各点都可以直接连接
}
int st=*s.begin();
for(int i=1;i<=n;i++)
{
if(i!=st)
{
cout<<st<<" "<<i<<endl;
}
}
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}
https://codeforces.com/contest/1559/problem/B2.B. Mocha and Red and Blue
题意：
给一串字符串有问号和BR,问号用B或R填充,使串中BB和RR最少（RRR有2对）
思路：
选择第一个不是问号的字符,从中间,先向后与前一个对比,再向前与后一个对比。
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
void ZB1()
{
int n;
cin>>n;
string s;
cin>>s;
//要找中间再左右两边
int idx=0;
for(int i=0;i<n;i++)
{
if(s[i]!='?')
{
idx=i;
break;
}
}
//与前面对比--->
for(int i=idx;i<n;i++)
{
if(s[i]=='?')
{
if(s[i-1]=='R')
{
s[i]='B';
}
else
{
s[i]='R';
}
}
}
//与后面对比<---
for(int i=idx;i>=0;i--)
{
if(s[i]=='?')
{
if(s[i+1]=='R')
{
s[i]='B';
}
else
{
s[i]='R';
}
}
}
cout<<s<<endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}3.C. Diluc and Kaeya
题意：
给以字符串只含D和K,求每个前缀的最大划分块数,使得每块的D:K相等。
思路：
从前往后遍历,用map<pair<int,int>,int>存每个最小D:K比例,后面枚举的只要取最大公约数使得到的比例与前面的相等,这样可以保证块数最多,注意最少一块。
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
void ZB1()
{
int n;
cin>>n;
string s;
cin>>s;
int cntk=0,cntd=0;
map<pii,int>mp;
int ans=0;
for(int i=0;i<n;i++)
{
if(s[i]=='K')
{
cntk++;
}
else cntd++;
int d=gcd(cntk,cntd);
mp[make_pair(cntk/d,cntd/d)]++;
ans=mp[make_pair(cntk/d,cntd/d)];
cout<<ans<<" ";
}
cout<<endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}
4.C. Infinite Replacement
https://codeforces.com/contest/1674/problem/C题意：
给一个字符串s只包含‘a’，再给一个字符串t（只包含小写字母），s中每个‘a’可以被t替换，可以做无数次，求共有多少个不同的字符串，若取不尽则输出-1。
思路：
（1）若t只有一个‘a’，则无论怎么替换都是本身；
（2）若t中不含‘a’，则可以把s中的‘a’，全部替换，且是有限次，可以用每一位有选和不选两种状态即为pow(2,s.size())种；
（3）若t中含‘a’，且长度大于等于2，则有无数个a可替换，故取不尽，输出-1.
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
void ZB1()
{
string s;
string t;
cin>>s>>t;
int n=s.size();
int a=t.find("a");
if(t=="a")cout<<1<<endl;
else if(a==-1)cout<<(ll)pow(2,s.size())<<endl;//选择或者不选
else
{
cout<<-1<<endl;//有a长度大于等于2
}
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}5.D. Vertical Paths
https://codeforces.com/contest/1675/problem/D题意：
给一棵树且已知根，求最少的路径使其覆盖所有的点。
思路：
用邻接表来存储树，vector<int>ans[N]来存储答案即每条路径上的点，使用dfs(u,flag)u表示当前点，flag确定要不要开出一条新的路径(0不开/1开)，临时变量t=0dfs到底(在同一条路径)后返回t=1.
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
const int M=2e5+10;
int e[M],ne[2*M],h[2*M],idx;
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
vector<int>ans[M];
int n,root,cnt;
void dfs(int u,int flag)
{
if(!flag)ans[cnt].push_back(u);
else ans[(++cnt)].push_back(u);//开新路径
int t=0;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
dfs(j,t);//一条到底t都为0,之后return时,枚举第二及之后的子节点会(t=1)开新路径
t=1;
}
}
void ZB1()
{
cin>>n;
idx=cnt=0;
for(int i=1;i<=n;i++)h[i]=-1;//不能用memset超时
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(x==i)root=i;
else add(x,i);//i为x的子节点
}
dfs(root,0);//0表示根
cout<<cnt+1<<endl;
for(int i=0;i<=cnt;i++)
{
cout<<ans[i].size()<<endl;
for(auto u:ans[i])
{
cout<<u<<" ";
}
cout<<endl;
ans[i].clear();
}
cout<<endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}6.E. Price Maximization
https://codeforces.com/contest/1690/problem/E题意：
给n件商品，n为偶数，可以分成n/2包，每包两个，每个包的重量x=ai+aj，给定k，求每个x的x/k下取整之和并让其最大。
思路：
ans先加上每个a[i]/k，然后a[i]=a[i]%k，之后再将a[i]进行升序排列，然后才用双指针的形式(i是头j是尾)，找到a[i]+a[j]>=k答案就加一（因为已经取%了只能最多贡献1），找的时候可以移动前面的i，可以保证尽量多的得到答案贡献。
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
void ZB1()
{
ll n,k;
cin>>n>>k;
vector<ll>a(n);
ll ans=0;
for(ll i=0;i<n;i++)
{
cin>>a[i];
ans+=(a[i]/k);
a[i]%=k;
}
sort(sall(a));//从小到大
for(ll i=0,j=n-1;i<j;i++,j--)
{
while(a[i]+a[j]<k&&i<j)i++;
if(i==j)break;
ans++;
}
cout<<ans<<endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}7.D. Black and White Stripe
https://codeforces.com/contest/1690/problem/D题意：
给长度为n的字符串，只包括B和W，给定k，求最小将W转换为B的操作次数使得字符串中有连续长为k的序列B。
思路：
利用前缀和的思想，用prew[i]记录当前第i位及之前有多少个W，接着从头往后枚举每k个的段要操作的W的个数，取最小值即ans=min(ans,prew[i]-prew[i-k])，i从k开始。(prew的下标从1开始到n）
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
void ZB1()
{
int n,k;
cin>>n>>k;
string s;
cin>>s;
vector<int>prew(n+1);
int w=0;//记录W的前缀和(有多少个W)
for(int i=0;i<n;i++)
{
if(s[i]=='W')w++;
prew[i+1]=w;
}
int ans=k;
//从头往后每k个枚举要操作W的个数，取最小值
for(int i=k;i<=n;i++)
{
ans=min(ans,prew[i]-prew[i-k]);
}
cout<<ans<<endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}8.B. Array Decrements
https://codeforces.com/contest/1690/problem/B题意：
给定两个长度为n的序列a和b，可以对a序列进行每个ai都减一的操作，若ai=0则不变，问能否通过对a序列进行任何次数这个操作使得a与b相等。
思路：
直接1~n进行枚举，若a[i]<b[i]则肯定不行，当a[i]>=b[i]时，对b[i]是否为0进行分类，如果b[i]为0则更新maxx(maxx是a[i]减为0的最大值）；如果b[i]不为0则更新map。因为map里面存的差值a[i]和b[i]都不为0，若map里的差值不止一个，则也肯定不行。最后再判断maxx是否大于map里的唯一差值，如果大于则不行，否则就行。
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
void ZB1()
{
int n;
cin>>n;
vector<int>a(n);
vector<int>b(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int j=0;j<n;j++)
{
cin>>b[j];
}
map<int,int>m;
bool flag=1;
int maxx=0;
for(int i=0;i<n;i++)
{
if(a[i]<b[i])flag=0;
else
{
if(b[i]==0)
{
maxx=max(maxx,a[i]);
}
else
{
m[a[i]-b[i]]++;//b[i]不为0,且a[i]>=b[i]的情况
}
}
}
if(m.size()>1)flag=0;
int x=-1;
for(auto t:m)
{
x=t.first;
}
if(x!=-1&&maxx>x)flag=0;
if(!flag)N;
else Y;
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}9.E. Split Into Two Sets
https://codeforces.com/contest/1702/problem/E题意：
给集合的数量n且保证n为偶数，接着输入每个集合，每个集合有两个属于1~n的数字，问是否能把n个集合分成两个集合，使得每个集合里的每个数都不相等。
思路：
将集合里的两个数看成两个点，即把两个点这个条边连起来用二维数组vector<vector<int>>g(M)，如果出现两个点相等或者其中一个点出现三次肯定就不行，然后再对1~n每个数如果未访问过就进行一次dfs（如果未走过就加一）,dfs出的答案如果不是偶数就不行。
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
const int M=2e5+10;
vector<vector<int>>g(M);
vector<bool>vis(M);
int dfs(int u)
{
vis[u]=1;
for(auto v:g[u])
{
if(!vis[v])
{
return dfs(v)+1;
}
}
return 1;
}
void ZB1()
{
int n;
cin>>n;
bool flag=0;
//预处理
for(int i=1;i<=n;i++)
{
g[i].clear();
vis[i]=0;
}
map<int,int>m;
for(int i=1;i<=n;i++)
{
int u,v;
cin>>u>>v;
m[u]++;
m[v]++;
g[u].push_back(v);
g[v].push_back(u);
if(u==v||m[u]>2||m[v]>2)flag=1;
}
if(flag){N;return;};
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
int ans=dfs(i);
if(ans%2!=0)
{
N;
return;
}
}
}
Y;
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}10.D. Not a Cheap String
https://codeforces.com/contest/1702/problem/D题意：
给一个只含小写字母的字符串，定义这个字符串的价值为每个字母的数值之和（a=1,b=2,c=3...），再给一个数字p求删掉字符串中尽量少的字母使得剩余字符串的价值小于等于p，并输出剩余字符串。
思路：
先求出原始字符串价值sum，并用a记录每个字母出现的次数，再定义一个removed数组初始全为0，接着因为要字母删得最少且小于p也OK，所以将a数组从25~0逆序枚举，次数正序枚举，如果sum>p则removed[i]++，将i移走，更新sum=sum-（i+1），如果sum<=n及时退出循环。最后枚举字符串的每个字符，若没被移走就输出，移走就--。
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
void ZB1()
{
string s;
int n;
cin>>s>>n;
vector<int>a(26);
int sum=0;
for(int i=0;i<s.size();i++)
{
a[s[i]-'a']++;
sum+=(s[i]-'a'+1);
}
vector<int>removed(26,0);
for(int i=25;i>=0;i--)//从大到小枚举，要删得最少且小于等于n
{
for(int j=0;j<a[i];j++)
{
if(sum>n)
{
removed[i]++;
sum-=(i+1);
}
else break;//sum<=n及时退出
}
}
for(int i=0;i<s.size();i++)
{
if(!removed[s[i]-'a'])
{
cout<<s[i];
}
else
{
removed[s[i]-'a']--;
}
}
cout<<endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}11.C. Train and Queries
https://codeforces.com/contest/1702/problem/C题意：
给定一个长度为n的序列u（ui可以相等），接着进行k次询问，每次询问为a和b，问是否满足在序列u中值为a的下标小于值为为b的下标。
思路：
用两个map，mi存u[i]的初始下标，ma存u[i]最大的下标，如果mi[a]&&mi[b]即a和b的初始下标都有，且mi[a]<ma[b]且a的初始下标小于b的最大下标则OK，反之就不行。
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
void ZB1()
{
ll n,k;
cin>>n>>k;
vector<ll>a(n+1);
map<ll,int>mi,ma;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
if(mi[a[i]]==0)
{
mi[a[i]]=i;
}
ma[a[i]]=i;//若a[i]相同只会取大的下标
}
while(k--)
{
ll l,r;
cin>>l>>r;
if(mi[l]&&mi[r]&&mi[l]<ma[r])Y;
else N;
}
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}12.D. Masha and a Beautiful Tree
https://codeforces.com/contest/1741/problem/D题意：
给一个permutation序列p，p的大小是一个可以是2的次数的一个数m,序列p的m个数可以构成一个完全二叉树，其中每个pi都是一个叶子，问需要交换多少次叶子或者父节点能使p是升序序列，又或者无法做到。
思路：
首先如果两个相邻叶节点的差值不为1肯定不行，如果序列p已经是升序可以不用操作（注意is_sorted(all(p))保证的是不下降，但是可以相等，本题中相等情况已排除），接着dfs(1,n)，dfs到最底层是两个左右节点（l,r），如果p[l]>p[l+len]就交换答案加一，保证p[l]最小即可，先到底层再从底层向上，如果可以的话一定存在p[l+len]=p[l]+len（len为l与另一边l的差值）。
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
const int M=3e5+10;
int a[M];
int ans;
int n;
bool flag;
void dfs(int l,int r)
{
if(l>=r)
{
return;
}
int mid=(l+r)/2;
int len=(r-l+1)/2;
dfs(l,mid);
dfs(mid+1,r);
if(a[l]>a[l+len])
{
ans++;
swap(a[l],a[l+len]);
}
//dfs到最底层是两个左右叶子
//保证a[l]是最小的就好了
//从底层向上
//如果可以的话一定存在a[l+len]=a[l]+len
if(a[l+len]!=(a[l]+len))
{
flag=1;
}
}
void ZB1()
{
ans=0;
flag=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<n;i+=2)
{
if(abs(a[i]-a[i+1])!=1)
{
cout<<-1<<endl;
return;
}
}
if(is_sorted(a+1,a+1+n))
{
cout<<0<<endl;
return;
}
dfs(1,n);
if(flag)cout<<-1<<endl;
else cout<<ans<<endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}13.C. Minimize the Thickness
https://codeforces.com/contest/1741/problem/C题意：
给定一个含n个正数的序列a，定义厚度是将a分成每个和相等的块的最大长度，划分时要尽可能的使厚度最小，并输出最小厚度。
思路：
先求整个序列的总和ssum，接着从小到大枚举每个前缀和sum[i]，如果总和不能整除前缀就继续下一个，若能整除，则枚举j=i+1，定义一个临时求和cur，如果cur==sum[i]就更新，若大于sum[i]就直接break，继续找下一个可行的前缀和。
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
const int M=2e3+10;
int a[M];
ll sum[M];
void ZB1()
{
memset(sum,0,sizeof(sum));
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
int minv=0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
if(sum[n]%sum[i])continue;
int mx=i;//长度
int cur=0;
bool flag=1;
int pi=i+1;
for(int j=i+1;j<=n;j++)
{
cur+=a[j];
if(cur>sum[i])
{
flag=0;
break;
}
if(cur==sum[i])
{
mx=max(mx,j-pi+1);
pi=j+1;
cur=0;
}
}
if(flag)minv=min(minv,mx);
}
cout<<minv<<endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}