C++小白训练第七天
以下为牛客挑战
今日收获
回顾了二分答案了,对于一个确定的答案的区间，我们可以直接进行二分答案就行了while(l<r){int mid=l+r>>1;if(check(mid)){r=mid;}else{l=mid+1;}}可以用for(int i=1;i<=n;i++){cin>>s[i];if(s[i]==s[i-1]){pr[i]=pr[i-1];}else{pr[i]=i-1;}}处理一段连续区间最后a[i]个数相同的个数。
j=i-s[i]+1
牛客小白月赛127
Flower_Rainbow_and_You
A-Flower_Rainbow_and_You_牛客小白月赛127
1 2 3 4 5 6 7
Violet
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);string s[7] = {"Red", "Orange", "Yellow", "Green", "Blue", "Indigo", "Violet"};int m=0;int ma=-1;for(int i=0,x;i<7;i++){cin>>x;if(x>ma){m=i;ma=x;}}cout<<s[m]<<endl;return 0;
}
Flower_Rainbow_and_Rhythm
B-Flower_Rainbow_and_Rhythm_牛客小白月赛127
4 3
1 1 4 4
Yes
这题我们只需要统计个数就行了，每个mod的接结果统计一下，如果不是偶数就肯定不行
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,k;cin>>n>>k;vector<int>m(N,0);for(int i=0,x;i<n;i++){cin>>x;m[x%k]++;}for(int i=0;i<N;i++){if(m[i]%2!=0){cout<<"No"<<endl;return 0;}}cout<<"Yes"<<endl;return 0;
}
Flower_Rainbow_and_Wave
C-Flower_Rainbow_and_Wave_牛客小白月赛127
4
1
3
9
18
-1
1 2 1
1 2 3 4 5 4 3 2 1
1 2 1 1 2 3 2 1 1 2 1 1 2 3 4 3 2 1
这个我们发现，对于一般的奇数来说一定可以。
然后偶数的话可化简为3+一个奇数。除来，2，4
对于一个奇数
1-（a+1）/2 ----1
对于一个数，如果是偶数，
1 2 1 剩下的按奇数的来
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];
void solve(){int n;cin>>n;if(n==1||n==2||n==4){cout<<"-1"<<endl;return;}if(n%2==0){cout<<"1 2 1 ";n-=3;}for(int i=1;i<=(n+1)/2;i++){cout<<i<<" ";}for(int i=n/2;i>=1;i--){cout<<i<<" ";}cout<<endl;};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}
Flower_Rainbow_and_Balloon
二分答案
D-Flower_Rainbow_and_Balloon_牛客小白月赛127
6
1 1 2
r
1 1 2
y
1 1 2
w
3 0 5
ryy
6 1 2
yyyywy
5 5 11
wwwww
1
1
1
3
1
-1
我们直接二分答案如下图
我们可以用一个前缀数组来记录前面到底有多少个r，和y，那显然就可以得到w的个数，且我们可以有便于算出这个东西价值。
实现check函数，因为我们二分答案枚举了区间，所以我们只要枚举左端点，那么右断点就自然得到了，然后，贪心一下，判断到底哪种方案最优，把价值全部加起来最后得到看看能不能满足条件
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];
void solve(){int n,m,k;cin>>n>>m>>k;string s;cin>>s;s=' '+s;vector<int>pr(n+1),py(n+1);for(int i=1;i<=n;i++){pr[i]=pr[i-1]+(s[i]=='r');py[i]=py[i-1]+(s[i]=='y');}auto check=[&](int mid)->bool {for(int l=1;l<=n-mid+1;l++){int r=l+mid-1;int sum=0;int mr=pr[r]-pr[l-1];int my=py[r]-py[l-1];sum+=max(mr*2+my,my*2+mr);sum+=min(m,mid-mr-my)*2;if(sum>=k) return true;}return false;};int l=1,r=n;//二分答案；while(l<r){int mid=l+r>>1;if(check(mid)){r=mid;}else{l=mid+1;}}int ans=l;if(!check(l))ans=-1;cout<<ans<<endl;};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}
牛客周赛 Round 122
Block Array
E-Block Array_牛客周赛 Round 122
2
6
1 2 2 3 3 3
7
1 2 2 1 3 1 1
6
9
这是就是dp计数
f[i]-->以i结尾的好数字个数，pr维护一个连续区间，相同个数的集合
解题代码
#include<bits/stdc++.h>
#define int long long
#define lll __uint128_t
#define PII pair<int ,int>
#define endl '\n'
using namespace std;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
#define REP(i, e) for (int i = 0; i < (e); ++i)
#define REP1(i, s, e) for (int i = (s); i <=(e); ++i)
#define TESTS int t; cin >> t; while (t--)
#define TEST
const int N=2e5+10,M=1e3+10,mod=1e9+7;
int a[N],b[N],c[N],pre[N];
void solve(){int n;cin>>n;vector<int>pr(n+1),f(n+1);vector<int>s(n+1);//预处理一下连续相同的个数。for(int i=1;i<=n;i++){cin>>s[i];if(s[i]==s[i-1]){pr[i]=pr[i-1];}else{pr[i]=i-1;}}int ans=0;for(int i=1;i<=n;i++){int j=i-s[i]+1;//表示我这一段有多少个相同的aiif(j>pre[i]){f[i]+=f[j-1]+1;//转移是加上上一个以j为后缀的}ans+=f[i];}cout<<ans<<endl;};
signed main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);TESTS{solve();};return 0;
}