A
思路
直接模拟即可。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int x,y; cin>>x>>y;
cout<<min(x,y)<<" "<<max(x,y)<<"\n";
}
int main()
{
int t=1;
cin>>t;
for(int i=1;i<=t;i++)
{
solve();
}
return 0;
}
|
B
思路
直接在里面找相邻不同的两个字符进行交换。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
string s; cin>>s;
bool ok=false;
for (int i = 0; i+1 < s.size(); ++i)
{
if(s[i]!=s[i+1]) swap(s[i],s[i+1]),ok=true;
}
if(ok)
{
cout<<"Yes\n";
cout<<s<<"\n";
}
else cout<<"No\n";
}
int main()
{
int t=1;
cin>>t;
for(int i=1;i<=t;i++)
{
solve();
}
return 0;
}
|
C
思路
研究一下交叉情况的数字特征，其实就是两个区间是否存在交叉（不包括包含的情况）。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int a,b,c,d; cin>>a>>b>>c>>d;
if(a>b) swap(a,b);
if(c>d) swap(c,d);
if(a<=c && c<=d && c<=b && b<=d)
{
cout<<"YES\n";
return;
}
swap(a,c);
swap(b,d);
if(a<=c && c<=d && c<=b && b<=d)
{
cout<<"YES\n";
return;
}
else cout<<"NO\n";
}
int main()
{
int t=1;
cin>>t;
for(int i=1;i<=t;i++)
{
solve();
}
return 0;
}
|
D
还是太着急了，没有考虑清楚全部的情况。
思路
不难想到从000111这种类型的串入手：
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
string s; cin>>s;
int n=s.size();
int cnt=0;
bool ok=false;
for (int i = 0; i < n; ++i)
{
ok=false;
while(i<n && s[i]=='0')
{
i++;
ok=true;
}
if(ok) cnt++;
}
if(cnt==0)
{
cout<<1<<"\n";
return;
}
else if(cnt==1)
{
if(s[0]!='0')
{
cout<<"2\n";
return;
}
cout<<"1\n";
return;
}
cnt=1+(cnt-1)*2;
if(s[0]=='1') cnt++;
if(s[n-1]=='0') cnt--;
cout<<cnt<<"\n";
}
int main()
{
int t=1;
cin>>t;
for(int i=1;i<=t;i++)
{
solve();
}
return 0;
}
|
F
思路
不难想到只需要处理一个象限即可。我们以第一象限为例子。
这里直接枚举x和y肯定会TLE。另外注意到满足以下不等式：
\[
r^2 \leq x^2+ y^2 \leq (r+1)^2
\] 不难得到： \[
\sqrt{(r^2-x^2)} \leq y \leq \sqrt{(r+1)^2-x^2}
\]
可以通过枚举x，计算所有满足的y的情况。（其实就是\(y_{max}-y_{min}+1\)）
Trick
这里使用sqrt可能会爆精度，所以需要减一。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
ll r; cin>>r;
ll ans=0;
for (ll x = 0; x < r+1; ++x)
{
ll maxn=sqrt(1ll*(r+1)*(r+1)-1ll*x*x-1);
ll minn=sqrt(1ll*r*r-1ll*x*x-1);
ans+=maxn-minn;
}
ans*=4;
cout<<ans<<"\n";
}
int main()
{
int t=1;
cin>>t;
for(int i=1;i<=t;i++)
{
solve();
}
return 0;
}
|
G
思路
不难发现：可以交换的这些数字，除了最低两位，其他为都是相同的。
那么只需要将这些前面位的数字按照从小到大的顺序排序即可。
至于这些不同的各个数字集合，我们可以使用一个map进行维护。
这里集合内部的数字可以用优先队列维护，也可以sort+vector。
Trick
这里可以使用map来维护一个集合，key维护的是索引mask，value维护的是这个mask对应的数字集合。
还有可以先>>2再<<2来得到索引mask。
代码
一
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
std::vector<ll> a(n);
for (int i = 0; i < n; ++i)
{
cin>>a[i];
}
std::map<string, std::vector<int>> map;
for (int i = 0; i < n; ++i)
{
ll x=(a[i]>>2);
string s="";
while(x>0)
{
if(x&1) s+="1";
else s+="0";
x>>=1;
}
map[s].push_back(i);
}
for (auto [s,v]: map)
{
std::vector<ll> tmp;
for (int i = 0; i < v.size(); ++i)
{
tmp.push_back(a[v[i]]);
}
sort(begin(tmp),end(tmp));
for (int i = 0; i < v.size(); ++i)
{
a[v[i]]=tmp[i];
}
}
for (int i = 0; i < n; ++i)
{
cout<<a[i]<<" \n"[i==n-1];
}
}
int main()
{
int t=1;
cin>>t;
for(int i=1;i<=t;i++)
{
solve();
}
return 0;
}
|
二
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
int n; cin>>n;
std::vector<ll> a(n,0);
std::map<int, priority_queue<int,vector<int>,greater<int> > > map;
for (int i = 0; i < n; ++i)
{
cin>>a[i];
ll y=(a[i]>>2)<<2;
map[y].push(a[i]);
}
for (auto t: a)
{
ll y=(t>>2)<<2;
cout<<map[y].top()<<" ";
map[y].pop();
}
cout<<"\n";
}
int main()
{
int t=1;
cin>>t;
for(int i=1;i<=t;i++)
{
solve();
}
return 0;
}
|
