A.茕茕孑立之影
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int Q = 2e5 + 9;
const ll MOD = 1e9 + 7;
ll a[Q];
void solve(){
ll n;cin>>n;
for (ll i = 1; i <= n; i++)
{
cin>>a[i];
}
for (ll i = 1; i <= n; i++)
{
if(a[i]==1){
cout<<-1<<"\n";
return;
}
}
cout<<MOD<<"\n";
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll _ = 1;cin>>_;
while(_--){
solve();
}
return 0;
}
B.一气贯通之刃
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int Q = 2e5 + 9;
const ll MOD = 1e9 + 7;
vector<ll> d[Q];
void solve(){
ll n;cin>>n;
for (ll i = 1; i < n; i++)
{
ll o,p;cin>>o>>p;
d[o].push_back(p);
d[p].push_back(o);
}map<ll,ll> mp;
ll l=0,r=0;
for (ll i = 1; i <= n; i++)
{
mp[d[i].size()]++;
if(d[i].size()==1){
if(l==0) l=i;
else r=i;
}
}
if(mp[1]==2 and mp[2]==n-2){
cout<<l<<" "<<r<<"\n";
}else{
cout<<-1<<"\n";
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll _ = 1;//cin>>_;
while(_--){
solve();
}
return 0;
}c
D.双生双宿之决
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int Q = 2e5 + 9;
const ll MOD = 1e9 + 7;
ll a[Q];
void solve(){
ll n;cin>>n;
map<ll,ll> mp;
for (ll i = 1; i <= n; i++)
{
cin>>a[i];mp[a[i]]++;
}
if(mp.size()==2){
ll cnt=mp[a[1]];
for(auto i:mp) if(i.second!=cnt){
cout<<"No\n";
return;
}
}else{
cout<<"No\n";
return;
}
cout<<"Yes\n";
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll _ = 1;cin>>_;
while(_--){
solve();
}
return 0;
}
E.双生双宿之错
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int Q = 2e5 + 9;
const ll MOD = 1e9 + 7;
ll a[Q];
void solve(){
ll n;cin>>n;
for (ll i = 1; i <= n; i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
ll l=n/2,r=l+1;
ll lcnt=a[(l+1)/2],rcnt=a[(r+n)/2];
ll ans=0,ans2=0,ans3=0;
if(lcnt!=rcnt){
for (ll i = 1; i <= l; i++)
{
ans+=abs(a[i]-lcnt);
}
for (ll i = r; i <= n; i++)
{
ans+=abs(a[i]-rcnt);
}
cout<<ans<<"\n";
}else{
for (ll i = 1; i <= l; i++)
{
ans2+=abs(a[i]-lcnt+1);//前半部分-1 因为前半部分永远比后半部分小
ans3+=abs(a[i]-lcnt);
}
for (ll i = r; i <= n; i++)
{
ans2+=abs(a[i]-rcnt);
ans3+=abs(a[i]-rcnt-1);//后半部分+1 后半部分永远比前半部分大
}
cout<<min(ans2,ans3)<<"\n";
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll _ = 1;cin>>_;
while(_--){
solve();
}
return 0;
}
G.井然有序之衡
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int Q = 2e5 + 9;
const ll MOD = 1e9 + 7;
ll a[Q];
void solve(){
ll n;cin>>n;ll cnt=0,sum=0,ans=0;
map<ll,ll> mp;
for (ll i = 1; i <= n; i++)
{
cnt+=i;
cin>>a[i];mp[a[i]]++;
sum+=a[i];
}
ll it=n;
if(sum!=cnt){
cout<<-1<<"\n";
}else{
sort(a+1,a+1+n);
ll ans=0;
for (ll i = 1; i <= n; i++)
{
ans+=abs(a[i]-i);
}
cout<<ans/2<<"\n";
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll _ = 1;//cin>>_;
while(_--){
solve();
}
return 0;
}
H.井然有序之窗
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int Q = 1e5 + 9;
const ll MOD = 1e9 + 7;
ll ans[Q];
struct op
{
ll l,r,ct;
};
bool cmp(op l,op r){
if(l.l==r.l) return l.r<r.r;
else return l.l<r.l;
}
struct cmp2
{
bool operator()(pair<ll,ll> l,pair<ll,ll> r){
return l.first>r.first;
}
};
op a[Q];
void solve(){
ll n;cin>>n;
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,cmp2> pq;
for (ll i = 1; i <= n; i++) cin>>a[i].l>>a[i].r,a[i].ct=i;
sort(a+1,a+1+n,cmp);
ll it=1;
for (ll i = 1; i <= n; i++)
{
while(it<=n and a[it].l<=i){
pq.push({a[it].r,a[it].ct});it++;
}
if(pq.size()==0){
cout<<-1<<"\n";
return;
}
pair<ll,ll> now=pq.top();
pq.pop();
if(now.first>=i){
ans[now.second]=i;
}
else{
cout<<-1<<"\n";
return;
}
}
for (ll i = 1; i <= n; i++)
{
cout<<ans[i]<<" ";
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll _ = 1;//cin>>_;
while(_--){
solve();
}
return 0;
}
J.硝基甲苯之袭
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int Q = 3e5 + 9;
const ll MOD = 1e9 + 7;
ll a[Q];
ll mp[Q];
void solve(){
ll n;cin>>n;
for (ll i = 1; i <= n; i++){
cin>>a[i];mp[a[i]]++;
}
ll ans=0;// x^y == gcd(x,y)
for (ll i = 1; i <= 2e5; i++)//枚举x
{
for (ll j = 1; j * j <= i ; j++)//枚举x的因子 y=i+j,x=i;
{
if(i%j==0){//是因子
if((i^(i+j))==gcd(i,(i+j))) ans+=mp[i]*mp[i+j];
if(j!=i/j) //平方时只加一次
if((i^(i+i/j))==gcd(i,(i+i/j))) ans+=mp[i]*mp[i+i/j];
}
}
}
cout<<ans;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll _ = 1;//cin>>_;
while(_--){
solve();
}
return 0;
}
M.数值膨胀之美
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int Q = 1e5 + 9;
const ll MOD = 1e9 + 7;
ll a[Q];
void solve(){
ll n;cin>>n;
ll l=1,r=1;
multiset<ll> st;
for (ll i = 1; i <= n; i++)
{
cin>>a[i];
st.insert(a[i]);
if(a[i]<a[l]){
l=i,r=i;
}
}
ll ans=1e18;
st.erase(st.lower_bound(a[l]));
st.insert(a[l]*2);
ans=min(*st.rbegin()-*st.begin(),ans);
l--,r++;
while(l>=1 or r<=n){
if(r>n or (a[l]<a[r] and l>=1)){
st.erase(st.lower_bound(a[l]));
st.insert(a[l]*2);
l--;
ans=min(*st.rbegin()-*st.begin(),ans);
}else{
st.erase(st.lower_bound(a[r]));
st.insert(a[r]*2);
r++;
ans=min(*st.rbegin()-*st.begin(),ans);
}
}
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll _ = 1;//cin>>_;
while(_--){
solve();
}
return 0;
}
