Wannafly挑战赛3

A 珂朵莉

题意：

给你一个长 n 的序列，m 次查询

每次查询给一个 x，然后：

从序列的最左端 1 开始，每次随机的选择一个右端点 r，如果两个端点间的区间和不超过 x ，就进行一次分割，然后把左端点变成 r + 1，否则一直随机下去。

问这样分割出来的期望段数

tags：概率 dp

dp[i]表示第 i 个数到第 n 个数的期望段数，转移即： dp[i] = 1/len*(dp[i+1]+dp[i+2]+.....)， len表示相加在 x 范围内的长度。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi  first
#define se  second
typedef long long ll;
const int N = 200005;

int n, m, ma, a[N], x, r[N];
double dp[N], last[N];
int main()
{
    scanf("%d%d", &n, &m);
    ma = -1;
    rep(i,1,n)
        scanf("%d", &a[i]), ma=max(ma, a[i]);
    while(m--)
    {
        scanf("%d", &x);
        if(x < ma) { puts("YNOI is good OI!");  continue; }
        int i, j, l;
        ll  sum=0;
        for(i=1, j=1; i<=n && j<=n; ++i)
        {
            while(j<=n && sum+a[j]<=x)
                sum+=a[j], ++j;
            r[i] = j-1,  sum-=a[i];
        }
        for(l=i; l<=n; ++l) r[l]=n;
        dp[n]=1, last[n]=1;
        for(i=n-1, j=n; i>0; --i)
        {
            dp[i] = 1.0/(r[i]-i+1)*(last[i+1]-last[r[i]+2])+1;
            last[i] = dp[i]+last[i+1];
        }
        printf("%.2f
", dp[1]);
    }

    return 0;
}

View Code

B 遇见

水题

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi  first
#define se  second
typedef long long ll;
const int N = 800005;
 
int n, a[N];
double m, k;
int main()
{
    scanf("%d%lf%lf", &n, &m, &k);
    rep(i,1,n) scanf("%d", &a[i]);
    sort(a+1, a+1+n);
    printf("%d %d
", (int)ceil(1.0*k*36/10/(m+a[n])), (int)ceil(1.0*k*36/10/(m+a[1])));
 
    return 0;
}

View Code

C 位数差

题意：给一个数组{a}，定义 h(a,b)为在十进制下 a + b 与 a 的位数差，求，0的位数为1。

tags：树状数组

对于 a[i] ，只要找它后面有多少个数和它相加会在 10, 100..... 内的，稍变一下就是找后面有多少个数在 10-a[i], 100-a[i].....内的。这个只要离散一下，再树状数组即可实现。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi  first
#define se  second
typedef long long ll;
const int N = 200005;

int n, a[N], a2[N], cnt;
ll  ans, bit[N];
void Add(int x, int y)
{
    for(int i=x; i<N; i+=i&-i) bit[i]+=y;
}
void Init() {
    mes(bit, 0);
    ans = 0;
}
ll  query(int x)
{
    ll  ans1=0;
    for(int i=x; i>0; i-=i&-i) ans1+=bit[i];
    return ans1;
}
int get(ll x)
{
    if(x==0) return 1;
    else  return (int)log10(x)+1;
}
int main()
{
    Init();
    scanf("%d", &n);
    rep(i,1,n)
        scanf("%d", &a[i]), a2[i]=a[i];
    sort(a2+1, a2+1+n);
    cnt = unique(a2+1, a2+1+n) - (a2+1);
    rep(i,1,n) {
        int pos = lower_bound(a2+1, a2+1+cnt, a[i]) - a2;
        Add(pos, 1);
    }
    rep(i,1,n)
    {
        int pos = lower_bound(a2+1, a2+1+cnt, a[i]) - a2;
        Add(pos, -1);
        for(ll j=10; j<=1e8; j*=10)
            if(j>=a[i])
        {
            int p1=j-a[i], p2=j*10-a[i];
            int pos1 = lower_bound(a2+1, a2+1+cnt, p1) - a2;
            int pos2 = lower_bound(a2+1, a2+1+cnt, p2) - a2;
            --pos2;
            ans += (query(pos2)-query(pos1-1)) * (get(j)-get(a[i]));
        }
    }
    printf("%lld
", ans);

    return 0;
}

View Code

D Butterfly2

水题

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi  first
#define se  second
typedef long long ll;
const int N = 1005;

int n, m, ans, pre[N][N][2], pre1, pre2;
char G[N][N];
int main()
{
    scanf("%d%d", &n, &m);
    rep(i,1,n)  scanf("%s", G[i]+1);
    rep(j,1,m)
    {
        pre1=n+1, pre2=n+1;
        rep(i,1,n)
        {
            if(G[i][j]=='X') pre1=min(pre1, i), pre2=n+1;
            else pre1=n+1, pre2=min(pre2, i);
            pre[i][j][0] = pre1;
            pre[i][j][1] = pre2;
        }
    }
    rep(i,1,n) rep(j,1,m)
        if(G[i][j]=='X')
    {
        ans = max(ans, 1);
        int tmp = min(i-1, min(n-i, min(j-1, m-j)));
        rep(k,1,tmp)
        {
            if(G[i-k][j-k]=='X' && G[i+k][j-k]=='X' && G[i-k][j+k]=='O' && G[i+k][j+k]=='O')
            {
                if(pre[i+k][j-k][0]<=i-k && pre[i+k][j+k][1]<=i-k)
                    ans = max(ans, k*2+1);
            }
            else
                break;
        }
    }
    printf("%d
", ans);

    return 0;
}

View Code