赛场上只写出来ABC好伤心，其实DEF在看完官方题解时发现也不难
DEF的代码是借鉴官方题解的，指路牛客竞赛
https://ac.nowcoder.com/acm/contest/103948
A.小紫的均势博弈
地上共有n 枚石子，小红和小紫轮流操作，每次拿走一枚石子，谁先不能操作谁就输了。
小红先手操作，请问双方都采用最优策略时，谁会获得最终的胜利？
只需判断奇偶即可。
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin>>n;
if(n%2==0)cout<<"yukari";
else cout<<"kou";
}
B.小紫的劣势博弈
题目大意：n个长度的数组，小红小紫轮流操作，小红拿走元素ai，会让x加上ai，小紫则让x减上ai。
小红想让x尽可能小，小紫想让其大。 小红先手，双方都最优条件下，x为多少。
就按照题目意思来就好了，先对数组排序，再依次加减。
#include<bits/stdc++.h>
using namespace std;
int n;
long long a[100005];
long long x;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i+=2){
//if(i+1<=n)cout<<a[i]<<" "<<a[i+1]<<"\n";
if(i+1<=n)x+=(a[i]-a[i+1]);
}
if(n%2!=0)x+=a[n];
cout<<x;
}
C.小紫的01串操作
博主懒了，不写题目大意了。
这道题目不用考虑复杂，只用考虑什么情况下不能合作成功。 应该就是出现： 000 111 000 1；
我们会发现只要有邻居数字不相同，就肯定要换，那么最坏能合作情况就是邻居不相同次数为4，即：000 111 00
#include<bits/stdc++.h>
using namespace std;
int t;
int main(){
cin>>t;
while(t--){
string s;
cin>>s;
int ans=0;
for(int i=0;i<s.size();i++){
if(i){
if(s[i]!=s[i-1])ans++;
}
}
if(ans<=4)cout<<"Yes\n";
else cout<<"No\n";
}
}
D.小紫的优势博弈
首先先上代码
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int S[4];
int ans;
int main(){
cin>>n;
cin>>s;
s=' '+s;
int c1=0,c0=0;//c1表示1的奇偶性，同理c0
S[0]=1;//此时后缀为空串
for(int i=n;i>1;i--){
//if(s[i]=='0')c0^=1;
//if(s[i]=='1')c1^=1;
c0^=(s[i]=='0');
c1^=(s[i]=='1');
int now=(c0<<1)|c1;//当前状态
ans+=S[now];
S[now]=1;
}
cout<<1.0*ans/n;
}
当时比赛时没写出来，反思一下是不是没有考虑这题要ac的时间复杂度要在O(n)或者是O(nlogn),因此这说明不会涉及很难的算法。
再根据题目意思，小红先手，小紫后手，且小红随机删除前缀，计算小紫获胜的概率。
随机删除说明我们要依次判断删除不同位置前缀计算
再考虑什么情况下小紫能赢，设删除到的前缀为ai，从i+1开始我只要在能找到一个形成双生串的点就可以了
至于怎么找这个点看下方
怎么找是本题的关键！！！
1.二进制表示状态
2.后缀思想
只要我有两个不同位置的状态一致，就说明在这两个位置之内的连续子串满足题目要求
那么状态有 00 01 10 11
从后往前判断只要遇到1改变1的奇偶性，同理0
再计算出当前状态，查看后缀中有没有同状态的可能，若有ans+1，若无 S[now]=1
E.小紫的线段染色
贪心
其实不难，就是难想到，也是看来官方题解才写出来的，哭哭。
什么时候能自己写出来E和F；
首先你一看这道题会发现题意是好理解的，但是直接考虑怎么样是成功的是有难度的。
正难则反
考虑怎么样会不成功。
用a表示红，b表示紫
aaaaa
aaaaa
aaaaa
会发现无论怎么变紫色，总会有两个紫色或者红色相交
只要有一个点被覆盖了三次以上就失败
此时要考虑怎么收集一个点的被覆盖个数！！
排序
判断覆盖点：
vector<interval>a(n+1);
vector<pair<int,int>>d;
for(int i=1;i<=n;i++){
cin>>a[i].l>>a[i].r;
a[i].id=i;
d.emplace_back(a[i].l,1);
d.emplace_back(a[i].r+1,-1);
}
sort(d.begin(),d.end());
int sum=0;
for(int i=0;i<d.size();i++){
sum+=d[i].second;
if(sum>2){
cout<<-1<<"\n";
return;
}
}
用到了差分思想
如果一个线段还没结束，另一个线段又开始了，说明一定又重复！！！
完成判断后已经确定是否能成功
然后
先按照左端点排序，在左端点相同的情况下，按照右端点排序（默认从小到大） 即符号重载
struct interval{
int l,r,id;
bool operator<(const interval & in) const {
if(l==in.l){
return r<in.r;
}
return l<in.l;
}
};
排序完后
按照红紫红紫红紫的顺序记录答案
完整代码
#include<bits/stdc++.h>
using namespace std;
int n;
struct interval{
int l,r,id;
bool operator<(const interval & in) const {
if(l==in.l){
return r<in.r;
}
return l<in.l;
}
};
void solve(){
vector<interval>a(n+1);
vector<pair<int,int>>d;
for(int i=1;i<=n;i++){
cin>>a[i].l>>a[i].r;
a[i].id=i;
d.emplace_back(a[i].l,1);
d.emplace_back(a[i].r+1,-1);
}
sort(d.begin(),d.end());
int sum=0;
for(int i=0;i<d.size();i++){
sum+=d[i].second;
if(sum>2){
cout<<-1<<"\n";
return;
}
}
sort(a.begin()+1,a.end());
int r=-1,id=0;
vector<int>ans(1+n);
for(int i=1;i<=n;i++){
if(a[i].l<=r){
ans[a[i].id]=(ans[id]^1);
}
if(a[i].r>r){
r=a[i].r;
id=a[i].id;
}
}
vector<int>purple;
for(int i=1;i<=n;i++){
if(ans[i])purple.push_back(i);
}
if(purple.size()==0){
purple.push_back(1);
}
cout<<purple.size()<<"\n";
for(int i=0;i<purple.size();i++){
cout<<purple[i]<<" ";
}
}
int main(){
cin>>n;
solve();
}
F.小紫的树上染色
这题没啥好讲的，就是看到
最大值最小或者是最小值最大
要想到二分答案
#include<bits/stdc++.h>
using namespace std;
int n,k,x,y;
const int N=1e5+10;
vector<int>edge[100005];
vector<int>cnt(N);
int need;
void dfs(int u,int fa,int mid){
for(auto v :edge[u]){
if(v==fa)continue;
dfs(v,u,mid);
cnt[u]+=cnt[v];
}
if(cnt[u]+1>mid){
need++;
cnt[u]=0;
}
else{
cnt[u]++;
}
}
bool check(int mid){
need=0;
//cnt.clear();
cnt.assign(1+n,0);
dfs(1,0,mid);
return need<=k;
}
int main(){
cin>>n>>k;
for(int i=1;i<n;i++){
cin>>x>>y;
edge[x].push_back(y);
edge[y].push_back(x);
}
int l=0,r=n;
while(l<r){
int mid=(l+r)/2;
if(check(mid))r=mid;
else{
l=mid+1;
}
}
cout<<l;
}
然后清空vector数组要用assign不能用clear
京公网安备 11010502036488号