> 文章列表 > 未初始化警告(2023寒假每日一题 12)

未初始化警告(2023寒假每日一题 12)

未初始化警告(2023寒假每日一题 12)

一个未经初始化的变量,里面存储的值可能是任意的。

因此直接使用未初始化的变量,比如将其赋值给另一个变量,并不符合一般的编程逻辑。

代码中出现这种情况,往往是因为遗漏了初始化语句、或是打错了变量名。

对代码中使用了未初始化变量的语句进行检查,可以方便地排查出代码中的一些隐秘 BugBugBug

考虑一段包含 kkk 条赋值语句的简单代码。

该段代码最多使用到 nnn 个变量,分别记作 a1,a2,⋯,ana_1,a_2,⋯,a_na1,a2,,an;该段代码使用的常量均记作 a0a_0a0

iii 条(1≤i≤k1≤i≤k1ik)赋值语句为 axi=ayia_{x_i}=a_{y_i}axi=ayi,满足 1≤xi≤n、0≤yi≤n1≤x_i≤n、0≤y_i≤n1xin0yin,表示将 ayia_{y_i}ayi 的值赋给变量 axia_{x_i}axi

其中 axia_{x_i}axi 被称为该赋值语句的左值,一定是个变量;ayia_{y_i}ayi 被称为右值,可以是一个常量或变量。

对于任意一条赋值语句 axi=ayia_{x_i}=a_{y_i}axi=ayi,如果右值 ayia_{y_i}ayi 是一个变量,则其应该在此之前被初始化过。

具体来说,如果变量 ayia_{y_i}ayi 在前 i−1i−1i1 条赋值语句中做为左值出现过,即存在 j<ij<ij<i 满足 xj=yix_j=y_ixj=yi
(这里无需考虑第 j 条赋值语句本身是否也有右值未初始化的问题),我们就认为在第 iii 条赋值语句中 ayia_{y_i}ayi 已被初始化;否则,我们认为该条语句存在右值未初始化的问题。

按照上述规则,试统计给定的代码中,有多少条赋值语句右值未被初始化。

输入格式
输入的第一行包含空格分隔的两个正整数 n、kn、knk,分别表示变量的数量和赋值语句的条数。

接下来输入 kkk 行,其中第 iii 行(1≤i≤k1≤i≤k1ik)包含空格分隔的两个正整数 xi、yix_i、y_ixiyi,表示第 iii 条赋值语句。

纠错: 其实 yiy_iyi 可以等于 000,所以 yiy_iyi 不一定是正整数(可参考样例),此为官网题面描述存在问题,特此指出。

输出格式
输出一个整数,表示有右值未被初始化问题的赋值语句条数。

数据范围
50%50\\%50% 的测试数据满足 0<n,k≤10000<n,k≤10000<n,k1000;全部的测试数据满足 0<n,k≤105,1≤xi≤n,0≤yi≤n0<n,k≤10^5,1≤x_i≤n,0≤y_i≤n0<n,k1051xin0yin

输入样例:

10 7
1 2
3 3
3 0
3 3
6 2
2 1
8 2

输出样例:

3

样例解释
其中第一、二、五一、二、五一、二、五条赋值语句右值未被初始化。


#include<iostream>using namespace std;const int N = 100010;int n, k;
bool st[N];int main(){scanf("%d%d", &n, &k);int x, y;int cnt = 0;for(int i = 0; i < k; i++){scanf("%d%d", &x, &y);if(!y) st[x] = true;else{if(!st[y]) cnt++;st[x] = true;}}printf("%d\\n", cnt);return 0;
}