首页 > 代码库 > 2017-0722 模拟赛
2017-0722 模拟赛
Digits
(digits.cpp/c/pas)
Description
给一个关于 的多项式，并给定一个 ，求该多项式在带入该 时的值最后 位数字。
Input
第一行两个整数 、 ；
之后的 行，每行两个数 和 ，表示多项式的一项 ；
最后一行一个整数 。
Output
输出 行，按顺序输出该多项式带入 后值的最后 位数字，若不足 位，则高位补零。
Example
digits.in digits.out
2 1
3 2
1 5
3
0
附加样例见选手目录下『digits』文件夹。
Hint
对于 的数据， ；
对于 的数据， 。
1 #include <algorithm> 2 #include <cstdio> 3 4 using namespace std; 5 6 #define LL long long 7 const int N(100005); 8 LL n,k,x,a[N],b[N]; 9 LL tot,mod=1;10 int ans[10];11 12 LL Qpow(LL a,LL b)13 {14 LL ret=1,base=a;15 for(;b;b>>=1)16 {17 if(b&1) ret=(ret*base)%mod;18 base=(base*base)%mod;19 }20 return ret;21 }22 23 void read(LL &x)24 {25 LL ch=getchar();x=0;26 for(;ch>‘9‘||ch<‘0‘;) ch=getchar();27 for(;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) x=ch-‘0‘+x*10;28 }29 30 int main()31 {32 freopen("digits.in","r",stdin);33 freopen("digits.out","w",stdout);34 read(n); read(k);35 for(int i=1;i<=n;i++) read(a[i]),read(b[i]);36 read(x);37 for(int i=1;i<=k;i++) mod*=10;38 for(int i=1;i<=n;i++) tot=(tot%mod+a[i]%mod*Qpow(x,b[i])%mod)%mod;39 for(int i=k;i&&tot;i--) ans[i]=tot%10,tot/=10;40 for(int i=1;i<=k;i++) printf("%d\n",ans[i]);41 return 0;42 }
Equation
(equation.cpp/c/pas)
Description
求方程 在 内有多少组正整数解。
Input
一行七个整数 。
Output
一行一个整数，原方程有多少正整数解。
Example
equation.in equation.out
10 -24 74 -25 22 -7 -22 5
附加样例见选手目录下『equation』文件夹。
Hint
对于 的数据，方程无解；
对于 的数据， ；
对于 的数据， 。
1 #include <algorithm> 2 #include <cstdio> 3 #include <map> 4 5 using namespace std; 6 7 #define LL long long 8 int k,a[7],ans; 9 LL tot,cx[666*666];10 map<LL,LL>ma;11 12 int main()13 {14 freopen("equation.in","r",stdin);15 freopen("equation.out","w",stdout);16 scanf("%d",&k);17 for(int i=1;i<=6;i++) scanf("%d",a+i);18 for(int x=1;x<=k;x++)19 for(int y=1;y<=k;y++)20 for(int z=1;z<=k;z++)21 {22 tot=a[1]*x+a[3]*y+a[5]*z;23 ma[tot]++;24 }25 for(int x=1;x<=k;x++)26 for(int y=1;y<=k;y++)27 for(int z=1;z<=k;z++)28 {29 tot=a[2]*x+a[4]*y+a[6]*z;30 ans+=ma[tot];31 }32 printf("%d",ans);33 return 0;34 }
Graph
( graph .cpp/c/pas)
Description
小 Y 又开始了一段旅途。
这次，他要经过一个图，从 号点到达 号点，每个点设有休息站。
小 Y 计划用最多 天走完全程，除第 天外，每一天小 Y 都必须在休息站过夜。所以，一段路
必须在同一天走完。
小 Y 的体力有限，他希望走的路程最大的一天中走的路尽可能少，请求出这个最小值。
Input
第一行三个整数 、 、 表示图的顶点数、边数、天数。
从第二行开始，之后的 行，每行三个整数 、 、 表示从 和 间有一条双向道路，长度
为 。
Output
一行一个正整数，如果小 Y 能走完全程，输出走的路程最大的一天中走的路程最小值，否则输
出 。
Example
graph.in graph.out
3 2 4
3 2 4
1 2 1
4
附加样例见选手目录下『graph』文件夹。
Hint
对于 的数据， ；
对于 的数据， ；
对于 的数据， ， ， ；
保证没有重边和自环。
1 #include <algorithm> 2 #include <cstdio> 3 4 using namespace std; 5 6 const int M(200005); 7 const int N(7555); 8 int n,m,k,u,v,w,ans=-1; 9 void read(int &x) 10 { 11 int ch=getchar();x=0; 12 for(;ch>‘9‘||ch<‘0‘;) ch=getchar(); 13 for(;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) x=ch-‘0‘+x*10; 14 } 15 16 int head[N],sumedge; 17 struct Edge 18 { 19 int v,next,w; 20 Edge(int v=0,int next=0,int w=0): 21 v(v),next(next),w(w){} 22 }edge[N<<1]; 23 void ins(int u,int v,int w) 24 { 25 edge[++sumedge]=Edge(v,head[u],w); 26 head[u]=sumedge; 27 } 28 struct E 29 { 30 int u,v,w; 31 E(int u=0,int v=0,int w=0): u(u),v(v),w(w){} 32 }road[M]; 33 bool cmp(E a,E b) 34 { 35 return a.w<b.w; 36 } 37 38 int cnt,fa[N]; 39 int find(int x) 40 { 41 return x==fa[x]?x:fa[x]=find(fa[x]); 42 } 43 bool K() 44 { 45 for(int i=1;i<=m;i++) 46 { 47 int u=road[i].u,fx=find(u); 48 int v=road[i].v,fy=find(v); 49 if(fx==fy) continue; 50 cnt++; fa[fx]=fy; 51 ins(u,v,road[i].w); 52 ins(v,u,road[i].w); 53 if(cnt==n-1) return 1; 54 } 55 return 0; 56 } 57 58 int deep[N],dis[N][25],dad[N][25]; 59 void DFS(int x) 60 { 61 deep[x]=deep[dad[x][0]]+1; 62 for(int i=0;dad[x][i];i++) 63 { 64 dad[x][i+1]=dad[dad[x][i]][i]; 65 dis[x][i+1]=max(dis[x][i],dis[dad[x][i]][i]); 66 } 67 for(int i=head[x];i;i=edge[i].next) 68 { 69 int v=edge[i].v; 70 if(deep[v]) continue; 71 dad[v][0]=x; 72 dis[v][0]=edge[i].w; 73 DFS(v); 74 } 75 } 76 int LCA(int x,int y) 77 { 78 int ret=0; 79 for(int i=24;i>=0;i--) 80 if(dad[x][i]!=dad[y][i]) 81 { 82 ret=max(ret,max(dis[x][i],dis[y][i])); 83 x=dad[x][i]; y=dad[y][i]; 84 } 85 return max(ret,max(dad[x][0],dad[y][0])); 86 } 87 88 int main() 89 { 90 freopen("graph.in","r",stdin); 91 freopen("graph.out","w",stdout); 92 read(n); read(m); read(k); 93 for(int i=1;i<=m;i++) 94 { 95 read(u),read(v),read(w); 96 road[i]=E(u,v,w); 97 } 98 sort(road+1,road+m+1,cmp); 99 for(int i=1;i<=n;i++) fa[i]=i;100 if(K()||find(1)==find(n))101 DFS(1),ans=LCA(1,n);102 printf("%d",ans);103 return 0;104 }
2017-0722 模拟赛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。