FZU周练-0528老队员场题解

（ACM）数学----概率论

题目链接

B. HIT 3209 Mod! Mod! Mod!

题意

题解

• 线段树维护被模数最大值。
• 每次取模，如果最大值小于模数，整段都不用更新。
• 复杂度：每次取模向下log层，每个数访问log次，总的复杂度nlognlogn

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define de(x) cout << #x << "=" << x << endl
const int N=100005;
int a[N],b[N],Max[N<<2];
void build(int l,int r,int rt) {
    if(l==r) {
        Max[rt]=b[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
}
void upd(int c,int l,int r,int rt) {
    if(c>Max[rt]) return ;
    if(l==r) {
        b[l]=b[l]%c;
        Max[rt]=b[l];
        return ;
    }
    int mid=(l+r)>>1;
    upd(c,lson);
    upd(c,rson);
    Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
}
int main() {
    int T;scanf("%d\n",&T);
    while(T--) {
        ///read
        int n;scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%d",a+i);
        int m;scanf("%d",&m);
        for(int i=1;i<=m;++i) scanf("%d",b+i);
        ///solve
        build(1,m,1);
        for(int i=1;i<=n;++i) upd(a[i],1,m,1);
        ///print
        for(int i=1;i<=m;++i) printf("%d\n",b[i]);
    }
    return 0;
}

E. HIT 3212 Traverse graph

题意

题解

• 每个点要么翻转(1)，要么不翻转(0)。
• 如果边是红色，那么端点只能是(1,1)，(0,0)。
• 如果边是蓝色，那么端点只能是(1,0)，(0,1)。
• 确定了一个点的颜色，那么整张图的颜色都确定了。
• 于是确定一下第一个点的颜色，dfs确定其他点即可。

代码

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int N=5005;
vector<pair<int,int> > G[N];
int ans;
int col[N];
int dfs(int u) {
    int sz=G[u].size();
    for(int i=0;i<sz;++i) {
        int v=G[u][i].fi;
        int ty=G[u][i].se;
        if(col[v]!=-1) {
            if(ty&&col[v]!=col[u]) return ans=-1;
            if(!ty&&col[v]!=1-col[u]) return ans=-1;
        } else {
            if(ty) col[v]=col[u];
            else col[v]=1-col[u];
            dfs(v);
        }
    }
    return 1;
}
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        ///
        int n,m;scanf("%d%d",&n,&m);
        ///init
        for(int i=1;i<=n;++i) G[i].clear();
        memset(col,-1,sizeof(col));
        ans=0;col[1]=0;
        ///read
        for(int i=1;i<=m;++i) {
            int u,v;char c;
            scanf("%d%d %c",&u,&v,&c);
            G[u].pb(mp(v,c=='R'));
            G[v].pb(mp(u,c=='R'));
        }
        ///solve
        dfs(1);
        if(ans==-1) puts("-1");
        else {
            for(int i=1;i<=n;++i) ans=ans+col[i];
            printf("%d\n",min(ans,n-ans));
        }
    }
    return 0;
}

G. HIT 3214 Greedy Game

题意

题解

• 排序（A数组大到小，B数组大到小），先手肯定从左往右取。
• 问题就变成：对于一个数组，先手肯定每次取最左边的，后手要如何取才能让取出来的和最大？
• 先手肯定取第一个数，那么从第二个数开始，后手都是“先手”。
• 那么后手只要先取当前的，轮到先手取的时候，如果后手取的最小的数x比当前数小y，就对换x,y。

代码

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1005;
struct Node {
    int x,y;
    bool operator < (const Node &tmp) const {
        if(x==tmp.x) return y>tmp.y;
        return x>tmp.x;
    }
}a[N];
priority_queue<int> q;
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        ///
        int n;scanf("%d",&n);
        ///init
        int tt=q.size();
        while(tt--) q.pop();
        ///read
        for(int i=1;i<=n;++i) scanf("%d",&a[i].x);
        for(int i=1;i<=n;++i) scanf("%d",&a[i].y);
        ///sort
        sort(a+1,a+1+n);
        ///solve
        for(int i=2;i<=n;++i) {
            if(i&1) {
                if(a[i].y>-q.top()) {
                    q.pop();
                    q.push(-a[i].y);
                }
            } else {
                q.push(-a[i].y);
            }
        }
        ///print
        ll ans=0;
        while(!q.empty()) {
            ans=ans-q.top();
            q.pop();
        }
        printf("%lld\n",ans);
    }
    return 0;
}

J. HIT 3207 GiriGiri Eye~（概率论）

题意

题解

• 期望的和等于和的期望。
• 求总的期望-->求单个期望-->求单个概率
• -->求亮一次的概率-->如果最后亮，肯定亮了偶数次-->写出来之后用二项式定理化简

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define de(x) cout << #x << "=" << x << endl
double kpow(double a,ll b) {
    double r=1;
    while(b) {
        if(b&1) r=r*a;
        a=a*a;
        b>>=1;
    }
    return r;
}
int main() {
    //freopen("xx.out","w",stdout);
    int T;scanf("%d",&T);
    while(T--) {
        int n,m;scanf("%d%d",&n,&m);
        double ans=0;
        for(int i=1;i<=n;++i) {
            double p=1-(1.0*(i-1)*(i-1)+1.0*(n-i)*(n-i))/n/n;
            ans=ans+(1+kpow(1-2*p,m))/2;
        }
        printf("%.3lf",ans);
        if(T) puts("");
    }
    return 0;
}