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++; } else if(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奶酪
现有一块大奶酪，它的高度为 hh，它的长度和宽度我们可以认为是无限大的，奶酪 中间有许多 半径相同 的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中， 奶酪的下表面为z = 0z=0，奶酪的上表面为z = hz=h。
现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐 标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别 地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果 一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。
位于奶酪下表面的 Jerry 想知道，在 不破坏奶酪 的情况下，能否利用已有的空洞跑 到奶酪的上表面去?
#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宝藏
参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 n 个深埋在地下的宝藏屋， 也给出了这 n 个宝藏屋之间可供开发的m 条道路和它们的长度。
小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远， 也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路 则相对容易很多。
小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某 个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。
在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路 所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。
新开发一条道路的代价是：
L代表这条道路的长度，K代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。
请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代 价最小，并输出这个最小值。
Solution
看到n非常小，考虑直接暴力枚举每个起点，设dp[S]表示挖到的集合为S的最小花费，记忆化搜索即可，每次枚举集合里的一个点和一个新点（非常暴力对不对）。
Code
#include<iostream> #include<cstring> #include<cstdio> #define inf 0x7f7f7f7f using namespace std; int dis[20],l[20][20],n,m,a,b,c; long long dp[1<<12],ans; void dfs(int S) { for(int u=1;u<=n;++u) if(S&(1<<(u-1))) for(int v=1;v<=n;++v) if(!(S&(1<<(v-1)))&&l[u][v]!=inf&&dp[S|1<<(v-1)]>dp[S]+dis[u]*l[u][v]) { dp[S|(1<<(v-1))]=dp[S]+dis[u]*l[u][v]; dis[v]=dis[u]+1; dfs(S|(1<<(v-1))); dis[v]=inf; } } int main() { scanf("%d%d",&n,&m); memset(l,0x7f,sizeof(l)); for(int i=1;i<=m;++i) { scanf("%d%d%d",&a,&b,&c); l[a][b]=min(l[a][b],c); l[b][a]=l[a][b]; } ans=0x7f7f7f7f; for(int i=1;i<=n;++i) { memset(dis,0x7f,sizeof(dis)); memset(dp,0x7f,sizeof(dp)); dp[1<<(i-1)]=0; dis[i]=1; dfs(1<<(i-1)); ans=min(ans,dp[(1<<n)-1]); //cout<<dp[(1<<n)-1]<<" "; } cout<<ans; return 0; }
T6列队
Solution
观察到最后一列很特殊，考虑分开维护。
对于每行的前m-1个点开线段树，里面记个size有表示这个位置没人。
那么整体向做移动怎么维护？
其实不用管它，毕竟对于前m-1列只会从后面插入。
在最后一列开线段树，操作时分类讨论一下。
Code
#include<iostream> #include<cstdio> #define ls tr[root].l #define rs tr[root].r #define N 300002 using namespace std; typedef long long ll; ll tot,q,T[N],t[N],m,n,x,y; ll rd(){ ll x=0;char c=getchar();while(!isdigit(c))c=getchar(); while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return x; } struct fd{ ll l,r,size,tag; }tr[6000002]; void ins(ll &root,ll l,ll r,ll x,ll y){ if(!root)root=++tot; if(l==r){ tr[root].tag=y; tr[root].size=0; return; } int mid=(l+r)>>1; if(mid>=x)ins(ls,l,mid,x,y); else ins(rs,mid+1,r,x,y); tr[root].size=tr[ls].size+tr[rs].size; } pair<ll,bool> find(ll &root,ll l,ll r,ll k,ll tag){ if(!root)root=++tot;tr[root].size++; if(l==r) if(r<=tag)return make_pair(l,1); else return make_pair(tr[root].tag,0); int mid=(l+r)>>1,cnt=(mid-l+1)-tr[ls].size; if(cnt>=k)return find(ls,l,mid,k,tag); else return find(rs,mid+1,r,k-cnt,tag); } int main(){ n=rd();m=rd();q=rd(); for(int i=1;i<=n;++i)t[i]=m-1; t[n+1]=n; for(int i=1;i<=q;++i){ x=rd();y=rd(); if(y==m){ pair<ll,bool> tmp=find(T[n+1],1,n+q,x,n);//在(n+1)棵线段树中找x大 ll ji=tmp.first; if(tmp.second)ji*=m;//乘上列 printf("%lld\n",ji); ins(T[n+1],1,n+q,++t[n+1],ji);//在这一列中插入 } else{ pair<ll,bool>tmp=find(T[x],1,m+q,y,m-1);//在x行中找y大。 ll ji=tmp.first; if(tmp.second)ji+=(x-1)*m; printf("%lld\n",ji); pair<ll,bool>tmp2=find(T[n+1],1,n+q,x,n); ll ji2=tmp2.first; if(tmp2.second)ji2*=m; ins(T[x],1,m+q,++t[x],ji2); ins(T[n+1],1,n+q,++t[n+1],ji); } } return 0; }
原文：https://www.cnblogs.com/ZH-comld/p/9607257.html