A-宙天
考虑到 x 非常小，暴力枚举前10个 k 即可。
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,mod=998244353;
int x;
signed main()
{
cin>>x;
bool f=0;
for(int i=0;i<=10;i++)
if(i*(i+1)==x){
cout<<"YES";
return 0;
}
cout<<"NO";
}B-Random
题目中有一句，保证数组元素在 [1,10^9] 范围内独立均匀随机生成。
我们可以发现，如果存在两个数都是偶数，那么就满足题意。而生成一个数为偶数的概率为\frac{1}{2}，如果我们检查前100个数，那么都是奇数的概率就为(\frac{1}{2})^{100}，这是一个非常非常小的概率。因此我们可以暴力检查前100个数，如果不存在两个数的最大公因数大于1，就可以认为数组不满足条件了。
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,mod=998244353;
int t,n,a[N];
signed main()
{
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
bool f=0;
for(int i=1;i<=min(100ll,n)&&!f;i++)
for(int j=1;j<=min(100ll,n);j++)
if(i!=j){
if(__gcd(a[i],a[j])>1) {
f=1;
cout<<a[i]<<" "<<a[j]<<"\n";
break;
}
}
if(!f) cout<<"-1\n";
}
}G-スピカの天秤
我们检查初始的天平状况。如果初始就两侧相等，则从任意一边拿走一个即可，输出1；假设左边重量小于右边，我们就讲右边的砝码按重量排序，贪心地取走大的砝码，这样就能保证取走的砝码数量最少。另一种情况同理。
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,mod=998244353;
int t,n,m,a[N],b[N];
signed main()
{
cin>>t;
while(t--){
cin>>n>>m;
int resl=0,resr=0;
for(int i=1;i<=n;i++) cin>>a[i],resl+=a[i];
for(int i=1;i<=m;i++) cin>>b[i],resr+=b[i];
if(resl==resr) cout<<"1\n";
else if(resl<resr){
sort(b+1,b+m+1);
int ans=0;
for(int i=m;i>=1;i--){
resr-=b[i];
ans++;
if(resr<=resl) break;
}
cout<<ans<<"\n";
}else{
sort(a+1,a+n+1);
int ans=0;
for(int i=n;i>=1;i--){
resl-=a[i];
ans++;
if(resl<=resr) break;
}
cout<<ans<<"\n";
}
}
}J-Branch of Faith
一颗完全二叉树除了最深一层其他层全都是满的，而我们发现第i层有2^{i-1}个结点,前i层一共有2^i-1个结点，于是我们就能够找到目标结点位于第几层，从而得知该层有几个点。
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,mod=998244353;
int t,n,q,f[70];//f[i]:2^i
signed main()
{
cin>>t;f[0]=1;
for(int i=1;i<=63;i++)
f[i]=f[i-1]*2;
while(t--){
cin>>n>>q;
int res=0;
for(int i=0;i<=62;i++)
if(f[i+1]-1>=n) {res=i-1;break;}
//res表示原二叉树直到第res层都是满的
while(q--){
int x;cin>>x;
int k=__lg(x);//k是log2(x)，表示x在第几层
//用log2(x)会有精度问题
if(k<=res) cout<<f[k]<<"\n";//如果不在叶子层，则答案是2^k
else cout<<n-f[k]+1<<"\n";//否则答案就是总节点数减去除了叶子层的满树
}
}
}H- Tic Tac DREAMIN'
有两种情况：
如果 ya=yb ，此时两点所在直线与x轴平行，需要特判
否则，两点所连接直线一定与x轴有交点，设为(x_0,0)。我们已知线段长度，就能够知道所需要的高为多少。作出目标长度的高，与直线、x轴会形成一个直角三角形，而我们要求的点(x,0)与(x_0,0)形成了三角形的斜边。我们只需要求出高对应角的正弦值，就能算出斜边了。公式自推。
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,mod=998244353;
int xa,ya,xb,yb;
signed main()
{
cin>>xa>>ya>>xb>>yb;
if(ya==yb){
if(abs(xa-xb)*abs(ya)==4) cout<<0;//面积要为2才满足
else cout<<"no answer";
return 0;
}
double l=sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));//线段长度
double h=4.0/l;//所需高的长度
double A=yb-ya;
double B=xa-xb;
double C=-xa*A-ya*B;
//设直线方程为Ax+By+C=0
double pos=-C/A;//直线与x轴交点横坐标
double s=fabs(A)/sqrt(A*A+B*B);//对应角的正弦值
printf("%.10lf",pos+h/s);//pos-h/s也可，两种答案任选
}F-Energy Synergy Matrix
如果没有阻碍，小小红到达第n列需要走n-1步。
小小红增加步数的方法只有向下走或者向上走(拐弯)，所以小紫要尽可能让小小红拐弯，而小红要尽可能阻止小紫。
结论：想让小小红换行，最少需要5列。换行一次步数会加一。因此答案为n-1+\lfloor \frac{n}{5} \rfloor。
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,mod=998244353;
int t,n;
signed main()
{
cin>>t;
while(t--){
cin>>n;
cout<<n-1+n/5<<"\n";
}
}C- Inverted World
要让最后的字符串相邻不相同，那么就只有两个种情况：01010...或者10101...。两种情况分别计算取最小即可。
对于特定的情况，我们把原串于目标串相同位置不相同的字符提取出来，组成一个新的字符串。我们的目标就是要从这个字符串里选出若干个01相间的子序列（一个序列代表一个修改操作）。
设cnt[0]为以0结尾的01串数量，cnt[1]为以1结尾的01串数量。我们依次扫描字符串。如果当前是1，我们先看是否有以0结尾的字符串(cnt[0]>=1?)。如果有，我们可以把它加入到以0结尾的字符串，这样0结尾的字符串数量会减少1，否则这个1当作一个新的字符串。0结尾的字符串数量会增加0。另一种情况同理。最后答案是cnt[0]+cnt[1]。
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,mod=998244353;
int t,n;
string s;
inline int get(string res){
string now="";
for(int i=0;i<n;i++)
if(s[i]!=res[i]) now+=s[i];
int r=0,m=now.size(),c0=0,c1=0;
for(int i=0;i<m;i++)
if(now[i]=='0'){
if(c1>0) c1--;
c0++;
}else{
if(c0>0) c0--;
c1++;
}
return c1+c0;
}
signed main()
{
cin>>t;
while(t--){
cin>>n>>s;
string res1="",res2="";
int now=0;
for(int i=0;i<n;i++){
res1+=('0'+now);
res2+=('0'+(now^1));
now^=1;
}
cout<<min(get(res1),get(res2))<<'\n';
}
}
I-BenzenE
转换思路：我们不妨先全部选a数组，得出一个异或值S。然后我们用b数组中的数去替换，替换第i个数相当于给S异或上了a_i\oplus b_i 。所以我们新建一个数组d,d_i=a_i\oplus b_i，原问题就变成了从d中选出若干个数，使得异或和为S。
如果不输出方案，就是一道线性基模板题。现在考虑方案。
我们要解决的核心问题是：当我们使用线性基中的第j层基底时，我们到底用了原始的哪些d_i?
除了线性基数组p以外，我们再额外维护两个数组：
pos[i]：记录谁是第i位的主元，即确定插入时插入到这里的数原先在d中的下标rev[i]：一个二进制掩码，记录要构成现在的p[i]，需要用到哪些主元
在插入时同时维护这三个数组，这样我们就能在构造异或和S的时候知道使用了d中的哪些元素。
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int t,n,a[N],b[N],p[70],rev[70],pos[70];
inline void init(int x,int id){
int res=0;
for(int i=62;i>=0;i--){
if(!((x>>i)&1)) continue;
if(!p[i]){
p[i]=x;
pos[i]=id;
rev[i]=res|(1<<i);
break;
}
x^=p[i];
res^=rev[i];
}
}
signed main()
{
cin>>t;
while(t--){
int s=0;
cin>>n;
memset(p,0,sizeof p);
for(int i=1;i<=n;i++)cin>>a[i],s^=a[i];
for(int i=1;i<=n;i++)cin>>b[i],init(a[i]^b[i],i);
bool f=1;
int cur=0;
for(int i=31;i>=0;i--)
if((s>>i)&1){//构成S的第i位
if(p[i]) s^=p[i],cur^=rev[i];
else f=0;
}
if(!f) cout<<"-1\n";
else{
vector<int>vis(n+1,0);
for(int i=0;i<=31;i++)
if((cur>>i)&1) vis[pos[i]]=1;
for(int i=1;i<=n;i++)
if(vis[i]) cout<<b[i]<<" ";
else cout<<a[i]<<" ";
cout<<"\n";
}
}
}
评论