2019年NOIP普及组T1-数字游戏 

题目描述

小K同学向小P同学发送了一个长度为 8 的 01 字符串来玩数字游戏，小 P 同学想 要知道字符串中究竟有多少个 1。   

注意：01 字符串为每一个字符是 0 或者 1 的字符串，如"101"（不含双引号）为一 个长度为 3 的 01 字符串。

输入格式

输入文件名为 number.in。  

输入文件只有一行，一个长度为 8 的 01 字符串 S。

输出格式

输出文件名为 number.out。  

输出文件只有一行，包含一个整数，即 01 字符串中字符 1 的个数。 

输入输出样例

输入样例1：

00010100

输出样例1：

2

输入样例2：

11111111

输出样例2：

8

说明

【输入输出样例 1 说明】 该 01 字符串中有 2 个字符 1

【输入输出样例 2 说明】 该 01 字符串中有 8 个字符 1

【数据规模与约定】 

 对于 20% 的数据，保证输入的字符全部为 0。 

 对于 100% 的数据，输入只可能包含字符 0 和字符 1，字符串长度固定为 8。 

耗时限制1000ms  内存限制128MB

解析

考点：字符串

解法一：遍历每个字符， 统计字符'1'出现的数量。

参考代码

#include<bits/stdc++.h>
using namespace std;
/*
遍历每个字符，判断如果是字符'1'则计数
*/
int main() {
	string s;
	cin>>s;
	int c = 0;
	for(int i = 0;i < s.size();i++){
		if(s[i] == '1') c++;
	}
	cout<<c;
	return 0;
}

解法二：读入 8 个字符，逐个判断是否是字符’1’

#include <bits/stdc++.h>
using namespace std;
int r = 0;//最终结果
char c;
int main(){
	//读入 8 个字符
	for(int i = 1;i <= 8;i++){
		cin>>c;
		//如果是字符 1
		if(c == '1') r++;
	}
	cout<<r;
	return 0;
}

注意：

如果遇到先读入整数，再读入一行字符串这一类的问题，可以使用 getchar() / cin.get()读掉多余的回车符；

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    string s;
    cin>>n;
    getchar();//读掉回车
    //cin.get();
    getline(cin,s);
    cout<<n<<endl<<s<<endl;
    return 0;
}

2019年NOIP普及组T2-公交换乘

题目描述

著名旅游城市 B 市为了鼓励大家采用公共交通方式出行，推出了一种地铁换乘公交 车的优惠方案： 

1. 在搭乘一次地铁后可以获得一张优惠票，有效期为 45 分钟，在有效期内可以消耗这张优惠票，

免费搭乘一次票价不超过地铁票价的公交车。在有效期内指 开始乘公交车的时间与开始乘地铁的时间之差小于等于 45 分钟，

    即：   tbus-tsubway≤45 

2. 搭乘地铁获得的优惠票可以累积，即可以连续搭乘若干次地铁后再连续使用优 惠票搭乘公交车。 

3. 搭乘公交车时，如果可以使用优惠票一定会使用优惠票；如果有多张优惠票满 足条件，则优先消耗获得最早的优惠票。 

现在你得到了小轩最近的公共交通出行记录，你能帮他算算他的花费吗？ 

输入格式

输入文件名为 transfer.in。  

输入文件的第一行包含一个正整数 n，代表乘车记录的数量。  

接下来的n行，每行包含 3 个整数，相邻两数之间以一个空格分隔。

第i行的 第 1 个整数代表第i条记录乘坐的交通工具，0 代表地铁，1 代表公交车；

        第 2 个整数代表第i条记录乘车的票价pricei

        第 3 个整数代表第i条记录开始乘车的时间ti （距 0 时刻的分钟数）。 

我们保证出行记录是按照开始乘车的时间顺序给出的，且不会有两次乘车记录出现在同一分钟。

输出格式

输出文件名为 transfer.out。 

输出文件有一行，包含一个正整数，代表小轩出行的总花费 

输入输出样例

输入样例1：

6  
0 10 3  
1 5 46  
0 12 50  
1 3 96  
0 5 110  
1 6 135

输出样例1：

36

输入样例2：

6  
0 5 1  
0 20 16  
0 7 23  
1 18 31  
1 4 38  
1 7 68

输出样例2：

32

说明

【输入输出样例 1 说明】 

第一条记录，在第 3 分钟花费 10 元乘坐地铁。 

第二条记录，在第 46 分钟乘坐公交车，可以使用第一条记录中乘坐地铁获得的优惠票，因此没有花费。 

第三条记录，在第 50 分种花费 12 元乘坐地铁。 

第四条记录，在第 96 分钟乘坐公交车，由于距离第三条记录中乘坐地铁已超过 45 分钟，所以优惠票已失效，花费 3元乘坐公交车。 

第五条记录，在第 110 分钟花费 5 元乘坐地铁。 

第六条记录，在第 135 分钟乘坐公交车，由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效，而本次公交车的票价为6元，

高于第五条记录中地铁的票价 5 元， 所以不能使用优惠票，花费 6 元乘坐公交车。 

总共花费 36 元

【输入输出样例 2 说明】 

第一条记录，在第 1 分钟花费 5 元乘坐地铁。 

第二条记录，在第 16 分钟花费 20 元乘坐地铁。

第三条记录，在第 23 分钟花费 7 元乘坐地铁。 

第四条记录，在第 31 分钟乘坐公交车，此时只有第二条记录中乘坐的地铁票价高于本次公交车票价，所以使用第二条记录中乘坐地铁获得的优惠票。 

第五条记录，在第 38 分钟乘坐公交车，此时第一条和第三条记录中乘坐地铁获得的优惠票都可以使用，使用获得最早的优惠票，即第一条记录中乘坐地铁获得的优惠票。

第六条记录，在第 68 分钟乘坐公交车，使用第三条记录中乘坐地铁获得的优惠票。 总共花费 32 元。

【数据规模与约定】  

 对于30%的数据，n≤ 1,000，ti≤ 10^6。 

 另有 15% 的数据，ti≤ 10^7，pricei都相等。 

 另有 15% 的数据，ti ≤ 10^9，pricei都相等。  

 对于 100% 的数据，n ≤ 10^5，ti ≤ 10^9，1 ≤ pricei ≤ 1,000。 

耗时限制1000ms  内存限制256MB

解析

考点:队列、模拟

维护 45 分钟的优惠券队列，来存储当前可用的优惠券：

1、如果是当前是地铁票， 先买票，然后将优惠券存入队列；

2、如果当前是公交车：

从队列中， 找出第 1 个没有被用过的，且金额>=当前票价的优惠券； 找到： 标记该优惠券使用；

没找到：只能买票！

队列可以用数组模拟（本题不适合用 STL 的 queue 解题， 因为 queue 无法遍历， 我们 需要遍历 queue 找到第 1 张符合条件的优惠券）！

参考代码:

#include <bits/stdc++.h>
using namespace std;
/*
有多张优惠票满足条件，
则优先消耗获得最早的优惠票
1.坐地铁
买票
获得等额的优惠券：金额、获得时间、是否使用过
2.坐公交
在有效期内的优惠券中，查找第 1 张金额>=公交票价的优惠券
找到：使用该优惠券
找不到：买票
使用队列，维护优惠券的信息
*/
const int N = 1e5 + 10;
struct node{
	int price,time;
bool used;
}q[N];//优惠券的队列
int h = 1,t = 0;
int n,ans = 0;
int main(){
	scanf("%d",&n);
	int type,money,start;
	for(int i = 1;i <= n;i++){
		scanf("%d%d%d",&type,&money,&start);
		//如果是地铁
		if(type == 0){
			//买票，获得优惠券
			ans += money;
			t++;
			q[t].price = money;
			q[t].time = start;
			q[t].used = false;//默认没有使用
		}else{
			//公交
			//丢弃过期的优惠期
			while(h<=t&&start-q[h].time>45) h++;
			bool f = false;//假设没找到			
			//在有效期内的优惠券，找第一张>=公交票价的 且 没有用过的优惠券 
			for(int j = h;j <= t;j++){
				if(q[j].price >= money && q[j].used == false){
					q[j].used = true;
					f = true;
					break;
				}
			}
			//如果没有找到能用的优惠券，买票
			if(f == false) ans += money;
		}
	}
	printf("%d",ans);
	return 0;
}
	

2019年NOIP普及组T3-纪念品

题目描述

小伟突然获得一种超能力，他知道未来 T 天 N 种纪念品每天的价格。某个纪念品 

的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。

每天，小伟可以进行以下两种交易无限次： 

1．任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品； 

2．卖出持有的任意一个纪念品，以当日价格换回金币。 

每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。

当然，一直持有纪念品也是可以的。 T 天之后，小伟的超能力消失。因此他一定会在第 T 天卖出所有纪念品换回金币。 

小伟现在有 M 枚金币，他想要在超能力消失后拥有尽可能多的金币

输入格式

输入文件名为 souvenir.in。  

第一行包含三个正整数 T,N,M，相邻两数之间以一个空格分开，分别代表未来天数 T，纪念品数量 N，小伟现在拥有的金币数量 M。  

接下来 T 行，每行包含 N 个正整数，相邻两数之间以一个空格分隔。

第 i 行的 N 个正整数分别为 pi1, pi2,......, PiN，其中 Pij表示第i天第j种纪念品的价格

输出格式

输出文件名为 souvenir.out。 

输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。

输入输出样例

输入样例1：

6 1 100  
50 
20 
25 
20 
25 
50

输出样例1：

305

输入样例2：

3 3 100  
10 20 15  
15 17 13  
15 25 16 

输出样例2：

217

说明

【输入输出样例 1 说明】  

 最佳策略是： 

 第二天花光所有 100 枚金币买入 5 个纪念品 1； 

 第三天卖出 5 个纪念品 1，获得金币 125 枚； 

 第四天买入 6 个纪念品 1，剩余 5 枚金币； 

 第六天必须卖出所有纪念品换回 300 枚金币，

 第四天剩余 5 枚金币,共 305 枚金币。

 超能力消失后，小伟最多拥有 305 枚金币。

 【输入输出样例 2 说明】 

 最佳策略是： 

 第一天花光所有金币买入 10 个纪念品 1； 

 第二天卖出全部纪念品 1 得到 150 枚金币并买入 8 个纪念品 2 和 1 个纪念品 3，剩 余 1 枚金币； 

 第三天必须卖出所有纪念品换回216 枚金币，第二天剩余1枚金币，共 217 枚金币。 

 超能力消失后，小伟最多拥有 217 枚金币。

 【数据规模与约定】  

 对于 10% 的数据，T= 1。  

 对于 30% 的数据，T≤ 4, N≤ 4, M≤ 100，所有价格 10 ≤Pij≤ 100。  

 另有 15% 的数据，T≤ 100, N= 1。  

 另有 15% 的数据，T= 2, N ≤ 100。  

 对于 100% 的数据,T≤ 100,N≤ 100, M≤ 10^3，所有价格 1 ≤ Pij ≤ 10^4，数据保证任意时刻，小明手上的金币数不可能超过10^4。 

耗时限制1000ms  内存限制128MB

解析：

考点：动态规划、背包 DP,贪心

（1）10%的 t=1 的结果，答案是确定的， 1 天不可能产生交易，因此答案肯定是 m 个 金币。

（2）在第 a 天买入，第 b 天卖出（b>a）

等价于：第 a 天买入，第 a+1 天卖出，第 a+1 天买入，第 a+2 天卖出……最后在第 b 天卖出。

从而将多天的买卖转换为：周期为 1 天的交易。

问题转换： 如果有 m 元， 在第 i 天买入， 第 i+1 天卖出， 不限制购买数量的情况下， 最大收益是多少？

（3）初始金币数： M

目标：让第二天的金币数尽可能的多，再让第三天的金币数量尽可能多，依次类推……

贪心求解：

第 i 天金币数量 M(i)，第 i+1 天的金币数量 M(i+1)

第 i 天可以买纪念品无限多个， 第 i 天有 M(i)个金币，那么最大收益就是完全背包问 题！

（4）背包容量： M

体积： price[i][j]（第 i 天的第 j 个物品的价格）

价值： 第 i 天买入， 第 i+1 天卖出，所获得的收益（卖出 -买入）。

M(i+1)=M(i)+最大收益

（5）本题只需要计算： price(i,j)<price(i+1,j)的数据，来减少循环！

背包的容量就是现有的钱数，物品的价值就是第 i+1 天和第 i 天的价值的差！！！ 本题相当于做 t-1 次完全背包！

参考代码

#include <bits/stdc++.h>
using namespace std;
int p[110][110];//存储所有的物品每天的价格
int f[10010];//最大收益
int t,n,m;
int main(){
	cin>>t>>n>>m;
	//读入 t 天每天的 n 个物品的价格
	for(int i = 1;i <= t;i++){
		for(int j = 1;j <= n;j++){
			cin>>p[i][j];
		}
	}
	//进行 t-1 次交易（完全背包）
	for(int i = 1;i < t;i++){
		memset(f,0,sizeof(f));
		//循环 n 个物品
		for(int j = 1;j <= n;j++){
		//如果涨价的情况下，产生交易
			if(p[i][j] < p[i+1][j]){
			//循环物品重量（价格） ~背包容量
				for(int k = p[i][j];k <= m;k++){
					f[k] = max(f[k],f[k-p[i][j]]+(p[i+1][j] - p[i][j])); 
				}
			}
		}
		m += f[m];
	}
	cout<<m;
	return 0;
}

2019年NOIP普及组T4-加工零件

题目描述

凯凯的工厂正在有条不紊地生产一种神奇的零件，神奇的零件的生产过程自然也很神奇。

工厂里有n位工人，工人们从 1~n编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。 

如果x号工人想生产一个被加工到第L(L> 1) 阶段的零件，则所有与x号工人有传送带直接相连的工人，都需要生产一个被加工到第L-1 阶段的零件（但x号工 人自己无需生产第L-1阶段的零件）。 如果x号工人想生产一个被加工到第1阶段的零件，则所有与x号工人有传送带直接相连的工人，都需要为x号工人提供一个原材料。 

轩轩是 1 号工人。现在给出q张工单，第i张工单表示编号为ai的工人想生产一个第Li阶段的零件。轩轩想知道对于每张工单，他是否需要给别人提供原材料。他 知道聪明的你一定可以帮他计算出来！

输入格式

san输入文件名为 work.in。 

第一行三个正整数N,M和q，分别表示工人的数目、传送带的数目和工单的数目。 

接下来 M行，每行两个正整数u和v，表示编号为u和v的工人之间存在一条零 件传输带。保证u不等于v。 

接下来 Q行，每行两个正整数a和L，表示编号为a的工人想生产一个第L阶段的零件

输出格式

输出文件名为 work.out。 

共Q行，每行一个字符串 “Yes” 或者 “No”。

如果按照第i张工单生产，需要编号为1的轩轩提供原材料，则在第i行输出 “Yes”；否则在第i行输出 “No”。注意输出不含引号。 

输入输出样例

输入样例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：

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,4 的工人提供原材料。 

编号为 1 的工人想生产第 3 阶段的零件，需要编号为 2 和 5 的工人生产第 2 阶段的零件，需要编号为 1,3,4 的工人生产第 1 阶段的零件，需要编号为 2,3,4,5 的工人提供 原材料。 

编号为 1 的工人想生产第 4 阶段的零件，需要编号为 2 和 5 的工人生产第 3 阶段 的零件，需要编号为 1,3,4 的工人生产第 2 阶段的零件，需要编号为 2,3,4,5 的工人生产 第 1 阶段的零件，需要全部工人提供原材料。 

编号为 1 的工人想生产第 5 阶段的零件，需要编号为 2 和 5 的工人生产第 4 阶段 的零件，需要编号为 1,3,4 的工人生产第 3 阶段的零件，需要编号为 2,3,4,5 的工人生产 第 2 阶段的零件，需要全部工人生产第 1 阶段的零件，需要全部工人提供原材料 

【数据规模与约定】  

 1≤u,v,a≤n。 

 测试点 1~4，1≤n,m ≤1000，q= 3，L= 1。 

 测试点 5~8，1 ≤n,m≤ 1000，q= 3，1 ≤L≤ 10。 

 测试点 9~12，1 ≤n,m,L≤ 1000，1 ≤q≤ 100。 

 测试点 13~16，1 ≤n,m,L≤ 1000，1≤q≤ 10^5。 

 测试点 17~20，1 ≤n,m,q≤ 10^5，1 ≤L≤ 10^9。

耗时限制1000ms   内存限制128MB

解析

考点:图论、图的最短路、邻接表

解法一：

思路：深搜枚举每个点  40分

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
vector<int> g[N]; //邻接表存储图
int vis[N][N]; //标记是否访问
int n, m, q;
void dfs(int u, int d){
    if(d == -1 || vis[u][d]) return;
    vis[u][d] = 1;
    for(int i = 0; i < g[u].size(); i++)    {
        int v = g[u][i];
        dfs(v, d - 1);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    while(m--){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    while(q--){
        int a, L;
        cin >> a >> L;
        memset(vis,0,sizeof(vis));
        dfs(a, L); //对于每个点，都深搜找一遍能否到1点需要0步
        if(vis[1][0]) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

解法二：奇偶最短路

很容易想到用最短路来解决这道题，因为两个点之间可以互相无限走，所以如果到某个点的最短路是x，那么x+2，x+4也一定能够达到。

但是如何保证这是正确的呢？比如说到某个点的最短路是x，为什么不可能走一下弯路，是某一条路径的长度是x+1或者x+3或者x+5呢？

所以就用到了奇偶最短路。所谓奇偶最短路，就是对于每一个点，记录下走偶数步的最短路（ou[i]）和走奇数步的最短路（ji[i]），转移式为：

ji[v]=min(ou[u]+1,ji[v]);

ou[v]=min(ji[u]+1,ou[v]);

初始，源点的偶数最短路为 0，奇数最短路为无穷大。

代码实现上，因为是无权图，所以可以使用 BFS，如果是带权图，那必须使用 最短路算法。

邻接表写法

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n, m, q, d1[N], d2[N], flag[N];  //1: 奇数 2: 偶数
vector<int> g[N];    //邻接表 
void bfs(int s) {
    memset(d1, 0x3f, sizeof d1);
    memset(d2, 0x3f, sizeof d2);
    d2[s] = 0;
    queue<int> q;
    q.push(s);
    flag[s] = 1;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        flag[u] = 0;
        for(int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if(flag[v]) continue;
            if(d1[v] > d2[u] + 1) {
                d1[v] = d2[u] + 1;
                flag[v] = 1;
                q.push(v);
            }
            if(!flag[v] && d2[v] > d1[u] + 1) {
                d2[v] = d1[u] + 1;
                flag[v] = 1;
                q.push(v);
            }
        }
    }
}
int main(){
    cin >> n >> m >> q;
    while(m--) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs(1);
    while(q--) {
        int a, L;
        cin >> a >> L;
        if(a ==1 && g[a].empty()) {
            cout << "No\n";
            continue;
        }
        if(L%2==0) {
            if(d2[a] <= L) cout << "Yes\n";
            else cout << "No\n";
        }else{
            if(d1[a] <= L) cout << "Yes\n";
            else cout << "No\n";
        }
    }
    return 0;
}

链式前向星存图

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e5+5;
int n, m, q;
//xx[i]:走到节点 i 偶数步的最短路（ou[i]）和奇数步的最短路（ji[i]）
int ji[N], ou[N];
bool vis[N];
queue<int> que;

// 链式前向星存图
struct edge{
    int v, next;  // 表示与这个边起点相同的上一条边的编号
} e[2*N];
int cnt, head[N]; // head[i]：以 i 为起点的最后一条边的编号

void insert(int u, int v){
    e[++cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt;    // 
}

int main(){
    ios::sync_with_stdio(false);
    memset(ji, 0x3f, sizeof ji);
    memset(ou, 0x3f, sizeof ou);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        insert(u, v);
        insert(v, u);
    }
    
    // bfs 最短路
    ou[1] = 0;
    que.push(1);
    while(!que.empty()){
        int u = que.front();
        que.pop();
        vis[u] = false;
        for(int i = head[u]; i; i = e[i].next){
            int v = e[i].v;  // 当前
            if(ji[v] > ou[u] + 1){
                ji[v] = ou[u] + 1;
                if(!vis[v]){
                    que.push(v);
                    vis[v] = true;
                }
            }
            if(ou[v] > ji[u] + 1){
                ou[v] = ji[u] + 1;
                if(!vis[v]){
                    que.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    for(int i = 1; i <= q; i++){
        int a, l;
        cin >> a >> l;
        if(a ==1 && head[a]==0) {
            cout << "No\n";
            continue;
        }
        if(((l&1)&&ji[a]<=l) || (!(l&1)&&ou[a] <= l))
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}

    

补充一个较为详细的题解

1 1：1 要生产 1 阶段， 2 提供原材料，1 不可能要，No

2 1：2 要生产 1 阶段， 1 和 3 提供原材料，Yes

3 1：3 要生产 1 阶段， 1 提供原材料，No

1 2：1 要生产 2 阶段， 2 生产 1 阶段，3 和 1 提供原材料，Yes

2 2：2 要生产 2 阶段， 1 和 3 生产 1 阶段， 2 提供原材料，No

3 2：3 要生产 2 阶段， 2 生产 1 阶段，1 和 3 提供原材料，Yes

问： x 号要生产 len 阶段的零件， 1 号是否需要提供原材料。

相当于问：从 1 号点出发，经过 len 步能否走到 x 点。路线可以折回走（来回走）

如果从 1 号点走到 x 号点，有最少奇数次的步数 mins，x 号点可以要求生产>=mins 的
奇数阶段的零件。
如果从 1 号点到 x 号点，有最少偶数次的步数 mins，x 号点可以要求生产>=mins 的偶
数阶段的零件。

核心思想：

假设 L 是奇数。

存在长度是 L 的奇数路径，相当于： L>=长度是奇数的最短路。

因此， 需要求： 1~a 中长度是奇数的最短路 和 长度为偶数的最短路。

3.变量含义

dis[v][1] 表示 1 号点到达 v 的最短奇数路径

dis[v][0] 表示 1 号点到达 v 的最短偶数路径

dis[v][0] = min(dis[v][0],dis[u][1]+1)

dis[v][1] = min(dis[v][1],dis[u][0]+1)

1 号点到 1 号点的最短偶数路径为 0

1 号点到 1 号点的最短奇数路径为不存在，设置为无穷大

思路：

1. 求出 1 号点到每个点的最短奇数路径，和最短偶数路径；

2. q 次询问，每次询问 x 号工人，如果生产 len 阶段的零件， 1 号点是否需要原材料；

如果 1 号点存在到 x 号点的最短奇数路径 mins，且 len 是奇数，且 len >= mins，1 号点就需要提供原 材料

偶数性质同上；

SPFA 求奇偶最短路。

#include <bits/stdc++.h>
using namespace std;
using namespace std;
const int N = 1e5 + 10;
struct node{
	int to,next;
}a[N*2];
int pre[N],k = 0;
queue<int> q;//队列
//d[i][0]代表走到每个点的偶数最短路
int d[N][2];
bool vis[N][2];
int n,m,t;
//建边
void add(int u,int v){
	k++;
	a[k].to = v;
	a[k].next = pre[u];
	pre[u] = k;
}
int main(){
	scanf("%d%d%d",&n,&m,&t);
	int x,y;
	for(int i = 1;i <= m;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);//双向建边
	}
	//求 1 号点到每个点的奇偶最短路
	memset(d,0x3f,sizeof(d));
	//1 号点走到自己的偶数最短路是 0
	d[1][0] = 0;
	//如果 1 号点到其他点没有边
	if(pre[1] == 0) d[1][0] = 0x3f3f3f3f;
	q.push(1);
	while(!q.empty()){
		int u = q.front();
		for(int i = pre[u];i != 0;i = a[i].next){
			int to = a[i].to;
			if(d[u][0]+1<d[to][1]){
				d[to][1] = d[u][0] + 1;
				//如果该点不在队列，存入队列
				if(!vis[to][1]){
					q.push(to);
					vis[to][1] = true;
				}
			}
			//走到 u 点奇数最短路+1<走到 to 点的偶数最短路
			if(d[u][1]+1<d[to][0]){
				//更新走到 to 点的偶数最短路
				d[to][0] = d[u][1] + 1;
				if(!vis[to][0]){
					q.push(to);
					vis[to][0] = true;
				}
			}
		}
		q.pop();
	}
	//t 次询问
	int len;
	while(t--){
		scanf("%d%d",&x,&len);
		if(d[x][len%2]<=len) printf("%s\n","Yes");
		else printf("%s\n","No");
	}
	return 0;
}