C
这题很多人挂掉了 （
其实纯暴力就行，全排列枚举 看数字的顺序，记录这一行看到的上一个数字是什么，以及这一行已经看了那几个数字。按题意统计所有情况中 不会失望的个数即可。
#include<bits/stdc++.h>
using namespace std;
int arr[5][5];
int main(){
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
cin>>arr[i][j];
}
}
int p[9]={1,2,3,4,5,6,7,8,9};
double cnt=0;
double all=0;
do{
all++;
int v[5]={},h[5]={},d1=0,d2=0;
int vq[5]={},hq[5]={},d1q=0,d2q=0,f=0;
for(int i=0;i<9;i++){
// cout<<p[i]<<" ";
int posx=(p[i]-1)/3+1;
int posy=p[i]-(posx-1)*3;
// cout<<posx<<" "<<posy<<endl;
if(vq[posx]==0){
vq[posx]++;
v[posx]=arr[posx][posy];
}else if(v[posx]==arr[posx][posy]&&vq[posx]==1){
vq[posx]++;
v[posx]=arr[posx][posy];
}else if(vq[posx]==2&&v[posx]!=arr[posx][posy]){
f=1;
break;
}
if(hq[posy]==0){
hq[posy]++;
h[posy]=arr[posx][posy];
}else if(h[posy]==arr[posx][posy]&&hq[posy]==1){
hq[posy]++;
h[posy]=arr[posx][posy];
}else if(hq[posy]==2&&h[posy]!=arr[posx][posy]){
f=1;
break;
}
if(posx==posy&&d1q==0){
d1q++;
d1=arr[posx][posy];
}else if(posx==posy&&d1==arr[posx][posy]&&d1q==1){
d1q++;
d1=arr[posx][posy];
}else if(posx==posy&&d1q==2&&d1!=arr[posx][posy]){
f=1;
break;
}
if(posx+posy==4&&d2q==0){
d2q++;
d2=arr[posx][posy];
}else if(posx+posy==4&&d2==arr[posx][posy]&&d2q==1){
d2q++;
d2=arr[posx][posy];
}else if(posx+posy==4&&d2q==2&&d2!=arr[posx][posy]){
f=1;
break;
}
}
// cout<<endl;
if(f){
cnt+=1.0;
}
}while(next_permutation(p,p+9));
printf("%.9lf",1.0-cnt/all);
return 0;
}
D
首先要发现一个结论，如果宽 格能行，那么 格也能行，因为只需要在 格方案的基础上把新增的格子都放空就行了。
然后我们就可以二分答案了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int arr[200005];
int N,M,all=0;
bool ck(int md){
int s=1,c=-1;
for(int i=1;i<=N;i++){
if(arr[i]>md){
return false;
}
if(c+arr[i]+1<=md){
c=c+arr[i]+1;
}else{
c=arr[i];
s++;
}
}
return s<=M;
}
signed main(){
cin>>N>>M;
for(int i=1;i<=N;i++){
cin>>arr[i];
all+=arr[i]+1;
}
int l=1,r=all,ans=1;
while(l<=r){
int mid=(l+r)/2;
if(ck(mid)){
r=mid-1;
ans=mid;
}else{
l=mid+1;
}
}
cout<<ans<<endl;
return 0;
}
E
首先直到出发时间可以在 复杂度得到到达时间。但是询问次数太多了。
然后可以发现，如果第一辆公交每隔 分钟发车，第二辆每隔 分钟发车，那么第 分钟和第 分钟出发途中时间是一样的。
题目保证了 ，所以我们只用计算 的最小公倍数以内的途中路程就可以了，然后询问的时候把出发时间对 的最小公倍数取模得到途中时间，再把出发时间加上就行了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int P[100005],T[100005];
int N,X,Y,mxp=0;
int ans[40325];
int calc(int tim){
int la=tim;
tim+=X;
for(int i=1;i<N;i++){
if(tim%P[i]==0){
tim+=T[i];
}else{
tim+=T[i]+P[i]-tim%P[i];
}
}
tim+=Y;
return tim-la;
}
signed main(){
scanf("%lld%lld%lld",&N,&X,&Y);
for(int i=1;i<N;i++){
scanf("%lld%lld",&P[i],&T[i]);
mxp=max(mxp,P[i]);
}
int qp=840;
for(int i=0;i<qp;i++){
ans[i]=calc(i);
}
int q;
scanf("%lld",&q);
while(q--){
int qi;
scanf("%lld",&qi);
printf("%lld\n",qi+ans[qi%qp]);
}
return 0;
}
共 1 条回复
qp