阅读量:0
这里写目录标题
A 圆周率日挑战
题意描述：
给出圆周率前100位，有n组数据：每组有两个整数a，b分别表示该图案的周长的平方和面积的4倍。一个图形越接近圆，它的a/b的值就越接近 圆周率。找出最接近圆的一组，如果接近程度相同，则选择其中周长最小的那一个“圆”所对应的一组，输出该组的a，b
解题思路：
- 设变量p记录a/b与圆周率的差值的绝对值
- 选择差值最小的一组
- 如果差值相同，则选择a较小的一组
- 这道题难处理的是数据，用python会更好处理
（该题数据范围需要用高精，如果用C++/C语言会很麻烦，Python中可以引用decimal库，这样可以简化运算。我不会python，也是写这道题才接触，注释可能写的有点问题，代码是能过的，代码记得选python3）
解题代码：
import decimal from decimal import *//导入Python中decimal模板 getcontext().prec=40//.prec用来设置精度，这里设置为40位 pi=decimal.Decimal("3.1415926535897932384626433832795028841971")//pi为Decimal类型，给pi赋值， ans,d=(0,0),pi//将(0,0)赋值给ans,pi赋值给d for i in range(int(input()))://循环，从0，循环到输入数字-1 p, a = list(map(int, input().split()))//将输入的数分别赋给p,a代表分子和分母 dis=abs(decimal.Decimal(decimal.Decimal(p)/decimal.Decimal(a))-pi)//求思路中所说与圆周率的接近程度 if dis==d://比较接近程度 if p<ans[0]://比较周长，ans中ans[0]存储的为周长平方，ans[1]存储的为面积的四倍 ans=(p,a)////如果接近程度相同，选择周长最小的 elif dis<d: d=dis ans=(p,a)//如果接近程度不同，选择最为接近的 print(ans[0],ans[1]) C Circle
题意描述：
t组询问，每组询问一个整数n，输出n个圆（半径可以不同）可以分割的最大区域数
解题思路：
- 题中给出0，1，2，3个圆分别可以分割的最大区域数，我们可以画图看看4个圆的情况，发现是16.
- 通过画图我发现，分割最大区域时，区域分三块：所有圆都不包括的部分为1，所有圆共同的部分为1和每两个圆相交的部分（n-1）*n
- 因此得到公式为2+（n-1)*n
- n为0时没有圆内区域，因此需要特判为1
(赛时看了数据，以为是2的n，还在那想21000000咋处理，数据范围那么大，我应该早点发现思路是错的，而且我也处理不了这么大的数据吖）
解题代码：
#include<bits/stdc++.h> 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<<endl; return; } signed main() { IOS int t=1; while(t--) { solve(); } return 0; } D 开心消消乐（Right Version）
题意：
任意选择两个数字作为左右区间进行异或，找到使得序列中所有元素全部变为0的最小操作次数
解题思路：
由于相同数字异或后结果为0，所以需要操作数加一需要满足：当前数字与前一个数字不同并且不为0，遍历数组得到最小操作数
（赛时咋没发现这道题呢。。。）
解题代码：
#include<bits/stdc++.h> 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<<sum<<endl; } signed main() { IOS int t=1; while(t--) { solve(); } return 0; } F 累加器
题意：
给出整数T代表T次询问，接下来T行：每行两个整数x,y,求出对x进行y次累加操作，其二进制下每位发生改变的总次数
解题思路：
- 我们可以利用前缀和的思想:
用一个数组a来存从1累加，每次加1位数改变的情况 - 当计算改变的情况时，我们可以使用bitset，
每次用r存异或的结果，由于异或相同为0，不同为1，因此**r.count()**即可反映出变化的情况 - 当x累加y时，**a[x+y]-a[x]**的结果即为所求
（注：x,y的范围为1<=x,y<-106,但题目中会用到x+y，因此数组应开2e6+10,我赛时开1e6,自己没发现问题，到最后也没改出来😭）
解题代码：
#include<bits/stdc++.h> using namespace std; #define int long long #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #include<bitset> int a[2000010]; bitset<64>p,q,r; int x,y,w=0; void solve() { cin>>x>>y; cout<<a[y+x-1]-a[x-1]<<endl; } signed main() { 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所有值与矩阵2对应值相乘，最后结果相加得到结果
- 在每得到一个结果后，需要对所得矩阵与矩阵2进行位置的变换，因此需要对其横纵坐标进行判断
- 当所得矩阵横纵坐标均满足（m-n+1）时，即可退出
解题代码：
#include<bits/stdc++.h> 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<<c[x][y]<<" "; if(y==m-n+1) cout<<endl; if(x==m-n+1&&y==m-n+1) break; if(y!=m-n+1) y++; else { 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
题意描述：
这个题目有点长，先顺一遍题目吧：
- 先输入m,n,q
- 先输入m行，每行表示一个密钥对，分别为公钥，私钥
- 接下来为n组： 每组为一台主机的ip和用户数k: 然后是k行：每行一个用户名，公钥数量和对应公钥名称
- 最后为q行查询，每次有一个用户名，一个ip，一个私钥
我们需要查询的进行检验：
- 看用户名是否在对应ip出现
- 检验用户是否拥有这个私钥对应的公钥
如果满足条件1，2输出Yes,否则输出No
解题思路：
这道题是字符串模拟
- 用容器map1存储密钥对，键为私钥，值为公钥，因为最后检验时给出的是私钥，直接用map1便可得出其需要拥有的公钥
- 用map2（map套用vector）存储ip下对应的用户
- 用map3（map套用vector），存储用户拥有的公钥
- 在最后检验时，遍历map2，看是否在该ip下存在该用户，然后用map1找到私钥对应的公钥，然后遍历map3，查看该用户是否拥有此公钥，均满足输出Yes,否则输出No
解题代码：
#include<bits/stdc++.h> using namespace std; #define int unsigned long long #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define endl "\n" map<string,string>mp1; 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<string,vector<string> >mp2; map<string,vector<string> >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"<<endl; else { string w=mp1[z]; int u=0; for(auto s:mp3[x]) { if(s==w) { u=1; break; } } if(u==0) cout<<"No"<<endl; else cout<<"Yes"<<endl; } } } signed main() { IOS int t=1; while(t--) { solve(); } return 0; } 