做的网站在小窗口中怎么保持中间,万网网站备案授权书,怎么样建设网站,做服装到哪个网站拿货品质好目录 原题描述#xff1a;
题目描述
输入格式
输出格式
样例 #1
样例输入 #1
样例输出 #1
样例 #2
样例输入 #2
样例输出 #2
提示
题目大意#xff1a;
主要思路#xff1a;
但是我们怎么才能判断出x走到1时L是偶数还是奇数呢#xff1f;
初始化#xff1a;…目录 原题描述
题目描述
输入格式
输出格式
样例 #1
样例输入 #1
样例输出 #1
样例 #2
样例输入 #2
样例输出 #2
提示
题目大意
主要思路
但是我们怎么才能判断出x走到1时L是偶数还是奇数呢
初始化
代码code 原题描述 时间限制: 1000ms 空间限制: 524288kB 题目描述
凯凯的工厂正在有条不紊地生产一种神奇的零件神奇的零件的生产过程自然也很神奇。工厂里有 位工人工人们从编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。
如果 号工人想生产一个被加工到第 阶段的零件则所有与号工人有传送带直接相连的工人都需要生产一个被加工到第 阶段的零件但 号工人自己无需生产第 阶段的零件。
如果 号工人想生产一个被加工到第 1 阶段的零件则所有与 号工人有传送带直接相连的工人都需要为 号工人提供一个原材料。
轩轩是 1 号工人。现在给出 张工单第 张工单表示编号为 的工人想生产一个第 阶段的零件。轩轩想知道对于每张工单他是否需要给别人提供原材料。他知道聪明的你一定可以帮他计算出来
输入格式
第一行三个正整数分别表示工人的数目、传送带的数目和工单的数目。
接下来 行每行两个正整数 和 表示编号为 和 的工人之间存在一条零件传输带。保证。
接下来 行每行两个正整数 和 表示编号为 的工人想生产一个第阶段的零件。
输出格式
共 行每行一个字符串 Yes 或者 No。如果按照第张工单生产需要编号为 1 的轩轩提供原材料则在第 行输出 Yes否则在第 行输出 No。注意输出不含引号。
样例 #1
样例输入 #1
3 2 6
1 2
2 3
1 1
2 1
3 1
1 2
2 2
3 2
样例输出 #1
No
Yes
No
Yes
No
Yes
样例 #2
样例输入 #2
5 5 5
1 2
2 3
3 4
4 5
1 5
1 1
1 2
1 3
1 4
1 5
样例输出 #2
No
Yes
No
Yes
Yes
提示
【输入输出样例 1 说明】 编号为 1 的工人想生产第 1 阶段的零件需要编号为 2 的工人提供原材料。
编号为 2 的工人想生产第 1 阶段的零件需要编号为 1 和 3 的工人提供原材料。
编号为 3 的工人想生产第 1 阶段的零件需要编号为 2 的工人提供原材料。
编号为 1 的工人想生产第 2 阶段的零件需要编号为 2 的工人生产第 1 阶段的零 件需要编号为 1 和 3 的工人提供原材料。
编号为 2 的工人想生产第 2 阶段的零件需要编号为 1 和 3 的工人生产第 1 阶段的零件他/她们都需要编号为 2 的工人提供原材料。
编号为 3 的工人想生产第 2 阶段的零件需要编号为 2 的工人生产第 1 阶段的零件需要编号为 1 和 3 的工人提供原材料。 【输入输出样例 2 说明】 编号为 1 的工人想生产第 1 阶段的零件需要编号为 2 和 5 的工人提供原材料。
编号为 1 的工人想生产第 2 阶段的零件需要编号为 2 和 5 的工人生产第 1 阶段的零件需要编号为 的工人提供原材料。
编号为 1 的工人想生产第 3 阶段的零件需要编号为 2 和 5 的工人生产第 2 阶段的零件需要编号为的工人生产第 1 阶段的零件需要编号为 的工人提供原材料。
编号为 1 的工人想生产第 4 阶段的零件需要编号为 2 和 5 的工人生产第 3 阶段的零件需要编号为 的工人生产第 2 阶段的零件需要编号为 的工人生产第 1 阶段的零件需要全部工人提供原材料。
编号为 1 的工人想生产第 5 阶段的零件需要编号为 2 和 5 的工人生产第 4 阶段的零件需要编号为 的工人生产第 3 阶段的零件需要编号为 的工人生产第 2 阶段的零件需要全部工人生产第 1 阶段的零件需要全部工人提供原材料。
【数据规模与约定】
共 20 个测试点。
。
测试点 1~4。
测试点 5~8。
测试点 9~12。
测试点 13~16。
测试点 17~20。
题目大意
有一张无向图每次有个节点a要级别为L的部件则与a直接相连的节点要提供L-1的部件。
当节点a要1级的部件时那么与a直接相连的节点要提供1个原材料。
问你每次节点1是否提供原材料。
主要思路
这个题目可以用分类讨论。
分三个部分用cnt表示从节点a到1的路径长度每条边长为1
L cntLcntLcnt
对于部分1
画图来看一下。 当Lcnt时节点1要提供原材料。
注意有些童鞋会说4生产3那么5又要生产2不是还要进一步的推导吗
可是题目中只说是否要1提供原材料其他的就不用管太多。
第二部分
Lcnt
还是画图 我们发现还没轮到1时就结束了说明1不用提供什么。
第三部分
Lcnt
从x走到1时L是奇数。 1不用提供任何原材料
但是but,当Lcnt 且从x走到1时L是偶数。 这时1要提供原材料了。
得出结论
当L cnt,1要提供原材料。
当L cnt,1不用提供任何原材料。
当L cnt,且从x走到1时L-cnt是奇数1不用提供任何原材料。
当L cnt,且从x走到1时L是偶数1要提供原材料。
但是我们怎么才能判断出x走到1时L是偶数还是奇数呢
int even[100010];// even[x]表示从1走到x长度最短为偶数的路径的长度even是偶数的意思
int odd[100010];// odd[x]表示从1走到x长度最短为奇数的路径的长度odd是奇数的意思
注是最短路径。
奇数-奇数偶数。
奇数-偶数奇数
偶数-奇数奇数
偶数-偶数偶数。
cnt被替代了
这样我们就发现了
L是奇数且lodd[x](odd[x]肯定是奇数长度路径那么就输出Yes(等于也输出Yes
L是奇数且lodd[x](odd[x]肯定是奇数长度路径那么就输出No
L是偶数且leven[x](even[x]肯定是偶数长度路径那么就输出Yes(等于也输出Yes
L是偶数且leven[x](even[x]肯定是偶数长度路径那么就输出No
不明白为啥就看重新看一下三个部分。
初始化
都初始化成0x3f(是一个较大数就可以了
代码code
#includebits/stdc.h
using namespace std;
int n,m,q;
int even[100010];// even[x]表示从1走到x长度最短为偶数的路径的长度even是偶数的意思
int odd[100010];// odd[x]表示从1走到x长度最短为奇数的路径的长度odd是奇数的意思
vectorvectorint v(100010);
//int vis[100010][10010];
void init()
{queuepairint,int q;q.push({1,0});while(!q.empty()){int nodeq.front().first,stepq.front().second;q.pop();for(auto it:v[node]){if(step%2 1even[it] 0x3f3f3f3f){even[it] step1;
// vis[it][step1] 1;q.push({it,step1});}if(step%2 0odd[it] 0x3f3f3f3f)//有没有走过{odd[it] step1;
// vis[it][step1] 1;q.push({it,step1});}/*有些童鞋会说这里odd是奇数可是为啥是放在step%2 0里面不应该是放even吗。回答step还要1因为已经走了这一步要加一偶数加1就是奇数所以是odd放在里面。18行~23行同理*/}}
}
int main()
{cinnmq;for(int i1;im;i){int u,v1;cinuv1;v[u].push_back(v1);v[v1].push_back(u);}memset(odd,0x3f,sizeof(odd));memset(even,0x3f,sizeof(even));init();while(q--){int l,x;cinxl;if(l%2 1){if(lodd[x]){coutYes\n;}else{coutNo\n;}}else{if(leven[x]){coutYes\n;}else{coutNo\n;}}}return 0;
}
