11.1 NOIP 模拟赛
期望得分：50；实际得分：50；
思路：暴力枚举 + 快速幂
#include <algorithm> #include <cstring> #include <cstdio> using namespace std; typedef long long LL; const int Mod = 1e9 + 7; int n, m; LL ans; LL qpow(LL a, LL b) { LL res = 1; while (b) { if (b & 1) res = res * a % Mod; a = a * a % Mod; b >>= 1; } return res; } int main() { freopen("sum.in","r",stdin); freopen("sum.out","w",stdout); scanf("%d%d", &n, &m); ans += m; for (int i = 2; i <= n; ++i) { ans += i; for (int j = 2; j <= m; ++j) { ans = ans + qpow(i, j); if (ans >= Mod) ans -= Mod; } } printf("%lld\n", ans); fclose(stdin); fclose(stdout); return 0; }
正解：等比数列求和公式
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> typedef long long i64; const i64 modulo = i64(1e9) + 7; int n, m; i64 power(i64 base, i64 k) { i64 res = 1; for ( ; k; k >>= 1) { if (k & 1) res = (res * base) % modulo; base = (base * base) % modulo; } return res; } i64 inv(i64 k) { return power(k, modulo - 2); } int main(void) { freopen("sum.in","r",stdin); freopen("sum.out","w",stdout); scanf("%d%d", &n, &m); i64 ans = m; for (int i = 2; i <= n; ++i) { i64 t = i; t = t * ((power(i, m) - 1 + modulo) % modulo) % modulo; t = t * inv(i - 1) % modulo; ans = (ans + t) % modulo; } printf("%d\n", (int) ans); fclose(stdin); fclose(stdout); return 0; }
期望得分：100；实际得分：100；
思路：输入时统计边权和，用边权和的两倍减去距 1 号点最远点的距离，即为最后答案
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <deque> using namespace std; const int INF = 0x3f3f3f3f; const int M = 50005; int ans; int n, m, tot; int dis[M], vis[M]; int to[M*2], net[M*2], head[M], cap[M*2]; void add(int u, int v, int w) { to[++tot] = v; net[tot] = head[u]; head[u] = tot; cap[tot] = w; to[++tot] = u; net[tot] = head[v]; head[v] = tot; cap[tot] = w; } deque<int> Q; void spfa(int x) { for (int i = 1; i <= n; ++i) vis[i] = 0, dis[i] = INF; vis[x] = 1; dis[x] = 0; Q.push_back(x); while (!Q.empty()) { int y = Q.front(); Q.pop_front(); vis[y] = 0; for (int i = head[y]; i; i = net[i]) { int t = to[i]; if (dis[t] > dis[y] + cap[i]) { dis[t] = dis[y] + cap[i]; if (!vis[t]) { vis[t] = 1; if (Q.empty() || dis[t] > dis[Q.front()]) Q.push_back(t); else Q.push_front(t); } } } } } int main() { freopen("tour.in","r",stdin); freopen("tour.out","w",stdout); scanf("%d", &n); for (int i = 1; i < n; ++i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); add(u, v, w); ans += w * 2; } spfa(1); int maxn = 0; for (int i = 1; i <= n; ++i) maxn = max(maxn, dis[i]); printf("%d\n", ans - maxn); fclose(stdin); fclose(stdout); return 0; }
好像还可以用树形DP做 qwq
放上学姐的代码 Orz
#include<cmath> #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 50010 using namespace std; int n,tot; int dad[MAXN],sum[MAXN],bns[MAXN],size[MAXN],dp[MAXN]; int to[MAXN*2],cap[MAXN*2],net[MAXN*2],head[MAXN]; int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void add(int u,int v,int w){ to[++tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot; } void dfs(int now){ size[now]=1; for(int i=head[now];i;i=net[i]) if(dad[now]!=to[i]){ dad[to[i]]=now; dfs(to[i]); sum[now]+=sum[to[i]]+cap[i]; size[now]+=size[to[i]]; } } void pre(int now){ if(size[now]==1) dp[now]=0; for(int i=head[now];i;i=net[i]) if(dad[now]!=to[i]) pre(to[i]); } void work(int now){ int x; for(int i=head[now];i;i=net[i]) if(dad[now]!=to[i]){ work(to[i]); dp[now]=min(dp[to[i]]+cap[i]+(sum[now]-sum[to[i]]-cap[i])*2,dp[now]); } } int main(){ //freopen("lpp.in","r",stdin); freopen("tour.in","r",stdin); freopen("tour.out","w",stdout); n=read(); for(int i=1;i<n;i++){ int u=read(); int v=read(); int w=read(); add(u,v,w);add(v,u,w); } memset(dp,0x7f,sizeof(dp)); dfs(1); pre(1); work(1); cout<<dp[1]; }
期望得分：0。。。实际么。。。没有分 qwq
思路：暴力搜索，枚举每一个长度等于 K 的子序列并进行判断
然后。。。没调出来，就gg了。。
#include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int M = 100005; int ans = 1; int n, k; int a[M]; void dfs(int now, int tmp, int t1, int t2) { if (a[now] == 4 && t1 == 1) return ; else if (a[now] == 7 && t2 == 1) return ; if (tmp == k) { ++ans; return ; } if (a[now] == 4) dfs(now + 1, tmp + 1, t1 + 1, t2); else if (a[now] == 7) dfs(now + 1, tmp + 1, t1, t2 + 1); else dfs(now + 1, tmp + 1, t1, t2); } int main() { freopen("lucky.in","r",stdin); freopen("lucky.out","w",stdout); scanf("%d%d", &n, &k); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } for (int i = 1; i <= n - k + 1; ++i) { if (a[i] == 4) dfs(i, 1, 1, 0); else if (a[i] == 7) dfs(i, 1, 0, 1); else dfs(i, 1, 0, 0); } printf("%d\n", ans); fclose(stdin); fclose(stdout); return 0; }
正解：DP + 组合数
#include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <iostream> #include <vector> #include <map> using std::min; using std::max; typedef long long i64; const i64 modulo = i64(1e9) + 7; const int MaxN = 100005; const int MaxM = 1024; i64 power(i64 base, i64 k) { i64 res = 1; for ( ; k; k >>= 1) { if (k & 1) res = (res * base) % modulo; base = (base * base) % modulo; } return res; } i64 inv(i64 k) { return power(k, modulo - 2); } std::vector<i64> gen_lucky(i64 upper) { std::vector<i64> res; res.clear(); std::vector<i64> a; a.clear(); a.push_back(0); for (int i = 0; i < 10; ++i) { std::vector<i64> b; b.clear(); for (size_t j = 0; j < a.size(); ++j) { b.push_back(a[j] * 10 + 4); b.push_back(a[j] * 10 + 7); } if (b[0] < upper) { res.insert(res.end(), b.begin(), b.end()); a = b; } else { return res; } } return res; } std::vector<i64> lucky; std::map<i64, int> lucky2idx; int n, m, unlucky, k, a[MaxN], cnt[MaxM]; i64 dp[MaxM][MaxM]; i64 f[MaxN]; i64 bincoef(int a, int b) { i64 tmp = f[a]; tmp = tmp * inv(f[b]) % modulo; tmp = tmp * inv(f[a-b]) % modulo; return tmp; } int main(void) { freopen("lucky.in","r",stdin); freopen("lucky.out","w",stdout); lucky = gen_lucky(1e9); m = lucky.size(); for (int i = 0; i < m; ++i) { lucky2idx[lucky[i]] = i; } scanf("%d%d", &n, &k); unlucky = n; for (int i = 0; i < n; ++i) { scanf("%d", a+i); std::map<i64, int>::iterator it = lucky2idx.find(a[i]); if (it != lucky2idx.end()) ++cnt[it->second], --unlucky; } dp[0][0] = 1; for (int i = 0; i < m; ++i) { for (int j = 0; j <= i; ++j) { dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % modulo; dp[i+1][j+1] += (dp[i+1][j+1] + (dp[i][j] * cnt[i] % modulo)) % modulo; } } f[0] = 1; for (int i = 1; i <= n; ++i) { f[i] = f[i-1] * i % modulo; } i64 ans = 0; int st = max(0, k-m); int ed = min(k, unlucky); for (int i = st; i <= ed; ++i) { ans += dp[m][k-i] * bincoef(unlucky, i) % modulo; ans %= modulo; } printf("%d\n", (int) ans); fclose(stdin); fclose(stdout); return 0; }