1. 给定长为n的序列a，$a_i$的元素均为$[0,10^9]$内的整数。计算
$\sum_{i=1}^n[i \equiv 1(mod2)] \sum _{1 \leq j\leq n}^{i|j} a_j$
对$10^9+7$取模后的值。其中[P]当命题P为真时值为1,否则值为0。
#include<cstdio>
#include <vector>
const int mod=1e9+7;
std::vector <int>vec;
inline int inc(int x,int y)
{ x+=y-mod;return x+(x>>31 & mod);}
inline int mul(int x,int y) {return 1ll*x*y%mod;}
int main()
{
int n;
scanf ("%d",&n);
vec.push_back(0);
for (int i=1;i<=n;++i)
{
int x;
scanf ("%d",&x) ;
vec.push_back(x);
}
int ans=0;
for (int i=1;i<=n;++i)
if(i&1)
for (int j=i;j<=n;j+=i)
ans=inc(ans,mul(vec[i],vec[j]));
printf ("%d\n",ans);
return 0;
}
判断题
1) (1分) vec.push_back(x)的含义为向容器vec的尾部插入元素x。( )
2) (1分) 对于0≤i≤2^31-1,语句 i&1 的含义与i mod 2等价。( )
3) 该程序需要注意运算时可能超出int类型所能容纳的最大数据的风险。( )
4) inc(x，y)的含义为返回(x+y) mod(10*+7)的值(0<=x,y<10^9+7)。( )
选择题
5) (3分)该算法的时间复杂度为( )。
6) 下列说法错误的是( )。
2.
#include<bits/stdc++.h>
const int N=1e6+50;
int n, m, min[N],out[N],f[N],siz[N],ans;
struct edge
{
int u, v, w;
} e[N];
inline int find(int x)
{
while (x!=f[x])
x=f[x]=f[f[x]];
return x;
}
inline void merge(int x,int y)
{
if (siz[x]>siz[y]) std::swap(x,y);
f[x]=y;
}
int main()
{
scanf ("%d%d", &n, &m);
for (int i=1; i<=n; ++i)
{
f[i]=i,siz[i]=1;
}
for (int i=1; i<=m; ++i)
{
scanf ("%d%d%d", &e[i].u,&e[i].v,&e[i].w);
}
int components=n;
while (components>1)
{
memset (min,0x3f,sizeof (min));
for (int i=1; i<=m; ++i)
{
int u=find(e[i].u),v=find(e[i].v),w=e[i].w;
if (u!=v)
{
if (w<min[u]) min[u]=w,out[u]=v;
if (w<min[v]) min[v]=w,out[v]=u;
}
}
for (int i=1; i<=n; ++i)
{
int x=find(i) ;
if (out[x])
{
int y=find(out[x]);
if (x!=y)
{
merge(x,y);
--components;
ans+=min[x];
}
}
}
}
printf("%d",ans);
return 0;
}
提示:该程序的输入为一张n个点m条边的连通无向图。输入格式为:
输入的第一行包含两个整数 n,m(1≤n≤m≤100)。
接下来一行，包含三个整数u,v,w(1≤u,v≤n,1≤w≤100)。
判断题
1) (1分)该程序实现了用于求无向图G=(V,E)的最小生成树的算法。( )
2) (1分)程序中使用了邻接矩阵来存储图G=(V,E)。( )
3) 为了确保该算法的结果符合预期输入需要保证所有的w互不相同。( )
4) 对于任意合法的输入，该程序一定会在有限步内返回结果。( )
选择题
5) 变量components在运行过程中可达到的最小值为( )。
6) 该程序的时间复杂度为( ) 。
3.
#include<bits/stdc++.h>
const int N=2e6+50;
int n, head[N], nxt[N], ver[N], dep[N],prv[N],suc[N],cnt;
inline void add(int u, int v)
{
nxt[++cnt] =head[u], ver[cnt]=v, head[u]=cnt;
}
void dfs (int u, int fa)
{
dep[u]=dep[fa]+1;
for(int i=head[u]; i; i=nxt[i])
if (ver[i] !=fa) dfs(ver[i],u);
}
void solve(int u,int fa,bool rv=false)
{
int isLeaf=true,t=u;
for (int i=head[u]; i; i=nxt[i])
{
int y=ver[i];
if (y !=fa)
{
isLeaf= false;
solve(y,u,rv ^ 1);
if (rv)
{
int mp=prv[y];
suc[t]=y,prv[y]=t,t=mp;
}
else
{
suc[t]=suc[y];
prv[suc[y]]=t;
suc[t=y]=0;
}
}
}
if (isLeaf) suc[u] =prv[u]=u;
else suc[t]=u,prv[u]=t;
}
int main()
{
scanf ("%d", &n) ;
for (int i=1,u,v; i<n; ++i)
{
scanf ("%d%d",&u,&v);
add(u,v) ; add(v,u) ;
}
dfs (1,1) ; solve(1,-1);
printf("1 ");
int p=1,v=suc[p];
while (v !=p)
{
printf ("%d ",v) ;
v=suc[v];
}
return 0;
}
提示：该程序的输入为一张n个点的连通图。
判断题
1) (1分)由程序的建图方式，可以猜测输入的图G为一棵树。( )
2) 函数dfs(int, int)用于计算每个节点的深度，并存储至数组dep[]。( )
3) 函数solve()通过广度优先搜索，在树T上构造了一条路径。( )
4) (2分)程序将输出一个大小为n的排列。( )
选择题
5) 该程序读入以下数据后，输出结果为( )。8 \1 2 \2 3 \3 4\4 5\4 6\4 7\7 8
6) (5分)该程序对于给定的图G，构造出另一个图G'，并在G'上构造某条特殊的路径。记dg(u,v)为图G中u,v两点的距离，则有关G'(V',E')的构造方法与找出的路径的说法,正确的为( )