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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-11-01 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录