2022/4/22

排队 - 题目 - Daimayuan Online Judge 算相对顺序的方法

想了很久没有想出来，当对一个有公式的题没有思路的时候可以试一试把公式化简或展开一下，就比如这个就可以变成,前面的不会变，我们只要2ab最大就可以了，那就是让两数组的乘积最大，有一个结论是两数组有序的情况下比无序的情况乘积和更大，所以我们只要让他们相对有序就可以了，我们假定数组a是有序的，以a为准，把b离散化一下，离散化完的数组再求一遍逆序对就是答案了；但这个离散化还挺奇妙的；id这个属性就相当于离散化后的数组，c[a[i].id]=b[i].id就是以a[i].id为关键字对b[i]排序，这也算是个桶排序的思想了，之后求逆序对就可以了；我靠，这题之前做过，这在直接没印象了，不愧是我；

(7条消息) 2022-04-22每日刷题打卡_你好_Ä的博客-CSDN博客

#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

结案了，不会算概率，只要会算概率期望，这题就是一个深搜，，，

#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 算法课的加分题目

给你一个点让你算一下这个点所在连通块的周长，连通块都知道要如何去搜，关键是周长，其实不难发现只要一个X的上或下或左或右是'.'或边界就说明这个点的上或下或左或右就可以作为周长的一部分，所以周长就能算出来了，另外去搜点的时候是向八个方向搜不是四个了；

#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;
}