2018年哈尔滨工程大学ACM校赛
【2018-05-01更新】校赛题目已经挂到OJ：https://oj.zjw1.top/problemset.php?page=3（2019.6.4更：该网站到期未续费，现已无法访问），题目id 1219~1231
题目原文请见：ContestProblems
其中，第9题Hint部分有改动，f_max=1*100*100+0*100+0=10000；
第3题注意引号中英文，要输出的是中文引号内部的内容。
本次比赛中，我过了5道题，排名第9名
题解
顺序由易到难
1. T13
类似a+b的问题，水题
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main()
{
int t, a, b, c;
scanf("%d", &t);
while (t--)
{
scanf("%d%d%d", &a, &b, &c);
printf("%d\n", a*b+c);
}
return 0;
}
2. T3
按要求输出题目中给出的文本，注意C语言的格式控制即可。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main()
{
printf("Our lab is aimed at taking part in the competitions regarding the programming, especially on algorithm.A series of the competitions requires the participants doing well in using the programming skills, which are attractive to those internet companies.Thus getting on with the competitions means that you have advantages to compete with other candidates.So do the interviews for postgraduates.Now, be a winner\"\\\\(\%_\%)//``And good luck!By the way, our lab is located at 21B\\573.");
return 0;
}
3. T1
实际上我也不确定这道题难度排第几，我最先做出的这道题，是因为前一阵做蓝桥杯模拟题的时候刚好做过它。求n!的末尾零的个数，只需要求1~n中间有多少个5，因为5×2=0然而2的个数是足够的，所以只需要找有多少个5。注意，25是5×5，其中有2个5；125中有3个5。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main()
{
int t, n, ans;
scanf("%d", &t);
while (t--)
{
ans = 0;
scanf("%d", &n);
while (n)
{
ans += n /= 5;
}
printf("%d\n", ans);
}
return 0;
}
4. T6
大一上线性代数中矩阵的问题，注意读题，看好A的伴随矩阵是什么，题目求的是A的伴随矩阵的行列式，我因为没读好题WA了一次还是两次的。直接根据题目描述以及数学功底列出公式即可。还有，需要注意，这题会爆int，必须用long long。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
typedef long long LL;
using namespace std;
LL a[10][10], A[10][10];
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
scanf("%lld", &A[i][j]);
}
}
a[1][1] = A[2][2]*A[3][3]-A[2][3]*A[3][2];
a[1][2] = A[2][3]*A[3][1]-A[2][1]*A[3][3];
a[1][3] = A[2][1]*A[3][2]-A[2][2]*A[3][1];
a[2][1] = A[1][3]*A[3][2]-A[1][2]*A[3][3];
a[2][2] = A[1][1]*A[3][3]-A[1][3]*A[3][1];
a[2][3] = A[1][2]*A[3][1]-A[1][1]*A[3][2];
a[3][1] = A[1][2]*A[2][3]-A[1][3]*A[2][2];
a[3][2] = A[1][3]*A[2][1]-A[1][1]*A[2][3];
a[3][3] = A[2][2]*A[1][1]-A[2][1]*A[1][2];
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= i; j++)
{
swap(a[i][j], a[j][i]);
}
}
printf("%lld\n", a[1][1]*a[2][2]*a[3][3]-a[1][1]*a[2][3]*a[3][2]-a[1][2]*a[2][1]*a[3][3]+a[1][2]*a[2][3]*a[3][1]+a[1][3]*a[2][1]*a[3][2]-a[1][3]*a[2][2]*a[3][1]);
}
return 0;
}
5. T5
要求N次操作后站着的人数，打一下表就会发现，蹲着的人的位置是平方数，其余人全是站着的。1代表蹲着，0代表站着。表如下：1001000010000001000000001000…（我当时没看出是平方数，但是发现了0的个数是2,4,6,8,…递增的）
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int num[1000006] = {0};
int main()
{
int t = 1, n = 1, a, b, f = 1;
while (t < 1000003)
{
if (f) num[t] = 1, f = !f, t++;
else
{
t += n*2;
n++;
f = !f;
}
}
scanf("%d", &t);
while (t--)
{
int ans = 0;
scanf("%d%d%d", &n, &a, &b);
for (int i = a; i <= b; i++)
{
if (num[i] == 0) ans++;
}
printf("%d\n", ans);
}
return 0;
}
接下来两道题是我WA了无数次（每道题都WA了5次以上），最终也没过，然后回到实验室对着数据看，发现犯了智障错误的两道题。
6. T9
二次函数求极值，在给定[l, r]整数域区间内求f(x)=ax^2+bx+c的最大值最小值。
我刚开始用三分做，WA了两三次。然后改用取点判断大小来做，取左端点ll，右端点rr，对称轴极其两侧tt, tt+1, tt-1，然而还是WA。最后发现只是多了一行调试输出！！！！%>_<%
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
typedef long long LL;
using namespace std;
LL a, b, c, ll, rr;
LL f(LL x)
{
return a*x*x + b*x + c;
}
int main()
{
int t;
LL f_min, f_max;
scanf("%d", &t);
while (t--)
{
scanf("%lld%lld%lld%lld%lld", &a, &b, &c, &ll, &rr);
if (ll > rr) swap(ll, rr);
if (a > 0)
{
LL tt = -b / (2*a);
//cout<<tt<<endl; /// 只是因为这一行忘了删了，并且在最后比较急躁，没有发现这个问题。
f_min = min(f(ll), f(rr));
f_max = max(f(ll), f(rr));
if (tt >= ll && tt <= rr) f_min = min(f_min, f(tt));
if (tt-1 >= ll && tt-1 <= rr) f_min = min(f_min, f(tt-1));
if (tt+1 >= ll && tt+1 <= rr) f_min = min(f_min, f(tt+1));
}else if (a < 0)
{
LL tt = -b / (2*a);
f_max = max(f(ll), f(rr));
f_min = min(f(ll), f(rr));
if (tt >= ll && tt <= rr) f_max = max(f_max, f(tt));
if (tt-1 >= ll && tt-1 <= rr) f_max = max(f_max, f(tt-1));
if (tt+1 >= ll && tt+1 <= rr) f_max = max(f_max, f(tt+1));
}else { if (b > 0)
{
f_max = f(rr);
f_min = f(ll);
}
else
{
f_max = f(ll);
f_min = f(rr);
}
}
printf("%lld %lld\r\n", f_max, f_min);
}
return 0;
}
7. T2
大模拟，要删除给定C语言代码中的注释。注意每一个细节就好。
我当时是通过不断的WA来不断地思考没注意到的细节，所以也WA了好多次。
在代码标注出的那里，当时写的是if，就造成了char str[] = "abcd\\\"def"这种字符串解析中引号的提前结束。因为转义字符\\只解析了一个，而后面的\"没有解析，而是直接识别成了引号结束，导致引号判断的错位。
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
char is_q = 0, is_c = 0; // is_q表示是否在引号中间（单引号及双引号），is_c表示是否在段落注释中间（/*...*/）
string s[100001];
int main()
{
int cnt = 0;
while(getline(cin, s[cnt])) cnt++;
for (int i = 0; i < cnt; i++)
{
int len = s[i].length();
for (int j = 0; j < len; j++)
{
if (!is_q)
{
if (!is_c && s[i][j] == '"') is_q = '"';
if (!is_c && s[i][j] == '\'') is_q = '\'';
if (!is_c && s[i][j] == '/' && s[i][j+1] == '/')
{
break;
}
if (!is_c && s[i][j] == '/' && s[i][j+1] == '*')
{
is_c = 1;
putchar(' ');
}
if (s[i][j-1] == '*' && s[i][j] == '/') is_c = 0;
else if (!is_c) putchar(s[i][j]);
}else
{
while (s[i][j] == '\\') // 之前这里写的是if,就错了
{
putchar(s[i][j]);
putchar(s[i][j+1]);
j += 2;
}
if (is_q == '"' && s[i][j] == '"')
{
is_q = 0;
}
if (is_q == '\'' && s[i][j] == '\'')
{
is_q = 0;
}
putchar(s[i][j]);
}
}
if (!is_c) printf("\n");
}
return 0;
}
剩下几道题就是彻底没做出来的了，所以只有简略的题解。
T4. 麻将牌，直接没看，题太长了
T7. 数位dp
T8. bfs暴搜
T10. 矩阵快速幂
T11. dp
T12. 后缀数组处理字符串
唉，总之好气啊！！！要是T2，T9不出错，就能一等了 QAQ
还是自己太菜了啊啊啊
XDL
不菜，我才准备开始学算法……