C Circle

原题链接

题意描述：

t组询问，每组询问一个整数n，输出n个圆（半径可以不同）可以分割的最大区域数

解题思路：

1. 题中给出0，1，2，3个圆分别可以分割的最大区域数，我们可以画图看看4个圆的情况，发现是16.
2. 通过画图我发现，分割最大区域时，区域分三块：所有圆都不包括的部分为1，所有圆共同的部分为1和每两个圆相交的部分（n-1）*n
3. 因此得到公式为2+（n-1)*n
4. n为0时没有圆内区域，因此需要特判为1
   (赛时看了数据，以为是2的ⁿ，还在那想2^1000000咋处理，数据范围那么大，我应该早点发现思路是错的，而且我也处理不了这么大的数据吖）

解题代码：

#include using namespace std; #define int long long #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); double a[1000005]; void solve() { 	int n,x; 	cin>>n; 	while(n--) 	{ 		cin>>x; 		if(x==0) 		cout<<"1"<<" "; 		else  		cout<<2+((x-1)*x)<<" "; 	} 	 	cout< 	IOS 	int t=1; 	while(t--) 	{ 		solve(); 	} 	return 0;  } 

D 开心消消乐（Right Version）

题意：

任意选择两个数字作为左右区间进行异或，找到使得序列中所有元素全部变为0的最小操作次数

解题思路：

由于相同数字异或后结果为0，所以需要操作数加一需要满足：当前数字与前一个数字不同并且不为0，遍历数组得到最小操作数

（赛时咋没发现这道题呢。。。）

解题代码：

#include using namespace std; #define int long long #define endl "\n" #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int a[1000010]; void solve() { 	int n; 	cin>>n; 	int sum=0; 	a[0]=-1; 	for(int i=1;i<=n;i++) 	{         cin>>a[i];         if(a[i]==0)             continue; 		if(a[i]!=a[i-1]) 		sum++; 	} 	cout< 	IOS 	int t=1; 	while(t--) 	{ 		solve(); 	} 	return 0;  } 

F 累加器

原题链接

题意：

给出整数T代表T次询问，接下来T行：每行两个整数x,y,求出对x进行y次累加操作，其二进制下每位发生改变的总次数

解题思路：

1. 我们可以利用前缀和的思想:
   用一个数组a来存从1累加，每次加1位数改变的情况
2. 当计算改变的情况时，我们可以使用bitset，
   每次用r存异或的结果，由于异或相同为0，不同为1，因此**r.count()**即可反映出变化的情况
3. 当x累加y时，**a[x+y]-a[x]**的结果即为所求
   （注：x,y的范围为1<=x,y<-10⁶,但题目中会用到x+y，因此数组应开2e6+10,我赛时开1e6,自己没发现问题，到最后也没改出来😭）

解题代码：

#include using namespace std; #define int long long #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #include int a[2000010]; bitset<64>p,q,r; int x,y,w=0;  void solve() { 	cin>>x>>y; 	 	cout< 	IOS 	int t=1; 	cin>>t;     p=0;     for(int i=1;i<=2000010;i++) 	{ 		q=i; 		r=p^q; 		w+=r.count(); 		a[i]=w; 		p=q; 	} 	while(t--) 	{ 		solve(); 	} 	return 0;  } 

J keillempkill学姐の卷积

原题链接

题意：

输入两个矩阵，将第一个矩阵覆盖第二个矩阵的每一个可以容纳它的部分，对应的值相乘的和为所得矩阵对应位置的值，所得矩阵大小为（m-n+1)*(m-n+1)，然后输出即可。

解题思路：

这是一道模拟题

1. 将矩阵1所有值与矩阵2对应值相乘，最后结果相加得到结果
2. 在每得到一个结果后，需要对所得矩阵与矩阵2进行位置的变换，因此需要对其横纵坐标进行判断
3. 当所得矩阵横纵坐标均满足（m-n+1）时，即可退出

解题代码：

#include using namespace std; //#define int long long #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int a[30][30],b[30][30],c[30][30]; void solve() { 	int n,m; 	cin>>n>>m; 	for(int i=1;i<=n;i++) 	{ 		for(int j=1;j<=n;j++) 		{ 			cin>>a[i][j]; 		 }  	} 	 		for(int i=1;i<=m;i++) 	{ 		for(int j=1;j<=m;j++) 		{ 			cin>>b[i][j]; 		}  	} 	 	int x=1,y=1,p=0,q=0,w,u; 	int st=(m-n+1)*(m-n+1); 	while(st--) 	{ 		for(int i=1;i<=n;i++) 		{ 			for(int j=1;j<=n;j++) 			{ 				c[x][y]+=a[i][j]*b[i+p][j+q]; 				w=i+p,u=j+q; 			}  		} 		cout< 			 			x++;y=1; 		} 		if(u==m) 		{ 			q=0; 			p++; 		} 		else 		q++;  	} 	 	return; }  int main() { 	IOS 	int t=1; 	while(t--) 	{ 		solve(); 	} 	return 0;  } 

L SSH

原题链接

题意描述：

这个题目有点长，先顺一遍题目吧：

1. 先输入m,n,q
2. 先输入m行，每行表示一个密钥对，分别为公钥，私钥
3. 接下来为n组： 每组为一台主机的ip和用户数k: 然后是k行：每行一个用户名，公钥数量和对应公钥名称
4. 最后为q行查询，每次有一个用户名，一个ip，一个私钥

我们需要查询的进行检验：

1. 看用户名是否在对应ip出现
2. 检验用户是否拥有这个私钥对应的公钥
   如果满足条件1，2输出Yes,否则输出No

解题思路：

这道题是字符串模拟

1. 用容器map1存储密钥对，键为私钥，值为公钥，因为最后检验时给出的是私钥，直接用map1便可得出其需要拥有的公钥
2. 用map2（map套用vector）存储ip下对应的用户
3. 用map3（map套用vector），存储用户拥有的公钥
4. 在最后检验时，遍历map2，看是否在该ip下存在该用户，然后用map1找到私钥对应的公钥，然后遍历map3，查看该用户是否拥有此公钥，均满足输出Yes,否则输出No

解题代码：

#include using namespace std; #define int unsigned long long #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define endl "\n" mapmp1; void solve() { 	int m,n,q,a,b,c; 	string s1,s2,s3,s4,s5; 	cin>>m>>n>>q; 	while(m--) 	{ 		cin>>s1>>s2; 		mp1[s2]=s1; 	} 	map >mp2; 	map >mp3; 	for(int i=1;i<=n;i++) 	{ 		cin>>s3>>a; 		for(int j=1;j<=a;j++) 		{ 			cin>>s4; 			mp2[s3].push_back(s4); 			cin>>b; 			for(int k=1;k<=b;k++) 			{ 				cin>>s5; 				mp3[s4].push_back(s5); 			} 		} 	 } 	 for(int i=1;i<=q;i++) 	 { 	 	int r=0; 	 	string x,y,z; 	 	cin>>x>>y>>z; 	 	 for (auto t : mp2[y]) 	 	{ 	 		if(t==x) 	 		{ 		 		r=1; 		 		break; 			 } 		 } 		 if(r==0) 		 cout<<"No"< 		 	string w=mp1[z]; 		 	int u=0; 		 	for(auto s:mp3[x]) 		 	{ 			 	if(s==w) 			 	{ 			 		u=1; 			 		break; 				 } 			 } 		 	if(u==0) 		 	cout<<"No"< 	IOS 	int t=1; 	while(t--) 	{ 		solve(); 	} 	return 0;  }