第十七届电子科技大学程序设计竞赛暨西南地区高校邀请赛热身赛个人解题记录

用的是去年初赛的题目

E题:Charlie

题目链接:https://acm.uestc.edu.cn/problem/charlie/description

这道题一开始想的是,寻找01,然后删除

然后很不幸的TLE了

再观察数据大小,认为无论怎样优化都会TLE,所以开始思考别的写法

既然他是要删除01,那么1必然在0后面才有可能删

那么可以利用栈的思想,遇到0进栈,1出栈(前提是有东西出),但实际上不用管栈里是啥,用一个int变量计数即可

代码如下:

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int main()
{
	int t,n;
	string str;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		cin >> n;
		cin >> str;
		int len = str.size();
		int a = 0;
		int sum = str.size();
		for (int j = 0; j < len; j++)
		{
			if (str[j] == '0')
			{
				a++;
			}
			if (str[j] == '1'&& a > 0)
			{
				a--;
				sum -= 2;
			}
		}
		printf("%d.000\n",sum);
	}
	return 0;
}

G题:Find Substring

题目链接:https://acm.uestc.edu.cn/problem/find-substring/description

这道题后来看题解,似乎有更简单的做法

当然我是没想到,想到的唯一方法就是枚举所有子字符串

然后TLE了8次

经过我不懈的优化,终于过了……

代码如下:

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int strnum[100000];
int main()
{
	string str;
	int len;
	int num[26];
	int lin[26];
	int sum1=0;
	int q;
	bool isok=false;
	cin >> str;
	len = str.size();
	for (int i = 0; i < len; ++i)
	{
		strnum[i] = str[i] - 97;
	}
	for (int i = 0; i < 26; i++)
	{
		cin >> num[i];
		sum1 += num[i];
	}
	for (int i = 0; i < len ; ++i)
	{
		if (isok)
		{
			break;
		}
		memset(lin,0,sizeof(lin));
		for (int j = 0; j <= sum1; ++j)
		{
			if (sum1 == j)
			{
				isok = true;
				break;
			}
			++lin[strnum[i+j]];
			if (lin[strnum[i + j]] > num[strnum[i + j]])
			{
				break;
			}
		}
	}
	if (isok)
	{
		cout << "Yes";
	}
	else
	{
		cout << "No";
	}
	return 0;
}

L题: Foxtrot

题目链接:https://acm.uestc.edu.cn/problem/foxtrot/description

比赛时没做出来

后来看了题解有一种恍然大悟的感觉

老鼠有两种状态,要么生要么死,对应到数学里面,就是二进制

那么这个数转换成二进制后有多少位,就需要多少只老鼠

代码如下:

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
	int t, n, k;
	cin >> t;
	for (int i=0;i<t;i++)
	{
		cin >> n;
		k = 0;
		while ( pow(2,k) < n)
		{
			k++;
		}
		cout << k <<endl;
	}
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注