首页 > 代码库 > 2017-7-22 Noip模拟（gryz）
2017-7-22 Noip模拟（gryz）
Digits
(digits.cpp/c/pas)
Description
给一个关于 的多项式，并给定一个 ，求该多项式在带入该 时的值最后 位数字。
Input
第一行两个整数 、 ；
之后的 行，每行两个数 和 ，表示多项式的一项 ；
最后一行一个整数 。
Output
输出 行，按顺序输出该多项式带入 后值的最后 位数字，若不足 位，则高位补零。
Example
digits.in digits.out
2 1
3 2
1 5
3
0
附加样例见选手目录下『digits』文件夹。
Hint
对于 的数据， ；
对于 的数据， 。
/* 要求后k位，实际上就是对10^k取模，用快速幂*/#include<iostream>#include<cstdio>#include<cmath>#include<cstring>long long n,k,a[100010],b[100010],X,tmp[10],mod,ans,Ans[10];using namespace std;long long Pow(long long x,long long t){ long long res=1; while(t){ if(t&1) res=x*res%mod; x=x*x%mod; t>>=1; } return res;}int main(){ freopen("digits.in","r",stdin); freopen("digits.out","w",stdout); scanf("%lld%lld",&n,&k); for(long long i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]); scanf("%lld",&X); mod=1; for(long long i=1;i<=k;i++)mod*=10; X%=mod; for(long long i=1;i<=n;i++){ long long now=((a[i]%mod)*Pow(X,b[i]))%mod; ans+=now; } for(long long i=1;i<=k;i++){ Ans[i]=ans%10; ans/=10; } for(long long i=k;i>=1;i--)cout<<Ans[i]<<endl; fclose(stdin); fclose(stdout); return 0;}
Equation
(equation.cpp/c/pas)
Description
求方程 在 内有多少组正整数解。
Input
一行七个整数 。
Output
一行一个整数，原方程有多少正整数解。
Example
equation.in equation.out
10 -24 74 -25 22 -7 -22 5
附加样例见选手目录下『equation』文件夹。
Hint
对于 的数据，方程无解；
对于 的数据， ；
对于 的数据， 。
/* a1x1-a2x2+a3x3-a4x4+a5x5-a6x6=0 方程可化为 a1x1-a2x2+a3x3=a4x4-a5x5+a6x6 通过映射匹配，2n^3跑得过 */#include<iostream>#include<cstring>#include<cstdio>#include<map>using namespace std;map<int,int>b;int a[7],K,ans;int main(){ freopen("equation.in","r",stdin); freopen("equation.out","w",stdout); scanf("%d",&K); bool flag1,flag2; for(int i=1;i<=6;i++){ scanf("%d",&a[i]); if(a[i]>0)flag1=1; if(a[i]<0)flag2=1; }; a[2]=-a[2];a[4]=-a[4];a[6]=-a[6]; if(flag1!=flag2){ printf("0"); return 0; } for(int i=4;i<=6;i++)a[i]=-a[i]; int now; for(int i=1;i<=K;i++) for(int j=1;j<=K;j++) for(int k=1;k<=K;k++){ now=a[1]*i+a[2]*j+a[3]*k; b[now]++; } for(int i=1;i<=K;i++) for(int j=1;j<=K;j++) for(int k=1;k<=K;k++){ now=a[4]*i+a[5]*j+a[6]*k; ans+=b[now]; } printf("%d",ans); fclose(stdin); fclose(stdout); return 0;}
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<cstdio>#include<iostream>#include<algorithm>using namespace std;struct node{ int from,to,v;}e[200010];int fa[7510],m,n,k;bool cmp(node x,node y){ return x.v<y.v;}int find(int x){ if(fa[x]==x)return x; return fa[x]=find(fa[x]);}bool connect(int x,int y){ int f1=find(x),f2=find(y); if(f1==f2)return 0; fa[f1]=f2; return 1;}int main(){ freopen("graph.in","r",stdin); freopen("graph.out","w",stdout); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].v); sort(e+1,e+m+1,cmp); bool flag=false;int tot=0; for(int i=1;i<=m;i++){ if(connect(e[i].from,e[i].to))tot++; if(find(1)==find(n)){ printf("%d",e[i].v); flag=true; break; } if(tot==n-1)break; } if(!flag)printf("-1"); fclose(stdin); fclose(stdout); return 0;}
2017-7-22 Noip模拟（gryz）