[20181024][模拟赛]

T1

思路

只要会sort就能a

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100000 + 100;
typedef long long ll;
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 a[N],b[N];
bool cmp(int x,int y) {
    return x > y;
}
int main() {
    freopen("stone.in","r",stdin);
    freopen("stone.out","w",stdout);
    int T = read();
    while(T--) {
        int n = read(), m = read();
        for(int i = 1;i <= n;++i) a[i] = read();
        for(int i = 1;i <= m;++i) b[i] = read();
        ll ans = 0;
        sort(a+1,a+n+1,cmp);
        sort(b+1,b+m+1);
        int k = min(n,m);
        for(int i = 1;i <= k;++i) {
            int z = a[i] - b[i];
            if(z <= 0) break;
            ans = ans + z;
        }
        printf("%lld\n",ans); 
    }
    return 0;
}

T2

思路

据说标程是\(O(n^3)\)dp,然而我写了O(nlogk)的容斥。因为二进制的每一位是互不影响的,所以可以先考虑k = 1时的做法。考虑先不管行,只考虑每一列满足条件会有多少种情况。假设有m行,那么对于每一列都有\(2^n\)种情况,其中只有全都是0的一种情况是不满足条件的。所以每一列满足条件的情况数就是\(2^n-1\)。因为有m列,所以就是\((2^n-1)^m\)种情况。然后在考虑减去有某一行,某两行...某n行不满足条件的情况。自然就考虑到了容斥。
用f[i]表示只考虑i行m列的时候每一列都满足条件的情况数。怎么求上面已经说了。容斥式子就是\[\sum\limits_{i = 0}^n{f[i] * C_n^i * (-1)^i}\]

代码

#include<cstdio>
#include<iostream>
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;
const int N = 100;
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 ksm(ll x,ll 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;
}
ll C[N][N];
void pre() {
    C[0][0] = 1;
    for(int i = 1;i <= 60;++i) {
        C[i][0] = 1;
        for(int j = 1;j <= i;++j) {
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
        }
    }
}
ll n, m ,k;
ll f(ll x) {
    return ksm((ksm(2,x) - 1),m);
}
int main() {
    freopen("code.in","r",stdin);
    freopen("code.out","w",stdout);
    int T =  read();
    pre();
    while(T--) {
        n = read(),m = read(), k = read();
        if(n > m) swap(n,m);
        ll ans = 0;
        for(int i = 0;i <= n;++i) {
            ll b = 1;
            if(i & 1) b = -1;
            ans += (C[n][i] * f(n - i) * b % mod+ mod )% mod;
            ans >= mod ? ans -= mod:0;
        }
        printf("%lld\n",((ksm(ans,k)) % mod + mod ) % mod);
    }
    return 0;
}

T3

心路历程

为什么这个题没有思路而是心路历程?因为不会啊啊
真的不知道该怎么吐槽这个题了。先是发一个假的大样例,导致改暴力改了1h,然后说重新发样例,结果把第四个数据给发下来了。然后我并不知道这是数据。然后看见我的暴力re了。还以为要离散化。然后还是re,然后发现样例不是在暴力数据范围内的。然后删离散化,再给回去。然后就交卷了。fu*k。最后标程180行。90分的老哥写了230行。。。。。cnm

暴力代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
const int N = 100000 + 100;
typedef unsigned int lint;
lint read() {
    lint 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;
}
map<int,int>ma;
int a[700][700];
struct node {
    int x,y,w;
}e[700 * 700];
int ls[1000];
lint n ,m , q;
int main() {
    freopen("triangle.in","r",stdin);
    freopen("triangle.out","w",stdout);
    int T = read();
    while(T--) {
        n = read(), m = read(),q = read();
//      cout<<n<<endl;
            memset(a,0,sizeof(a));
            if(m < 3) { puts("0");continue;}
            int js = 0;
            while(q--) {
                int u = read(),v = read(),w = read();
                e[++js].x = u,e[js].y = v;e[js].w= w;
                ls[++ls[0]] = u;ls[++ls[0]] = v;
            }
            sort(ls+1,ls + ls[0] + 1);
            int now = 0;
            ma[ls[1]] = ++now;
            for(int i = 2;i <= ls[0];++i) {
                if(ls[i] != ls[i-1]) ma[ls[i]] = ++ now;
            }
            for(int i =1 ;i<= js;++i) {
                int x = ma[e[i].x],y = ma[e[i].y];
                a[x][y] = a[y][x] = e[i].w;
            }
            lint ans = 0;
            for(int i = 1;i <= n;++i) {
                for(int j = 1;j < i;++j) {
                    for(int k = 1;k < j;++k) {
                        if(((a[i][j] == a[i][k] || a[i][j] == a[j][k]) && a[i][j] != 0) || (a[j][k] == a[i][k] && a[j][k] != 0)) continue;
                        lint x = 3,y = 0;
                        if(a[i][j]) x--,y++;if(a[i][k]) x--,y++;if(a[j][k]) x--,y++;
                        lint t = 1;
                        lint mm = m - y;
                        for(int z = 0;z < x;++z) {
                            t *= (mm - z);
                        }
                        ans += t;
                    }
                }
            }
            cout<<ans<<endl;
    }
    return 0;
}

总结

期望得分:100 + 100 + 30 = 230
实际得分:100 + 100 + 30 = 230
前两个题写完的比较早,时间基本上都花在了t3上。然而t3还是只有30分。

一言

因为有了因为,所以有了所以。既然已成既然,何必再说何必。 ——因为

全部评论

相关推荐

不愿透露姓名的神秘牛友
11-26 18:54
说等下个版本吧的发呆爱好者很贪睡:佬最后去了哪家呀
点赞 评论 收藏
分享
贺兰星辰:不要漏个人信息,除了简历模板不太好以外你这个个人简介是不是太夸大了...
点赞 评论 收藏
分享
实习挂完提前批挂_提前批挂完秋招挂:我是来结束这个秋招的😤
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务