HZNU Training 1 for Zhejiang Provincial Competition 2020
先写个总结吧:
本次训练作为大一选手，能做的题为A、B、D、E。其他题目目前补题应该是意义不大的，不如把时间用在学习新内容上，至于J题的区间dp由于没有学优化比赛时放弃了，学完之后会回来补上的。下面是ABDE的题解:
A-People Counting
来源 :ZOJ - 3944
题意:给一个照片,问照片中能看到的人的个数。
分析：可以把照片补全,相应的操作就是把输入的照片补全为一张图,图应该比照片大一圈(一个人那么多),然后以当前位置当做照片的左上角进行遍历,当照片中出现符合条件的人让答案加1即可。
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 110;
char m[maxn][maxn];
int main(){
int t,h,w;
scanf("%d",&t);
while (t--){
memset(m,0,sizeof m);
int ans = 0;
scanf("%d%d",&h,&w);
for (int i = 2; i < h+2; i++){
for (int j = 2; j < w+2; j++){
cin>>m[i][j];
}
}
for (int i = 0; i < h+2; i++){
for (int j = 0; j < w+2; j++){
if (m[i][j+1] == 'O' || m[i+1][j] == '/' || m[i+1][j+1] == '|' ||
m[i+1][j+2] == '\' || m[i+2][j] == '(' || m[i+2][j+2] == ')')
ans++;
}
}
cout<<ans<<endl;
}
return 0;
}
B-Fibonacci Sequence Chicken Edition
来源：ZOJ - 3952
题意:给你一种鸡语言,让你用编程语言告诉鸡语言如何实现输入一个n求出斐波那契数列的第n项。有个栈，栈底元素下标为1，记为s[1]。从下到上下标依次增加。有7种操作:1.弹出栈顶两个元素,压入他们之和。2.弹出栈顶两个元素x,y压入x-y。3.弹出栈顶两个元素,如果他们相等压入1,否则压入0。4.输入一个数。5.弹出栈顶两个元素x,y，然后把s[y]复制给s[x]。(比赛时这个复制搞反了而wa了:()。6.弹出栈顶x,y,如果y非0直接跳到第x行语句(用于制造循环的操作)。7+.往栈中压入值为(7+)-7的元素。最后在栈顶输出f(n)的值。(程序输出格式为操作编号个c)
分析:应该算一种模拟，我们需要模拟三个过程：1.斐波那契数列的递推 2.如何判断 3.如何循环
把上面各个操作合并后输出即可。(第三幅图底层的n-1为之前的n减减之后的值 顶层的n为形式上的n 数值上等于n-1 f(n) f(n+1)中的n也为形式上的n 与底层的n-1没有关系)
#include<bits/stdc++.h>
using namespace std;
int arr[] = {4,7,8,8,7,8,12,5,2,11,8,5,9,11,5,10,9,5,1,7,8,11,5,7,3,7,3,11,6,7,9,11,5};
int main(){
for (int i = 0; i < sizeof (arr)/sizeof (int); i++){
for (int j = 0; j < arr[i]; j++){
printf("c");
}
printf("
");
}
return 0;
}
D-Almost Equal
题意:给一个数字n，问是否能用1~2n个数字组成一个环使得这个环上任意连续n个数字之和相差不超过1。如果可以找到，输出YES和圆环，如果找不到，输出NO。
分析：根据样例可以先大胆猜测n为偶数时无法组成这种环，为奇数时可以，下面是本人用图片推导的结果。
#include<cstdio>
using namespace std;
const int maxn = 1e6+5;
int ans[maxn];
int main(){
int n;
scanf("%d",&n);
if (n & 1){
puts("YES");
int flag = 1,cnt = 1,b1 = 1,b2 = n+1;
while (cnt<2*n+1)
if (flag==1||flag==0) ans[b1++]=cnt++,flag++,flag%=4;
else ans[b2++] = cnt++,flag++,flag%=4;
for (int i = 1; i <= 2*n; i++) printf("%d ",ans[i]);
}
else puts("NO");
return 0;
}
E-Citations
题意：按规定格式输出一串电报?(还是啥书刊的出版信息啥的?)反正就是字符串模拟。
分析：水题 %,就硬%。
#include<iostream>
#include<string>
#include<vector>
#include<cstring>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int t,n;
scanf("%d",&t);
while (t--){
scanf("%d",&n);
getchar();
while (n--){
string tmp[10];
string str;
for (int k = 1; k <= 10; k++){
getline(cin,str);
if (str[0] == '@' || str[0] == '}') continue;
else if (str[0] == 'a'){
for (int i = 0; i < str.length(); i++){
if (str[i] == '{'){
int pos = i;
int cnt = 0;
vector<char> s;
while (str[pos] != '}'){
if (str[pos] == '{' || str[pos] == ','){
if (str[pos] == ','){
s.push_back(',');
s.push_back(' ');
}
while (! isupper(str[pos])) pos++;
s.push_back(str[pos++]);
s.push_back(str[pos]);
s.push_back('.');
}
if (str[pos] == ' '){
s.push_back(str[pos++]);
s.push_back(str[pos]);
}
if (str[pos] == ',') s.push_back(str[pos]);
pos++;
}
for (int i = 0; i < s.size(); i++){
tmp[1] += s[i];
}
break;
}
}
}
else{
for (int i = 0; i < str.length(); i++){
if (str[i] == '{'){
int pos = i;
pos++;
vector<char> s;
while (str[pos] != '}'){
s.push_back(str[pos]);
pos++;
}
int pn;
if (str[0] == 't') pn = 2; if (str[0] == 'j') pn = 3; if (str[0] == 'y') pn = 4;
if (str[0] == 'v') pn = 5; if (str[0] == 'n') pn = 6; if (str[0] == 'p' && str[1] == 'a') pn = 7;
if (str[0] == 'p' && str[1] == 'u') pn = 0;
for (int i = 0; i < s.size(); i++){
tmp[pn] += s[i];
}
break;
}
}
}
}
cout<< tmp[1] << ". " << tmp[2] << ". " << tmp[3] << ". " <<tmp[4] << ";" << tmp[5] << "(" << tmp[6] << "):" << tmp[7] << "." <<endl;
}
}
return 0;
}