首页 > 代码库 > 某deed笔试题

某deed笔试题

1.  删除ra,输入s,然后从前往后扫,遇到直接删除,O(n),算水题吧。

2. 矩阵乘法,看完题,感觉这么简单,估计有什么套路,仔细再读一遍,发现真是水题,50*50*50=125000,在2s时限内完全可以,而且数据范围很小,最大也是125000,不需要long long,直接写。

3. 读完题,看数据范围,maxn = 6, 6!=720, 然后是运算符的方式有2^5 = 32,然后总的复杂度为720 * 32 * 5 = 115200,这在1s的时限内完全可以,全排列可以用next_pemutation,运算符可以用二进制枚举,代码如下,(最后一个测试数据wa,我没找出来,后来换递归的ac了)。(找到错误了,比如 n = 1, k = 1, a1 = 10; 这里初始值应该设置为INT_MAX,结果才正确)。

 1 /* 2 ID: y1197771 3 PROG: test 4 LANG: C++ 5 */ 6 #include<bits/stdc++.h> 7 #define pb push_back 8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl10 typedef long long ll;11 using namespace std;12 typedef pair<int, int> pii;13 const int maxn = 1e3 + 10;14 int a[10];15 int n, k;16 void solve() {17     cin >> n >> k;18     for (int i = 0; i < n; i++) cin >> a[i];19     sort(a, a + n);20     int res = k;21     do {22         if(res == 0) break;23         for (int i = 0; i < (1 << n - 1); i++) {24             int s = a[0];25             for (int j = 0; j < n - 1; j++) {26                 if(i >> j & 1) {27                     s += a[j + 1];28                 } else {29                     s *= a[j + 1];30                 }31             }32             if(abs(s - k) < res) res = abs(s - k);33         }34     } while(next_permutation(a, a + n));35     cout << res << endl;36 }37 int main() {38     freopen("test.in", "r", stdin);39     //freopen("test.out", "w", stdout);40     solve();41     return 0;42 }

4. 先看懂题意,然后考虑怎么做,我没做出来!

分析:1. 考虑最后的结果不是1010就是0101,然后可以考虑从0000怎么转移过去,但是考虑n=1e5,数据范围发,状态数非常多,这种方法无法实现。

2. 考虑子问题性质,长问题是否可以转化为短问题。找一些短的小例子,划一下从0转移到结果的情况。然后就是动态规划dp,考虑长度dp[n],

3. dp[0] = 1, dp[1] = 1, dp[2] = 1, dp[3] = 5.0/3,dp[4] = 2.然后考虑5的时候怎么转移,枚举第一个涂的位置,下标从1-n,然后比如(10000,01000,00100,00010,00001),1代表涂黑,接下看怎么考虑,对于10000,10无法改变,只需计算000,右边的3个0的期望黑色的个数,而这个期望已经算出来,由于先是涂的第一个黑色,右边三个0算的时候还要乘一个转移概率1/5,然后2边期望加起来。这里为什么需要加起来,那就需要考虑期望的性质,这里是期望黑色球的个数,可以把10000分开2段,总的期望等于左端的期望加上右端的期望,就是总的期望。 最后,第一个涂的位置有5种,然后把所有的期望加起来即可。下面用公式推导一下。

dp[n] = ∑ni=1 (dp[i - 1 - 1] / n + dp[n - i - 1] / n + 1/n) = ∑ni=1 (dp[i - 1 - 1] / n + dp[n - i - 1] / n) + 1 = 2 / n * ∑n-2i=1 (dp[i]) + 1.

就是上面的公式,这个公式应该不难理解吧,接下来,就可以直接码代码了。

 1 /* 2 ID: y1197771 3 PROG: test 4 LANG: C++ 5 */ 6 #include<bits/stdc++.h> 7 #define pb push_back 8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl10 typedef long long ll;11 using namespace std;12 typedef pair<int, int> pii;13 const int maxn = 1e5 + 10;14 int n;15 double dp[maxn];16 void solve() {17     dp[0] = 0;18     dp[1] = dp[2] = 1;19     dp[3] = 5.0 / 3; dp[4] = 2;20     cin >> n;21     if(n < 5) {22         printf("%.10f\n", dp[n]);23         return;24     }25     double s = dp[1] + dp[2] + dp[3];26     for (int i = 5; i <= n; i++) {27         dp[i] = s * 2 / i + 1;28         s += dp[i - 1];29     }30     printf("%.10f\n", dp[n]);31 32 }33 int main() {34     //freopen("test.in", "r", stdin);35     //freopen("test.out", "w", stdout);36     solve();37     return 0;38 }

感觉遇到题,还是先想清楚,有什么性质,复杂度满足要求么,最后才是码代码!

某deed笔试题