f[u][s][cnt0][cnt1]表示当前该回合轮到了谁，A手中是奇数还是偶数，偶数还剩cnt0个，奇数还剩cnt1个，如果最后的回合A手中是奇数，那么如果该回合是A的话就是A输，如果该回合是B的话就是B赢；如果A中的数是偶数，那么该回合是A的话就是A赢，是B的话就是B输。
搜索的时候去搜对方的情况，如果对方摸了一个偶数并且输了，那就是自己赢，如果对方摸了一个奇数输了，那也是自己赢，别的就都是自己输的情况了
#include<bits/stdc++.h>
#define int long long
#define endl "
"
using namespace std;
int t,n,cnt[2],f[2][2][105][105];
bool dfs(int u,int s,int cnt0,int cnt1)
{
if(cnt0+cnt1==0)
{
if(s==1)//最后A手中的数是奇数
{
if(u==0) return 0;//如果是A的回合那么就是A输
else return 1;//如果是B的回合，那么就是B赢
}
else//最后B手中的数是偶数
{
if(u==0) return 1;//如果是A的回合就是A赢
else return 0;//如果是B的回合那就是B输
}
}
if(f[u][s][cnt0][cnt1]!=-1) return f[u][s][cnt0][cnt1];
if(cnt0)
{
if(!dfs(u^1,s,cnt0-1,cnt1)) return f[u][s][cnt0][cnt1]=1;
//如果在对方的回合中对方输了，那么就是自己赢了
}
if(cnt1)
{
if(!dfs(u^1,(u==0)?(s^1):s,cnt0,cnt1-1)) return f[u][s][cnt0][cnt1]=1;
}
return f[u][s][cnt0][cnt1]=0;
}
signed main()
{
cin>>t;
while(t--)
{
cin>>n;
memset(f,-1,sizeof(f));
cnt[0]=cnt[1]=0;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
cnt[x&1]++;
}
bool flag=dfs(0,0,cnt[0],cnt[1]);
if(flag) cout<<"Alice
";
else cout<<"Bob
";
}
system("pause");
return 0;
}
当然还可以直接推出结论来，是和奇数odd的个数有关系
odd%4==0:那么A必然可以拿走偶数个奇数，必赢
odd%4==1:那么如果n是偶数，那么A赢，否则B赢，因为都不想去拿最后那个奇数，所以就要看偶数的个数了，如果偶数的个数是奇数，那么最后还是B拿走最后那个奇数，但是如果是偶数，那就是A拿走最后一个奇数，拿走最后一个奇数的就是输家
odd%4==2:A必败，最后一定会剩下两个奇数，A只能拿走1个，所以必输
odd%4==3:A必胜，因为最后剩下三个奇数，A一定会拿走2个，所以必赢
#include<bits/stdc++.h>
#define int long long
#define endl "
"
using namespace std;
int t,n,cnt[2],f[2][2][105][105];
bool dfs(int u,int s,int cnt0,int cnt1)
{
if(cnt0+cnt1==0)
{
if(s==1)//最后A手中的数是奇数
{
if(u==0) return 0;//如果是A的回合那么就是A输
else return 1;//如果是B的回合，那么就是B赢
}
else//最后B手中的数是偶数
{
if(u==0) return 1;//如果是A的回合就是A赢
else return 0;//如果是B的回合那就是B输
}
}
if(f[u][s][cnt0][cnt1]!=-1) return f[u][s][cnt0][cnt1];
if(cnt0)
{
if(!dfs(u^1,s,cnt0-1,cnt1)) return f[u][s][cnt0][cnt1]=1;
//如果在对方的回合中对方输了，那么就是自己赢了
}
if(cnt1)
{
if(!dfs(u^1,(u==0)?(s^1):s,cnt0,cnt1-1)) return f[u][s][cnt0][cnt1]=1;
}
return f[u][s][cnt0][cnt1]=0;
}
signed main()
{
cin>>t;
while(t--)
{
cin>>n;
memset(f,-1,sizeof(f));
cnt[0]=cnt[1]=0;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
cnt[x&1]++;
}
if(cnt[1]%4==0||cnt[1]%4==3) cout<<"Alice"<<endl;
else if(cnt[1]%4==1)
{
if(n&1) cout<<"Bob"<<endl;
else cout<<"Alice
";
}
else cout<<"Bob
";
}
system("pause");
return 0;
}
可以发现a中的元素都是一块一块的，要么是a[i]<=k,要么a[i]>k,可以发现0或者n+1的情况只可能出现在a数组第一块，那么可以以这个地方为切入点，而且还可以发现每一块的最后一个元素在下一块可能是有用的，如果给每个b[i]和i连一条边的话，发现只有每一块的最后一个元素是有size的，这个元素要放在这一块的最后输出
CodeforcesGlobalRound22DE-知乎
#include<bits/stdc++.h>
#define int long long
#define endl "
"
using namespace std;
int t,n,b[100005];
vector<int>g[100005];
bool cmp(int a,int b)
{
return g[a].size()<g[b].size();
}
signed main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=0;i<=n+1;i++) g[i].clear();
vector<int>ans;
int k=0;
for(int i=1;i<=n;i++)
{
cin>>b[i];
if(b[i]>i) k++;
g[b[i]].push_back(i);
}
for(int i=0;i<=n+1;i++) sort(g[i].begin(),g[i].end(),cmp);
if(g[0].size()) ans.push_back(0);
else ans.push_back(n+1);
while(ans.size()<n+1)
{
int u=ans.back();
for(int v:g[u]) ans.push_back(v);
}
cout<<k<<endl;
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
cout<<endl;
}
system("pause");
return 0;
}
D-Walker二分
其实只要管两种大情况就可以了：两个人反向走走到各自的端点后在对着走，两个人对着走一直走到各自的端点；
然后每种情况对于一个人来说有两种选择，拿p1来举例，p1可以走到自己的端点，然后还有时间的话就再向p2的端点走去；p1如果走到0还有时间的话，它还可以先向p2的点走看看最大能走多远，然后再走回p1
#include <bits/stdc++.h>
#define endl "
"
using namespace std;
const long double eps=1e-7;
long double n,p1,v1,p2,v2;
bool qk1(long double mid)
{
long double l1,r1;
long double t1=p1/v1;
if(mid-t1>=eps)
{
l1=0;
r1=max(p1,v1*(mid-t1));
long double tt1=(mid-t1)/2;
r1=max(r1,p1+v1*tt1);
r1=min(r1,n);
}
else l1=p1-mid*v1,r1=p1;
long double l2,r2;
long double t2=(n-p2)/v2;
if(mid-t2>=eps)
{
r2=n;
l2=min(p2,n-v2*(mid-t2));
long double tt2=(mid-t2)/2;
l2=min(l2,p2-v2*tt2);
l2=max(l2,(long double)0.0);
}
else l2=p2,r2=p2+mid*v2;
if(l2-r1>eps) return 0;
long double l=min(l1,l2),r=max(r1,r2);
if(l<=eps&&abs(n-r)<=eps) return 1;
else return 0;
}
bool qk2(long double mid)
{
long double l1,r1;
long double t1=(n-p1)/v1;
if(mid-t1>=eps)
{
r1=n;
l1=min(p1,n-(mid-t1)*v1);
long double tt1=(mid-t1)/2;
l1=min(l1,p1-tt1*v1);
l1=max(l1,(long double)0.0);
}
else l1=p1,r1=p1+mid*v1;
long double l2,r2;
long double t2=p2/v2;
if(mid-t2>=eps)
{
l2=0;
r2=max(p2,(mid-t2)*v2);
long double tt2=(mid-t2)/2;
r2=min(r2,p2+tt2*v2);
r2=min(r2,n);
}
else l2=p2-mid*v2,r2=p2;
if(l2-r1>eps) return 0;
long double l=min(l1,l2),r=max(r1,r2);
if(l<=eps&&abs(n-r)<=eps) return 1;
else return 0;
}
bool check(long double mid)
{
if(qk1(mid))
{
return 1;
}if(qk2(mid))
{
return 1;
}
return 0;
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int t;cin>>t;
while(t--)
{
cin>>n>>p1>>v1>>p2>>v2;
if(p1>p2)
{
swap(p1,p2);
swap(v1,v2);
}
long double l=0,r=1e18,ans;
while(r-l>=eps)
{
long double mid=(l+r)/2;
if(check(mid)) ans=mid,r=mid;
else l=mid;
}
l+=1e-8;
cout<<fixed<<setprecision(12)<<ans<<endl;
}
system("pause");
return 0;
}
文章为作者独立观点，不代表观点
相关文章
股民评论