今天考试了, 考了好几道题
依次为:
矩阵乘法
代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 502, mod = 1e9+7;
int n, p, m;
int f1[N][N], f2[N][N];
int f3[N][N];
inline int work (int x, int y) {
int res = 0;
for (int i = 1; i <= p; ++ i) {
res += (f1[x][i]*f2[i][y])%mod;
res %= mod;
}
if (res >= 0) return res%mod;
if (res < 0) return (res+mod)%mod;
}
main () {
cin >> n >> p >> m;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= p; ++ j)
cin >> f1[i][j];
for (int i = 1; i <= p; ++ i)
for (int j = 1; j <= m; ++ j)
cin >> f2[i][j];
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j)
f3[i][j] = work(i, j);
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j)
cout << f3[i][j] << ' ';
cout << '
';
}
return 0;
}
其实这个题特别水，就是没有学过矩阵乘法的人都能做对
说白了就是个模拟，需要注意(long long)，还有(res)要边算边模，并且还要判负数
但是我考试的时候，没开(longlong), (res)没有中途取模
就是(zero)了....
大炮
代码:
#include <bits/stdc++.h>
#define int long long
#define mod 2333
using namespace std;
const int N = 6e6;
int n, k, T;
int js[N];
inline int ksm (int a, int b) {
if (b == 0) return 1%mod;
if (b&1) return a*ksm(a, b-1)%mod;
int tmp = ksm(a, b/2)%mod;
return tmp*tmp%mod;
}
inline int C (int n, int m) {
if (m > n) return 0;
return (js[n]*ksm(js[m],mod-2))%mod*ksm(js[n-m], mod-2)%mod;
}
inline int lucas (int n, int m) {
if (!m) return 1;
return C (n%mod, m%mod)*lucas(n/mod, m/mod)%mod;
}
inline int calc(int n, int k) {
int res = 0, t = 0;
for (int i = 0; i <= k; ++i) {
t = lucas(n, i)%mod;
res += t;
res %= mod;
}
return res%mod;
}
signed main() {
cin >> T;
while (T-- > 0) {
cin >> n >> k;
js[0] = 1;
for (int i = 1; i <= mod; ++i)
js[i] = (js[i - 1] * i) % mod;
cout << calc(n, k) << '
';
}
return 0;
}
这就是一个**数学题，要推式子，但是我不会，看出来是个Lucas但是不会写
这个数据比较**正好卡我百分之五十的数据，也就是说，不动脑子，敲Lucas板子的话，可以拿到百分之五十的数据
但是我就是不会推 也不想去推
这种操蛋数学题，正如郑好学长所言，爱练不练的，考的几率没准，简单的大家都会，难的大家都不会
第三题
(Description)
桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。
(Input)
一行输入两个数R,B,其值在0到5000之间
(Output)
在最优策略下平均能得到多少钱
(Sample) (Input)
5 1
(Sample) (Output)
4.166666
(HINT)
输出答案时,小数点后第六位后的全部去掉,不要四舍五入.
代码:
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
const int N = 1e5+66;
double R, B, res;
long long nows;
double f[6][6666];
int main() {
cin >> R >> B;
for (int i = 0; i <= R; ++ i, nows ^=1, f[nows][0] = i)
for (int j = 1; j <= B; ++ j)
f[nows][j] = max(0*1.0,
1.0 * i/(i + j)*(f[nows ^ 1][j]+1)
+ 1.0 * j/(i + j)*(f[nows][j - 1]-1));
res = f[nows^1][(int)B];
long long z = res*10000000;
long long k = z%10;
z -= k;
double ans = (double)z/10000000;
printf ("%.6lf", ans);
return 0;
}
这是一道期望dp
(f[i][j])表示选(i)张红的(j)张黑色的答案
卡内存所以需要滚动数组
(f[i][j]) = (max)((0,dfrac{i}{i*j}*(f[i-1][j]+1)+dfrac{j}{i*j}*(f[i][j-1]-1)))
奶牛去搬砖
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+66, INF = 214748364;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
struct edge {int to, nxt, val;}e[N]; int cnt, head[N];
int n, S, E;
int dis[N], tag[N];
inline void add (int u, int v, int w) {
e[++cnt].nxt = head[u]; head[u] = cnt;
e[cnt].to = v;
e[cnt].val = w;
}
inline void dij () {
for (int i = S; i <= E+6; ++ i) dis[i] = INF;
dis[S] = 0, q.push(make_pair(0, S));
while (q.size()) {
int x = q.top().second; q.pop();
if (tag[x]) continue; tag[x] = 1;
for (int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to;
if (dis[y] > dis[x]+e[i].val){
dis[y] = dis[x]+e[i].val, dis[y];
q.push(make_pair(dis[y], y));
}
}
}
}
int main () {
cin >> n >> S >> E;
for (int i = S; i <= E; ++ i) add(i+1, i, 0);
for (int i = 1; i <= n; ++ i) {
int u, v, w;
cin >> u >> v >> w;
if (u < S) u = S;
if (v > E) v = E;
add(u, v+1, w);
}
dij();
if (dis[E+1] == INF) puts ("-1");
else cout << dis[E+1];
return 0;
}
建个图，跑一跑，完事。可是考试时候的我，连题目都没看懂什么意思（英文题面， 教练给翻译了，但是感觉那个翻译看起来很不爽，索性没有做）
但是这个题真的很简单，就是需要一步很巧妙的回退思想
(add(i+1, i, 0)):建一条权值为零的回退的边
1 3
4 5
虽然没有交集，但是上述情况是可以满足题意的
所以建边的时候要(add(u,v+1,w))
单位错选
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7+10;
int n, A, B, C, tmp;
int a[N];
double res;
int main () {
scanf("%d%d%d%d%d", &n, &A, &B, &C, a + 1);
for (int i = 2; i <= n; i++)
a[i] = ((long long) a[i - 1] * A + B) % 100000001;
for (int i = 1; i <= n; i++)
a[i] = a[i] % C + 1;
res += 1.0*min(a[1], a[n])/a[1]/a[n];
for (int i = 1; i < n; ++ i) res += 1.0*min(a[i], a[i + 1])/a[i]/a[i + 1];
printf ("%.3lf", res);
return 0;
}
假设第(i)个题目的选项数是(a[i]),那么(gx)做对这道题目的概率就是(dfrac{min(a[i],a[i-1])}{a[i]*a[j]})
(i == 1)的时候特判 然后把每个题做对的概率加起来就好了
其实说实话，我还是感觉不太理解 也说不出来哪里不明白
可能是初次接触概率的题吧，这是个锅，以后得补上
互相伤害
#include <bits/stdc++.h>
using namespace std;
const int N = 666;
int n, k;
long long f[10][N][N], res;
inline int self (int x) {
if ((x&(x<<1)) || (x&(x>>1))) return false;
return true;
}
inline int Double (int x, int y) {
if ((x&(y<<1)) || (x&(y>>1) || (x&y))) return false;
return true;
}
inline int work (int x) {
int nows(0);
while (x) {if (x&1) ++ nows; x >>= 1;}
return nows;
}
signed main () {
scanf ("%d%d", &n, &k);
f[0][0][0] = 1;
for (int i = 1; i <= n; ++ i) {
for (int j = 0; j < (1<<n); ++ j) {
if (self (j)) {
for (int z = 0; z < (1<<n); ++ z) {
if (self(z) && Double(z, j)) {
for (int len = 0; len <= k; ++ len) {
int nx = work(j), ny = work(z);
if (nx+ny>len) continue;
f[i][j][len] += f[i-1][z][len-nx];
}
}
}
}
}
}
for (int i = 0; i < (1<<n); ++ i) res += f[n][i][k];
cout << res;
return 0;
}
状压dp
(f[i][j][k])表示我们当前摆放棋子摆到了第(i)行的时候（包括前(i)行）当前第(i)行的状态为(j)，并且一共用了(k)个国王所呈现出的方案数
又因为i行之前的状态方案数都是互不影响的，所以说，是“或”的关系，根据加法原理，可以直接相加
所以转移方程可以写出来:
(f[i][j][k] += f[i-1][z][k-Work(j)])
自此所有题目分析完毕
(7.28update)
关于第二题大炮，看了看题解，还是不会推
给出ac代码
// da pao
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e3, p = 2333;
int n, m, T;
int c[N][N], f[N][N];
inline int Lucas (int n, int m) {
if (!m || n == m) return 1;
if (n < m) return 0;
return Lucas(n/p, m/p)*c[n%p][m%p]%p;
}
inline int calc (int n, int m) {
if (m == -1) return 0;
if (!m) return 1;
if (n < p) return f[n][m];
return (f[n%p][n%p]*calc(n/p,m/p-1)+Lucas(n/p,m/p)*f[n%p][min(n%p, m%p)])%p;
}
inline void yuchuli() {
c[0][0] = f[0][0] = 1;
for (int i = 1; i <= p; ++ i) {
f[i][0] = c[i][0] = c[i][i] = 1;
for (int j = 1; j <= i-1; ++ j)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1])%p;
for (int j = 1; j <= p; ++ j)
f[i][j] = (f[i][j - 1] + c[i][j])%p;
}
}
inline void caozuoyixia () {
scanf ("%lld%lld", &n, &m);
cout << calc(n, m) << '
';
}
signed main () {
yuchuli();
cin >> T;
while (T --> 0) caozuoyixia();
return 0;
}