首页 > 代码库 > 2017 7.22 模拟赛
2017 7.22 模拟赛
最水的一次模拟赛。。
点击查看题目
T1
求最后K位
那前面的数是没有比要求的 ，
我们就把 10k 作为模数 ，对答案进行取模 就好了
#include <ctype.h>#include <cstdio>#define N 100005typedef long long LL;void read(LL &x){ x=0;bool f=0; register char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch==‘-‘) f=1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-‘0‘; x=f?(~x)+1:x;}LL Ans,x,a[N],b[N],n,k,m=1;int ans[11];LL qpow(LL a,LL b){ LL base=a,r=1%m; for(;b;b>>=1) { if(b&1) r=(r*base)%m; base=base*base%m; } return r%m;}int main(){ freopen("digits.in","r",stdin); freopen("digits.out","w",stdout); read(n); read(k); for(int i=1;i<=k;i++) m*=10; for(int i=1;i<=n;i++) read(a[i]),read(b[i]); read(x); for(int i=1;i<=n;i++) Ans=(Ans+(qpow(x,b[i])*a[i]%m))%m; for(int i=k;i>=1&&Ans;Ans=Ans/10,i--) ans[i]=Ans%10; for(int i=1;i<=k;i++) printf("%d\n",ans[i]); return 0;}
T2
求满足条件的x值
移项之后用三重循环把左边能取到的值计数，
这里会取到负数 于是本弱鸡使用了map。
最后三重循环求右边的取值 ，
累加结果
#include <ctype.h>#include <cstdio>#include <map>typedef long long LL;using namespace std;map<LL,int>Q;void read(LL &x){ x=0; bool f=0; register char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch==‘-‘) f=1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-‘0‘; x=f?(~x)+1:x;}LL ans,k,A[7];int main(){ freopen("equation.in","r",stdin); freopen("equation.out","w",stdout); read(k); for(int i=1;i<=6;i++) { read(A[i]); if(i%2==0) A[i]=(~A[i])+1; } for(int i=4;i<=6;i++) A[i]=(~A[i])+1; for(int a=1;a<=k;a++) for(int b=1;b<=k;b++) for(int c=1;c<=k;c++) { LL d=a*A[1]+b*A[2]+c*A[3]; Q[d]++; } for(int o=1;o<=k;o++) for(int p=1;p<=k;p++) for(int q=1;q<=k;q++) { LL r=o*A[4]+p*A[5]+q*A[6]; ans=ans+Q[r]; } printf("%d",ans); return 0;}
T3
k>=n 所以每天一条边
走的路程最大的一天中走的路尽可能少
所以就建一棵最小生成树 ，同班大佬都看出了最小编瓶颈生成树，本弱鸡没有。。
然后我就只能弱弱的跑了LCA 。。
但还是过了 。
#include <algorithm>#include <ctype.h>#include <cstdio>#define N 85005using namespace std;struct E{ int x,y,z; bool operator<(E a)const { return z<a.z; }}e[N];struct Edge{ int next,v,dist; Edge (int next=0,int v=0,int dist=0) : next (next), v (v), dist (dist) {}}edge[N<<1];int dep[N],dad[N][30],f[N][25],fa[N],head[N],cnt,n,m,k;void read(int &x){ x=0;bool f=0; register char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch==‘-‘) f=1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-‘0‘; x=f?(~x)+1:x;}int find_(int x){ return x==fa[x]?x:fa[x]=find_(fa[x]);}void insert(int u,int v,int l){ edge[++cnt]=Edge(head[u],v,l); head[u]=cnt;}class lcA{ public: void dfs(int x) { dep[x]=dep[dad[x][0]]+1; for(int i=0;dad[x][i];i++) { dad[x][i+1]=dad[dad[x][i]][i]; f[x][i+1]=max(f[dad[x][i]][i],f[x][i]); } for(int u=head[x];u;u=edge[u].next) { int v=edge[u].v; if(dad[x][0]!=v) { dad[v][0]=x; f[v][0]=edge[u].dist; dfs(v); } } } int lca(int x,int y) { int ans=0; if(dep[x]<dep[y]) swap(x,y); for(int i=25;i>=0;i--) { if(dep[dad[x][i]]>=dep[y]) { ans=max(ans,f[x][i]); x=dad[x][i]; } } if(x==y) return ans; for(int i=25;i>=0;i--) { if(dad[y][i]!=dad[x][i]) { ans=max(ans,f[y][i]); ans=max(ans,f[x][i]); x=dad[x][i]; y=dad[y][i]; } } return max(ans,max(f[y][0],f[x][0])); }};class lcA LCA;bool MST(){ int num=0; for(int i=1;i<=m;i++) { int fx=find_(e[i].x),fy=find_(e[i].y); if(fx!=fy) { fa[fy]=fx; num++; insert(e[i].x,e[i].y,e[i].z); insert(e[i].y,e[i].x,e[i].z); if(num==n-1) break; } } return num==n-1;}int main(){ freopen("graph.in","r",stdin); freopen("graph.out","w",stdout); read(n); read(m); read(k); if(m==0) { printf("-1\n"); return 0; } for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { read(e[i].x); read(e[i].y); read(e[i].z); if(e[i].x>e[i].y) swap(e[i].x,e[i].y); } sort(e+1,e+1+m); if(MST()||find_(1)==find_(n)) { LCA.dfs(1); printf("%d\n",LCA.lca(1,n)); } else { printf("-1\n"); return 0; } return 0;}
2017 7.22 模拟赛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。