A.
最大最小
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1e5+9;
int a[N];
void solve(){
int x,y;
cin>>x>>y;
cout<<min(x,y)<<" "<<max(x,y)<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int q;
cin>>q;
while(q--){
solve();
}
return 0;
}
B.
只有字符串只存在一个字母的时候才是NO,然后YES随便搞一下
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1e5+9;
void solve(){
string s;
cin>>s;
map<char,int> mp;
for(int i=0;i<s.size();i++){
mp[s[i]]++;
}
if(mp.size()<=1){
cout<<"NO"<<'\n';
}else{
cout<<"YES"<<'\n';
string ans=s;
sort(ans.begin(),ans.end());
if(s==ans){
char t=s[0];
for(int i=1;i<s.size();i++){
if(t!=s[i]){
swap(ans[0],ans[i]);
break;
}
}
}
cout<<ans<<'\n';
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int q;
cin>>q;
while(q--){
solve();
}
return 0;
}
C.
一眼可以看出一个线段,有没有区间相交,但是我调了很久
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1e5+9;
bool outofrange(int L,int R,int l,int r){
return L>r || l>R;
}
bool inrange(int L,int R,int l,int r){
return L>=l && R<=r;
}
void solve(){
int l,r,L,R;
cin>>L>>R>>l>>r;
// cout<<L<<" "<<R<<" "<<l<<" "<<r<<'\n';
ll LL=min(L,R);
ll RR=max(L,R);
ll lll=min(l,r);
ll rr=max(l,r);
// cout<<L<<" "<<R<<" "<<l<<" "<<r<<'\n';
// cout<<LL<<" "<<RR<<" "<<lll<<" "<<rr<<'\n';
if(inrange(LL,RR,lll,rr)){
cout<<"NO"<<'\n';
}else if(inrange(lll,rr,LL,RR)){
cout<<"NO"<<'\n';
}else if(!outofrange(LL,RR,lll,rr)){
cout<<"YES"<<'\n';
}else{
cout<<"NO"<<'\n';
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int q;
cin>>q;
while(q--){
solve();
}
return 0;
}
// 5 3 4 12
// 3 5
// 4 12
实际上只要outofrange判断区间是否相交就行了
D.
贪心剪一个01,其他是1的连续或者0的连续
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1e5+9;
void solve(){
string s;
cin>>s;
string res=s;
sort(res.begin(),res.end());
if(res==s){
cout<<1<<'\n';
return;
}
ll ans=0;
char t=s[0]-'0';
// cout<<s[0]-'0'<<'\n';
// cout<<(int)t<<" sadd"<<'\n';
bool fl=true;
for(int i=1;i<s.size();i++){
if(t>(s[i]-'0')){
ans++;
t=s[i]-'0';
// fl=false;
}else if(t<(s[i]-'0') && fl){
t=s[i]-'0';
fl=false;
}else if(t<(s[i]-'0') && !fl){
ans++;
t=s[i]-'0';
}else if(t==(s[i]-'0')){
continue;
}
// cout<<ans<<" "<<t<<" "<<1<<'\n';
}
cout<<ans+1<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int q;
cin>>q;
while(q--){
solve();
}
return 0;
}
//11010
//11 01 0
E.
二分找到两个数据的中间,加前面的时间,再算后面的速度,最后求总时间
// Problem: E. Find the Car
// Contest: Codeforces - Codeforces Round 944 (Div. 4)
// URL: https://codeforces.com/contest/1971/problem/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e5+9;
ll a[N],b[N];
void solve(){
int n,k,q;
cin>>n>>k>>q;
for(int i=1;i<=k;i++){
cin>>a[i];
}
for(int i=1;i<=k;i++){
cin>>b[i];
}
while(q--){
int d;
cin>>d;
int l=0,r=k;
while(l<=r){
int mid=(l+r)>>1;
if(d>=a[mid]){
l=mid+1;//l
}else{
r=mid-1;
}
}
// cout<<l<<" "<<r<<" sdsadad"<<'\n';
ll res=(d-a[r])*(b[l]-b[r])/(a[l]-a[r]);
// cout<<res<<'\n';
ll ans=b[r]+res;//t+s/v
// a = (int)(a*1000+0.5)/1000.0;
// ans=(int)(ans*1000+0.5)/(1000.0);
// cout<<l<<" "<<r<<'\n';
cout<<ans<<" ";
}
cout<<'\n';
for(int i=1;i<=k;i++){
a[i]=0;
b[i]=0;
}
}
/*
6 1 3
6
5
2 6/5*2
6 5
5 6/5*5
*/
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
F.
枚举找一个象限的点<<2
// Problem: F. Circle Perimeter
// Contest: Codeforces - Codeforces Round 944 (Div. 4)
// URL: https://codeforces.com/contest/1971/problem/F
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
double dist(double x,double y){
return sqrt(x*x+y*y);
}
void solve(){
ll r;
cin>>r;
ll ans=0;
ll y=r;
for(int x=0;x<=r;x++){
while(x*x+y*y>=(r+1)*(r+1)){
y--;
}
ll top=y;
while(top && x*x+top*top>=r*r){
ans++;
top--;
}
}
//得到一个象限的点
cout<<(ans<<2)<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
G.
a[i] ^ a[j]<4,可以发现全部>>2后如果数都相同,那就可以交换,把这些处理完相同的看成一个块,
每个块sort处理一下或者用优先队列操作一下
// Problem: G. XOUR
// Contest: Codeforces - Codeforces Round 944 (Div. 4)
// URL: https://codeforces.com/contest/1971/problem/G
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int N=2e5+9;
// int a[N];
void solve(){
int n;
cin>>n;
vector<int> a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
map<int,priority_queue<int> > mp;
for(int i=1;i<=n;i++){
mp[(a[i]>>2)].push(-a[i]);
}
for(int i=1;i<=n;i++){
cout<<-1*(mp[a[i]>>2].top())<<" ";
mp[a[i]>>2].pop();
}
cout<<'\n';
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}