2020-02-16 20:56 已编辑字节跳动_AI-LAB_后端研发工程师

关注

[ 2019-12-15第十八次CCF计算机软件能力认证]总结 Apare_xzc

[ 2019-12-15第十八次CCF计算机软件能力认证]总结

导言：今天第一次参加CCF考试，考完回来迫不及待地想要做一点笔记

链接：我做的CCF题目汇总Apare_xzc <–

比赛题目(凭记忆描述)

A.报数

题面：

Sample Input 1

Sample Output 1

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

Sample Output 2

大致题意：

有甲乙丙丁四个人从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

Sample Output 1

Explanation of Sample 1

如图所示，仅有（1，1）可选为回收站地址，评分为2.

Sample Input 2

2
0 0
-100000 10

Sample Output 2

Explanation of Sample 2

不存在可选地址。

Sample Input 3

Sample Output 3

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记录每种原子的个数
统计每种元素的个数，重要的有三个点：

注意每一项前面统一的系数(配平的系数)，如 32H2O
注意分子式中每种元素的系数，如H3PO4
注意括号以及括号的嵌套，如 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

Sample Output1

Sample Input 2

Sample Output2

我的思路

暴力模拟。每次只需要求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

Sample Output 1

Sample 1 解释

Sample Input 2

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