洛谷P3952 时间复杂度题解

17年提高组的原题，相当有练习的价值。
题目

来直接切切入正题。

这个题就是个大模拟，难于处理的原因在于需要注意的细节比较多。只要挑选好模拟的数据结构，处理好细节问题，这道题就可以A掉了。

大致设想

为了模拟循环的嵌套关系，数据结构上选择先进后出的栈结构。 考虑到在计算嵌套层数同时还需要判定循环变量是否重复。所以，需要同时维护两个栈，一个统计层数，一个统计变量。

（有一个需要注意的点，就是在读入的时候，最好不要使用字符，而是用字符串，可以避免一系列的扯皮问题。）

开始模拟

• 每组数据，读入行数和复杂度字符串，从字符串中提取指定复杂度。（注意，复杂度的提取有两种情况，不是O(1)时还需要注意指定复杂度可能是多位数）
  • 每一行数据，先读第一个字符，
    是E则
    弹栈并继续 ，若栈已经清空不能弹栈，说明出现了额外结束的情况，应标记错误。 （注意弹栈不要让栈顶为负RE警告）
    是F则：

    • 继续读入循环变量并判定重复并记录，重复则标记错误。

    • 读入循环始末，判断并计算该层的复杂度贡献。共可能有四种情况：

      • 前数后数，判断大小，前小后大，常数；前大后小，无效。
      • 前n后n，常数
      • 前数后n，一个标准的循环，复杂度指数指数加一。
      • 前n后数，n很大，所以无效。

      在计算这里的复杂度时，应该由上一层继承而来。

      • 复杂度常数时，指数不变，照抄上一位
      • 复杂度n时，指数加一，抄上一位并加一。
      • 无效复杂度时，定为负无穷，令后面的循环一并无效。

      （需要注意的是：由于栈顶从0开始计数，照抄上一位时需要判定是否为第一位，当然，从1开始计数可以避免这个问题。）

    • 统计答案，令当前最高统计复杂度与改位复杂度取大

    • 栈顶向前移动。

易错点总结

WA血泪史，划重点！！！

1 输入使用字符串代替字符.
2. 弹栈时注意栈顶不要减为负数
3. 数字可能不止一位
4. 记栈时注意首元素没有前一位

代码

C：

#include<stdio.h>
#include<string.h>
#define N 200
#define INF 1 << 30

int stack[N];		//统计层数 
char cstack[N];		//统计变量 
char ch[20],ch2[20];

//检查数组中是否包含元素k 
bool check(char ch[],int len,char k)
{
	for(int i = 0;i < len;i++)
	{
		if(ch[i] == k)
		{
			return true;
		}
	}
	return false;
}

//字符串转数字 
int getNumber(char ch[])
{
	int num = 0;
	for(int i = 0;i < strlen(ch);i++)
	{
		num = num * 10 + ch[i] - '0';
	}
	return num;
}

int max(int a,int b)
{
	return a > b ? a : b;
}

int main()
{
	int T;		//组数 
	int num;	//给定复杂度 
	int ma;		//统计复杂度 
	int n;		//每组行数 
	int top;	//栈顶 
	char a,b;	//循环始末 
	bool flag;	//错误标记 
	
	//读入组数 
	scanf("%d",&T);
	
	while(T--)
	{
		/*数据初始化：统计复杂度为零，栈清空，清除错误标记*/
		num = 0;
		flag = false;
		top = 0;
		ma = 0;
		//输入行数和给定复杂度 
		scanf("%d%s",&n,ch);
		//计算给定复杂度 
		if(strcmp(ch,"O(1)") == 0)
		{
			num = 0;
		}
		else
		{
			for(int i = 4;i < strlen(ch) - 1;i++)
			{
				num = num * 10 + ch[i] - '0';
			}
		}
		
		//开始处理 
		while(n--)
		{
			//第一个字符 
			scanf("%s",ch);
			if(ch[0] == 'E')
			{
				//结束一层循环，弹栈 
				top--;
				//结束符多余 
				if(top < 0)
				{
					top = 0;//重置栈顶 
					flag = true;//错误标记 
				}
				continue;
			}
			
			//首字母不是'E'继续处理
			//判定循环变量 
			scanf("%s",ch);
			if(check(cstack,top,ch[0]))
			{
				//循环变量重复，错误标记 
				flag = true;
			}
			cstack[top] = ch[0];
			
			//计算循环复杂度 
			scanf("%s%s",ch,ch2);
			a = ch[0];
			b = ch2[0];
			//四种情况（合法指数加一或零，否则刷为负无穷）：
			//完整循环
			if(a != 'n' && b == 'n')
			{
				stack[top] = top == 0 ? 1 : stack[top - 1] + 1;
			}
			//常数(前小后大合法，后大前小不合法)
			if(a != 'n' && b != 'n')
			{
				stack[top] = getNumber(ch) <= getNumber(ch2) ? (top == 0 ? 0 : stack[top - 1]) : -INF;
			}
			//n到常数,不合法
			if(a == 'n' && b != 'n')
			{
				stack[top] = -INF;
			}
			//n到n,复杂度指数不变
			if(a == 'n' && b == 'n')
			{
				stack[top] = top == 0 ? 0 : stack[top - 1];
			}
			//统计复杂度 
			ma = max(ma, stack[top]);
			//下一层 
			top++;
		}
		
		//有错误标记或者循环没有完全退出 
		if(flag || top != 0)
		{
			printf("ERR\n");
		}
		//否则判定给定复杂度是否与统计复杂度相同 
		else
		{
			printf(ma == num ? "Yes\n" : "No\n");
		}
	}
}

java：

import java.util.Scanner;

public class Main {
	
	static final int INF = 1 << 30;
	
	static boolean charge(char[] cstack,int k,char c)
	{
		for(int i = 0 ;i < k;i++)
		{
			if(cstack[i] == c)
			{
				return true;
			}
		}
		return false;
	}
	
	static int getNumber(String ch)
	{
		int num = 0;
		for(int i = 0;i < ch.length();i++)
		{
			num = num * 10 + ch.charAt(i) - '0';
		}
		return num;
	}
	
	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		
		int n;
		int num = 0;
		int[] stack = new int[2000];
		char[] cstack = new char[2000];
		int top;
		int max;
		boolean flag;
		String ch,ch2;
		
		while(T-- > 0)
		{
			//初始化，栈清空，复杂度设1，错误标记清除
			top = 0;
			max = 0;
			num = 0;
			flag = false;
			
			
			//读取程序信息
			n = scan.nextInt();
			ch = scan.next();
			
			//分离复杂度
			if(ch.equals("O(1)"))
			{
				num = 0;
			}
			else
			{
				for(int i = 4;i < ch.length() - 1;i++)
				{
					num = num * 10 + ch.charAt(i) - '0';
				}
			}
			
			//开始处理
			while(n-- > 0)
			{
				//第一个字符
				ch = scan.next();
				//循环结束
				if(ch.charAt(0) == 'E')
				{
					top--;
					//不匹配情况1：E多
					if(top < 0)
					{
						flag = true;
						top = 0;
					}
					continue;
				}
				
				ch = scan.next();
				//判定字符是否出现
				if(charge(cstack,top,ch.charAt(0)))
				{
					flag = true;
				}
				cstack[top] = ch.charAt(0);
				
				//接入循环始末
				ch = scan.next();
				ch2 = scan.next();
				char a = ch.charAt(0);
				char b = ch2.charAt(0);
				
				//四种情况（合法指数加一或零，否则刷为负无穷）：
				//完整循环
				if(a != 'n' && b == 'n')
				{
					stack[top] = top == 0 ? 1 : stack[top - 1] + 1;
				}
				//常数(前小后大合法，后大前小不合法)
				if(a != 'n' && b != 'n')
				{
					stack[top] = getNumber(ch) <= getNumber(ch2) ? (top == 0 ? 0 : stack[top - 1]) : -INF;
				}
				//n到常数,不合法
				if(a == 'n' && b != 'n')
				{
					stack[top] = -INF;
				}
				//n到n,复杂度指数不变
				if(a == 'n' && b == 'n')
				{
					stack[top] = top == 0 ? 0 : stack[top - 1];
				}
				
				max = Math.max(max, stack[top]);
				
				//指向下一位
				top++;
			}
			//输出答案,不匹配情况2：F多
			if(flag || top != 0)
			{
				System.out.println("ERR");
			}
			else
			{
				System.out.println(max == num ? "Yes" : "No");
			}
		}
	}
}

如有错误，敬请指教。