2022河南青训联赛第（三）场

A.玉米大炮

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+100;
const int M=1e6+100;
ll n,m,t;
ll a[N],b[N];

int check(__int128 mid)
{
    __int128 sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=(mid/b[i])*a[i];
		if(sum>=m) return 1;
	}
	return 0;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		m-=a[i];
	}

	__int128 l=0,r=1e18+100;

	while(l<r)
	{
		__int128 mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	
	cout<<(ll)l<<endl;


	return 0;
}

B.逆序对计

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=6500;
const int M=1e6+100;
const int mod=998244353;
const double eps=1e-9;
typedef pair<int,int> PII; 
#define endl '\n'
#define x first
#define y second
#define INF 0x3f3f3f3f
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int n,m,t;
int a[N],f[N][N];
int tr[N];

int lowbit(int x)
{
    return x&-x;
}

void add(int x,int c)
{
    for(int i=x;i<N;i+=lowbit(i)) 
    tr[i]+=c;

}

ll query(int x)
{
    ll res=0;
    for(int i=x;i;i-=lowbit(i))
    res+=tr[i];
    return res;
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++)    //计算[l,r]区间的逆序对个数
    {
        for(int j=i;j<=n;j++)
        {
            f[i][j]=f[i][j-1]+(j-1-i+1-query(a[j]));
            add(a[j],1);
        }
        memset(tr,0,sizeof tr); //每次计算完要清空树状数组
        
    }

    cin>>t;

    while(t--)
    {
        int l,r;
        cin>>l>>r;
        cout<<f[1][n]+(r-l+1)*(r-l)/2-2*f[l][r]<<endl; //1~n的逆序对+（正序对-逆序对）
    }
 
   

	return 0;
}

C.区间操作

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e6+100;
const int M=1e6+100;
const int mod=998244353;
const double eps=1e-9;
typedef pair<int,int> PII; 
#define endl '\n'
#define x first
#define y second
#define INF 0x3f3f3f3f
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int n,m,t;
int f[N],b[N];
int prime[N],cnt;
bool st[N];

struct Node
{
    int l,r;
    ll sum,add;
}tr[N<<2];

void init(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) prime[cnt++]=i,f[i]=1;
        for(int j=0;prime[j]<=n/i;j++)
        {
            st[prime[j]*i]=1;
            f[prime[j]*i]=f[i]+1;
            if(i%prime[j]==0) break;
        }
    }
}

void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void pushdown(int u)
{
    auto &left=tr[u<<1],&root=tr[u],&right=tr[u<<1|1];
    if(root.add)
    {
        left.sum+=(left.r-left.l+1)*root.add,left.add+=root.add;
        right.sum+=(right.r-right.l+1)*root.add,right.add+=root.add;
        root.add=0;
    }
}

void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,b[l],0};
    else
    {
        tr[u]={l,r};
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }

}

void modify(int u,int l,int r,ll c)
{
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        tr[u].sum+=(tr[u].r-tr[u].l+1)*c;
        tr[u].add+=c;
        return ;
    }
   
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) modify(u<<1,l,r,c);
    if(r>mid) modify(u<<1|1,l,r,c);
    pushup(u);
}

ll query(int u,int l,int r)
{
    if(l<=tr[u].l&&tr[u].r<=r) return tr[u].sum;
    
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    ll sum=0;
    if(l<=mid) sum=query(u<<1,l,r);
    if(r>mid) sum+=query(u<<1|1,l,r);
     
    return sum;

}

int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    init(N-1);
    cout<<cnt<<endl;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>b[i],b[i]=f[b[i]];

    build(1,1,n);

    cin>>t;
    int op,l,r,w;
    while(t--)
    {
        cin>>op>>l>>r;
        if(op==1) cout<<query(1,l,r)<<endl;
        else
        {
            cin>>w;
            modify(1,l,r,f[w]);
        }

    }


    

    

	return 0;
}

D.小蓝的新技能

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+100;
const int M=1e6+100;
const int mod=998244353;
const double eps=1e-9;
typedef pair<int,int> PII; 
#define endl '\n'
#define x first
#define y second
#define INF 0x3f3f3f3f
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
ll n,m,t;

ll get(ll x)
{
	ll l=1,r=1e6;

	while(l<r)
	{
		ll mid=l+r+1>>1;
		if(mid*mid*mid<=x) l=mid;
		else r=mid-1;
	}
	return l;

}



int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	
	cin>>n;
	int ans=0;
	for(ll g=1;g<=n/g/g;g++)
	{
		for(ll a=g;a<=n/a/a;a+=g)
		{
			ll p=n-g*g*g; //利用题目的等式条件
			ll k=get(p); //求出lcm
			if(k*k*k==p)  //判断lcm合法
			{
				ll lcm=k;
				ll b=lcm*g/a;  //利用公式求出b
				if(!b) continue;  //有可能会出现浮点数错误，即除0
				if(__gcd(a,b)==g&&a*b/__gcd(a,b)==lcm) //最后返回来判断是否满足gcd,lcm
				ans++;

			}
		}

	}
	 cout<<ans<<endl;

    

	return 0;
}

G.小蓝的玻璃球

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+100;
const int M=1e6+100;
const int mod=998244353;
const double eps=1e-9;
const double pi = acos(-1) ;
typedef pair<int,int> PII; 
typedef pair<double,double> PDD; 
#define endl '\n'
#define x first
#define y second
#define INF 0x3f3f3f3f
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int n,m,t;
double x,y;
vector<PDD> ans;

double dist(double x,double y)
{
	return x*x+y*y;
}

int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

	cin>>n;

	while(n--)
	{
		cin>>x>>y;
		double gel=atan2(y,x);
		double keg=asin(2.0/sqrt(dist(x,y)));
		
		ans.push_back({gel,min(gel+keg,pi)});
		if(gel+keg>pi) ans.push_back({-pi,-pi+gel+keg-pi}); //大小可以按弧度范围看[-pi,pi]，小的在前，大的在后，否则会影响最后合并
                  
		ans.push_back({max(gel-keg,-pi),gel});
		if(gel-keg<-pi) ans.push_back({pi-fabs(gel-keg+pi),pi});
	}

	sort(ans.begin(),ans.end());

	double res=0,pre=-1e9;

	for(int i=0;i<ans.size();i++)   //合并区间
	{
		if(pre>ans[i].x) res+=max(0.0,ans[i].y-pre);// 可能pre大于该区间的右端点，即已经包括了该区间
		else res+=ans[i].y-ans[i].x;
		pre=max(pre,ans[i].y);
	}

	printf("%.12f",res/(2.0*pi));


    

	return 0;
}

 H.树上问题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+100;
const int M=1e6+100;
const int mod=998244353;
const double eps=1e-9;
typedef pair<int,int> PII; 
#define endl '\n'
#define x first
#define y second
#define INF 0x3f3f3f3f
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int n,m,t;
vector<int> e[N];
// f表示u一直向下走能走的最远距离，r表示u经过父节点继续向上走的最远距离，w表示u能到达的最远距离
ll f[N],r[N],w[N],dp[N],a[N];
ll res;

void dfsf(int u,int fa) //由子节点更新父节点 求出其向下能走的最远距离
{
	f[u]=a[u];
	ll t=0;
	for(auto to:e[u])
	{
		if(to==fa) continue;
		dfsf(to,u);
		t=max(t,f[to]);
	}
	f[u]+=t;
}

void dfsw(int u,int fa)  //由父节点更新子节点 求出w
{
	ll m1=0,m2=0;
	for(auto to:e[u])
	{
		if(to==fa) continue;
		if(f[to]>m1) m2=m1,m1=f[to];
		else if(f[to]>m2) m2=f[to];
	}

	for(auto to:e[u])
	{
		if(to==fa) continue;
		if(m1==f[to])
		{
			//v能走的最远距离为max(子节点向下所达到的最远距离 f[v]，向上走经父节点并且继续向上走 a[v]+r[u]，该节点向上走通过父节点,经父节点向下走能走的最远距离(这里只能是次远距离),a[v]+a[u]+m2)              
			w[to]=max({f[to],a[to]+r[u],a[to]+a[u]+m2});
			r[to]=max(a[to]+r[u],a[to]+a[u]+m2);
		}
		else
		{
			w[to]=max({f[to],a[to]+r[u],a[to]+a[u]+m1});
			r[to]=max(a[to]+r[u],a[to]+a[u]+m1);
		}
		dfsw(to,u);
	}

}

void dfsres(int u,int fa) // 更新选该节点u，并且选一个儿子节点的能到达的最远距离，并且计算出该点的两种情况的最大值
{
	//m1,m2 记录子节点的最大/次大最远距离，m3记录选择u的子节点v，并且再选一个v的子节点的能到距离的最大值
	ll m1=0,m2=0,m3=0;  
	for(auto to:e[u])
	{
		if(to==fa) continue;
		if(w[to]>m1) m2=m1,m1=w[to];
		else if(w[to]>m2) m2=w[to];
		
		dfsres(to,u);      //先递归由子节点求出dp值，再求最大值
		m3=max(m3,dp[to]);
		
	}
	dp[u]=w[u]+m1;  //更新dp值 u能到达的最远距离+其儿子能到达的最远距离

	res=max({m1+m2+w[u],m3+w[u],res}); //两种情况

}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

	cin>>n;

	for(int i=1;i<=n;i++) cin>>a[i];

	for(int i=0;i<n-1;i++)
	{
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}

	dfsf(1,0);

	w[1]=f[1];  //1为根节点，能到达的最远距离就是f[1]
	r[1]=a[1];  //向上走的距离只有本身节点的值
	
	dfsw(1,0);

	dfsres(1,0);
	
	cout<<res<<endl;

	return 0;
}

 I.旅行

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+100;
const int M=1e6+100;
const int mod=998244353;
const double eps=1e-9;
typedef pair<int,int> PII; 
#define endl '\n'
#define x first
#define y second
#define INF 0x3f3f3f3f
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int n,m;
int h[2*N],e[2*M],ne[2*M],idx;
ll w[2*M],x;
ll dis[2*N];
bool st[2*N];

void add(int a,int b,ll c)
{
    w[idx]=c;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

void dj()
{
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;  //因为起初一号点不用做核酸，且路途花费为0，所以初始为0
    heap.push({0,1});

    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        if(st[t.y]) continue;
        st[t.y]=1;

        for(int i=h[t.y];~i;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>dis[t.y]+w[i])
            {
                dis[j]=dis[t.y]+w[i];
                heap.push({dis[j],j});
            }
        }
    }


}

int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    memset(h,-1,sizeof h);
 
    cin>>n>>m>>x;
    int a,b;
    ll c;
    while(m--)
    {
        cin>>a>>b>>c;
        add(a,b+n,c+x),add(a+n,b,c); 
        add(b,a+n,c+x),add(b+n,a,c);
    }
    
    dj();

    cout<<min(dis[n],dis[2*n])<<endl; //因为不知道最优路径n号点的核酸情况，所以需要两者取min.


	return 0;
}