刷题记录

yisit · 2025-11-08 22:56:38 · 个人记录

P1569Generic Cow Protests

题意

1. 第一个大于 20 的数是 37，坐标是 4，4-1-1=2
2. 第一个大于 22 的数是 37，坐标是 4，4-2-1=1

看懂没有？本来从第一个大于 a_i+d 的数到 i 的距离是 x-i+1，x 表示为第一个大于 a_i+d 的数的坐标，因为 a_x>a_i+d，所以实际能到的是 x-i，但是自己又不能和自己说话，所以就是 x-i-1 了。

代码

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define lb long double
#define il inline
#define endl '\n'
#define ull unsigned long long
#define llt __int128
#define gcd(x,y) __gcd(x,y)
#define lcm(x,y) ((x)*(y)/(gcd(x,y))) 
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
#define fff(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
#define ls (k<<1)
#define rs (k<<1|1)
#define umap unordered_map
#define uset unordered_set
#define mmap multimap
#define mset multiset
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
#define psi pair<string,int>
#define psl pair<string,long long>
#define gc getchar
#define numpy(a,n) a+1,a+n+1
#define fi first
#define copy(a,b) memcpy(a,b,sizeof(a))
#define se second
#define clr(a) memset(a,0,sizeof(a))
#define mem(a,v)    memset(a,v,sizeof(a))
#define lowbit(x) (x&(-x))
#define all(s) s.begin(),s.end()
#define mkp make_pair
#define maxi INT_MAX
#define maxl LONG_LONG_MAX
#define mini INT_MIN
#define minl LONG_LONG_MIN
#define debug(x) cerr<<#x<<"="<<(x)<<'\n' 
#define hmod 212370440130137957ll
#define sss "--------------------------------------------------"
//-----------------------------------------------------------------------------
const int N=1e6+5;
int a[N];
ll ans;
int n,d;
signed main(){
//  fff("")
    IOS
    cin>>n>>d;
    for(int i=1;i<=n;i++)   cin>>a[i];
    sort(numpy(a,n));
    for(int i=1;i<=n;i++){
        ll r=upper_bound(numpy(a,n),a[i]+d)-a;
        ll l=i;
        ans+=(r-l-1);
    }
    cout<<ans;
    return 0;   
}   
//CODE BY tc291311 Luogu uid1340395 in Windows-VScode

P1194 买礼物

kruskal+一点思维

题意

明明需购买 B 样单价均为 A 元的物品，购买第 I 样后再买第 J 样可享优惠价 K_{I,J}（K_{I,J}=K_{J,I}，0 表示无优惠，可能大于 A）。求购买所有物品的最小总花费。

思路

kruskal 的板子。

目标是把所有节点连接起来，求最小的权值。

先用一个主节点 0 把所有点连接，边权均为 A。

• 如果此时 K=0：不管。
• 如果此时 K\neq0：连接一条从 i 到 j 边权为 K_{i,j} 的边。

再跑一边 kruskal 即可。

代码

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define lb long double
#define il inline
#define endl '\n'
#define ull unsigned long long
#define llt __int128
#define gcd(x,y) __gcd(x,y)
#define lcm(x,y) ((x)*(y)/(gcd(x,y))) 
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
#define fff(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
#define ls (k<<1)
#define rs (k<<1|1)
#define umap unordered_map
#define uset unordered_set
#define mmap multimap
#define mset multiset
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
#define psi pair<string,int>
#define psl pair<string,long long>
#define gc getchar
#define numpy(a,n) a+1,a+n+1
#define fi first
#define copy(a,b) memcpy(a,b,sizeof(a))
#define se second
#define clr(a) memset(a,0,sizeof(a))
#define mem(a,v)    memset(a,v,sizeof(a))
#define lowbit(x) (x&(-x))
#define all(s) s.begin(),s.end()
#define mkp make_pair
#define maxi INT_MAX
#define maxl LONG_LONG_MAX
#define mini INT_MIN
#define minl LONG_LONG_MIN
#define debug(x) cerr<<#x<<"="<<(x)<<'\n' 
#define hmod 212370440130137957ll
#define sss "--------------------------------------------------"
//-----------------------------------------------------------------------------
const int N=5e5+5;
struct node{
    int u,v,w;
}a[N];
int ans;
int cnt;
int fa[N];
int find(int u){
    if(u==fa[u])    return u;
    return fa[u]=find(fa[u]);
}
void merge(int u,int v){
    fa[find(u)]=find(v);
}
bool cmp(node x,node y){
    return x.w<y.w;
}
void kruskal(){
    sort(a+1,a+cnt+1,cmp);
    for(int i=1;i<=cnt;i++){
        if(find(a[i].v)==find(a[i].u))  continue;
        merge(a[i].v,a[i].u);
        ans+=a[i].w;
    }
}
signed main(){
//  fff("")
    IOS
    int v,n;
    cin>>v>>n;
    for(int i=1;i<=n;i++){
        a[++cnt].u=0;
        a[cnt].v=i;
        a[cnt].w=v;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int k;
            cin>>k;
            if(k!=0){
                a[++cnt].u=i;
                a[cnt].v=j;
                a[cnt].w=k;
            }
        }
    }
    for(int i=1;i<=cnt;i++){
        fa[i]=i;
    }
    kruskal();
    cout<<ans;
    return 0;   
}   
//CODE BY tc291311 Luogu uid1340395 in Windows-VScode