c/c++语言开发共享11.1NOIP模拟赛解题报告

心路历程

预计得分：(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; }