[20181105][模拟赛]

题面

T1

思路

把题目读错了。P[i][j]单调不升我看成单调上升了23333

然后正解是忽略上面这句话？然后我就A了？？？

用f[i][j]表示前i场赢了j场的概率，那么将当前这一场赢或输分类dp就好了。

代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1010;
ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
double P[N][N],f[N][N];
int main() {
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    int n = read();
    for(int i = 1;i <= n;++i)
        for(int j = 0;j < i; ++j)
            scanf("%lf",&P[i][j]);
    f[0][0] = 1;
    for(int i = 1;i <= n;++i) {
        for(int j = 0;j <= i;++j) {
            if(j >= 1)
            f[i][j] += f[i-1][j-1] * P[i][j-1];
            if(j < i)
            f[i][j] += f[i-1][j] * (1-P[i][j]);
        }
    }
    double ans = 0;
    for(int i = 0;i <= n;++i)
        ans += f[n][i] * (double)i;
    printf("%.2lf",ans);
    return 0;
}
/*
2 
0.5 
0.5 0.5
*/

T2

思路

meet in the middle + 二分

先正着搜一半，将所有能够构成的价格存到一个数组里。然后排个序，再倒着搜一半。搜完之后二分一下剩下的价格找个最优值就好了。

代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 50;
ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
ll a[N];
ll tmp[2000000 + 100];
int n,tot;
ll W;
ll ans;
void dfs1(int pos,ll now) {
    if(now > W) return;
    if(pos > n / 2) {
        tmp[++tot] = now;
        return;
    }
    dfs1(pos + 1,a[pos] + now);
    dfs1(pos + 1,now);
}
ll erfen(int x) {
    int l = 1,r = tot;
    ll re = 0;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(tmp[mid] <= x) re = tmp[mid],l = mid + 1;
        else r = mid - 1;
    }
    return re;
}
void dfs2(int pos,ll now) {
    if(now > W) return;
    if(pos <= n / 2) {
        ll x = W - now;
        ans = min(ans,x - erfen(x));
        return;
    }
    dfs2(pos - 1,now + a[pos]);
    dfs2(pos - 1,now);
}
int main() {
    freopen("cake.in","r",stdin);
    freopen("cake.out","w",stdout);
    n = read(),W = read();
    ans = W;
    for(int i = 1;i <= n;++i) a[i] = read();
    dfs1(1,0);
    sort(tmp + 1,tmp + tot + 1);
    dfs2(n,0);
    cout<<ans;
    return 0;
}
/*
4 50
1 2 3 4

4 5
1 2 3 4
*/

T3

20分思路

对于前20分。直接枚举所有情况，然后暴力判断即可

30分思路

对于n=0的情况，显然每个点都有m种取值,输出\(m^{(h*w)}\)就行了

50分思路

当n=1的时候，考虑给出的这个矩形中的点的最大值必须是w，所以用全部情况减去不满的情况即可。全部情况是\(w^{siz}\),siz是这个矩形的大小，满足的情况就是这个矩形中所有值都比w小。所以这个矩形内部的情况就有\(w^{siz}-(w-1)^{siz}\)。然后再考虑矩形外部的情况。矩形外部当然还和上面一样，每个点都有m种取值，所以情况数量就是\(m^{h*w-siz}\)将这个两者乘起来就行了。

100分思路

我也不知道为什么我的错误代码也a了2333。RP--。

代码(下方高能，慎看！！)

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<map>
#include<ctime>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 10010,mod = 1e9 + 7;
map<int,int>Max,May;
ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int h,w,n,m;
struct node {
    int x_1,x_2,y_1,y_2,w,siz;
    node() {
        siz = 0;
    }
}Q[N];
ll qm(ll x,int y) {
    if(x == 0) return 0;
    ll ans = 1;
    for(;y;y >>=1 ,x = x * x % mod) 
        if(y & 1) ans = ans * x % mod;
    return ans;
}

namespace BF1 {
    int a[10][10];
    ll ans = 0;
    void check() {
        for(int i = 1;i <= n;++i) {
            int Max = -1;
            int X1 = Q[i].x_1,X2 = Q[i].x_2,Y1 = Q[i].y_1,Y2 = Q[i].y_2;
            for(int j = 1;j <= h;++j) {
                for(int k = 1;k <= w;++k) {
                    if(j >= X1 && j <= X2 && k >= Y1 && k <= Y2) {
                        Max = max(Max,a[j][k]);
                    }
                }
            }
            if(Max != Q[i].w) return;
        }
        ans++;
    }
    void dfs(int x,int y) {
        if(x > h) {
            check();
            return;
        }
        for(int i = 1;i <= m;++i) {
            a[x][y] = i;
            if(y == w) dfs(x + 1,1);
            else dfs(x,y+1);
        }
    }
    void Main() {
        for(int i = 1;i <= n; ++i) {
            Q[i].x_1 = read(),Q[i].y_1 = read(),Q[i].x_2 = read(),Q[i].y_2 = read(),Q[i].w = read();
        }
        dfs(1,1);
        cout<<ans;
    }       
}
namespace BF2 {
    
    void Main() {
        for(int i = 1;i <= n; ++i) {
            Q[i].x_1 = read(),Q[i].y_1 = read(),Q[i].x_2 = read(),Q[i].y_2 = read(),Q[i].w = read();
        }
        ll siz = (Q[1].x_2 - Q[1].x_1 + 1) * (Q[1].y_2 - Q[1].y_1 + 1);
        ll ans = 0;
        ans = (qm(Q[1].w,siz) - qm(Q[1].w - 1,siz) + mod) % mod;
        cout<<ans * qm(m,h * w - siz) % mod;
        return;
    }
}
namespace BF3 {
    int Wx[N * 10],Wy[N * 10],xjs = 0,yjs = 0,tmpx[N * 10],tmpy[N * 10];
    int NEWH = 0,NEWW = 0;
    ll SIZ;
    void init() {
        for(int i = 1;i <= n;++i) {
            Q[i].x_1 = tmpx[++xjs] = read();Q[i].y_1 = tmpy[++yjs] = read();
            Q[i].x_2 = tmpx[++xjs] = read();Q[i].y_2 = tmpy[++yjs] = read();
            Q[i].w = read();
            tmpx[++xjs] = Q[i].x_1 - 1;
            tmpy[++yjs] = Q[i].y_1 - 1;
        }
        tmpx[++xjs] = 1,tmpx[++xjs] = h;
        tmpy[++yjs] = 1,tmpy[++yjs] = w;
    }
    void lisan() {
        sort(tmpx + 1,tmpx + xjs + 1);
        sort(tmpy + 1,tmpy + yjs + 1);
        int now = 0;
        for(int i = 1;i <= xjs;++i) {
            if(tmpx[i] == tmpx[i - 1]) continue;
             Max[tmpx[i]] = ++now;
             Wx[now] = tmpx[i] - tmpx[i - 1]; 
        }
        now = 0;
        for(int i = 1; i <= yjs; ++i) {
            if(tmpy[i] == tmpy[i - 1]) continue;
            May[tmpy[i]] = ++now;
            Wy[now] = tmpy[i] - tmpy[i-1];
        }
        for(int i = 1;i <= n;++i) {
            Q[i].x_1 = Max[Q[i].x_1];Q[i].x_2 = Max[Q[i].x_2];
            Q[i].y_1 = May[Q[i].y_1];Q[i].y_2 = May[Q[i].y_2];
        }
        NEWH = Max[h],NEWW = May[w];
    }
    ll calc(int x) {
        ll siz = Q[x].siz;
        ll re = (qm(Q[x].w,siz) - qm(Q[x].w - 1,siz) + mod) % mod;
        return re;
    }
    void solve() {
        for(int i = 1;i <= n;++i) {
            int X1 = Q[i].x_1,X2 = Q[i].x_2,Y1 = Q[i].y_1,Y2 =Q[i].y_2;
//          printf("%d %d %d %d\n",X1,Y1,X2,Y2);
            for(int j = 1;j <= NEWH; ++j) {
                if(j < X1 || j > X2) continue;
                for(int k = 1;k <= NEWW;++k) {
                    if(k < Y1 ||k > Y2) continue;
                    Q[i].siz += Wx[j] * Wy[k];
                    for(int z = 1; z <= n;++z) {
                        if(z==i) continue;
                        if(j >= Q[z].x_1 && j <= Q[z].x_2 && k >= Q[z].y_1 && k <= Q[z].y_2) {
                            if(Q[z].w > Q[i].w) continue;
                            if(Q[z].w == Q[i].w) {
                                if(z > i) {
                                    Q[i].siz -= Wx[j] * Wy[k];
                                    break;
                                }
                            }
                            if(Q[z].w < Q[i].w)  {
                            Q[i].siz -= Wx[j] * Wy[k];
                            break;
                        }
                        }
                    }
                }
            }
        }
        ll ans = 1;
        for(int i = 1;i <= n;++i) {
            SIZ -= Q[i].siz;
            ans *= calc(i);
            ans %= mod;
//          cerr<<Q[i].siz<<endl;
        }
//      cerr<<<<endl;
        ans *= qm(m,SIZ);
        ans %= mod;
        cout<<ans;
    }
    void Main() {
        SIZ = h * w;
        init();
        lisan();
//      for(int i = 1;i <= h;++i) {
//          printf("%d ",Wy[i]);
//      }
        solve();
    }
}
int main() {
    freopen("grid.in","r",stdin);
    freopen("grid.out","w",stdout);
    h = read(),w = read(),m = read(),n = read();
    if(n == 0) {
        cout<<qm(m,h * w);
        return 0;
    }
    if(h <= 3 && w <= 3) {
        BF1::Main();
        return 0;
    }
    if(n == 1) {
        BF2::Main();
        return 0;
    }
    BF3::Main();
    return 0;
}
/*
2 3 2 1
1 2 2 3 1
*/