牛客练习赛100
B.小红的子序列(dp)
子序列问题一般是dp问题，这里结尾dp状态只有四种，蓝偶，红偶，蓝奇，红奇。对于当前物品，所要做的判断就是加与不加入状态完全相反的背包中，例如，当前是蓝色偶数，现在就要判断加不加到当前以红色奇数为结尾的数组中，状态方程：
f[c[i][a[i]&1]=max(f[c[i]][a[i]&1],f[1-c[i]][1-(a[i]&1)]+(LL)a[i]);
// Problem: 小红的子序列
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11251/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long LL;
const int N=2e5+10;
int a[N],n;
string col;
int c[N];
LL f[2][2];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
cin>>col;
for(int i=0;i<n;i++){
c[i+1]=(col[i]=='R');
}
for(int i=1;i<=n;i++){
f[c[i]][a[i]&1]=max(f[c[i]][a[i]&1],f[1-c[i]][1-(a[i]&1)]+(LL)a[i]);
}
LL ans=0;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
ans=max(f[i][j],ans);
// cout<<f[i][j]<<" ";
}
}
printf("%lld",ans);
return 0;
}
C.小红的删数字
题目链接
先将
- 数学题，博弈论，小红先手且要保证删去一个位数后还是3的倍数，假设所有位数之和为s，则必须删除一个sum%3的一位，否则肯定失败。
- 接下来就是a[sum%3]--，问题转换为小紫先手了，此时如果a[1]和a[2]相等,且没有a[0]那么小红必胜
- 否则就是小红必败
// Problem: 小红的删数字
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11251/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long LL;
const int N=2e5+10;
int a[3];
int sum=0;
string s;
int main(){
cin>>s;
int len=s.length();
for(int i=0;i<len;i++){
if(s[i]-'0'){
a[(s[i]-'0')%3]++;
}
sum+=s[i]-'0';
}
if(!a[sum%3]) puts("yukari");
else{
a[sum%3]--;
if(a[1]==a[2]&&a[0]) puts("kou");
else puts("yukari");
}
return 0;
}
D. 小红的构造题
题目链接
考虑数列re……re……re……re…………
对于每个在第k个re后添加一个d,那么共添加 \(\sum_{i=1}^k\)x*i(i+1)/2 个子序列，将上列式子化简可得k个re总共可有x*k(k+1)*(k+2)个red子序列，其中x为添加几个d
这样枚举复杂度降到了n1/3 可以枚举(但是有个疑问怎么证明这样可以包含所有整数呢？)
// Problem: 小红的构造题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11251/D
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long LL;
const int N=2e5+10;
LL n;
LL ned[N];
int main(){
cin>>n;
// if(!n) {puts("d"); return 0;}
LL i,j;
for(i=1;i*i*i/6<=n;i++);
i--;
for(j=i;j>0;j--){
ned[j]+=n/(j*(j+1)/2);
n%=j*(j+1)/2;//剩余还要构造的字符串数量
}
for(j=1;j<=i;j++){
cout<<"re";
while(ned[j]--){
cout<<"d";
}
}
return 0;
}