最水的一次模拟赛。。
T1
求最后K位
那前面的数是没有比要求的 ，
我们就把 10k 作为模数 ，对答案进行取模 就好了
#include <ctype.h> #include <cstdio> #define N 100005 typedef 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 ",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 85005 using 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 "); 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 ",LCA.lca(1,n)); } else { printf("-1 "); return 0; } return 0; }