2019.11.09考试解题报告
总结
期望得分：(100+ 30 + 40 = 170)
实际得分：(100 + 50 + 40 = 190)
简单记录一下
思路&&代码
T1
(n^2算法)
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 1e5 + 11;
const int B = 1e6 + 11;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
int n, m, all, cnt;
int d[A], w[A], a[A], la[A];
inline bool check(int x) {
memset(la, 0, sizeof(la));
for(int i = 1; i <= n; i++) a[i] = d[i];
for(int i = 1; i <= x; i++) if(a[i]) a[la[a[i]]] = 0, la[a[i]] = i;
int tl = 0, cnt = 0;
for(int i = 1; i <= x; i++) {
if(a[i]) { tl -= w[a[i]]; if(tl < 0) return 0; else cnt++; }
else tl++;
}
return cnt == m;
}
int main() {
freopen("generals.in", "r", stdin);
freopen("generals.out", "w", stdout);
n = read(), m = read();
if(n < m) return puts("-1"), 0;
for(int i = 1; i <= n; i++) d[i] = read();
for(int i = 1; i <= m; i++) w[i] = read(), all += w[i];
if(all > n) return puts("-1"), 0;
int l = 0, r = n, ans = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
return cout << ans << '
', 0;
}
*/
T2
找规律
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int A = 1e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
int n, m, a[A], k, ans = 0, pd[A];
int power(int a, int b, int res = 1) {
if(a == 0 && b == 0) return 1;
while(b) {
if(b & 1) res = res * a % mod;
a = a * a % mod; b >>= 1;
} return res;
}
int an[100][100];
signed main() {
freopen("transfer.in", "r", stdin);
freopen("transfer.out", "w", stdout);
an[1][1] = 1;
an[2][1] = 1,an[2][2] = 2;
an[3][1] = 4,an[3][2] = 2,an[3][3] = 9;
an[4][1] = 27,an[4][2] = 8,an[4][3] = 9,an[4][4] = 64;
an[5][1] = 256,an[5][2] = 54,an[5][3] = 36,an[5][4] = 64,an[5][5] = 625;
an[6][1] = 3125,an[6][2] = 512,an[6][3] = 243,an[6][4] = 256,an[6][5] = 625,an[6][6] = 7776;
an[7][1] = 46656,an[7][2] = 625,an[7][3] = 2304,an[7][4] = 1728,an[7][5] = 2500,an[7][6] = 7776,an[7][7] = 117649;
int T = read();
while(T--) {
n = read(), k = read();
if(k == n) {
int now = power(n, n - 1) % mod;
now = (now % mod + mod) % mod;
cout << now << '
';
continue;
} else if(k == 1) {
int now = power(n - 1, n - 1) % mod;
now = (now % mod + mod) % mod;
cout << now << '
';
continue;
} else if(n <= 7) {
cout << an[n][k] % mod << '
';
continue;
} else {
int oo = power(n - k, n - k) % mod * power(k, k - 1);
oo = (oo % mod + mod) % mod;
cout << oo << '
';
continue;
}
}
return 0;
}
T3
树形(DP)预处理，然后伪(O(1))查询（快速幂呀~~）
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int A = 2e5 + 11;
const int B = 2e3 + 11;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
int n, m, ans;
struct node { int to, nxt, val; } e[A << 1];
int head[A], cnt, dis[B][B], o[A][2];
inline void add(int from, int to, int val) {
e[++cnt].to = to;
e[cnt].nxt = head[from];
e[cnt].val = val;
head[from] = cnt;
}
int power(int a, int b, int res = 1) {
while(b) {
if(b & 1) res = res * a % mod;
a = a * a % mod; b >>= 1;
} return res;
}
int tot[A][2], siz[A][2], f[A][2];
void dfs1(int now, int fa, int ww) {
f[1][ww & 1] += ww, f[1][ww & 1] %= mod;
tot[1][ww & 1]++;
siz[now][0] = 1;
for(int i = head[now]; i; i = e[i].nxt) {
int to = e[i].to;
if(to == fa) continue;
dfs1(to, now, ww + e[i].val);
if(e[i].val & 1) siz[now][0] += siz[to][1], siz[now][1] += siz[to][0];
else siz[now][0] += siz[to][0], siz[now][1] += siz[to][1];
}
}
void dfs2(int now, int fa) {
for(int i = head[now]; i; i = e[i].nxt) {
int to = e[i].to;
if(to == fa) continue;
if(e[i].val & 1) {
tot[to][0] = tot[now][1], tot[to][1] = tot[now][0];
f[to][1] = (((f[now][0] % mod + e[i].val * (tot[to][1] - 2 * siz[to][1]) % mod) % mod) % mod) % mod;
f[to][0] = (((f[now][1] % mod + e[i].val * (tot[to][0] - 2 * siz[to][0]) % mod) % mod) % mod) % mod;
} else {
tot[to][0] = tot[now][0], tot[to][1] = tot[now][1];
f[to][1] = (((f[now][1] % mod + e[i].val * (tot[to][1] - 2 * siz[to][1]) % mod) % mod) % mod) % mod;
f[to][0] = (((f[now][0] % mod + e[i].val * (tot[to][0] - 2 * siz[to][0]) % mod) % mod) % mod) % mod;
}
dfs2(to, now);
}
}
signed main() {
freopen("meet2.in", "r", stdin);
freopen("meet.out", "w", stdout);
n = read(), m = read();
for(int i = 1, u, v, w; i < n; i++) {
u = read(), v = read(), w = read();
add(u, v, w), add(v, u, w);
}
dfs1(1, 0, 0), dfs2(1, 0);
while(m--) {
int x = read(), y = read();
int qwq = f[x][y] % mod * power(tot[x][y], mod - 2) % mod;
qwq = (qwq % mod + mod) % mod; cout << qwq << '
';
}
return 0;
}