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