2024 China Collegiate Programming Contest (CCPC) Zhengzhou Onsite 基础题题解

今天先发布基础题的题解，明天再发布铜牌题和银牌题的题解

L. Z-order Curve

 思路：这题目说了，上面那一行，只有在偶数位才有可能存在1，那么一定存在这样的数，0 ,1,100, 10000,那么反之，我们的数列是行的二倍，因此会出现10,1000,100000这样的数，因此，就可以发现，其实组成的数也是由二进制数递推的，因此我们可以从高位到低位逐步去找，如果相同且为1就变成0，如果不同就直接结束，输出L即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int l,r;
void solve()
{cin>>l>>r;for(int i=61;i>=0;i--){int bitl=(l>>i)&1;int bitr=(r>>i)&1;if(bitl==bitr&&bitl==1){l-=(1LL<<i);r-=(1LL<<i);}else if(bitl!=bitr){cout<<l<<"\n";return ;}}
}
signed main()
{cin>>t;while(t--){solve();}return 0;
}

F. Infinite Loop

 思路：这题有一个比较恶心的地方，就是说从1小时开始，实际上是从0小时开始计算，然后我们去计算公差是多少，我们现将所有的bi加在一起为sum，然后取sum和k的较大值作为公差，然后去对题目进行分析，我们会发现，从第二天开始，就去进行等差数列了，因此我们只需要计算出来第一天和第二天在什么时候完成即可，还有一个特判就是要对小时特判，如果小时是0，那么天数-1，小时+k

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,q;
int a[200005];
int b[200005];
int ans1[200005];
int ans2[200005];
int d;
int flag,x;
signed main()
{cin>>n>>k>>q;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];a[i]-=1;d+=b[i];}d=max(d,k);int t=0;for(int i=1;i<=n;i++){ans1[i]=max(t,a[i])+b[i];t=ans1[i];}for(int i=1;i<=n;i++){a[i]+=k;}for(int i=1;i<=n;i++){ans2[i]=max(t,a[i])+b[i];t=ans2[i];}for(int i=1;i<=q;i++){cin>>flag>>x;if(flag==1){int day=ans1[x]/k;int hour=ans1[x]%k; if(hour==0){day-=1;hour+=k;}cout<<day+1<<" "<<hour<<"\n";}else{int time=ans2[x]+(flag-2)*d;int day=time/k;int hour=time%k; if(hour==0){day-=1;hour+=k;}cout<<day+1<<" "<<hour<<"\n";}}return 0;
}

B. Rolling Stones

思路：很板的一个广搜，只需要找到翻转之后，每个面上面是什么就可以了，同时要确保翻转的时候翻转过去的面，等于那个底面上的值

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[205][205];
struct node{int x,y;int qian;int zuo;int you;int di;int tmp;
};
deque<node> q;
int vis[205][205];
int ans[205][205];
int fx,fy;
void bfs()
{while(!q.empty()){node test=q.front();q.pop_front();int x=test.x;int y=test.y;
//		cout<<x<<" "<<y<<"\n";
//		cout<<test.qian<<" "<<test.zuo<<" "<<test.you<<" "<<test.di<<"\n";if(y%2==0){if(vis[x][y-1]==0&&y-1>=1&&y-1<=2*x-1&&a[x][y-1]==test.zuo)//向左移动{vis[x][y-1]=1;q.push_back((node){x,y-1,test.you,test.qian,test.di,test.zuo,test.tmp+1});ans[x][y-1]=test.tmp+1;} if(vis[x][y+1]==0&&y+1>=1&&y+1<=2*x-1&&a[x][y+1]==test.you)//向右移动{vis[x][y+1]=1;q.push_back((node){x,y+1,test.zuo,test.di,test.qian,test.you,test.tmp+1});ans[x][y+1]=test.tmp+1;} if(vis[x-1][y-1]==0&&y-1>=1&&y-1<=2*(x-1)-1&&x-1>=1&&x-1<=n&&a[x-1][y-1]==test.qian)//向上移动{vis[x-1][y-1]=1;q.push_back((node){x-1,y-1,test.di,test.zuo,test.you,test.qian,test.tmp+1});ans[x-1][y-1]=test.tmp+1;}}else{if(vis[x][y-1]==0&&y-1>=1&&y-1<=2*x-1&&a[x][y-1]==test.zuo)//向左移动{vis[x][y-1]=1;q.push_back((node){x,y-1,test.you,test.qian,test.di,test.zuo,test.tmp+1});ans[x][y-1]=test.tmp+1;} if(vis[x][y+1]==0&&y+1>=1&&y+1<=2*x-1&&a[x][y+1]==test.you)//向右移动{vis[x][y+1]=1;q.push_back((node){x,y+1,test.zuo,test.di,test.qian,test.you,test.tmp+1});ans[x][y+1]=test.tmp+1;} if(vis[x+1][y+1]==0&&y+1>=1&&y+1<=2*(x+1)-1&&x+1>=1&&x+1<=n&&a[x+1][y+1]==test.qian)//向下移动{vis[x+1][y+1]=1;q.push_back((node){x+1,y+1,test.di,test.zuo,test.you,test.qian,test.tmp+1});ans[x+1][y+1]=test.tmp+1;}}}
}
signed main()
{cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=2*i-1;j++){cin>>a[i][j];}}cin>>fx>>fy;if(fx==1&&fy==1){cout<<0<<"\n";return 0;}q.push_back((node){1,1,2,1,3,4,0});vis[1][1]=1;bfs();if(ans[fx][fy]==0){cout<<"-1\n";}else{cout<<ans[fx][fy]<<"\n";}return 0;
}

 M. Rejection Sampling

 思路：这题一开始看起来其实是有点儿乱的，不知道在说什么，而且也不知道到底要操作什么，但是仔细阅读后会发现，那个S的概率就是C(n,k)*pi^k+(1-pi)^(n-k),若想要满足题目中的S与ai乘正比的话，我们需要满足pi/(1-pi)与ai成正比，我们可以将比例系数C设为c，因此我们可以得到式子

pi/(1-pi)=c*ai;

可以得到pi=c*ai/(1+c*ai),可知，pi关于c单调递增

c=pi/((1-pi)*ai)，我们可以去二分c然后去判断pi的和是否是k

然后就解决了

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, k;
long double a[100005];  
bool check(long double c) 
{long double ans=0;long double x;for(int i=1;i<=n;i++) {x =(c*a[i])/(1.00+c*a[i]);ans+=x;}return ans<=k;
}
signed main() 
{cin>>n>>k;for (int i=1;i<=n;i++) {cin>>a[i];}long double l=0.0;long double r=1e15;for (int i=1;i<=200;i++) {long double mid=(l+r)/2;if (check(mid)) {l=mid;} else {r=mid;}}cout<<fixed<<setprecision(10);for (int i = 1;i<=n;i++) {cout<<(long double)(l*a[i])/(1.00+l*a[i])<<"\n";}return 0;
}