GESP-C++八级 题库
遍历计数
时间限制:1 s,内存限制:512 MB
【问题描述】
给定一棵有 n 个结点的树 T,结点依次以 1、2、……、n 标号。树 T 的深度优先遍历序可由以下过程得到:
(1)选定深度优先遍历的起点 s(1<=s<=n ),当前所在结点即是起点。
(2)若当前结点存在未被遍历的相邻结点 u 则遍历 u,也即令当前所在结点为 u 并重复这一步;否则回溯。
(3)按照遍历结点的顺序依次写下结点编号,即可得到一组深度优先遍历序。
第一步中起点的选择是任意的,并且第二步中遍历相邻结点的顺序是任意的,因此对于同一棵树 T 可能有多组不同的深度优先遍历序。
请你求出树 T 有多少组不同的深度优先遍历序。由于答案可能很大,你只需要求出答案对 10^9 取模之后的结果。
【输入描述】
第一行,一个整数 n,表示树 T 的结点数。
接下来 n - 1 行,每行两个正整数 ui、vi,表示树 T 中的一条连接结点 ui、vi 的边。
【输出描述】
输出一行,一个整数,表示树 的不同的深度优先遍历序数量对 10^9 取模的结果。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于40%的测试点,保证 1 <= n <= 8。
对于另外20%的测试点,保证给定的树是一条链。
对于所有测试点,保证 1 <= n <= 100000。
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9;
int n, deg[N], fac[N];
int pre[N], suf[N], ans;
int main() {
cin >> n;
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = 1ll * fac[i - 1] * i % mod;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
deg[u]++;
deg[v]++;
}
pre[0] = 1;
for (int i = 1; i <= n; i++)
pre[i] = 1ll * pre[i - 1] * fac[deg[i] - 1] % mod;
suf[n + 1] = 1;
for (int i = n; i; i--)
suf[i] = 1ll * suf[i + 1] * fac[deg[i] - 1] % mod;
for (int i = 1; i <= n; i++)
ans = (ans + 1ll * pre[i - 1] * fac[deg[i]] % mod * suf[i + 1]) % mod;
cout << ans << endl;
return 0;
}上学
时间限制:1 s,内存限制:512 MB
【问题描述】
C 城可以视为由 n 个结点与 m 条边组成的无向图。这些结点依次以 1、2、……、n 标号,边依次以 1、2、……、m 标号。
第 i 条边(1<=i<=m)连接编号为 ui 与 vi 的结点,长度为 li 米。
小 A 的学校坐落在 C 城中编号为 s 的结点。小 A 的同学们共有 q 位,他们想在保证不迟到的前提下,每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校,于是找到了聪明的小 A。
第 i 位同学(1<=i<=q )告诉小 A,他的家位于编号为 hi 的结点,并且他每秒能行走 1 米。请你帮小 A 计算,每位同学从家出发需要多少秒才能到达学校呢?
【输入描述】
第一行,四个正整数 n、m、s、q,分别表示 C 城的结点数与边数,学校所在的结点编号,以及小 A 同学们的数量。
接下来 m 行,每行三个正整数 ui、vi、li,表示 C 城中的一条无向边。
接下来 q 行,每行一个正整数 hi,表示一位同学的情况。
【输出描述】
共 q 行,对于每位同学,输出一个整数,表示从家出发到学校的最短时间。
【样例输入1】
【样例输出1】
【数据范围】
对于 20% 的测试点,保证 q=1。
对于另外 20% 的测试点,保证 1<=n<=500,1<=m<=500 。
对于所有测试点,保证 1<=n<=2×10^5,1<=m<=2×10^5 ,1<=q<=2×10^5 ,1<=ui、vi、hi<=n ,1<=li<=10^6 。
保证给定的图联通。
#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;
const int N = 2e5 + 5;
const int E = N << 1;
const long long oo = 1e18;
int n, m, s, q;
int h[N], to[E], nx[E], wt[E], et;
int vis[N];
long long d[N];
priority_queue <pair<long long, int>> pq;
void ae(int u, int v, int w) {
et++;
to[et] = v;
nx[et] = h[u];
wt[et] = w;
h[u] = et;
}
int main() {
scanf("%d%d%d%d", &n, &m, &s, &q);
for (int i = 1; i <= m; i++) {
int u, v, l;
scanf("%d%d%d", &u, &v, &l);
ae(u, v, l);
ae(v, u, l);
}
for (int i = 1; i <= n; i++)
d[i] = oo;
d[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto p = pq.top();
pq.pop();
int u = p.second;
if (vis[u])
continue;
vis[u] = 1;
for (int i = h[u]; i; i = nx[i])
if (d[u] + wt[i] < d[to[i]]) {
d[to[i]] = d[u] + wt[i];
pq.push({-d[to[i]], to[i]});
}
}
while (q--) {
int p;
scanf("%d", &p);
printf("%lld\n", d[p]);
}
return 0;
}割裂
时间限制:1 s,内存限制:512 MB
【问题描述】
小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n。
小杨设置了 a 个好点对 {<u1,v1>、<u2,v2>、……、<ua,va>} 和 1 个坏点对 {<bu,bv>}。一个节点能够被删除,当且仅当:
◆ 删除该节点后对于所有的 i(1<=i<=a),好点对 ui 和 vi 仍然连通;
◆ 删除该节点后坏点对 bu 和 bv 不连通。
如果点对中的任意一个节点被删除,其视为不连通。
小杨想知道,有多少个节点能够被删除。
【输入描述】
第一行包含两个正整数 n、a,含义如题面所示。
之后 n - 1 行,每行包含两个正整数 xi、yi,代表存在一条连接节点 xi 和 yi 的边。
之后 a 行,每行包含两个正整数 ui、vi,代表一个好点对 <ui,vi>。
最后一行包含两个正整数 bu、bv,代表坏点对 <bu,bv>。
【输出描述】
输出一个正整数,代表能够删除的节点个数。
【样例输入】
【样例输出】
【数据范围】
对于全部数据,保证有 。

![]()
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n, k;
vector<int> e[N];
int f[N][25], dep[N], g[N], h[N];
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1;
f[u][0] = fa;
for(int i = 1; i <= 20; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
for(auto v: e[u]) {
if(v == fa) continue;
dfs(v, u);
}
}
int lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
int t = dep[u] - dep[v];
for(int i = 0; i <= 20; i++) {
if(t & (1 << i)) u = f[u][i];
}
for(int i = 20; i >= 0; i--) {
if(f[u][i] != f[v][i])
u = f[u][i], v = f[v][i];
}
if(u == v) return u;
return f[u][0];
}
int ans;
void dfs2(int u, int fa) {
for(auto v: e[u]) {
if(v == fa) continue;
dfs2(v, u);
g[u] += g[v];
h[u] += h[v];
}
if(!g[u] && h[u]) {
ans++;
}
}
void solve() {
cin >> n >> k;
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
for(int i = 1; i <= k; i++) {
int u, v;
cin >> u >> v;
int lc = lca(u, v);
g[u]++, g[v]++, g[lc]--, g[f[lc][0]]--;
}
int u, v;
cin >> u >> v;
int lc = lca(u, v);
h[u]++, h[v]++, h[lc]--, h[f[lc][0]]--;
dfs2(1, 0);
cout << ans << '\n';
}
int main() {
solve();
}树上移动
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n ,每个节点的颜色要么是白色要么是黑色。小杨可以任意选择节点 s 和节点 t 并从节点 s 出发移动到节点 t ,移动过程中小杨不能够经过重复节点。
小杨希望自己在至多经过 k 个黑色节点的前提下,经过的总节点数尽可能多,请你帮小杨选择经过最多的节点数是多少。
输入格式
第一行包含两个正整数 n,k,代表节点数量和至多经过的黑色节点数。
第二行包含 n 个正整数 a1,a2,...,an,代表节点颜色,如果 ai=0,代表节点颜色为白色,如果 ai=1,代表节点颜色为黑色。
之后 n−1 行,每行包含两个正整数 ui,vi,代表存在一条连接节点 ui和 vi的边。
输出格式
输出一个正整数,代表最多经过的节点数。
输入样例
输入样例

对于全部数据,保证有 1≤n≤1000,0≤k≤1000,0≤ai≤1。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1010;
vector<int> g[N];
int a[N];
int n,k;
int ans;
void dfs(int x,int fa,int tot,int le){
tot+=a[x];
if(tot>k){
ans = max(ans,le);
return;
}
le++;
ans = max(ans,le);
for(int i:g[x]){
if(i!=fa){
dfs(i,x,tot,le);
}
}
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++){
dfs(i,0,0,0);
}
cout<<ans<<"\n";
}排队
时间限制:1.0 s
内存限制:512.0 MB
题目描述
小杨所在班级共有 n 位同学,依次以 1,2,...,n 标号。这 n 位同学想排成一行队伍,其中有些同学之间关系非常好,在队伍里需要排在相邻的位置。具体来说,有 m 对这样的关系( m 是一个非负整数)。当 m≥1 时,第 i 对关系 (1≤i≤m) 给出 ai,bi,表示排队时编号为 ai的同学需要排在编号为 bi的同学前面,并且两人在队伍中相邻。
现在小杨想知道总共有多少种排队方式。由于答案可能很大,你只需要求出答案对 109+7 取模的结果。
输入格式
第一行,两个整数 n,m,分别表示同学们的数量与关系数量。
接下来 m 行,每行两个整数 ai,bi,表示一对关系。
输出格式
一行,一个整数,表示答案对 109+7 取模的结果。
输入样例 1
输出样例 1
输入样例 2
输出样例 2
输入样例 3
输出样例 3
数据范围
对于 20% 的测试数据点,保证 1≤n≤8,0≤m≤10 。
对于另外 20% 的测试数据点,保证 1≤n≤103,0≤m≤1 。
对于所有测试数据点,保证 1≤n≤2×105,0≤m≤2×105。
#include <cstdio>
using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n, m;
int pre[N], suf[N];
int vis[N];
int cnt;
int ans;
int main() {
scanf("%d%d", &n, &m);
ans = 1;
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d%d", &a, &b);
if (pre[b] == a && suf[a] == b)
continue;
if (pre[b] || suf[a])
ans = 0;
pre[b] = a;
suf[a] = b;
}
for (int i = 1; i <= n; i++) {
if (vis[i])
continue;
int j = i;
while (j) {
if (vis[j] == i)
ans = 0;
if (vis[j])
break;
vis[j] = i;
j = suf[j];
}
}
for (int i = 1; i <= n; i++)
cnt += !pre[i];
for (int i = 1; i <= cnt; i++)
ans = 1ll * ans * i % mod;
printf("%d\n", ans);
return 0;
}手套配对
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有 n 对不同的手套,每对手套由左右各一只组成。
小杨想知道从中取出 m 只手套,m 只手套恰好包含 k 对手套的情况有多少种。
小杨认为两种取出的情况不同,当且仅当两种情况取出的手套中存在不同的手套(同一对手套的左右手也视为不同的手套)。
输入格式
第一行包含一个正整数 t ,代表测试用例组数。
接下来是 t 组测试用例。对于每组测试用例,一共一行。
第一行包含三个正整数n,m,k,代表手套数量,取出的手套数和目标对数。
输出格式
对于每组测试数据,输出一个整数,代表可能的情况数量对109+7 取模的结果。
输入样例
输出样例

对于全部数据,保证有1≤t≤105,1≤n≤1000,1≤m≤2×n,1≤k≤n。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+10;
const int p = 1e9+7;
#define ll long long
ll c[N][N];
ll pw[N];
int n,m,k;
void init(){
pw[0]=1;
for(int i=0;i<N;i++){
if(i)pw[i]=pw[i-1]*2%p;
for(int j=0;j<=i;j++){
if(j==0)c[i][j]=1;
else c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
}
}
}
int main(){
init();
int t;
cin>>t;
while(t--){
cin>>n>>m>>k;
if(m<2*k||m-2*k>n-k){
cout<<"0\n";
continue;
}
ll ans=c[n][k]*c[n-k][m-2*k]%p;
ans=ans*pw[m-2*k]%p;
cout<<ans<<"\n";
}
}试题名称:美丽路径
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一棵包含 n 个节点的树,节点从 1 到 n 编号,并且每个节点要么是白色,要么是黑色。
对于树上的一条简单路径(不经过重复节点的路径),小杨认为它是美丽的当且仅当路径上相邻节点的颜色均不相同。例如下图,其中节点 1 和节点 4 是黑色,其余节点是白色,路径2−1−3−4 是美丽路径,而 路径2−1−3−5 不是美丽路径(相邻节点 3 和 5 颜色相同)。

对于树上的一条简单路径,小杨认为它的长度是路径包含节点的数量。小杨想知道最长的美丽路径的长度是多少。
输入格式
第一行包含一个正整数 n ,代表节点数量。
第二行包含 n 个整数c1,c2,...,cn,代表每个节点的颜色,如果 ci=0,代表节点 i 为白色,如果ci=1,代表节点 i 为黑色。
之后 n−1 行,每行包含两个正整数ui,vi,代表存在一条连接节点ui和节点vi的边。
输出格式
输出一个整数,代表最长美丽路径的长度。
输入样例1
输出样例1
输入样例2
输出样例

对于全部数据,保证有1≤n≤105,0≤ci≤1,同时保证给出的数据构成一棵树。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<int> g[N];
int dep[N],vis[N],c[N];
int n,ans;
int dfs(int x,int fa){
vis[x]=1;
dep[x]=dep[fa]+1;
int mx = dep[x];
vector<int> tmp;
tmp.push_back(mx);
for(auto i:g[x]){
if(i==fa||c[i]==c[x])continue;
int d = dfs(i,x);
tmp.push_back(d);
mx = max(d,mx);
}
sort(tmp.begin(),tmp.end());
int m = tmp.size(),res=1;
if(m>1){
res = tmp[m - 1] + tmp[m - 2] - 2 * dep[x] + 1;
}
ans=max(ans,res);
return mx;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i];
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i,0);
}
}
cout<<ans<<"\n";
}1.定义DP[x][0/1]:x以x为根的,x颜色为(0白1黑)的最长链路节点数量
初始化:DP[x][A[x]]=1 ,DP[x][1-A[x]]=0;
2.定义Fx:穿过x的满足题目要求的最长节点数量,则Fx由以x为端点的最长链和次长链组成。
状态转移方程:
对(父亲x->孩子y A[x]为x的节点颜色)
①若A[x]=0:DP[x][0]=max(DP[x][0],DP[y][1]+1);
②若A[x]=1:DP[x][1]=max(DP[x][1],DP[y][0]+1);
在此基础上,Fx因为由最长和次长组成,因此需要在DP[x]更新前完成更新,因此:
①若A[x]=0
Fx=max(Fx,DP[x][0]+DP[y][1]);
DP[x][0]=max(DP[x][0],DP[y][1]+1);
②若A[x]=1;
Fx=max(Fx,DP[x][1]+DP[y][0]);
DP[x][1]=max(DP[x][1],DP[y][0]+1);
目标状态:Fx
最远点对
题面描述
小杨有一棵包含n个节点的树,这棵树上的任意一个节点要么是白色,要么是黑色。
小杨想知道相距最远的一对不同颜色节点的距离是多少。
输入格式
第一行包含一个正整数 n,代表树的节点数。
第二行包含n个非负整数a1,a2,...,an(对于所有的1≤i≤n,均有ai等于0或1),其中如果ai=0,则节点i的颜色为白色;如果ai=1,则节点i的颜色为黑色。
之后n-1行,每行包含两个正整数xi,yi,代表存在一条连接节点xi和yi的边。
保证输入的树中存在不同颜色的点。
输出格式
输出一个整数,代表相距最远的一对不同颜色节点的距离。
输入样例
输出样例
样例解释
相距最远的不同颜色的一对节点为节点 2 和 5。
数据范围

对于全部数据,保证有1≤n≤105,0≤ai≤1。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<int> g[N];
int col[N];
int n;
int dep[N],far[N][2];
int ans;
void dfs(int x,int fa){
dep[x]=dep[fa]+1;
far[x][col[x]]=dep[x];
for(int i:g[x]){
if(i!=fa){
dfs(i,x);
for(int j=0;j<2;j++){
if(far[x][j]!=-1&&far[i][j^1]!=-1){
ans = max(ans,far[x][j]-dep[x]+far[i][j^1]-dep[x]);
}
}
for(int j=0;j<2;j++){
far[x][j]=max(far[x][j],far[i][j]);
}
}
}
ans = max(ans,far[x][col[x]^1]-dep[x]);
}
int main(){
int n;
cin>>n;
memset(far,-1,sizeof far);
for(int i=1;i<=n;i++){
cin>>col[i];
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
cout<<ans<<"\n";
}每个结点要么黑色要么白色,需要保存结点的颜色信息。选2个颜色不同的点,可以先枚举第1个点和第2个点,求他们的距离,再求最大值。任意2点都是连通的,能够相互访问,能求出最大值。根据数据范围,能得到部分分。另一种思路就是根据树的性质,答案的2个点假设是a和b,路径会经过他们的公共祖先,距离=公共祖先到a的距离+公共祖先到b的距离。每个点视为公共祖先的话,有可能是左孩子的黑色和右孩子的白色组合,也可能是左孩子的白色和右孩子的黑色组成,也可能只在左孩子或者右孩子中。所以,每个结点应该保留2种颜色的最远值。一次深搜即可。每个点访问1次,时间复杂度是O(n)。
空间跳跃
题面描述
小杨在二维空间中有n个水平挡板,并且挡板之间彼此不重叠,其中第i个挡板处于水平高度hi,左右端点分别位于li 与 ri。
小杨可以在挡板上左右移动,当小杨移动到右端点时,如果再向右移动会竖直掉落,从而落到下方第一个挡板上,移动到左端点时同理。小杨在挡板上每移动1个单位长度会耗费 1个单位时间,掉落时每掉落1 个单位高度也会耗费 1个单位时间。
小杨想知道,从第 s个挡板上的左端点出发到第t个挡板需要耗费的最少时间是多少?
注意:可能无法从第 s个挡板到达到第 t个挡板。
输入格式
第一行包含一个正整数n ,代表挡板数量。
第二行包含两个正整数s,t ,含义如题面所示。
之后 n行,每行包含三个正整数li,ri,hi ,代表第 i个挡板的左右端点位置与高度。
输出格式
输出一个整数代表需要耗费的最少时间,如果无法到达则输出 -1。
输入样例
输出样例
样例范围
耗费时间最少的移动方案为,从第3个挡板左端点移动到右端点,耗费3个单位时间,然后向右移动掉落到第 2个挡板上,耗费 100000-6=99994个单位时间,之后再向右移动1个单位长度,耗费1个单位时间,最后向右移动掉落到第1个挡板上,耗费3个单位时间。共耗费 3+99994+1+3=100001个单位时间。
数据范围

对于全部数据,保证有1≤n≤1000,1≤li≤ri≤105,1≤hi≤105。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
struct edge {
int v, w;
edge() {
}
edge(int vv,int ww) {
v=vv;
w=ww;
}
};
struct node {
int dis, u;
node () {
}
node (int diss,int uu) {
dis=diss;
u=uu;
}
bool operator>(const node& a) const {
return dis > a.dis;
}
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node> > q;
int cnt;
void dijkstra(int s) {
for (int i=1;i<=cnt;i++)dis[i]=INT_MAX;
dis[s] = 0;
q.push(node(0, s));
while (!q.empty()) {
int u = q.top().u;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push(node(dis[v], v));
}
}
}
}
map<pair<int,int>,int> mp;
vector<int> es[2010];
int l[maxn],r[maxn],h[maxn];
int main() {
int n;
cin>>n;
int s,t;
cin>>s>>t;
for (int i=1;i<=n;i++) {
cin>>l[i]>>r[i]>>h[i];
mp[make_pair(l[i],h[i])]=i;
mp[make_pair(r[i],h[i])]=n+i;
es[i].push_back(i);
es[i].push_back(n+i);
e[i].push_back(edge(n+i,r[i]-l[i]));
e[n+i].push_back(edge(i,r[i]-l[i]));
}
cnt=2*n+1;
for (int i=1;i<=n;i++) {
int hh = -1,idx = i;
for (int j=1;j<=n;j++) {
if(i==j)continue;
if(l[j]<=l[i]&&l[i]<=r[j]&&h[j]<=h[i]) {
if(h[j]>hh) {
hh=h[j];
idx=j;
}
}
}
if(hh!=-1) {
if(!mp[make_pair(l[i],hh)]) {
mp[make_pair(l[i],hh)]=cnt++;
}
int v = mp[make_pair(l[i],hh)];
e[i].push_back(edge(v,h[i]-hh));
e[idx].push_back(edge(v,abs(l[i]-l[idx])));
e[n+idx].push_back(edge(v,abs(l[i]-r[idx])));
e[v].push_back(edge(idx,abs(l[i]-l[idx])));
e[v].push_back(edge(n+idx,abs(l[i]-r[idx])));
es[idx].push_back(v);
}
hh = -1,idx = i;
for (int j=1;j<=n;j++) {
if(i==j)continue;
if(l[j]<=r[i]&&r[i]<=r[j]&&h[j]<=h[i]) {
if(h[j]>hh) {
hh=h[j];
idx=j;
}
}
}
if(hh!=-1) {
if(!mp[make_pair(r[i],hh)]) {
mp[make_pair(r[i],hh)]=cnt++;
}
int v = mp[make_pair(r[i],hh)];
e[n+i].push_back(edge(v,h[i]-hh));
e[idx].push_back(edge(v,abs(r[i]-l[idx])));
e[n+idx].push_back(edge(v,abs(r[i]-r[idx])));
e[v].push_back(edge(idx,abs(r[i]-l[idx])));
e[v].push_back(edge(n+idx,abs(r[i]-r[idx])));
es[idx].push_back(v);
}
}
dijkstra(s);
int ans = INT_MAX;
for (auto i:es[t]) {
ans=min(ans,dis[i]);
}
if(ans!=INT_MAX)cout<<ans<<"\n"; else cout<<"-1\n";
}发现n的数据范围是1000,求的是从1个挡板到另外1个挡板。注意,掉到目标挡板中的某个位置即可。同时1个挡板左端到右端或者右端到左端算距离,其他挡板的2个端点只要能垂直相交到下一个挡板(中间没有其他挡板阻碍),也算相连。将这些端点和相交点看成结点,相连看成边,整个结构就成为一张图的结构。起点是固定的,终点也是固定的(只要是目标挡板的某个点即可),求的就是最短路径。数据都是正整数,可以用dijkstra算法实现。
难点1在于建图。一个挡板左右算2个结点,要连边;一个挡板的左右两端能够垂直到其他挡板,中间不能有间隔,要连边。
难度2就是dijkstra算法的完成。按照优先队列的模板完成即可。
公倍数问题
问题描述
小 A 写了一个N×M的矩阵A,我们看不到这个矩阵,但我们可以知道,其中第i行第j列的元素Aij是i和j的公倍数(i=1,...,N,j=1,...,M)。现在有K个小朋友,其中第k个小朋友想知道,矩阵A中最多有多少个元素可以是k(k=1,2,...,K)。请你帮助这些小朋友求解。
注意:每位小朋友的答案互不相关,例如,有些位置既可能是x,又可能是y,则它同可以时满足x,y两名小朋友的要求。
方便起见,你只需要输出
即可,其中ansk表示第k名小朋友感兴趣的答案。
输入描述
第一行三个正整数N,M,K。
输出描述
输出一行,即
。
请注意,这个数可能很大,使用 C++ 语言的选手请酌情使用 long long 等数据类型存储答案。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
只有A1,1可以是1,其余都不行。
A1,1,A1,2,A2,1,A2,2都可以是2,而其余不行。
因此答案是1×1+2×4=9。
样例输入 2
样例输出 2
数据规模
对于30的测试点,保证N,M,K≤10;
对于60的测试点,保证N,M,K≤500;
对于100的测试点,保证N,M≤105,K≤106。
#include <iostream>
#include <vector>
using namespace std;
vector<int> count_divisors(int limit, int num) {
vector<int> s(num + 1, 0);
for (int i = 1; i <= limit; ++i) {
for (int j = i; j <= num; j += i) {
s[j] += 1;
}
}
return s;
}
int main() {
int N, M, K;
cin >> N >> M >> K;
vector<int> s_N = count_divisors(N, 1000000);
vector<int> s_M = count_divisors(M, 1000000);
long long result = 0;
for (int k = 1; k <= K; ++k) {
result += (long long)k * s_N[k] * s_M[k];
}
cout << result << endl;
return 0;
}接竹竿
题面描述
小杨同学想用卡牌玩一种叫做“接竹竿”的游戏。
游戏规则是:每张牌上有一个点数v,将给定的牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌点数相同的牌,则小杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列(包括这两张牌本身)。
小杨同学现在有一个长度为n的卡牌序列A,其中每张牌的点数为Ai(1≤i≤n)。小杨同学有q次询问。第i次(1≤i≤q)询问时,小杨同学会给出li,ri,小杨同学想知道如果用下标在[li,ri]的所有卡牌按照下标顺序玩“接竹竿”的游戏,最后队列中剩余的牌数。
输入格式
第一行包含一个正整数T,表示测试数据组数。
对于每组测试数据,第一行包含一个正整数n,表示卡牌序列A的长度。
第二行包含n个正整数A1,A2,...An,,表示卡牌的点数A。
第三行包含一个正整数q,表示询问次数。
接下来q行,每行两个正整数li,ri,表示一组询问。
输出格式
对于每组数据,输出q行。第i行(1≤i≤q)输出一个非负整数,表示第i次询问的答案。
样例输入
样例输入
样例解释
对于第一次询问,小杨同学会按照1,2,2的顺序放置卡牌,在放置最后一张卡牌时,两张点数为2的卡牌会被收走,因此最后队列中只剩余一张点数为1的卡牌。
对于第二次询问,队列变化情况为:
{}→{1}→{1,2}→{1,2,2}→{1}→{1,3}→{1,3,1}→{}→{3}。因此最后队列中只剩余一张点数为3的卡牌。
数据范围

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
int a[N];
int nxt[N][30],pos[20];
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
memset(pos,0,sizeof pos);
for(int i=1;i<=n;i++){
cin>>a[i];
for(int j=0;j<=20;j++)nxt[i][j]=n+1;
}
for(int i=n;i>=1;i--){
if(!pos[a[i]]){
nxt[a[i]][0]=n+1;
pos[a[i]]=i;
}else{
nxt[i][0]=pos[a[i]];
pos[a[i]]=i;
}
}
for(int i=n;i>=1;i--){
for(int j=1;j<=20;j++){
if(nxt[i][j-1]+1<=n)
nxt[i][j]=nxt[nxt[i][j-1]+1][j-1];
}
}
int q;
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
int ii=l;
int ans=0;
while(ii<=r){
while(ii<=r&&nxt[ii][0]>r){
ii++;
ans++;
}
if(ii>r)break;
for(int j=20;j>=0;j--){
if(nxt[ii][j]<=r){
ii=nxt[ii][j];
break;
}
}
ii++;
}
cout<<ans<<"\n";
}
}
}奖品分配
时间限制:1.0 s
内存限制:128.0 MB
问题描述
班上有N名同学,学号从0到N-1。有 种奖品要分给这些同学,其中,第M种奖品总共有ai个(i=0,1,…,M-1)。巧合的是,奖品的数量不多不少,每位同学都可以恰好分到一个奖品,且最后剩余的奖品不超过1个(即:N≤a0+a1+…+aM-1≤N+1)。
现在,请你求出每个班级礼物分配的方案数,所谓方案,指的是为每位同学都分配一个种类的奖品。只要有一位同学获得了不同种类的奖品,即视为不同的方案。方便起见,你只需要输出方案数对109+7取模后的结果即可。
共有T个班级都面临着奖品分配的问题,你需要依次为他们解答。
输入描述
第一行一个整数T,表示班级数量。
接下来 行,每行若干用单个空格隔开的正整数。首先是两个正整数N,M,接着是M个正整数a0,a1,…,aM-1。
保证N≤a0+a1+…+aM-1≤N+1。
输出描述
输出T行,每行一个整数,表示该班级分配奖品的方案数对109+7取模的结果。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
对于第 1 个班级,学号为0,1,2的同学可以依次分别获得奖品0,1,1,也可以依次分别获得奖品1,0,1,也可以依次分别获得奖品1,1,0,因此共有3种方案。
对于第 2 个班级,学号为0,1,2的同学可以依次分别获得奖品0,1,1,也可以依次分别获得奖品1,0,1,也可以依次分别获得奖品1,1,0,也可以依次分别获得奖品1,1,1,因此共有4种方案。
对于第 3 个班级,可以把编号为1的奖品分配给5名同学中的任意一名,共有5种方案;再把编号为2的奖品分配给剩余4名同学中的任意一名,共有4种方案;最后给剩余3名同学自然获得0号奖品。因此,方案数为5×4=20。
样例输入 2
样例输出 2
数据规模
对于30%的测试点,保证N≤10。
对于另外30%的测试点,保证M=2。
对于所有测试点,保证N≤1000;保证T≤1000;保证M≤1000。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
const int N = 1005;
const int mod = 1e9 + 7;
int C[N + 5][N + 5], a[N + 5];
void add(int &a, int b) {
a += b;
if (a >= mod)
a -= mod;
}
void init() {
C[0][0] = 1;
for (int i = 1; i <= N; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++)
C[i][j] = C[i - 1][j - 1], add(C[i][j], C[i - 1][j]);
}
}
int main() {
// freopen("data/10.in", "r", stdin);
init();
int T;
scanf("%d", &T);
while (T--) {
int n, m, sum = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d", &a[i]), sum += a[i];
int ans = 1;
for (int i = 1; i <= m; i++) {
ans = 1ll * ans * C[sum][a[i]] % mod;
sum -= a[i];
}
cout << ans << endl;
}
return 0;
}大量的工作沟通
时间限制:2.0 s
内存限制:128.0 MB
问题描述
某公司有N名员工,编号从0至N-1。其中,除了0号员工是老板,其余每名员工都有一个直接领导。我们假设编号为i的员工的直接领导是fi。
该公司有严格的管理制度,每位员工只能受到本人或直接领导或间接领导的管理。具体来说,规定员工x可以管理员工y,当且仅当x=y,或f=fy,或x可以管理fy。特别地,0号员工老板只能自我管理,无法由其他任何员工管理。
现在,有一些同事要开展合作,他们希望找到一位同事来主持这场合作,这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工,他们希望找到编号最大的员工。你能帮帮他们吗?
输入描述
第一行一个整数N,表示员工的数量。
第二行N-1个用空格隔开的正整数,依次为f1,f2…,fN-1。
第三行一个整数Q,表示共有Q场合作需要安排。
接下来Q行,每行描述一场合作:开头是一个整数m(2≤m≤N),表示参与本次合作的员工数量;接着是m个整数,依次表示参与本次合作的员工编号(保证编号合法且不重复)。
保证公司结构合法,即不存在任意一名员工,其本人是自己的直接或间接领导。
输出描述
输出Q行,每行一个整数,依次为每场合作的主持人选。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
对于第一场合作,员工3,4有共同领导2,可以主持合作。
对于第二场合作,员工2本人即可以管理所有参与者。
对于第三场合作,只有0号老板才能管理所有员工。
样例输入 2
样例输出 2
数据规模
对于25%的测试点,保证N≤50。
对于50%的测试点,保证N≤300。
对于所有测试点,保证3≤N≤105;保证Q≤100,保证m≤104。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;
const int N = 100005;
int fa[N], sz[N], dep[N], son[N], tp[N], mxId[N];
int cnt, fir[N], tar[N], nxt[N];
void link(int a, int b) { tar[++cnt] = b, nxt[cnt] = fir[a], fir[a] = cnt; }
void dfs(int x, int mxid) {
int Mx = 0;
sz[x] = 1;
mxId[x] = max(x, mxid);
for (int i = fir[x]; i; i = nxt[i]) {
dep[tar[i]] = dep[x] + 1;
dfs(tar[i], mxId[x]);
sz[x] += sz[tar[i]];
if (Mx < sz[tar[i]])
Mx = sz[son[x] = tar[i]];
}
}
void gettp(int x) {
tp[x] = x;
if (son[fa[x]] == x)
tp[x] = tp[fa[x]];
for (int i = fir[x]; i; i = nxt[i])
gettp(tar[i]);
}
int lca(int x, int y) {
while (tp[x] != tp[y])
dep[tp[x]] > dep[tp[y]] ? x = fa[tp[x]] : y = fa[tp[y]];
return dep[x] < dep[y] ? x : y;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 2; i <= n; i++)
scanf("%d", &fa[i]), link(++fa[i], i);
dfs(1, 1), gettp(1);
int q;
scanf("%d", &q);
while (q--) {
int m, x, y;
scanf("%d%d", &m, &x), x++;
for (int i = 2; i <= m; i++)
scanf("%d", &y), x = lca(x, ++y);
cout << mxId[x] - 1 << endl;
}
return 0;
}