Codeforces Round 1009 (Div. 3)（A-E）

2301_80299496

496人浏览 · 2025-03-25 10:59:44

2301_80299496 · 2025-03-25 10:59:44 发布

题目链接：Dashboard - Codeforces Round 1009 (Div. 3) - Codeforces

A. Draw a Square

思路

只有4个数相同才能构造正方形

代码

void solve(){
    int l,r,d,u;
    cin>>l>>r>>d>>u;
    if(l==r&&l==d&&u==d){
        cout<<"YES\n";
    }else{
        cout<<"NO\n";
    }
}

B. The Third Side

思路

每次选择两个数a,b将a+b-1插进去直到数组长度为1，其实就是把所有数加起来减去n-1

代码

void solve(){
    int n;
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        sum+=x;
    }
    cout<<(sum-(n-1))<<"\n";
}

C. XOR and Triangle

思路

根据异或性质来说如果 $x+y=x\bigoplus y$ 那么在二进制下x与y没有都是 1的情况，且 $x\bigoplus y<=max(x,y)$ 题目要求y<x

发现当 $x=2^{n}$ 或 $x=2^{n}-1$ 的时候无论怎么构造y都是 $x=y+x\bigoplus y$ 所以直接输出-1

其他情况我们只需要找到x的最高位1然后 $y=2^{p}-1$ 即可这样就能保证非退化三角形

当然这题可以用随机数跑过去....

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

void solve(){
    int x;
    cin>>x;
    int p=0;
    for(int i=63;i>=0;i--){
        if((x>>i)&1){
            p=i;break;
        }
    }
    if((x==(1ll<<(p+1))-1)||(x==(1ll<<p))){
        cout<<"-1\n";
    }else{
        cout<<(1ll<<p)-1<<"\n";
    }
}
signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

恶搞的随机数代码

#include <bits/stdc++.h>
#define inf 1e18
#define Endl endl
using namespace std;
#define int long long
#define PII pair<int, int>
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2e5 + 10, mod = 998244353;
std::random_device RD;
std::mt19937_64 gen(time(0));
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int roll(int l, int r)
{
    std::uniform_int_distribution<int> dist(l, r);
    return dist(gen);
}
int check(int x, int y, int z)
{
    int mx = max({x, y, z});
    if (x + y + z - mx > mx)
        return 1;
    return 0;
}
void solve()
{
    int x;
    cin >> x;
    int y = roll(1, x);
    int cnt = 0;
    while (!check(x, y, x ^ y))
    {
        y = roll(1, x);
        cnt++;
        if (cnt == 1e3)
            break;
    }
    if (check(x, y, x ^ y))
        cout << y << endl;
    else
        cout << "-1";
}
signed main()
{
    ios;
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
        if (T != 0)
            cout << endl;
    }
    return 0;
}

D. Counting Points

思路

这题有两种方法，差不多都是一种思想，只是固定的坐标轴不同，赛时用固定y轴的方法实现的比较麻烦

固定y轴。

我们通过发现半径r的范围，总和是=m的，这样我们可以尝试遍历所有半径r来统计答案，那么接下来我们可以尝试统计所有圆半径为0---r的所包含的数统计成区间，我们根据距离的公式勾股定理来找出所包含的区间，然后最后将r=[0,m]的区间全部合并，最后统计答案，注意因为圆是对称的，我们只需要统计y>=0的答案即可最后乘2

固定x轴。

和y轴的思想差不多，更容易实现一些，我们对x轴上的数统计一下它所包含的点数即可，有覆盖就统计最大值

代码

固定y轴

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

struct Circle{
    int x,r;
};

int cal(int r, int k) {
    int sq = r * r - k * k;
    if (sq < 0) return -1;
    int s = sqrt(sq);
    while (s * s > sq) s--;
    while ((s + 1) * (s + 1) <= sq) s++;
    return s;
}

void solve(){
    int n,m;
    cin>>n>>m;
    
    vi x(n+1),r(n+1);
    for(int i=1;i<=n;i++) cin>>x[i];
    for(int i=1;i<=n;i++) cin>>r[i];

    vector<Circle> v;
    for(int i=1;i<=n;i++) v.push_back({x[i],r[i]});

    sort(v.begin(),v.end(),[](const Circle& a,const Circle& b){
        return a.x<b.x;
    });

    vector<vector<pll>> qu(m+1);    //记录当坐标轴y=i时的所有区间
    for(int i=0;i<n;i++){
        for(int j=0;j<=v[i].r;j++){
            int t=cal(v[i].r,j);
            qu[j].push_back({v[i].x-t,v[i].x+t});
        }
    }

    //将区间合并
    vector<vector<pll>> meg(m+1);
    for(int i=0;i<=m;i++){
        if(qu[i].empty()) continue;

        vector<pll> tmp=qu[i];

        sort(tmp.begin(),tmp.end(),[](const pll& a,const pll& b){
            if(a.first==b.first) return a.second<b.second;
            return a.first<b.first;
        });

        int l=0,r=0;
        bool f=false;   //判断是否是第一个
        for(auto it:tmp){
            if(!f) l=it.first,r=it.second,f=true;
            else{
                if(it.first<=r){
                    r=max(r,it.second);
                }else{
                    meg[i].push_back({l,r});
                    l=it.first;
                    r=it.second;
                }
            }
            
        }
        meg[i].push_back({l,r});

    }

    int ans=0;
    for(int i=0;i<=m;i++){
        if(meg[i].empty()) continue;
        for(auto it:meg[i]){
            // cout<<i<<"   "<<it.first<<" "<<it.second<<"\n";
            if(i==0)
                ans+=(it.second-it.first+1);
            else
                ans+=(it.second-it.first+1)*2;
        }
    }
    cout<<ans<<"\n";
}
signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

固定x轴

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;


int cal(int r,int k){
    int sq=r*r-k*k;
    if(sq<0) return -1;
    int s=sqrt(sq);
    while(s*s>sq) s--;
    while((s+1)*(s+1)<=sq) s++;
    return 2*s+1;
}

void solve(){
    int n,m;
    cin>>n>>m;
    vi x(n+1),r(n+1);
    for(int i=1;i<=n;i++){cin>>x[i];}
    for(int i=1;i<=n;i++){cin>>r[i];}
    
    map<int,bool> mp;    //用于统计x坐标
    map<int,int> cnt;    //记录坐标为x时的最大值
    vi ax;
    for(int i=1;i<=n;i++){

        for(int j=0;j<=r[i];j++){
            if(!mp[x[i]-j]){
                ax.push_back(x[i]-j);
                mp[x[i]-j]=true;
                cnt[x[i]-j]=cal(r[i],j);
            }else{
                cnt[x[i]-j]=max(cnt[x[i]-j],cal(r[i],j));
            }
            if(!mp[x[i]+j]){
                ax.push_back(x[i]+j);
                mp[x[i]+j]=true;
                cnt[x[i]+j]=cal(r[i],j);
            }else{
                cnt[x[i]+j]=max(cnt[x[i]+j],cal(r[i],j));
            }
        }

    }

    int ans=0;
    for(auto tx:ax){
        ans+=cnt[tx];
    } 
    cout<<ans<<"\n";

}
signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

E. Empty Triangle

思路

随机数乱搞的题，具体证明看官方题解

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

mt19937 rnd(time(0));
uniform_int_distribution<int> uni(1,3);

int query(int x,int y,int z){
    cout<<"? "<<x<<" "<<y<<" "<<z<<endl;
    int res;
    cin>>res;
    return res;
}

void solve(){
    int n;cin>>n;
    int x=1,y=2,z=3;
    while(1){
        int t=query(x,y,z);
        if(t==0){
            cout<<"! "<<x<<" "<<y<<" "<<z<<endl;
            return;
        }else{
            int op=uni(rnd);
            if(op==1){
                x=t;
            }else if(op==2){
                y=t;
            }else{
                z=t;
            }
        }
    }
}
signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}