【博客】2019-12-15第十八次CCF xzc ABCE
[ 2019-12-15第十八次CCF计算机软件能力认证]总结
导言：今天第一次参加CCF考试，考完回来迫不及待地想要做一点笔记
链接：我做的CCF题目汇总Apare_xzc <--
比赛题目(凭记忆描述)
A.报数
题面：
Sample Input 1
20
Sample Output 1
2 1 1 0
Explanation of Sample 1
报数过程为：
甲：1，乙：2，丙：3，丁：4
甲：5，乙：6，丙：跳过，丁：8
甲：9，乙：10，丙：11，丁：12
甲：13，乙：跳过，丙：15，丁：16
甲：跳过，乙：18，：19，丁：20
甲：跳过，乙：22，丙：23，丁：24
在丁报出24后，四个人总计报出了20个数，游戏结束。
Sample Input 2
66
Sample Output 2
7 5 11 5
大致题意：
有甲乙丙丁四个人从1开始循环报数报数。甲1，乙2，丙3，丁4，甲5，乙6，丙7(跳过)，丁8，甲9 ……若某个人的数是7的倍数或者某一位含有数字7，那么这个人跳过(不报出声音)。给定以个n(n<=1000),表示报出了n个数，问甲，乙，丙，丁四人各自跳过了多少次？
思路：
直接模拟即可
我的代码
//Apare_xzc 2019.12.15 A题
#include <bits/stdc++.h>
using namespace std;
#define LL long long
int a[10];
bool jump(int x) //判断是否是7的倍数或者含有7
{
if(x%7==0) return true;
while(x>0)
{
if(x%10==7) return true;
x/=10;
}
return false;
}
int main()
{
int n;cin>>n;
int k = 1; //k代表当前报数人的编号，甲、乙、丙、丁依次为1,2,3,4
int tot = 0;
for(int i=1;tot<n;++i) //tot==n时结束
{
if(jump(i)) a[k]++; //跳过的话就给当前的人技术
else tot++;
if(++k==5) k = 1; //循环报数
}
for(int i=1;i<=4;++i) //输出结果
cout<<a[i]<<endl;
return 0;
} B.回收站选址</font### 题面
)
Sample Input 1
7 1 2 2 1 0 0 1 1 1 0 2 0 0 1
Sample Output 1
0 0 1 0 0
Explanation of Sample 1
如图所示，仅有（1，1）可选为回收站地址，评分为2.
Sample Input 2
2 0 0 -100000 10
Sample Output 2
0 0 0 0 0
Explanation of Sample 2
不存在可选地址。
Sample Input 3
11 9 10 10 10 11 10 12 10 13 10 11 9 11 8 12 9 10 9 10 11 12 11
Sample Output 3
0 2 1 0 0
Explanation of Sample 3
1分选址：（10，10）和（12，10）；
2分选址：（11，9）
数据范围
测试点1和2，保证对于任意的i皆满足0<=xi, yi<=2；
测试点3、4和5，保证对于任意的i皆满足0<=xi, yi<= 500；
测试点6、7和8，保证对于任意的i皆满足0<=xi, yi<= 10^9；
测试点9和10，保证对于任意的i皆满足|xi|, |yi|<=10^9，即坐标可以是负数。
所有的测试点保证1<=n<=10^3。
大致题意：
根据航拍信息，得到了n个比较理想的位置可能可以建立垃圾站。每个位置坐标为xi,yi( xi , yi 均为整数)。某个位置要建垃圾站，要满足它的上( x-1 , y )、下（x+1 , y）、左（ x , y-1）、右（x,y+1）都比较理想。现在给可以建垃圾站的地方打分。可建垃圾站的地方，左上(x-1,y-1)，左下（x+1,y-1），右上(x-1,y+1)，右下（x+1,y+1）4个位置理想位置的个数等于这个位置的评分。 输出5行，分别输出评分为0,1,2,3,4的位置的个数
思路：
小模拟？按照题意模拟一遍即可，定义一个结构体类型或者直接用pairl<int,int>来记录位置，判断每个位置上下左右是否理想，满足的话再计分即可。可以用map来保存所有理想的位置坐标
我的代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
struct Node{ //记录位置信息
int x,y; //x为横坐标，y为纵坐标
Node(int _x=0,int _y=0):x(_x),y(_y){} //构造函数
bool operator < (const Node& rhs)const{
return x==rhs.x?y<rhs.y:x<rhs.x; //重载小于号(要用map)
}
};
map<Node,int> mp; //记录地图
int cnt[10]; //cnt[i]表示得分为i的地址的个数
int dx[] = { 1, 1,-1,-1}; //偏移量
int dy[] = { 1,-1, 1,-1};
void solve(Node node) //判断某个点是否可以建垃圾场
{
int x = node.x, y = node.y; //上下左右都理想才可
if(!mp[Node(x,y+1)]||!mp[Node(x,y-1)]||!mp[Node(x+1,y)]||!mp[Node(x-1,y)])
return;
int mark = 0; //分数
for(int i=0;i<4;++i)
{
int xx = x+dx[i],yy=y+dy[i];
if(mp[Node(xx,yy)]) mark++;
}
cnt[mark]++; //计数
return;
}
int main()
{
vector<Node> v;
int n,x,y;
cin>>n;
for(int i=0;i<n;++i)
{
scanf("%d%d",&x,&y);
v.push_back(Node(x,y));
mp[v[i]] = 1; //标记该点在是理想点
}
for(int i=0;i<n;++i)
{
solve(v[i]);
}
for(int i=0;i<=4;++i) //输入答案
cout<<cnt[i]<<endl;
return 0;
} C. 化学方程式
题面：
)
数据范围
1<=n<=100
输入的化学方程式都是符合题目中给出的定义的，且长度不超过1000
系数不会有前导零，也不会有为零的系数化学方程式的任何一边，其中任何一种元素的原子总个数都不超过10^9
题意：
输入T，之后T个无空格的字符串，如果已经配平，输出“Y”，否则输出“N”,一共输出T行
化学方程式就是我们高中学的方程式，它有一个规范的词法定义，大致如下(凭借记忆+我的理解)：
方程:: 表达式=表达式
表达式:: 式子|表达式+式子
式子:: 分子式|系数+分子式
分子式:: 块|块+分子式
块::(块)|块+数字|(块)+数字
数字::1|2|3|4|5|6|7|8|9|数字+（0|1|2...|9）
块::化学元素|(化学元素)
化学元素::大写字母|大写字母+小写字母
一定不规范，大致意思理解就行了
如果分子式前面没系数，默认系数为1，如H2, 16H2
分子式中有括号，而且括号可以嵌套，如Na(Au(CN)2)
化学元素只有2种形式，一种是单个大写字母，如H, O, S, C, N ……另一种是1个大写字母+1个小写字母，如 Cl, Ag, Au, Cu, Ba, Fe, Al ……
方程中没有空格
Sample Input
（单击右上角可复制到剪切板）
11 H2+O2=H2O 2H2+O2=2H2O H2+Cl2=2NaCl H2+Cl2=2HCl CH4+2O2=CO2+2H2O CaCl2+2AgNO3=Ca(NO3)2+2AgCl 3Ba(OH)2+2H3PO4=6H2O+Ba3(PO4)2 3Ba(OH)2+2H3PO4=Ba3(PO4)2+6H2O 4Zn+10HNO3=4Zn(NO3)2+NH4NO3+3H2O 4Au+8NaCN+2H2O+O2=4Na(Au(CN)2)+4NaOH Cu+As=CS+Au
Sample Output
N Y N Y Y Y Y Y Y Y N
我的思路：
检查配平，思路很清晰，就是看方程两边每种元素的原子个数是否相等
我们首先找到等号的位置，把方程分割为左右两端
然后我们找到每个加号的位置，就可以用‘+’ 分割出若干的项(系数+分子式or分子式)
然后我们处理每一个项，统计项里面==每种元素(原子)的个数==(最重要的地方)
我们可以用map记录每种原子的个数
统计每种元素的个数，重要的有三个点：
- 注意每一项前面统一的系数(配平的系数)，如 ==32==H2O
- 注意分子式中每种元素的系数，如H==3==PO==4==
- 注意括号以及括号的嵌套，如 ==Na(Au(CN)2)==，这个可以用栈来解决
如何用栈来解决呢？ 这个我觉得类似中缀表达式转后缀表达式，和括号有关，我们如果遇到左括号'==(=='，直接入栈，如果遇到原子式，讲原子式和其个数一起入栈，如果遇到右括号'==)==', 讲栈中所有原子式pop出来到临时栈里面(为了保证顺序不乱)，直到遇见第一个左括号'('，然后把pop出来的原子式的个数乘以右括号后面的系数，再push回去
我的代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
char str[10000];
int posEqual,lenStr;
vector<int> vLeftAdd; //the pos of '+'
vector<int> vRightAdd;
map<string,int> mp; //element:=cnt 统计每个原子的个数
map<string,int>::iterator it;
struct Node{
string exp; //原子式(化学元素)
int countt; //原子的个数
Node(){}
Node(string s,int c){
exp = s; countt = c;
}
};
void calOne(string s,int flag); //用来统计一项的原子个数
//flag==1 Left; flag==-1 Right;
bool judge();
int main()
{
// freopen("in.txt","r",stdin);
int T;cin>>T;
while(T--)
{
scanf("%s",str); //缓冲区存放方程式
vLeftAdd.clear();
vRightAdd.clear();
mp.clear(); //初始化
vLeftAdd.push_back(-1);
lenStr = strlen(str); //方程式的长度
bool onLeft = true;
for(int i=0;i<lenStr;++i) //统计等号的位置，以及等号左右'+'的位置
{
if(str[i]=='=') posEqual = i,onLeft=false;
else if(str[i]=='+')
{
if(onLeft) vLeftAdd.push_back(i);
//等号左边'+'的下标存在vleftAdd中
else vRightAdd.push_back(i);
//等号右边'+'的下标存在vRightAdd中
}
}
if(judge()) //已经配平
{
printf("Y\n");
}
else
{
printf("N\n");
}
}
return 0;
}
void calOne(string s,int flag) //flag==1 Left; flag==-1 Right;
{
int i = 0;
int Num = 0;
int len = s.length();
if(!isdigit(s[0]))
{
Num = 1;
}
else
{
for(i=0;isdigit(s[i]);++i)
{
Num = Num*10+s[i]-'0';
}
}
//i is the first pos of the substance;
stack<Node> St; //stack to take element
for(int j=i;j<len;++j)
{
char now = s[j];
if(now=='(')
{
St.push(Node(string("("),1));
continue;
}
else if(now==')')
{
int totProduct = 0;
if(j==len-1||!isdigit(s[j+1]))
{
totProduct = 1;
}
else
{
int k;
for(k=j+1;isdigit(s[k]);++k)
{
totProduct = totProduct*10+s[k]-'0';
}
j = k-1;
}
stack<Node> tmpv;
while(!St.empty())
{
Node tpS = St.top();
St.pop();
if(tpS.exp==string("("))
{
break;
}
else
{
tmpv.push(Node(tpS.exp,tpS.countt*totProduct));
}
}
while(!tmpv.empty())
{
St.push(tmpv.top());
tmpv.pop();
}
continue;
}
else if(isupper(now))
{
string ttmmpp = string("");
if(j==len-1||!islower(s[j+1])) //only one letter
{
ttmmpp += now;
int cntWord = 0;
if(j==len-1||!isdigit(s[j+1]))
{
cntWord = 1;
}
else
{
int jj;
for(jj=j+1;isdigit(s[jj]);++jj)
{
cntWord = cntWord*10+s[jj]-'0';
}
j = jj-1;
}
St.push(Node(ttmmpp,cntWord));
continue;
}
else if(j<len&&islower(s[j+1])) //word has two letter: upper+lower
{
string tmptmp = "";
tmptmp+=now;
tmptmp+=s[j+1];
j++;
int cntWord = 0;
if(j==len-1||!isdigit(s[j+1]))
{
cntWord = 1;
}
else
{
int jj;
for(jj=j+1;isdigit(s[jj]);++jj)
{
cntWord = cntWord*10+s[jj]-'0';
}
j = jj-1;
}
St.push(Node(tmptmp,cntWord));
continue;
}
}
}
Node nodd;
while(!St.empty())
{
nodd = St.top();
St.pop();
int updateN = Num*nodd.countt*flag;
mp[nodd.exp] += updateN;
}
}
bool judge()
{
int szL = vLeftAdd.size();
vector<int> pHead;
for(int i=0;i<szL;++i)
{
str[vLeftAdd[i]] = '\0';
pHead.push_back(vLeftAdd[i]+1);
}
str[posEqual] = '\0';
for(int i=0;i<(int)pHead.size();++i)
{
string tmp = str+pHead[i];
calOne(tmp,1);
}
pHead.clear();
int szR = vRightAdd.size();
pHead.push_back(posEqual+1);
for(int i=0;i<szR;++i)
{
str[vRightAdd[i]] = '\0';
pHead.push_back(vRightAdd[i]+1);
}
for(int i=0;i<(int)pHead.size();++i)
{
string tmp = str+pHead[i];
calOne(tmp,-1);
}
for(it=mp.begin();it!=mp.end();++it)
{
if(it->second) return false;
}
return true;
}
D题没看，E题按题意写了暴力，不知道能骗多少分^_^
E.魔数
大致题意：
我们先定义6个常数：
U0 = 314882150829468584
U1 = 427197303358170108
U2 = 1022292690726729920
U3 = 1698479428772363217
U4 = 2006101093849356424
Md = 2009731336725594113再定义一个函数:
f(x) = (x%mod)%2019现在给定一个数列a，长度为n，其中a[i] = i
然后给出m个操作，每个操作输入一个Li,Ri(1<=Li<=Ri<=n)
令sum = f(a[Li])+f(a[Li+1])+f(a[Li+2]+...+f(a[Ri-1])+f(a[Ri]))
要求输出sum
然后令p = sum%5
然后进行一个操作：将a[Li],a[Li+1],a[Li+2]...a[Ri-1],a[Ri]都乘以Up数据范围：(n<=100,000, m<=1000,000)*
样例
(输入是考试的时候往文件里存了拷回来的，输出是根据输入用Python暴力计算的，应该没问题)
Sample Input 1
4 4 1 3 3 4 3 3 1 3
Sample Output1
6 1105 1735 4744
Sample Input 2
100 100 45 74 38 50 7 45 42 62 83 100 50 51 8 11 93 98 64 70 15 87 30 87 13 79 14 81 18 79 70 88 25 39 13 57 55 85 80 92 83 90 54 75 1 61 17 42 25 49 39 77 32 45 83 87 30 47 59 84 25 50 1 82 21 45 72 96 3 85 16 64 52 92 28 29 84 88 26 93 10 67 27 76 57 62 43 69 63 66 5 59 9 46 49 53 35 50 3 19 23 62 38 73 17 68 34 83 42 91 13 92 19 62 17 70 18 75 95 99 35 90 81 91 59 63 5 90 22 87 51 88 25 61 56 91 50 78 11 60 11 18 27 45 57 82 16 54 3 94 33 56 9 71 68 88 24 36 7 64 48 85 58 76 20 43 9 90 24 27 71 97 25 95 73 97 55 83 22 43 53 55 68 88 12 44 25 87 14 46 34 56 15 35 7 80 46 87 23 71 8 93
Sample Output2
1785 5741 10423 24915 1647 2154 1872 8559 12936 60048 52916 79974 61897 50541 16819 15646 48044 30156 14581 6906 17346 45805 25217 29837 44539 12602 5964 16894 23972 30665 64047 28029 26086 89745 49102 40236 2297 6040 64456 57625 48151 8311 27574 4166 52887 37703 4922 17603 17729 35771 35915 52458 54055 44140 70298 39690 49407 48808 4775 55131 9378 2839 75644 58663 40660 29344 38759 31862 51760 7924 22539 22003 31095 86980 25718 61094 18995 13703 56434 35626 18678 22776 82576 3233 24072 76470 23887 28161 26150 2017 19769 31420 63547 31533 24513 20199 62729 39286 43276 80411
我的思路
暴力模拟。每次只需要求f(ai)，不关心ai的大小。f(x) = x%mod%2019, 所以我们只需要维护ai%mod即可；每次暴力更新:
a[i] = a[i] * u[sum%5] % mod 但是2个1E18的数会乘爆，我们要用==快速乘==(俄罗斯农民乘法)
这样的话应该小数据都能过了
我的代码
（输出正确是没问题的，就是m,n大了肯定会TLE，估计AC的话要用线段树之类的维护吧）
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <string> #include <vector> #include <map> #include <set> #include <vector> #include <stack> #include <queue> using namespace std; #define LL unsigned long long const LL U0 = 314882150829468584ll; const LL U1 = 427197303358170108ll; const LL U2 = 1022292690726729920ll; const LL U3 = 1698479428772363217ll; const LL U4 = 2006101093849356424ll; const LL mod= 2009731336725594113ll; LL ArrU[10] = {U0,U1,U2,U3,U4}; LL u[10]; LL f(LL x) { return (x%mod)%2019; } LL a[1000000+100]; LL fast_mul(LL a,LL b) //俄罗斯农名乘法 { if(a<b) swap(a,b); LL ans = 0; while(b) { if(b&1) ans = (ans+a)%mod; a = (a<<1)%mod; b/=2; } return ans; } int main() { // freopen("in2.txt","r",stdin); for(int i=0;i<5;++i) u[i] = ArrU[i]%mod; int n,q; scanf("%d%d",&n,&q); for(int i=1;i<=n;++i) a[i] = i; int L,R; while(q--) { scanf("%d%d",&L,&R); LL sum = 0; for(int i=L;i<=R;++i) sum += a[i]%2019; printf("%lld\n",sum); int j = sum%5; for(int i=L;i<=R;++i) a[i] = fast_mul(a[i],u[j]); } return 0; }附：我写的python暴力用于对拍
# E.py # Author:Apare_xzc # 2019.12.16 11:03 U0 = 314882150829468584 U1 = 427197303358170108 U2 = 1022292690726729920 U3 = 1698479428772363217 U4 = 2006101093849356424 mod = 2009731336725594113 u = [U0,U1,U2,U3,U4] def f(x): return (x%mod)%2019 def main(): fileName = input('请输入文件名:') # 带拓展名 with open(fileName,'r') as IN: line = IN.readline() # 读入n,m n,m = map(int,line.split()) a = [x for x in range(0,n+1)] # lambda表达式生成列表 while m>0: m -= 1 L,R = map(int,IN.readline().split()) sum = 0 for i in range(L,R+1): # 求和 sum += f(a[i]) print(sum) j = sum % 5 for i in range(L,R+1): #更新 a[i] *= u[j] if __name__ == '__main__': main() #我真是个天才
写完啦~
xzc 2019.12.15 21:36
PS: 欢迎朋友们来加我QQ： 1363581749 快乐的xzc
D. 区块链
(题面是从博主[wingrez]的博客抄来的，感谢~)
题面：
输入：
输出
Sample Input 1
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5 1 27 1 1 1 2 1 2 3 1 3 4 1 4 5 1 5 1 1 2 1 3 1 4 1 5 1 1 2 2 2 3 2 4 2 5 2 1 10 10 2 11 9 1 11 2 11 3 11 4 11 5 11 1 12 2 12 3 12 4 12 5 12
Sample Output 1
2 0 1 2 0 2 2 0 3 2 0 4 2 0 5 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 3 0 1 10 4 0 1 10 9 3 0 1 10 3 0 1 10 3 0 1 10 4 0 1 10 9 4 0 1 10 9 4 0 1 10 9 4 0 1 10 9 4 0 1 10 9
Sample 1 解释
Sample Input 2
15 13 1 2 2 3 3 4 4 5 1 6 6 7 7 8 8 9 1 10 10 11 11 12 12 13 14 15 6 28 1 1 1 1 2 2 1 6 2 7 13 7 9 7 5 7 3 14 8 14 5 14 11 14 9 25 5 25 13 25 9 29 3 5 29 4 13 29 5 1 53 2 59 6 2 59 1 1000 3 1000 8 1000 9 1000 10 1000 13 1000 14 1000 15 1000
Sample Output 2
3 0 1 2 2 0 1 1 0 1 0 1 0 3 0 1 2 1 0 1 0 3 0 1 2 2 0 1 2 0 1 2 0 1 4 0 1 2 3 5 0 1 2 3 6 5 0 1 2 3 6 5 0 1 2 3 6 5 0 1 2 3 6 5 0 1 2 3 6 5 0 1 2 3 6 5 0 1 2 3 6 1 0 1 0
数据范围
