信息学奥赛-提高级 题库
铺设道路
【问题描述】
春春是一名道路工程师,负责铺设一条长度为 n 的道路。
铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块首尾相连的区域,一开始,第 i 块区域下陷的深度为 di 。
春春每天可以选择一段连续区间 [L, R] ,填充这段区间中的每块区域,让其下陷深度减少 1。在选择区间时,需要保证,区间内的每块区域在填充前下陷深度均不为 0 。
春春希望你能帮他设计一种方案,可以在最短的时间内将整段道路的下陷深度都变为 0 。
【输入格式】
输入文件名为 road.in。
输入文件包含两行,第一行包含一个整数 n,表示道路的长度。
第二行包含 n 个整数,相邻两数间用一个空格隔开,第 i 个整数为 di 。
【输出格式】
输出文件名为 road.out。
输出文件仅包含一个整数,即最少需要多少天才能完成任务。
【输入输出样例 1】

【样例解释】
一种可行的最佳方案是,依次选择:
[1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]。
【数据规模与约定】
对于 30% 的数据,1 ≤ n ≤ 10 ;
对于 70% 的数据,1 ≤ n ≤ 1000 ;
对于 100% 的数据,1 ≤ n ≤ 100000 ,0 ≤ di ≤ 10000 。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int ans,d[100001],N;
int partition1(int left, int right) //分治(实现这一片区域的操作)
{ int sum1=0;
if(left>=right) //当不能再分时返回
{
if(left==right) //如果区域是单个数
{ int t=d[left];
d[left]=0; //清0
return t; //直接返回里面的值(它里面的值代表这个单个区域需要的天数)
}
else
return 0;
}
int min1=inf,l=left;
for (int i=left; i<=right;i++) //求出这片区域的最小值
min1=min(d[i],min1);
sum1+=min1;//先把最小值加上
for(int i=left; i<=right; i++)
{ d[i]-=min1; //每个都减去最小值
if(d[i]==0&&d[i-1]!=0) //如果遇到0分界线
{
sum1+=partition1(l,i-1);//把之前的区域分治
}
if(d[i]!=0&&d[i-1]==0) l=i;//如果在0之后遇到新的左端点,更新
}
if(d[right]!=0)//不要忘掉最后一块区域
sum1+=partition1(l,right);
return sum1;
}
int main()
{
//freopen("in.txt","r",stdin);
cin>>N;
for(int i=1;i<=N;i++)
cin>>d[i];
ans=partition1(1,N);
cout<<ans;
return 0;
}
货币系统
【问题描述】
在网友的国度中共有 n 种不同面额的货币,第 i 种货币的面额为 a[i],你可以假设每一种货币都有无穷多张。为了方便,我们把货币种数为 n、面额数组为 a[1..n]的货币系统记作 (n,a)。
在一个完善的货币系统中,每一个非负整数的金额 x 都应该可以被表示出,即对每一个非负整数 x,都存在 n 个非负整数 t[i] 满足 a[i]× t[i] 的和为 x。然而,在网友的国度中,货币系统可能是不完善的,即可能存在金额 x 不能被该货币系统表示出。例如在货币系统 n=3, a=[2,5,9] 中,金额 1,3 就无法被表示出来。
两个货币系统 (n,a) 和 (m,b) 是等价的,当且仅当对于任意非负整数 x,它要么均可以被两个货币系统表出,要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。他们希望找到一个货币系统 (m,b),满足(m,b) 与原来的货币系统 (n,a) 等价,且 m 尽可能的小。他们希望你来协助完成这个艰巨的任务:找到最小的 m。
【输入格式】
输入文件名为 money.in。
输入文件的第一行包含一个整数 T,表示数据的组数。接下来按照如下格式分别给出 T 组数据。
每组数据的第一行包含一个正整数 n。接下来一行包含 n 个由空格隔开的正整数a[i]。
【输出格式】
输出文件名为 money.out。
输出文件共有 T 行,对于每组数据,输出一行一个正整数,表示所有与 (n,a) 等价的货币系统 (m,b) 中,最小的 m。
【输入输出样例 1】

【输入输出样例 1 说明】
在第一组数据中,货币系统 (2, [3,10]) 和给出的货币系统 (n, a) 等价,并可以验证不存在 m < 2 的等价的货币系统,因此答案为 2。
在第二组数据中,可以验证不存在 m < n 的等价的货币系统,因此答案为 5。
【数据规模与约定】

对于 100% 的数据,满足 1 ≤ T ≤ 20, n,a[i] ≥ 1。
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 25005
using namespace std;
bool dp[N]={0};
int a[103]={0};
int T=0,n=0;
int ret=0;
int main()
{
cin>>T;
while(T--)
{
cin>>n;
ret=0;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
if(dp[a[i]])
continue;
ret++;
for(int j=a[i];j<=a[n];j++)
{
dp[j]|=dp[j-a[i]];
}
}
cout<<ret<<endl;
}
return 0;
}
赛道修建
【问题描述】
C 城将要举办一系列的赛车比赛。在比赛前,需要在城内修建m 条赛道。
C 城一共有 n 个路口,这些路口编号为 1,2, … , n,有 n − 1 条适合于修建赛道的双向通行的道路,每条道路连接着两个路口。其中,第 i 条道路连接的两个路口编号为 ai和 bi,该道路的长度为 li。借助这 n − 1 条道路,从任何一个路口出发都能到达其他所有的路口。
一条赛道是一组互不相同的道路 e1, e2, … , ek,满足可以从某个路口出发,依次经过道路 e1, e2, … , ek(每条道路经过一次,不允许调头)到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全,要求每条道路至多被一条赛道经过。
目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案,使得修建的m条赛道中长度最小的赛道长度最大(即m条赛道中最短赛道的长度尽可能大)。
【输入格式】
输入文件名为 track.in。
输入文件第一行包含两个由空格分隔的正整数 n, m,分别表示路口数及需要修建的赛道数。
接下来 n − 1 行,第 i 行包含三个正整数 ai, bi, li,表示第 i 条适合于修建赛道的道路连接的两个路口编号及道路长度。保证任意两个路口均可通过这 n − 1 条道路相互到达。每行中相邻两数之间均由一个空格分隔。
【输出格式】
输出文件名为 track.out。
输出共一行,包含一个整数,表示长度最小的赛道长度的最大值。
【输入输出样例 1】

【输入输出样例 1 说明】
所有路口及适合于修建赛道的道路如下图所示:

道路旁括号内的数字表示道路的编号,非括号内的数字表示道路长度。
需要修建 1 条赛道。可以修建经过第 3,1,2,6 条道路的赛道(从路口 4 到路口 7),则该赛道的长度为 9 + 10 + 5 + 7 = 31,为所有方案中的最大值。
【输入输出样例 2】

【输入输出样例 2 说明】
所有路口及适合于修建赛道的道路如下图所示:

需要修建 3 条赛道。可以修建如下 3 条赛道:
1. 经过第 1,6 条道路的赛道(从路口 1 到路口 7),长度为 6 + 9 = 15;
2. 经过第 5,2,3,8 条道路的赛道(从路口 6 到路口 9),长度为 4 + 3 + 5 + 4 = 16;
3. 经过第 7,4 条道路的赛道(从路口 8 到路口 5),长度为 7 + 10 = 17。
长度最小的赛道长度为 15,为所有方案中的最大值。
【数据规模与约定】
所有测试数据的范围和特点如下表所示

其中,“分支不超过 3”的含义为:每个路口至多有 3 条道路与其相连。对于所有的数据,2 ≤ n≤ 50,000,1 ≤ m ≤ n − 1,1 ≤ ai, bi ≤ n,1 ≤ li ≤ 10,000。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
int head[50100],to[100100],nex[100100],val[100100];
int n,waysnumber,m,edges;
multiset <int> :: iterator it;
int dfs(int now,int father,int x){
multiset <int> son;
for (int v = head[now]; v ; v = nex[v])
if (to[v] != father){
int tmpways = dfs(to[v],now,x) + val[v];
if (tmpways >= x) ++waysnumber;
else son.insert(tmpways);
}
//对当前点now的所有子路径进行组合,用刚好能满足≥x的最小的边组合
//并返回所有儿子中最长的无法被组合成满足条件路的点
int maxwaylen = 0;
while (son.size() > 1){
it = son.lower_bound(x - *son.begin());
if (it == son.begin()) it++; //若最短的边≥x的时候,则用最短的两条边组合
if (it == son.end()){ //当前最短的边没办法找到够长的边组合出满足条件的路
//挑一条最长的子边返回
maxwaylen = max(maxwaylen,*son.begin());
son.erase(son.begin());
}
else{
//成功组合出了满足条件的边
++waysnumber;
son.erase(it);
son.erase(son.begin());
}
}
if (son.size() == 1) maxwaylen = max(maxwaylen,*son.begin());
return maxwaylen;
}
bool check(int x){
waysnumber = 0;
dfs(1,0,x);
if (waysnumber >= m) return true;
else return false;
}
void addedge(int u,int v,int c){
nex[++edges] = head[u], head[u] = edges, to[edges] = v, val[edges] = c;
}
int main()
{
edges = 0;
scanf("%d%d",&n,&m);
long long all = 0;
for (int i = 1 ; i < n ; ++i){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
all += c;
}
int l = 0 , r = all / m,mid,ans; //这里存在一个坑,对于ai = 1的图,如果这里的 r 使用极大值500000000,就会超时
while (l <= r){
mid = (l + r) >> 1;
if (check(mid)) ans = mid,l = mid + 1;
else r = mid - 1;
}
printf("%d\n",ans);
return 0;
}
旅行
【问题描述】
小 Y 是一个爱好旅行的 OIer。她来到 X 国,打算将各个城市都玩一遍。
小 Y 了解到,X 国的n 个城市之间有 m 条双向道路。每条双向道路连接两个城市。不存在两条连接同一对城市的道路,也不存在一条连接一个城市和它本身的道路。并且,从任意一个城市出发,通过这些道路都可以到达任意一个其他城市。小 Y 只能通过这些道路从一个城市前往另一个城市。
小 Y 的旅行方案是这样的:任意选定一个城市作为起点,然后从起点开始,每次可以选择一条与当前城市相连的道路,走向一个没有去过的城市,或者沿着第一次访问该城市时经过的道路后退到上一个城市。当小 Y 回到起点时,她可以选择结束这次旅行或继续旅行。需要注意的是,小 Y 要求在旅行方案中,每个城市都被访问到。
为了让自己的旅行更有意义,小 Y 决定在每到达一个新的城市(包括起点)时,将它的编号记录下来。她知道这样会形成一个长度为n 的序列。她希望这个序列的字典序最小,你能帮帮她吗?
对于两个长度均为 n 的序列 A 和 B,当且仅当存在一个正整数 x,满足以下条件时,我们说序列 A 的字典序小于 B。
⚫ 对于任意正整数 1 ≤ i < x,序列 A 的第 i 个元素 Ai 和序列 B 的第 i 个元素Bi 相同。
⚫ 序列 A 的第 x 个元素的值小于序列 B 的第 x 个元素的值。
【输入格式】
输入文件名为 travel.in。
输入文件共 m + 1 行。第一行包含两个整数 n, m(m ≤ n) ,中间用一个空格分隔。
接下来 m 行,每行包含两个整数 u, v (1 ≤ u, v ≤ n) ,表示编号为 u 和 v 的城市之间有一条道路,两个整数之间用一个空格分隔。
【输出格式】
输出文件名为 travel.out。
输出文件包含一行,n 个整数,表示字典序最小的序列。相邻两个整数之间用一个空格分隔。
【输入输出样例 1】

【输入输出样例 2】

【数据规模与约定】
对于 100% 的数据和所有样例,1 ≤ n ≤ 5000 且 m = n − 1 或 m = n 。
对于不同的测试点,我们约定数据的规模如下:

#include<bits/stdc++.h>
#define maxn 50500
using namespace std;
inline int read() {
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int n,m,cnt,del;
int ans[maxn],start[maxn],to[maxn],cur[maxn];
vector<int> v[maxn];
inline bool check() {
if(cnt != n) return false;
for(int i=1;i<=n;i++) if(cur[i]!=ans[i]) return ans[i]>cur[i];
}
void dfs(int u,int f) {
if(cnt>n) return ;
cur[++cnt]=u;
for(int i=0;i<v[u].size();i++) {
if(v[u][i]==f || (u==start[del]&&v[u][i]==to[del]) || (v[u][i]==start[del]&&u==to[del])) continue;
dfs(v[u][i],u);
}
}
int main() {
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
memset(ans,64,sizeof(ans));
n=read(),m=read();
for(int i=1;i<=m;i++) {
int x=read(),y=read();
v[x].push_back(y);
v[y].push_back(x);
start[i]=x;to[i]=y;
}
for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end());
if(m==n-1) {
del=0;cnt=0;
dfs(1,0);
memcpy(ans,cur,sizeof(cur));
} else {
for(int i=1;i<=m;i++) {
memset(cur,0,sizeof(cur));
del=i;cnt=0;
dfs(1,0);
if(check() ) {
memcpy(ans,cur,sizeof(cur));
}
}
}
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}
填数游戏
【问题描述】
小 D 特别喜欢玩游戏。这一天,他在玩一款填数游戏。
这个填数游戏的棋盘是一个n × m的矩形表格。玩家需要在表格的每个格子中填入一个数字(数字 0 或者数字 1),填数时需要满足一些限制。
下面我们来具体描述这些限制。
为了方便描述,我们先给出一些定义:
• 我们用每个格子的行列坐标来表示一个格子,即(行坐标,列坐标)。(注意:行列坐标均从 0 开始编号)
• 合法路径 P:一条路径是合法的当且仅当:
1. 这条路径从矩形表格的左上角的格子(0,0)出发,到矩形的右下角格子(n − 1, m − 1)结束;
2. 在这条路径中,每次只能从当前的格子移动到右边与它相邻的格子,或者从当前格子移动到下面与它相邻的格子。
例如:在下面这个矩形中,只有两条路径是合法的,它们分别是p1:(0,0) → (0,1) →(1,1)和p2:(0,0) → (1,0) → (1,1)。

对于一条合法的路径 P,我们可以用一个字符串w(P)来表示,该字符串的长度为n +m − 2,其中只包含字符“R”或者字符“D”,第 i 个字符记录了路径 P 中第 i 步的移动方法,“R”表示移动到当前格子右边与它相邻的格子,“D”表示移动到当前格子下面与它相邻的格子。例如,上图中对于路径p1,有w(P1) = "RD";而对于另一条路径p2,有w(P2) = "DR"。
同时,将每条合法路径 P 经过的每个格子上填入的数字依次连接后,会得到一个长度为n + m − 1的 01 字符串,记为 s(P)。例如,如果我们在格子(0,0)和(1,0)上填入数字0,在格子(0,1)和(1,1)上填入数字 1(见上图红色数字)。那么对于路径p1,我们可以得到s(P1) = "011",对于路径p2,有s(P2) = "001"。
游戏要求小 D 找到一种填数字 0、1 的方法,使得对于两条路径p1,P2,如果w(P1) >w(P2),那么必须s(P1) ≤ s(P2)。我们说字符串 a 比字符串 b 小,当且仅当字符串 a 的字典序小于字符串 b 的字典序,字典序的定义详见第一题。但是仅仅是找一种方法无法满足小 D 的好奇心,小 D 更想知道这个游戏有多少种玩法,也就是说,有多少种填数字的方法满足游戏的要求?
小 D 能力有限,希望你帮助他解决这个问题,即有多少种填 0、1 的方法能满足题目要求。由于答案可能很大,你需要输出答案对109 + 7取模的结果。
【输入格式】
输入文件名为 game.in。
输入文件共一行,包含两个正整数 n、m,由一个空格分隔,表示矩形的大小。其中 n 表示矩形表格的行数,m 表示矩形表格的列数。
【输出格式】
输出文件名为 game.out。
输出共一行,包含一个正整数,表示有多少种填 0、1 的方法能满足游戏的要求。
注意:输出答案对 10^9+7 取模的结果。
【输入输出样例 1】

【样例解释】

对于2 × 2棋盘,有上图所示的 12 种填数方法满足要求。
【输入输出样例 2】

【输入输出样例 3】

【数据规模与约定】

#include<cstdio>
#include<cstring>
#include<algorithm>
#define P 1000000007
using namespace std;
int n,m,inv128=570312504,inv384=190104168;
int add(int x,int y) {return x+y>=P?x+y-P:x+y;}
int dec(int x,int y) {return x-y< 0?x-y+P:x-y;}
int mul(int x,int y) {return 1ll*x*y%P;}
int power(int a,int b){
int ans=1;
for(;b;b>>=1,a=mul(a,a)) if(b&1) ans=mul(ans,a);
return ans;
}
int main(){
scanf("%d%d",&n,&m);
if(n>m) swap(n,m);
if(n==1) printf("%d\n",power(2,m));
else if(n==2) printf("%d\n",mul(4,power(3,m-1)));
else if(n==3) printf("%d\n",mul(112,power(3,m-3)));
else{
if(m==n) printf("%d\n",(83ll*power(8,n)%P+5ll*power(2,n+7)%P)*inv384%P);
else printf("%d\n",(83ll*power(8,n)%P+power(2,n+8))*power(3,m-n-1)%P*inv128%P);
}
return 0;
}
保卫王国
【问题描述】
Z 国有n座城市,n − 1条双向道路,每条双向道路连接两座城市,且任意两座城市都能通过若干条道路相互到达。
Z 国的国防部长小 Z 要在城市中驻扎军队。驻扎军队需要满足如下几个条件:
一座城市可以驻扎一支军队,也可以不驻扎军队。
由道路直接连接的两座城市中至少要有一座城市驻扎军队。
在城市里驻扎军队会产生花费,在编号为i的城市中驻扎军队的花费是pi。
小 Z 很快就规划出了一种驻扎军队的方案,使总花费最小。但是国王又给小 Z 提出了m个要求,每个要求规定了其中两座城市是否驻扎军队。小 Z 需要针对每个要求逐一给出回答。具体而言,如果国王提出的第j个要求能够满足上述驻扎条件(不需要考虑第 j 个要求之外的其它要求),则需要给出在此要求前提下驻扎军队的最小开销。如果国王提出的第j个要求无法满足,则需要输出-1 (1 ≤ j ≤ m)。现在请你来帮助小 Z。
【输入格式】
输入文件名为 defense.in。
第 1 行包含两个正整数n, m和一个字符串type,分别表示城市数、要求数和数据类型。type是一个由大写字母 A,B 或 C 和一个数字 1,2,3 组成的字符串。它可以帮助你获得部分分。你可能不需要用到这个参数。这个参数的含义在【数据规模与约定】中有具体的描述。
第2行n个整数pi,表示编号i的城市中驻扎军队的花费。
接下来n − 1行,每行两个正整数u, v,表示有一条u到v的双向道路。
接下来m行,第j行四个整数a, x, b, y(a ≠ b),表示第j个要求是在城市a驻扎x支军队,在城市b驻扎y支军队。其中,x 、 y 的取值只有 0 或 1:若 x 为 0,表示城市 a 不得驻扎军队,若 x 为 1,表示城市 a 必须驻扎军队;若 y 为 0,表示城市 b 不得驻扎军队,若 y 为 1,表示城市 b 必须驻扎军队。
输入文件中每一行相邻的两个数据之间均用一个空格分隔。
【输出格式】
输出文件名为 defense.out。
输出共m行,每行包含 1 个整数,第j行表示在满足国王第j个要求时的最小开销,如果无法满足国王的第j个要求,则该行输出-1。
【输入输出样例 1】

【样例解释】
对于第一个要求,在 4 号和 5 号城市驻扎军队时开销最小。
对于第二个要求,在 1 号、2 号、3 号城市驻扎军队时开销最小。
第三个要求是无法满足的,因为在 1 号、5 号城市都不驻扎军队就意味着由道路直接连
接的两座城市中都没有驻扎军队。
【数据规模与约定】
对于 100%的数据,n, m ≤ 300000,1 ≤ pi ≤ 100000。

数据类型的含义:
A:城市i与城市i + 1直接相连。
B:任意城市与城市 1 的距离不超过 100(距离定义为最短路径上边的数量),即如果这棵树以 1 号城市为根,深度不超过 100。
C:在树的形态上无特殊约束。
1:询问时保证a = 1, x = 1,即要求在城市 1 驻军。对b, y没有限制。
2:询问时保证a, b是相邻的(由一条道路直接连通)
3:在询问上无特殊约束。
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 100005
#define MAXM MAXN*2
#define ll long long
#define reg register ll
#define INF 1000000000000000007ll
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)
#define rep(i,a) for (reg i=last[a];i;i=next[i])
#define O3 __attribute__((optimize("-O3")))
ll last[MAXM],next[MAXM],tov[MAXM];
ll p[MAXN],depth[MAXN],fa[MAXN];
ll f[MAXN][2],g[MAXN][2];
ll anc[MAXN][21];
ll n,m,tot,ans;
char type[5];
struct node
{
ll a[2][2];
}dis[MAXN][21],A,B,C;
O3 inline ll read()
{
ll x=0,f=1;char ch=getchar();
while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
O3 inline ll min(ll x,ll y)
{
return x<y?x:y;
}
O3 inline void swap(ll &x,ll &y)
{
x=x+y,y=x-y,x=x-y;
}
O3 inline void link(ll x,ll y)
{
next[++tot]=last[x],last[x]=tot,tov[tot]=y;
}
O3 inline void dfs1(ll x)
{
depth[x]=depth[fa[x]]+1,anc[x][0]=fa[x];
fo(i,1,20)anc[x][i]=anc[anc[x][i-1]][i-1];
f[x][0]=0,f[x][1]=p[x];
rep(i,x)if (tov[i]!=fa[x])
{
fa[tov[i]]=x,dfs1(tov[i]);
f[x][0]+=f[tov[i]][1];
f[x][1]+=min(f[tov[i]][0],f[tov[i]][1]);
}
}
O3 inline void dfs2(ll x)
{
if (x==1)g[x][0]=f[x][0],g[x][1]=f[x][1];
else
{
g[x][0]=f[x][0]+g[fa[x]][1]-min(f[x][0],f[x][1]);
g[x][1]=f[x][1]+min(g[fa[x]][0]-f[x][1],g[fa[x]][1]-min(f[x][0],f[x][1]));
}
rep(i,x)if (tov[i]!=fa[x])
{
dis[tov[i]][0].a[0][0]=INF;
dis[tov[i]][0].a[1][0]=f[x][0]-f[tov[i]][1];
dis[tov[i]][0].a[0][1]=f[x][1]-min(f[tov[i]][0],f[tov[i]][1]);
dis[tov[i]][0].a[1][1]=f[x][1]-min(f[tov[i]][0],f[tov[i]][1]);
dfs2(tov[i]);
}
}
O3 inline node merge(node A,node B)
{
memset(C.a,60,sizeof(C.a));
fo(i,0,1)fo(j,0,1)fo(k,0,1)
C.a[i][j]=min(C.a[i][j],A.a[i][k]+B.a[k][j]);
return C;
}
O3 int main()
{
freopen("defense.in","r",stdin);
freopen("defense.out","w",stdout);
//freopen("readin.txt","r",stdin);
n=read(),m=read(),scanf("%s",&type);
fo(i,1,n)p[i]=read();
fo(i,1,n-1)
{
ll x=read(),y=read();
link(x,y),link(y,x);
}
dfs1(1),dfs2(1);
fo(j,1,20)fo(i,1,n)dis[i][j]=merge(dis[i][j-1],dis[anc[i][j-1]][j-1]);
while (m--)
{
ll a=read(),x=read(),b=read(),y=read();
if (x+y==0 && ((fa[a]==b) || (fa[b]==a)))
{
printf("-1\n");
continue;
}
if (depth[a]<depth[b])swap(a,b),swap(x,y);
memset(A.a,60,sizeof(A.a));
memset(B.a,60,sizeof(B.a));
A.a[x][x]=f[a][x],B.a[y][y]=f[b][y];
fd(i,20,0)if (depth[anc[a][i]]>depth[b])
{
A=merge(A,dis[a][i]),a=anc[a][i];
}
if (fa[a]==b)
{
printf("%lld\n",y==0?g[b][0]-f[a][1]+A.a[x][1]:
g[b][1]-min(f[a][0],f[a][1])+min(A.a[x][0],A.a[x][1]));
continue;
}
if (depth[a]!=depth[b])A=merge(A,dis[a][0]),a=fa[a];
fd(i,20,0)if (anc[a][i]!=anc[b][i])
{
A=merge(A,dis[a][i]),B=merge(B,dis[b][i]);
a=anc[a][i],b=anc[b][i];
}
printf("%lld\n",min(g[fa[a]][0]-f[a][1]-f[b][1]+A.a[x][1]+B.a[y][1],
g[fa[a]][1]-min(f[a][0],f[a][1])-min(f[b][0],f[b][1])+min(A.a[x][0],A.a[x][1])+min(B.a[y][0],B.a[y][1])));
}
return 0;
}
2-3 树是一种特殊的树,它满足两个条件:
(1)每个内部结点有两个或三个子结点;
(2)所有的叶结点到根的路径长度相同。
如果一棵 2-3 树有 10 个叶结点,那么它可能有( )个非叶结点。
甲乙丙丁四人在考虑周末要不要外出郊游。
已知:①如果周末下雨,并且乙不去,则甲一定不去;②如果乙去,则丁一定去;③如果丙去,则丁一定不去;④如果丁不去,而且甲不去,则丙一定不去。如果周末丙去了,则甲________(去了/没去)(1 分),乙________(去了/没去)(1 分),丁________(去了/没去)(1 分),周末________(下雨/没下雨)(2 分)。
去了 没去 没去 没下雨 (第4 空 2 分,其余 1 分)
方程 a*b = (a or b) * (a and b),在 a,b 都取 [0, 31] 中的整数时,共有_____组解。(*表示乘法;or 表示按位或运算;and 表示按位与运算)
共有454组解
#include <cstdio>
int main() {
int x;
scanf("%d", &x);
int res = 0;
for (int i = 0; i < x; ++i) {
if (i * i % x == 1) {
++res;
}
}
printf("%d", res);
return 0;
}
输入:15
输出:_________。
输出:4
#include <cstdio>
int n, d[100];
bool v[100];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", d + i);
v[i] = false;
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (!v[i]) {
for (int j = i; !v[j]; j = d[j]) {
v[j] = true;
}
++cnt;
}
}
printf("%d\n", cnt);
return 0;
}
输入:10 7 1 4 3 2 5 9 8 0 6
输出:_________
输出:6
#include <cstdio>
using namespace std;
const int N = 110;
bool isUse[N];
int n, t;
int a[N], b[N];
bool isSmall() {
for (int i = 1; i <= n; ++i)
if (a[i] != b[i]) return a[i] < b[i];
return false;
}
bool getPermutation(int pos) {
if (pos > n) {
return isSmall();
}
for (int i = 1; i <= n; ++i) {
if (!isUse[i]) {
b[pos] = i; isUse[i] = true;
if (getPermutation(pos + 1)) {
return true;
}
isUse[i] = false;
}
}
return false;
}
void getNext() {
for (int i = 1; i <= n; ++i) {
isUse[i] = false;
}
getPermutation(1);
for (int i = 1; i <= n; ++i) {
a[i] = b[i];
}
}
int main() {
scanf("%d%d", &n, &t);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= t; ++i) {
getNext();
}
for (int i = 1; i <= n; ++i) {
printf("%d", a[i]);
if (i == n) putchar('\n'); else putchar(' ');
}
return 0;
}
输入 1:6 10 1 6 4 5 3 2
输出 1:_________(3 分)
输入 2:6 200 1 5 3 4 2 6
输出 2:_________(5 分)
输出 1:2 1 3 5 6 4 (3 分)
输出 2:3 2 5 6 1 4 (5 分)
一只小猪要买 N 件物品(N 不超过 1000)。
它要买的所有物品在两家商店里都有卖。第 i 件物品在第一家商店的价格是a[i],在第二家商店的价格是 b[i],两个价格都不小于 0 且不超过 10000。如果在第一家商店买的物品的总额不少于 50000,那么在第一家店买的物品都可以打 95 折(价格变为原来的 0.95 倍)。
求小猪买齐所有物品所需最少的总额。
输入:第一行一个数 N。接下来 N 行,每行两个数。第 i 行的两个数分别代表 a[i],b[i]。
输出:输出一行一个数,表示最少需要的总额,保留两位小数。
试补全程序。(第一空 2 分,其余 3 分)
#include <cstdio>
#include <algorithm>
using namespace std;
const int Inf = 1000000000;
const int threshold = 50000;
const int maxn = 1000;
int n, a[maxn], b[maxn];
bool put_a[maxn];
int total_a, total_b;
double ans;
int f[threshold];
int main() {
scanf("%d", &n);
total_a = total_b = 0;
for (int i = 0; i < n; ++i) {
scanf("%d%d", a + i, b + i);
if (a[i] <= b[i]) total_a += a[i];
else total_b += b[i];
}
ans = total_a + total_b;
total_a = total_b = 0;
for (int i = 0; i < n; ++i) {
if ( (1) ) {
put_a[i] = true;
total_a += a[i];
} else {
put_a[i] = false;
total_b += b[i];
}
}
if ( (2) ) {
printf("%.2f", total_a * 0.95 + total_b);
return 0;
}
f[0] = 0;
for (int i = 1; i < threshold; ++i)
f[i] = Inf;
int total_b_prefix = 0;
for (int i = 0; i < n; ++i)
if (!put_a[i]) {
total_b_prefix += b[i];
for (int j = threshold - 1; j >= 0; --j) {
if ( (3) >= threshold && f[j] != Inf)
ans = min(ans, (total_a + j + a[i]) * 0.95
+ (4) );
f[j] = min(f[j] + b[i], j >= a[i] ? (5) : Inf);
}
}
printf("%.2f", ans);
return 0;
}
(1)a[i] * 0.95 <= b[i]或 b[i] >= a[i] * 0.95
(2)total_a >= threshold或 threshold <= total_a 或 total_a >= 50000 或 50000 <= total_a
(3)total_a + j + a[i]
(4)f[j] + total_b - total_b_prefix
(5)f[j - a[i]]
奶酪
【问题描述】
现有一块大奶酪,它的高度为 h,它的长度和宽度我们可以认为是无限大的,奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系,在坐标系中,奶酪的下表面为z = 0,奶酪的上表面为z = h。
现在,奶酪的下表面有一只小老鼠 Jerry,它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交,则 Jerry 可以从其中一个空洞跑到另一个空洞,特别地,如果一个空洞与下表面相切或是相交,Jerry 则可以从奶酪下表面跑进空洞;如果一个空洞与上表面相切或是相交,Jerry 则可以从空洞跑到奶酪上表面。
位于奶酪下表面的 Jerry 想知道,在不破坏奶酪的情况下,能否利用已有的空洞跑到奶酪的上表面去?

【输入格式】
输入文件名为 cheese.in。
每个输入文件包含多组数据。
输入文件的第一行,包含一个正整数 T,代表该输入文件中所含的数据组数。
接下来是 T 组数据,每组数据的格式如下:
第一行包含三个正整数 n,h 和 r,两个数之间以一个空格分开,分别代表奶酪中空洞的数量,奶酪的高度和空洞的半径。
接下来的 n 行,每行包含三个整数 x、y、z,两个数之间以一个空格分开,表示空洞球心坐标为(x, y, z)。
【输出格式】
输出文件名为 cheese.out。
输出文件包含 T 行,分别对应 T 组数据的答案,如果在第 i 组数据中,Jerry 能从下
表面跑到上表面,则输出“Yes”,如果不能,则输出“No”(均不包含引号)。
【输入输出样例 1】

【输入输出样例 1 说明】

【数据规模与约定】
对于 20%的数据,n = 1,1 ≤ h , r ≤ 10,000,坐标的绝对值不超过 10,000。
对于 40%的数据,1 ≤ n ≤ 8, 1 ≤ h , r ≤ 10,000,坐标的绝对值不超过 10,000。
对于 80%的数据,1 ≤ n ≤ 1,000,1 ≤ h , r ≤ 10,000,坐标的绝对值不超过 10,000。
对于 100%的数据,1 ≤ n ≤ 1,000,1 ≤ h , r ≤ 1,000,000,000,T ≤ 20,坐标的绝对值不超过 1,000,000,000。
#include<bits/stdc++.h>
#define rg register int
using namespace std;
long long T, n, h, r, x[1005], y[1005], z[1005], f[1005][1005], bz[1005], ans;
int dist(int i, int j) {
double s = sqrt((x[i] - x[j]) * 1.0 * (x[i] -x [j])*1.0 + (y[i] - y[j]) * 1.0 * (y[i] - y[j])*1.0 + (z[i] - z[j]) * 1.0 * (z[i] -z [j]) * 1.0) * 1.0;
if (s > (int)s) s++;
return s;
}
void dfs(int x) {
if (x == n + 1) {
ans = 1;
return;
}
bz[x] = 1;
for (rg i = 1; i <= n + 1; i++)
if (f[x][i] && (!bz[i])) {
dfs(i);
if (ans == 1)
return;
}
}
int main() {
scanf("%lld", &T);
while (T--) {
scanf("%lld%lld%lld", &n, &h, &r), ans = 0;
for (rg i = 1; i <= n; i++)
scanf("%lld%lld%lld", &x[i], &y[i], &z[i]);
for (rg i = 0; i <= n; i++)
for(rg j = i + 1; j <= n+1; j++)
f[i][j] = f[j][i] = 0;
for (rg i = 1; i <= n; i++)
for (rg j = i + 1; j <= n; j++)
if (dist(i,j) <= r * 2) f[i][j] = f[j][i] = 1;
for (rg i = 1; i <= n; i++) {
bz[i] = 0;
if (h - z[i] <= r) f[i][n + 1] = f[n + 1][i] = 1;
if (z[i] <= r) f[i][0] = f[0][i] = 1;
}
dfs(0);
if (ans) printf("Yes\n");
else printf("No\n");
}
return 0;
}
宝藏
【问题描述】
参与考古挖掘的小明得到了一份藏宝图,藏宝图上标出了 n 个深埋在地下的宝藏屋,也给出了这 n 个宝藏屋之间可供开发的 m 条道路和它们的长度。
小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是,每个宝藏屋距离地面都很远,也就是说,从地面打通一条到某个宝藏屋的道路是很困难的,而开发宝藏屋之间的道路则相对容易很多。
小明的决心感动了考古挖掘的赞助商,赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道,通往哪个宝藏屋则由小明来决定。
在此基础上,小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以任意通行不消耗代价。每开凿出一条新道路,小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外,小明不想开发无用道路,即两个已经被挖掘过的宝藏屋之间的道路无需再开发。
新开发一条道路的代价是:
这条道路的长度 × 从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量(包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋)。
请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路,使得工程总代价最小,并输出这个最小值。
【输入格式】
输入文件名为 treasure.in。
第一行两个用空格分离的正整数 n 和 m,代表宝藏屋的个数和道路数。
接下来 m 行,每行三个用空格分离的正整数,分别是由一条道路连接的两个宝藏屋的编号(编号为 1~n),和这条道路的长度 v。
【输出格式】
输出文件名为 treasure.out。
输出共一行,一个正整数,表示最小的总代价。
【输入输出样例 1】

【输入输出样例 1 说明】


【样例输入输出 2】

【输入输出样例 2 说明】

【数据规模与约定】
对于 20%的数据:
保证输入是一棵树,1≤n≤8,v≤5000 且所有的 v 都相等。
对于 40%的数据:
1≤n≤8,0≤m≤1000,v≤5000 且所有的 v 都相等。
对于 70%的数据:
1≤n≤8,0≤m≤1000,v≤ 5000
对于 100%的数据:
1≤n≤12,0≤m≤1000,v≤ 500000
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,tot,ans;
int mapp[110][110],dis[110][110],Log[4100];
int f[15][4100],g[4100],ref[4100],v[15],p[15];
int main(){
//freopen("treasure.in","r",stdin);
//freopen("treasure.out","w",stdout);
scanf("%d%d",&n,&m);
register int i,j,a,b,c,x;
for(i=0;i<n;i++) for(j=0;j<n;j++) mapp[i][j]=60000000;
for(i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c),a--,b--;
mapp[a][b]=mapp[b][a]=min(mapp[a][b],c);
}//建图
for(i=0;i<n;i++) Log[1<<i]=i;
memset(f,0x3f,sizeof(f));
for(i=0;i<n;i++) f[0][1<<i]=0;
for(i=0;i<n;i++) //开始DP
for(x=0;x<(1<<n);x++){
tot=0;
for(a=0;a<n;a++)
if(!(x&(1<<a))){
v[tot]=60000000,p[tot]=1<<a;
for(j=x;j;j-=j&-j){
b=Log[j&-j];
v[tot]=min(v[tot],mapp[a][b]*(i+1));//计算代价
}
tot++;
}
for(j=1;j<(1<<tot);j++){
g[j]=g[j-(j&-j)]+v[Log[j&-j]];//每个点与x中的某个点连通所需要的最小代价。
ref[j]=ref[j-(j&-j)]|p[Log[j&-j]];//枚举子集
f[i+1][x|ref[j]]=min(f[i+1][x|ref[j]],f[i][x]+g[j]);
}
}
ans=1<<30;
for(i=0;i<=n;i++) ans=min(ans,f[i][(1<<n)-1]);//最优状态从走到每一个点但最深深度不同的状态中取
printf("%d",ans);
return 0;
}
列队
【问题描述】
Sylvia 是一个热爱学习的女孩子。
前段时间,Sylvia 参加了学校的军训。众所周知,军训的时候需要站方阵。Sylvia所在的方阵中有n × m名学生,方阵的行数为 n,列数为 m。
为了便于管理,教官在训练开始时,按照从前到后,从左到右的顺序给方阵中的学生从 1 到 n × m 编上了号码(参见后面的样例)。
即:初始时,第 i 行第 j 列的学生的编号是(i − 1) × m + j。
然而在练习方阵的时候,经常会有学生因为各种各样的事情需要离队。在一天中,一共发生了 q 件这样的离队事件。每一次离队事件可以用数对(x, y) (1≤x≤n, 1≤y≤m)描述,表示第 x 行第 y 列的学生离队。
在有学生离队后,队伍中出现了一个空位。为了队伍的整齐,教官会依次下达这样的两条指令:
1. 向左看齐。这时第一列保持不动,所有学生向左填补空缺。不难发现在这条指令之后,空位在第 x 行第 m 列。
2. 向前看齐。这时第一行保持不动,所有学生向前填补空缺。不难发现在这条指令之后,空位在第 n 行第 m 列。
教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后,下一个学生才能离队。因此在每一个离队的学生要归队时,队伍中有且仅有第 n 行第 m 列一个空位,这时这个学生会自然地填补到这个位置。
因为站方阵真的很无聊,所以 Sylvia 想要计算每一次离队事件中,离队的同学的编号是多少。
注意:每一个同学的编号不会随着离队事件的发生而改变,在发生离队事件后方阵中同学的编号可能是乱序的。
【输入格式】
输入文件名为 phalanx.in。
输入共 q+1 行。
第 1 行包含 3 个用空格分隔的正整数 n, m, q,表示方阵大小是 n 行 m 列,一共发生了 q 次事件。
接下来 q 行按照事件发生顺序描述了 q 件事件。每一行是两个整数 x, y,用一个空格分隔,表示这个离队事件中离队的学生当时排在第 x 行第 y 列。
【输出格式】
输出文件名为 phalanx.out。
按照事件输入的顺序,每一个事件输出一行一个整数,表示这个离队事件中离队学生的编号。
【输入输出样例 1】

【输入输出样例 1 说明】

列队的过程如上图所示,每一行描述了一个事件。
在第一个事件中,编号为 1 的同学离队,这时空位在第一行第一列。接着所有同学向左标齐,这时编号为 2 的同学向左移动一步,空位移动到第一行第二列。然后所有同学向上标齐,这时编号为 4 的同学向上一步,这时空位移动到第二行第二列。最后编号为 1 的同学返回填补到空位中。
【数据规模与约定】

数据保证每一个事件满足 1≤x≤n,1≤y≤m。
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int Max=300005;
int n,m,q,sum,tot;
int tree[Max*20],lc[Max*20],rc[Max*20],rt[Max];
vector<ll>num[Max];
inline int get_int()
{
int x=0;char c;
for(c=getchar();!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
return x;
}
inline void print(ll x)
{
if(x>9) print(x/10);
putchar('0'+x%10);
}
inline void add(int &now,int l,int r,int pos)
{
if(!now) now=++tot;tree[now]++;
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) add(lc[now],l,mid,pos);
else add(rc[now],mid+1,r,pos);
}
inline int Q(int root,int l,int r,int k)
{
if(l==r) return l;
int mid=(l+r)>>1,sum=(mid-l+1)-tree[lc[root]];
if(sum>=k) Q(lc[root],l,mid,k);
else Q(rc[root],mid+1,r,k-sum);
}
inline ll Qr(int x,ll v)
{
int pos=Q(rt[n+1],1,sum,x);add(rt[n+1],1,sum,pos);
ll ans=pos<=n?(ll)m*pos:num[n+1][pos-n-1];
return num[n+1].push_back(v?v:ans),ans;
}
inline ll Ql(int x,int y)
{
int pos=Q(rt[x],1,sum,y);add(rt[x],1,sum,pos);
ll ans=pos<m?(ll)(x-1)*m+pos:num[x][pos-m];
return num[x].push_back(Qr(x,ans)),ans;
}
int main()
{
n=get_int(),m=get_int(),q=get_int(),sum=max(n,m)+q;
while(q--)
{
int x=get_int(),y=get_int();
if(y==m) print(Qr(x,0)),putchar('\n');
else print(Ql(x,y)),putchar('\n');
}
return 0;
}
信息传递
【问题描述】
有 n 个同学(编号为 1 到 n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 i 的同学的信息传递对象是编号为Ti的同学。
游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息,但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自己的生日时,游戏结束。请问该游戏一共可以进行几轮?
【输入格式】
输入文件名为 message.in。
输入共 2 行。
第 1 行包含 1 个正整数 n,表示 n 个人。
第 2 行包含 n 个用空格隔开的正整数 T1, T2, … … , Tn,其中第i 个整数Ti表示编号为 i
的同学的信息传递对象是编号为 Ti 的同学, Ti ≤ n 且 Ti ≠ i。
数据保证游戏一定会结束。
【输出格式】
输出文件名为 message.out。
输出共 1 行,包含 1 个整数,表示游戏一共可以进行多少轮。
【输入输出样例 1】

【输入输出样例 1 说明】

游戏的流程如图所示。当进行完第 3 轮游戏后,4 号玩家会听到 2 号玩家告诉他自己的生日,所以答案为 3。当然,第 3 轮游戏后,2 号玩家、3 号玩家都能从自己的消息来源得知自己的生日,同样符合游戏结束的条件。
【数据规模与约定】
对于 30%的数据,n ≤ 200;
对于 60%的数据,n ≤ 2500;
对于 100%的数据,n ≤ 200000。
#include <bits/stdc++.h>
using namespace std;
const int maxn=200010;
int n, fa[maxn],ans=0x3f3f3f3f;
int get(int x, int &cnt){
cnt++;
if(fa[x]==x)return x;
else return get(fa[x], cnt);
}
int main () {
cin>>n;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=n;i++) {
int cnt=0,f;
cin>>f;
if(get(f,cnt)==i){
ans=min(ans,cnt);
}else{
fa[i]=f;
}
}
cout<<ans;
return 0;
}