11.1NOIP模拟赛解题报告

来源：cnblogs　　作者：自为风月马前卒　　时间：2018/11/2 9:15:55　　对本文有异议

心路历程

预计得分：\(100 + 100 + 50\)

实际得分：\(100 + 100 + 50\)

感觉老师找的题有点水呀。

上来看T1，woc？裸的等比数列求和？然而我不会公式呀。。感觉要凉

T2应该比较简单，T3 dp能拿很多部分分。

但是T1只打暴力感觉好丢人啊。。想了10min发现不用公式也能做，就直接倍增一下就好了。

T2水题。感觉比T1还简单。。

T3。。。。。这个就比较厉害了呀。赛后我大概问了一下，发现全机房一共读出了\(4\)种题意Orzzz。

然后我花了\(2h\)做了一道水题。。然后发现错误的时候考试马上就结束了，然后只能打个暴力走人。。。

T1

Orz zbq现场推出等比数列求和公式

Orz 好像除了我都会等比数列求和公式

Orzzzzzzzzzzzzzzzzz

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<cmath>
#include<iostream>
using namespace std;
const int MAXN =1e5 + 10, mod = 1e9 + 7;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    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 add(int x, int y) {
    if(x + y < 0) return x + y + mod;
    return x + y >= mod ? x + y - mod : x + y;
}
int mul(int x, int y) {
    return 1ll * x * y % mod;
}
int fp(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = mul(base, a);
        a = mul(a, a); p >>= 1;
    }
    return base;
}
int N, M, pok[MAXN], g[MAXN];
int solve(int k, int n) {
    int len = 1;
    while((1ll << len) <= n) len <<= 1;
    pok[0] = k;
    for(int i = 1; i <= len; i++) pok[i] = mul(pok[i - 1], pok[i - 1]);
    g[0] = k;
    for(int i = 1; i <= len; i++) g[i] = add(g[i - 1], mul(g[i - 1], pok[i - 1]));
    int ans = 0, now = 0, base = 1;
    for(int i = len; i >= 0; i--) 
        if(now + (1 << i) <= n) 
            ans = add(ans, mul(g[i], base)), base = mul(base, pok[i]), now += (1 << i);
    return ans;
}
main() {
    freopen("sum.in", "r", stdin);
    freopen("sum.out", "w", stdout);
    N = read(); M = read();
    int ans = 0;
    for(int i = 1; i <= N; i++) {
        if(M & 1) ans = add(ans, add(solve(i, M - 1), fp(i, M)));
        else ans = add(ans, solve(i, M)); 
    //  cout << ans << endl;
    }
    cout << ans;
    return 0;
}

T2

\(ans = all - min(sum[i])\)

all表示所有边权和

\(sum[i]\)表示第\(i\)个节点到根的路径

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<cmath>
#include<iostream>
#define Pair pair<int, int>
#define MP make_pair
#define fi first
#define se second 
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e9 + 7;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    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 N, sum[MAXN], All;
vector<Pair> v[MAXN];
void dfs(int x, int fa) {
    for(int i = 0, to; i < v[x].size(); i++) {
        if((to = v[x][i].fi) == fa) continue;
        sum[to] = sum[x] + v[x][i].se;
        dfs(to, x);
    }
}
int main() {
    freopen("tour.in", "r", stdin);
    freopen("tour.out", "w", stdout);
    N = read();
    for(int i = 1; i <= N - 1; i++) {
        int x = read(), y = read(), z = read(); All += z; 
        v[x].push_back(MP(y, z));
        v[y].push_back(MP(x, z));
    }
    dfs(1, 0);
    All <<= 1;
    int ans = INF;
    for(int i = 1; i <= N; i++) ans = min(ans, All - sum[i]);
    cout << ans;
    return 0;
}

T3

神仙阅读理解题，不过还是挺interesting的

首先，序列内的元素是无序的，这样我们可以对相同的数字一起考虑

稍微想一下不难发现，幸运数字最多有\(2^9\)个

直接\(f[i][j]\)表示前\(i\)个数，选\(j\)的方案，dp一下

最后合并答案的时候背包一下

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<set>
#include<bitset>
#include<iostream>
#include<map>
#define Pair pair<int, int>
#define MP make_pair
#define fi first
#define se second 
//#define int long long 
using namespace std;
const int MAXN = 1e5 + 10, mod = 1e9 + 7;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    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 N, K, a[MAXN], tot, cnt, fac[MAXN], ifac[MAXN];
map<int, int> mp;
int add(int &x, int y) {
    if(x + y < 0) x = x + y + mod;
    else x = (x + y >= mod ? x + y - mod : x + y);
}
int add2(int x, int y) {
    if(x + y < 0) return x + y + mod;
    else return x + y >= mod ? x + y - mod : x + y;
}
int mul(int x, int y) {
    return 1ll * x * y % mod;
}
int fp(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = mul(base, a);
        a = mul(a, a); p >>= 1;
    }
    return base;
}
int C(int N, int M) {
    if(N < M) return 0;
    else return mul(fac[N], mul(ifac[M], ifac[N - M]));
}
int get(int x) {
    while(x) {
        if(x % 10 != 4 && x % 10 != 7) return 0;
        else x /= 10;
    }
    return 1;
}
map<int, Pair> id;
int rev[MAXN], f[2333][2333];
signed main() {
    freopen("lucky.in", "r", stdin);
    freopen("lucky.out", "w", stdout);
    N = read(); K = read();
    fac[0] = 1;
    for(int i = 1; i <= N; i++) fac[i] = mul(i, fac[i - 1]);
    ifac[N] = fp(fac[N], mod - 2);
    for(int i = N; i >= 1; i--) ifac[i - 1] = mul(ifac[i], i);
    
    for(int i = 1; i <= N; i++) {
        a[i] = read();
        if(get(a[i])) {
            if(!id[a[i]].fi) id[a[i]].fi = ++cnt, rev[cnt] = a[i];
            id[a[i]].se++;
        } else tot++;
    }
    f[0][0] = 1;
    for(int i = 1; i <= cnt; i++) {
        f[i][0] = 1;
        for(int j = 1; j <= cnt; j++) 
            f[i][j] = add2(f[i - 1][j], mul(f[i - 1][j - 1], id[rev[i]].se));       
    } 
    int ans = 0;
    for(int i = 0; i <= cnt; i++) add(ans, mul(f[cnt][i], C(tot, K - i)));
    cout << ans;
    
    return 0;
}