当前位置：首页 > news >正文

房地产新闻头条/百度seo公司电话

news 2025/7/4 2:20:27

房地产新闻头条,百度seo公司电话,广东米可信息技术有限公司,在线设计图纸T1小凯的疑惑小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币&…

T1小凯的疑惑

小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。

Solution

2017数论题，感觉是历史以来最难的一道。

对于ax+by=c(a>=0,b>=0)当方程无解是，必定为x<0&&y>0且下一组解x>0&&y<0那x为-1，y为a-1，那c就是a*b-a-b。

Code

#include<iostream>
#include<algorithm>
using namespace std;long long a,b;
int main(){cin>>a>>b;cout<<a*b-a-b;}

T2时间复杂度

题面太长不粘了

模拟题，注意细节。。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,vis[1009],tag,tag2,n,ans,num,tot,s[109],st[109],top,maxx=10000000,yy,zz;
char c,cc[109],x,y[10],z[10];
int main()
{cin>>t;while(t--){memset(vis,0,sizeof(vis));scanf("%d",&n);tag=tag2=tot=num=ans=top=0;cin>>cc;        int p=strlen(cc);if(cc[2]=='n')for(int j=4;j<=p;++j)if(cc[j]>='0'&&cc[j]<='9') num=num*10+cc[j]-'0';else break;   for(int i=1;i<=n;++i){cin>>c;if(c=='F'){cin>>x>>y>>z;yy=zz=0;if(vis[x])tag=1;vis[x]=1;s[++top]=x;if(y[0]!='n'){int o=strlen(y);for(int k=0;k<o;++k)yy=yy*10+y[k]-'0';}else yy=maxx;if(z[0]!='n'){int o=strlen(z);for(int k=0;k<o;++k)zz=zz*10+z[k]-'0';}else zz=maxx;if(yy<maxx&&zz==maxx){st[top]=1;tot++;}elseif(yy>zz){st[top]=-1;tag2++;}else{st[top]=0;}if(!tag2)ans=max(ans,tot);}else{if(!top)tag=1;    if(st[top]==1)tot--;else if(st[top]==-1)tag2--;vis[s[top]]=0;top--;}}if(top||tag){cout<<"ERR\n";continue;}if(ans==num)cout<<"Yes\n";else cout<<"No\n";}return 0;
}

T3逛公园

T4奶酪

现有一块大奶酪，它的高度为

现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道，在不破坏奶酪的情况下，能否利用已有的空洞跑到奶酪的上表面去?

$，可以把上界和下界都看成一个点，n^2并查集搞一下就可以了。$

#include<iostream>
#include<cstdio>
#include<cmath>
#define N 1012
using namespace std;
int n,t,f[N];
double h,r;
struct ssd{double x,y,z;
}a[N];
double calc(int i,int j){return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z));
}
int find(int x){return f[x]=f[x]==x?x:find(f[x]);} 
int main(){scanf("%d",&t);while(t--){scanf("%d%lf%lf",&n,&h,&r);for(int i=0;i<=n+1;++i)f[i]=i;for(int i=1;i<=n;++i){scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z);for(int j=1;j<i;++j)if(calc(i,j)<=r*2){int xx=find(i),yy=find(j);if(xx!=yy)f[xx]=yy;}if(a[i].z-r<=0){int xx=find(i),yy=find(0);if(xx!=yy)f[xx]=yy;}if(a[i].z+r>=h){int xx=find(i),yy=find(n+1);if(xx!=yy)f[xx]=yy;}}if(find(0)==find(n+1))printf("Yes\n");else printf("No\n");}return 0;
}

T5宝藏

如果我们设dp[s]表示当前选择集合为s时的最小代价，这个状态是有问题的，说不好听点它压根就是错的，因为它压根就没有考虑每个节点的深度。

我们可以这么考虑问题，我们以深度作为阶段，每次从当前选择集合中扩展一些点作为第i层。

这时我们就可以设计状态了，令dp[i][s]表示当前深度做到了i，当前选择集合为s时的最优方案。

转移时可以枚举扩展出哪些点，然后直接转移。

这样的复杂度是3^n*n^2。

但这样太慢，可以利用lowbit等技巧优化常数

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 13
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int dp[N][1<<N],n,m,x,y,l,e[N][N],ji[1<<N],f[1<<N],b[N],tag[N],be[1<<N],ans;
inline int rd(){int x=0;char c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return x;
}
int main(){n=rd();m=rd();memset(e,0x3f,sizeof(e));for(int i=1;i<=m;++i){x=rd();y=rd();l=rd();e[x][y]=e[y][x]=min(e[x][y],l);}memset(dp,0x3f,sizeof(dp));for(int i=0;i<n;++i)ji[1<<i]=i,dp[0][1<<i]=0;ans=inf;ans=min(ans,dp[0][(1<<n)-1]);for(int i=1;i<=n;++i)for(int s=1;s<(1<<n);++s){int top=0;memset(b,0x3f,sizeof(b));for(int j=1;j<=n;++j)if(!(s&(1<<j-1))){tag[top]=1<<j-1;for(int S=s;S;S-=(S&-S))if(e[j][ji[S&-S]+1]!=inf)b[top]=min(b[top],e[j][ji[S&-S]+1]*i);top++;}for(int j=1;j<(1<<top);++j){f[j]=f[j-(j&-j)]+b[ji[j&-j]];if(f[j]>=inf)f[j]=inf;be[j]=be[j-(j&-j)]|tag[ji[j&-j]];dp[i][s|be[j]]=min(dp[i][s|be[j]],dp[i-1][s]+f[j]);    }ans=min(ans,dp[i][(1<<n)-1]);}printf("%d",ans);return 0;
}

T6列队

Solution

观察到最后一列很特殊，考虑分开维护。

对于每行的前m-1个点开线段树，里面记个size有表示这个位置没人。

那么整体向做移动怎么维护？

其实不用管它，毕竟对于前m-1列只会从后面插入。

那么对于一颗线段树，我们的操作只有从后面插入一个节点，从集合删去一个节点和查找第K个元素。

在最后一列开线段树，操作时分类讨论一下。

注意：n和m不要弄反，初始化size要为m-1不是m！！！

Code

#include<iostream>
#include<cstdio>
#define N 300002
using namespace std;
typedef long long ll;
int size[N],T[N],tot,q;
long long x,y,n,m;
struct node{ll first;bool second;};
struct seg{ll num;int l,r,sum;}tr[N*20];
node find(int &cnt,int l,int r,int k){if(!cnt)cnt=++tot;tr[cnt].sum++;if(l==r){if(tr[cnt].num)return node{tr[cnt].num,0};else return node{l,1};}int mid=(l+r)>>1,num=mid-l+1-tr[tr[cnt].l].sum;if(num>=k)return find(tr[cnt].l,l,mid,k);else return find(tr[cnt].r,mid+1,r,k-num);
} 
void add(int &cnt,int l,int r,int x,ll y){if(!cnt)cnt=++tot;if(l==r){tr[cnt].num=y;return;}int mid=(l+r)>>1;if(mid>=x)add(tr[cnt].l,l,mid,x,y);else add(tr[cnt].r,mid+1,r,x,y);
}
inline int rd(){int x=0;char c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();return x;
}
int main(){n=rd();m=rd();q=rd();for(int i=1;i<=n;++i)size[i]=m-1;//caresize[n+1]=n;for(int i=1;i<=q;++i){x=rd();y=rd();if(y==m){node tmp=find(T[n+1],1,n+q,x);ll num=tmp.first;if(tmp.second)num=num*m;printf("%lld\n",num);add(T[n+1],1,n+q,++size[n+1],num);}else{node tmp=find(T[x],1,m+q,y);ll num=tmp.first;if(tmp.second)num=num+(x-1)*m;printf("%lld\n",num);tmp=find(T[n+1],1,n+q,x);ll num2=tmp.first;if(tmp.second)num2=num2*m;add(T[x],1,m+q,++size[x],num2);add(T[n+1],1,n+q,++size[n+1],num);}}return 0;
}