2024湖南第一师范学院程序设计新生赛 题解----YHW
A 七分之一的秘密
签到题 按照思路编程即可 需要注意的是题目中被7整除这个条件只有第一个数需要去判断 在判断数位是否包含7时不需要判断/10后的数能否被7整除
代码如下
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int q = n;
while (q)
{
if ((q % 10) == 7)
{
cout << "YES";
return 0;
}
q /= 10;
}
if (n % 7 == 0)
{
cout << "YES";
return 0;
}
cout << "NO";
return 0;
}
B 小p的文件目录
本题对于新生较难，设置在B题其实是为了让大家知道，acm不要从前往后做，要根据难度选择做题顺序，不要死磕题目。不难看出，实际上题意就是/与/之间的是目录的内容，而..出现时会删除上一级目录，/////这种连续出现的情况不需要特殊处理，我们只要在/出现就把之前出现的目录保存就好，然后处理遇到..删掉前一级目录的情况，具体看代码注释，这题用STL双端队列比较好处理，也可以试试string数组加单指针的做法。
#include <bits/stdc++.h>
using namespace std;
deque h; // 定义双端队列 可以从两端插入删除
string s, temp;
int main()
{
getline(cin, s); // 读入整行字符串
for (int i = 0; i < s.size(); i++)
{
if (s[i] >= 'a' && s[i] <= 'z')
temp += s[i]; // 用空串记录遇到的目录内容（小写字母）
if (s[i] == '/' && temp != "\0")
{ // 当遇到目录截止符号且temp内有目录内容就写入双端队列中
h.push_back(temp);
temp = ""; // 清空临时字符串
}
if (s[i] '.' && s[i + 1] '.' && !h.empty())
h.pop_back(); // 出现连续..就清除上一级目录
}
if (h.empty())
{ // 特殊情况 如果h为空要输出第一个/
cout << '/';
return 0;
}
while (!h.empty())
{ // 从前往后输出 最后一个/不用打
cout << '/';
cout << h.front();
h.pop_front();
}
return 0;
}
C 小qiの温柔
思维题，看到10的10的6次方就要想到这题不能把x当成正整数看，可以把x的每一位看做一个字符，x用字符串去读入，“把这个数看成n个正整数的和”也就是用n个正整数相加的到x，这些正整数只包含0和1，那么我们列个竖式尝试相加就能知道，最多加9次就能加完，实际上问题是找出给你的数字中哪个是最大的数，我们直接比较字符的大小就行了，字符的大小依旧符合数字的递增‘0’是32 ‘9’是41，中间依次递增
#include <bits/stdc++.h>
using namespace std;
int main()
{
string x;
char maxx = '0';
cin >> x;
for (auto m : x)
{
if (m > maxx)
maxx = m;
}
cout << maxx;
return 0;
}
D 暴力枚举
理事长还是仁慈了，本题本来考察二分查找，但是由于log2(x)在x->10e18时还是不太大，所以开long long从后往前暴力递减就能解决题目
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long m, i;
cin >> m;
for (i = m; i > 0; i--)
{
if (m == i + int(log(i) / log(2)))
break;
}
cout << i;
return 0;
}
E 小红给你签到题？
可恶的理事长，这不是真的签到题，读题发现ai-aj加了绝对值，所以i<j这个条件其实没有意义，那么题目转化为这样，给你的数列中用最大的数减去最小的数，如果大于k，那么最大价值就是最大数，但是如果最大的数减最小的数差值仍然不大于k，这个时候不要以为最大价值是最小的数，我们要采取摆烂策略，用最大的数减去第二大的数，虽然差值不可能大于k，但是可以保证这两个数里最小的也是第二大的数，所以解决这个题我们只需要数列中的三个数，最大的数，第二大的数，最小的数，问题就能解决，但是n只给到10e5，因此我直接用sort快速排序省事了。
#include <bits/stdc.h>
using namespace std;
int a[100010];
int main()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i)
{
cin >> a[i];
}
sort(a + 1, a + 1 + n);
if (a[n] - a[1] > k)
cout << a[n];
else
cout << a[n - 1];
return 0;
}
F 部落冲突
可恶的数学，首先瓦解题意，最小的凸多边形就是三角形，所以本题题意为给你n个点，让你去找出一个最小的三角形，直接三重循环暴力枚举即可，当然，这里需要已知坐标上三点求三角形面积公式，大家高考完没多久应该记得，我是赛场上现推的，花了不少时间，然后题目要最小面积的两倍，最后那个除以2就不用除了，无法组成三角形的情况要特殊处理一下，如果所有点都在一条线上就会导致-1。
#include <bits/stdc++.h>
using namespace std;
long long a[1000], b[1000], sm = 9e18;
long long csgo(int i, int j, int k)
{
long long x1 = a[i], y1 = b[i];
long long x2 = a[j], y2 = b[j];
long long x3 = a[k], y3 = b[k];
// int z,x,c;
if ((y2 - y1)(x3 - x2) == (y3 - y2)(x2 - x1))
return 0;
long long s = abs((x1 - x3) * y2 + (x2 - x1) * y3 + (x3 - x2) * y1);
return s;
}
int main()
{
long long m, i, n, sum = 0;
cin >> n;
for (int i = 1; i <= n; i)
cin >> a[i] >> b[i];
for (int i = 1; i <= n; i)
for (int j = i + 1; j <= n; j++)
for (int k = j + 1; k <= n; k++)
{
if (csgo(i, j, k) != 0)
sm = min(csgo(i, j, k), sm);
}
if (sm == 9e18)
cout << -1;
else
cout << sm;
return 0;
}
G Y染色体，分裂！
经典回文子串问题 这里给大家看几种解法
1 从中间枚举回文子串 要分奇数串和偶数串的情况
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t, maxx = 1;
string x;
cin >> x;
for (int i = 1; i < x.size() - 1; i++)
{
if (x[i - 1] == x[i + 1])
{
t = 1;
int temp = 1;
while (i - t >= 0 && i + t < x.size() && x[i + t] == x[i - t])
{
temp += 2;
t++;
}
if (temp > maxx)
maxx = temp;
}
if (x[i] == x[i + 1])
{
t = 1;
int temp = 2;
while (i - t >= 0 && i + t + 1 < x.size() && x[i + t + 1] == x[i - t])
{
temp += 2;
t++;
}
if (temp > maxx)
maxx = temp;
}
}
cout << maxx;
return 0;
}
2 动态规划
#include <bits/stdc++.h>
using namespace std;
string longestPalindrome(string s);
int main()
{
string s;
cin >> s;
cout << longestPalindrome(s).size();
return 0;
}
string longestPalindrome(string s)
{
int len = s.length();
int *dp = new int[len + 1];
for (int i = 0; i < len + 1; i++)
dp[i] = new int[len + 1];
for (int i = 0; i < len + 1; i++)
{
for (int j = 0; j < len + 1; j)
{
dp[i][j] = 0;
}
}
for (int j = 0; j < len; j)
{
dp[j][j] = 1;
dp[j + 1][j] = 1; // 这里也就是说的要手动初始话的这种情况
}
int l = 0, r = 0;
for (int i = 1; i < len; i++)
{
for (int j = 0; j + i < len; j++)
{
if (s[j] == s[i + j] && dp[j + 1][i + j - 1])
{ // 为了保证j+1 <= i+j-1, i >= 2那么将i也就是长度为1的手动初始化
l = j;
r = j + i;
dp[l][r] = 1;
}
}
}
string str = "";
for (int i = l; i <= r; i++)
str += s[i];
return str;
delete dp;
}
最暴力的是 On三次方的解法 枚举两个端点 求中间的字符串是不是回文串 这里就不展示代码了
H Hard Math
签到题 数列求和 我比较懒 写了个前缀和的方法 大家参考即可
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, t, q[100005] = {}, w[100005] = {};
for (int i = 1; i <= 100000; i++)
{
q[i] = i;
w[i] = q[i] + w[i - 1];
}
cin >> t;
while (t--)
{
int l, r;
cin >> l >> r;
cout << w[r] - w[l - 1] << '\n';
}
return 0;
}
I 强迫症犯了，烦！
思维题，删除ai，再将ai+aj放入数列，如何让ai+aj一定不一样呢，在每个数都大于0的情况下很好解决，直接令aj是数列中最大的数，再加一个ai一定不会和其他的数相同，所以题目转变为求相同数的个数，每次将两个相同数变为一个需要1次操作，所以我们求出sum个第一个数，用n-sum就能得到重复数的个数，这里使用了STLmap，如果这个数没有出现过，在map里的值就为0，出现了一次之后我们就标1，这样就可以得到sum。
#include <bits/stdc.h>
using namespace std;
map<int, int> a;
int main()
{
long long m, i, n, sum = 0;
cin >> n;
for (int i = 1; i <= n; i)
{
cin >> m;
if (a[m] == 0)
sum++;
a[m] = 1;
}
cout << n - sum;
return 0;
}
J 你会博弈论吗？
思维题 根据题意明显暗示 我们用字符串来储存这1000个数字 由题意可知，数字从左到右可组成十进制数，因此问题可简化为一个数字字符串从0开始递增，每次在字符串中搜索有没有这个数字字符串，第一个没有的就是题意中最小的十进制非负整数。
#include <bits/stdc.h>
using namespace std;
int main()
{
long long m, i, n, sum = 0;
char c[1005], x;
string s = "";
cin >> n;
for (int i = 1; i <= n; i)
{
cin >> x;
if (x != ' ')
s += x;
}
i = 0;
while (1)
{
if (s.find(to_string(i)) == -1)
{
cout << i;
return 0;
}
i++;
}
}
K XCPCの崛起
钝感力，去生成这个所需的序列，要确定一个不确定的m和一个不确定的序列，这压根没法实现，所以时间复杂度O（1）的通解肯定存在，诶？，这个m为什么要>=2呢，这说明无论k是个什么，m必定能等于2，那m带进去试一下，哦豁，a0的a1次方加上a1的a0次方，两个加起来等于n，n-1和1秒了，试着提交一发，过辣！！！！。
#include <bits/stdc++.h>
using namespace std;
int main()
{
unsigned long long n, k;
cin >> n >> k;
cout << 2 << '\n';
cout << n - 1 << ' ' << '1';
return 0;
}
京公网安备 11010502036488号