心路历程
预计得分:(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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/606490.html