7.21test

Posted on Edited on In

今天考试了, 考了好几道题 依次为:

矩阵乘法

代码: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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 << '\n';
   }
   return 0;
}
其实这个题特别水，就是没有学过矩阵乘法的人都能做对 说白了就是个模拟，需要注意\(long long\)，还有\(res\)要边算边模，并且还要判负数

但是我考试的时候，没开\(longlong\), \(res\)没有中途取模

就是\(zero\)了....

大炮

代码: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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) << '\n';
   }
   return 0;
}
这就是一个**数学题，要推式子，但是我不会，看出来是个Lucas但是不会写

这个数据比较**正好卡我百分之五十的数据，也就是说，不动脑子，敲Lucas板子的话，可以拿到百分之五十的数据

但是我就是不会推 也不想去推

这种操蛋数学题，正如郑好学长所言，爱练不练的，考的几率没准，简单的大家都会，难的大家都不会

第三题

\(Description\)

桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。

\(Input\)

一行输入两个数R,B,其值在0到5000之间

\(Output\)

在最优策略下平均能得到多少钱

\(Sample\) \(Input\)

5 1

\(Sample\) \(Output\)

4.166666

\(HINT\)

输出答案时,小数点后第六位后的全部去掉,不要四舍五入.

代码: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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))\)

奶牛去搬砖

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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)\)

单位错选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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\)的时候特判 然后把每个题做对的概率加起来就好了

其实说实话，我还是感觉不太理解 也说不出来哪里不明白

可能是初次接触概率的题吧，这是个锅，以后得补上

互相伤害

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 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) << '\n';
}	
	
signed main () {
   yuchuli();
   cin >> T;
   while (T --> 0) caozuoyixia();
   return 0;
}