H：机房
问题描述
这天, 小明在机房学习。
他发现机房里一共有 n 台电脑, 编号为 1 到 n, 电脑和电脑之间有网线连 接, 一共有 n−1 根网线将 n 台电脑连接起来使得任意两台电脑都直接或者间 接地相连。
小明发现每台电脑转发、发送或者接受信息需要的时间取决于这台电脑和 多少台电脑直接相连, 而信息在网线中的传播时间可以忽略。比如如果某台电脑 用网线直接连接了另外 d 台电脑, 那么任何经过这台电脑的信息都会延迟 d 单 位时间 (发送方和接收方也会产生这样的延迟, 当然如果发送方和接收方都是 同一台电脑就只会产生一次延迟)。
小明一共产生了 m 个疑问: 如果电脑 ui 向电脑 vi 发送信息, 那么信息从 ui 传到 vi 的最短时间是多少?
输入格式
输入共 n+m 行, 第一行为两个正整数 n,m 。
后面 n−1 行, 每行两个正整数 x,y 表示编号为 x 和 y 的两台电脑用网线 直接相连。
后面 mm 行, 每行两个正整数 ui,vi 表示小明的第i 个疑问。
输出格式
输出共 m 行, 第 i 行一个正整数表示小明第 ii 个疑问的答案。
样例输入
4 3 1 2 1 3 2 4 2 3 3 4 3 3
样例输出
5 6 1
样例说明
这四台电脑各自的延迟分别为 2,2,1,1 。
对于第一个询问, 从 2 到 3 需要经过 2,1,3, 所以时间和为 2+2+1=5 。
对于第二个询问, 从 3 到 4 需要经过 3,1,2,4, 所以时间和为 1+2+2+1=6。
对于第三个询问, 从 3 到 3 只会产生一次延迟, 所以时间为 1 。
评测用例规模与约定
对于 30% 的数据, 保证n,m≤1000;
对于 100% 的数据, 保证n,m≤100000 。
运行限制
最大运行时间：1s
最大运行内存: 512M
小编这题只会偏偏分，AC需要LCA加DFS加树的前缀和。我们看看大佬的代码吧，大体就是建一个数，统计每个节点到根节点的延时，然后通过LCA寻找询问两个点的最近公共祖先，算出最小延时。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N=100010; unordered_map<int,vector<int>> gra; int n,m; //单个点的出度 int d[N]; //记录点i到根节点的延迟 int w[N]; //并查集数组 int q[N]; //记录答案 int res[N]; int st[N]; //存下查询 vector<PII> query[N]; //并查集查询 int find(int x){ if(x!=q[x]) q[x]=find(q[x]); return q[x]; } void dfs(int u,int fa) { w[u]+=d[u]; for(auto g:gra[u]){ if(g==fa) continue; w[g]+=w[u]; dfs(g,u); } } void tarjan(int u) { st[u]=1; for(auto j:gra[u]){ if(!st[j]) { tarjan(j); q[j]=u; } } for(auto item: query[u]){ int y=item.first,id=item.second; if(st[y]==2){ int anc=find(y); res[id]=w[y]+w[u]-w[anc]*2+d[anc]; } } st[u]=2; } int main() { cin>>n>>m; for(int i=0;i<n-1;++i){ int a,b; scanf("%d%d",&a,&b); gra[a].push_back(b); gra[b].push_back(a); d[a]++,d[b]++; } for(int i=0;i<m;++i){ int a,b; scanf("%d%d",&a,&b); if(a!=b){ query[a].push_back({b,i}); query[b].push_back({a,i}); }else{ res[i]=d[a]; } } dfs(1,-1); for(int i=1;i<=n;++i) q[i]=i; tarjan(1); for(int i=0;i<m;++i) printf("%d\n",res[i]); return 0; }
I:齿轮
问题描述
这天, 小明在组装齿轮。
他一共有 n 个齿轮, 第 i 个齿轮的半径为 ri, 他需要把这 n 个齿轮按一定 顺序从左到右组装起来, 这样最左边的齿轮转起来之后, 可以传递到最右边的 齿轮, 并且这些齿轮能够起到提升或者降低转速 (角速度) 的作用。
小明看着这些齿轮, 突然有 QQ 个疑问：能否按一定顺序组装这些齿轮使得 最右边的齿轮的转速是最左边的齿轮的 qi 倍?
输入格式
输入共 Q+2 行, 第一行为两个正整数 n,Q, 表示齿轮数量和询问数量。 第二行为 n 个正整数 r1,r2,…,rn, 表示每个齿轮的半径。
后面 Q 行, 每行一个正整数 qi 表示询问。
输出格式
Q 行, 对于每个询问, 如果存在至少一种组装方案满足条件, 输出 'YES', 否则输出 'NO '。
样例输入
5 3 4 2 3 3 1 2 4 6
样例输出
YES YES NO
样例说明
询问 1 方案之一 ： 23341
询问 2 方案之一：42331
询问 3 没有方案
评测用例规模与约定
对于 15% 的数据, 保证 n,Q≤100;
对于 30% 的数据, 保证 n,Q≤2000;
对于100% 的数据, 保证 n,Q≤2×105;ri,qi≤2×105 。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
| C++ | 1s | 256M |
| C | 1s | 256M |
| Java | 3s | 256M |
| Python3 | 5s | 256M |
暴力做法：
#include <iostream> #include <algorithm> using namespace std; int n,q; int banjing[200005]; int xunwen[200005]; bool st[200005]; int main(){ cin>>n>>q; for(int i=1;i<=n;i++){ cin>>banjing[i]; } for(int i=1;i<=q;i++){ cin>>xunwen[i]; } sort(banjing,banjing+n+1); int len=0; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(banjing[j]%banjing[i]==0){ int b=banjing[j]/banjing[i]; st[b]=1; len++; } } } for(int i=1;i<=q;i++){ if(n==1&&xunwen[i]==1){ cout<<"YES"<<endl; }else if(st[xunwen[i]]){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } } return 0; }
寻找因式：
#include <iostream> #include <algorithm> #include <unordered_set> using namespace std; unordered_set<int> s; int n,q; int banjing[200005]; bool st[200005]; int main(){ ios_base::sync_with_stdio(false); //提高cin和cout效率 cin.tie(0); cin>>n>>q; for(int i=1;i<=n;i++){ cin>>banjing[i]; } sort(banjing,banjing+n+1); for(int i=1;i<=n;i++){ int v=banjing[i]; for(int j=1;j*j<=v;j++){ if(v%j==0){ if(s.find(j)!=s.end()){ st[v/j]=1; } if(s.find(v/j)!=s.end()){ st[j]=1; } } } s.insert(banjing[i]); } for(int i=1;i<=q;i++){ int xunwen; cin>>xunwen; if(n==1&&xunwen==1){ cout<<"YES"<<'\n'; }else if(st[xunwen]){ cout<<"YES"<<'\n'; }else{ cout<<"NO"<<'\n'; } } return 0; }
J:搬砖
问题描述
这天，小明在搬砖。
他一共有 n 块砖, 他发现第 i 砖的重量为 wi, 价值为 vi 。他突然想从这些 砖中选一些出来从下到上堆成一座塔, 并且对于塔中的每一块砖来说, 它上面 所有砖的重量和不能超过它自身的价值。
他想知道这样堆成的塔的总价值（即塔中所有砖块的价值和）最大是多少。
输入格式
输入共 n+1 行, 第一行为一个正整数 nn, 表示砖块的数量。
后面 n 行, 每行两个正整数 wi,vi 分别表示每块砖的重量和价值。
输出格式
一行, 一个整数表示答案。
样例输入
5 4 4 1 1 5 2 5 5 4 3
样例输出
10
样例说明
选择第 1、2、4 块砖, 从上到下按照2、1、4 的顺序堆成一座塔, 总价值 为 4+1+5=10
评测用例规模与约定
对于 20% 的数据, 保证 n≤10;
对于 100% 的数据, 保证n≤1000;wi≤20;vi≤20000 。
运行限制
最大运行时间：1s
最大运行内存: 512M
排序后，背包动态规划
#include <iostream> #include <algorithm> using namespace std; int n; int w; int ans; struct zhuan{ int jiazhi; int zhongliang; bool operator<(const zhuan&rhd)const { return jiazhi+zhongliang<rhd.jiazhi+rhd.zhongliang; } }; zhuan zhuant[1005]; int f[1010][50005]; int main() { cin>>n; for(int i=1;i<=n;i++){ cin>>zhuant[i].zhongliang>>zhuant[i].jiazhi; w+=zhuant[i].zhongliang; } sort(zhuant+1,zhuant+n+1); for(int i=1;i<=n;i++){ for(int j=0;j<=w;j++){ f[i][j]=f[i-1][j]; //不选 if(j>=zhuant[i].zhongliang && j-zhuant[i].zhongliang<=zhuant[i].jiazhi) { f[i][j]=max(f[i][j],f[i-1][j-zhuant[i].zhongliang]+zhuant[i].jiazhi); } ans=max(ans,f[i][j]); } } cout<<ans; return 0; }
