2022/4/22

line up - subject - Daimayuan Online Judge  How to calculate the relative order

I haven't thought of it for a long time , When you have no idea about a problem with formula, you can try to simplify or expand the formula , For example, this can become , The one in front won't change , All we have to do is 2ab The biggest is enough , That is to maximize the product of two arrays , One conclusion is that the product sum of two arrays in order is greater than that in disorder , So we just need to keep them relatively orderly , Let's assume that the array a Is ordered , With a Subject to , hold b Discretization , The answer is to find the inverse pair of the discretized array again ; But this discretization is wonderful ;id This property is equivalent to the discretized array ,c[a[i].id]=b[i].id That is to say a[i].id Is a keyword pair b[i] Sort , This is also a bucket sorting idea , Then find the reverse order pair ; I rely on , I've done this before , I'm not impressed at all , I am worthy of it ;

(7 Bar message ) 2022-04-22 Swipe questions and punch in every day _ Hello _Ä The blog of -CSDN Blog

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((-x)&(x))
using namespace std;
const ll inf=1e16;
const ll mod=1e8-7;
ll n;
struct node{
    ll id,v;
}a[100005],b[100005],c[100005];
bool cmp(node a,node b){
    return a.v<b.v;
}
bool cmp1(node a,node b){
    if(a.v==b.v) return a.id>b.id;
    return a.v>b.v;
}
ll t[100005];
void add(ll x){
    for(int i=x;i<=n;i+=lowbit(i))
        t[i]=(t[i]+1)%mod;
}
ll ask(ll x){
    ll res=0;
    for(int i=x;i;i-=lowbit(i))
        res=(res+t[i])%mod;
    return res;
}
int main(){
	//freopen("in.txt","r",stdin);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i].v),a[i].id=i;
	for(int i=1;i<=n;i++) scanf("%lld",&b[i].v),b[i].id=i;
	sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++) c[a[i].id].v=b[i].id,c[a[i].id].id=a[i].id;
	sort(c+1,c+n+1,cmp1);
	ll ans=0;
	for(int i=1;i<=n;i++){
        //cout<<c[i].id<<" "<<c[i].v<<endl;
        ans=(ans+ask(c[i].id-1))%mod;
        add(c[i].id);
	}
	printf("%lld\n",ans);
	return 0;
}

Problem - 839C - Codeforces

It's over , It's not a probability , As long as you can calculate the probability expectation , This question is a deep search ,,,

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((-x)&(x))
using namespace std;
const ll inf=1e16;
const ll mod=1e8-7;
ll n;
double sum;
vector<ll>v[100005];
void dfs(ll u,ll fa,double s,ll dep){
    ll cnt=0;
    for(int i=0;i<v[u].size();i++) if(v[u][i]!=fa) cnt++;
    if(cnt==0){
        sum+=(double)s*dep;
        return;
    }
    for(int i=0;i<v[u].size();i++){
        ll j=v[u][i];
        if(j==fa) continue;
        dfs(j,u,s*(1.0/cnt),dep+1);
    }
}
int main(){
	//freopen("in.txt","r",stdin);
	scanf("%lld",&n);
	for(int i=1;i<n;i++){
        ll u,vv;
        scanf("%lld%lld",&u,&vv);
        v[u].push_back(vv);
        v[vv].push_back(u);
	}
    sum=0;
	dfs(1,-1,1,0);
	printf("%.15f\n",sum);
	return 0;
}

ZOJ (pintia.cn)1047 Bonus topic of algorithm class

Give you a point and let you calculate the perimeter of the connecting block where this point is located , All connected blocks know how to search , The key is perimeter , In fact, it is not difficult to find that only one X Up or down or left or right is '.' Or boundary means that the upper or lower, left or right of this point can be used as part of the perimeter , So the perimeter can be calculated , In addition, when you search for points, you search in eight directions, not four ;

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((-x)&(x))
using namespace std;
const ll inf=1e16;
const ll mod=1e8-7;
ll n,m,vis[30][30],cx,cy,cnt;
char a[30][30];
struct node{
    ll x,y;
};
ll dx[8]={1,-1,0,0,1,1,-1,-1};
ll dy[8]={0,0,1,-1,1,-1,1,-1};
void bfs(){
    queue<node>q;
    q.push(node{cx,cy});
    while(!q.empty()){
        node u=q.front();q.pop();
        ll ux=u.x,uy=u.y;
        if(vis[ux][uy]) continue;
        vis[ux][uy]=1;
        for(int i=0;i<4;i++){
            ll tx=ux+dx[i],ty=uy+dy[i];
            if(tx<1||tx>n||ty<1||ty>m||a[tx][ty]=='.') cnt++;
        }
        for(int i=0;i<8;i++){
            ll tx=ux+dx[i],ty=uy+dy[i];
            if(tx<1||tx>n||ty<1||ty>m||a[tx][ty]=='.') continue;
            if(a[tx][ty]=='X'&&!vis[tx][ty]) q.push(node{tx,ty});
        }
    }
}
int main(){
	//freopen("in.txt","r",stdin);
	while(scanf("%lld%lld%lld%lld",&n,&m,&cx,&cy)){
        if(n==0&&m==0&&cx==0&&cy==0) break;
        cnt=0;
        for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
        for(int i=0;i<=n;i++)
            for(int j=0;j<=m;j++) vis[i][j]=0;
        //if(a[cx][cy]=='.'){printf("0\n");continue;}
        bfs();
        printf("%lld\n",cnt);
	}
	return 0;
}