360实习3.18笔试题目

http://discuss.acmcoder.com/topic/58cd31e475bf559a0653f98f

上面的是官方题解。

1. 第一题，跑步，就是计算坐标，首先计算终点相对于x轴坐标是多少度，然后参数方程计算坐标，sin和cos直接加上角度就是坐标，反着跑的话，用360度减一下就可以了。

 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 << endl
10 typedef long long ll;
11 using namespace std;
12 typedef pair<int, int> pii;
13 const int maxn = 1e3 + 10;
14 const double pi = acos(-1.0);
15 void solve() {
16     double l, r;
17     cin >> l >> r;
18     double t = (l - floor(l / (2 * pi * r))) / r;
19     double x = cos(t) * r, y = sin(t) * r;
20     double a = cos(2 * pi - t) * r, b = sin(2 * pi - t) * r;
21     printf("%.3f %.3f
", a, b);
22     printf("%.3f %.3f
", x, y);
23 }
24 int main() {
25     freopen("test.in", "r", stdin);
26     //freopen("test.out", "w", stdout);
27     //ios::sync_with_stdio(0);
28     //cin.tie(0); cout.tie(0);
29     solve();
30     return 0;
31 }

View Code

一直以为是找规律，排列组合的知识，没搞出来。想到了范例，1221的解法很容易推翻很多想法。

后来看答案，就是一般的套路，枚举最后一个可以得到的串，然后进行转移，这就是通常的dp思路，缩小问题规模，转化为规模更小的同一问题。

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 << endl 10 typedef long long ll; 11 using namespace std; 12 typedef pair<int, int> pii; 13 const int maxn = 1e5 + 10; 14 const int mod = 1e9 + 7; 15 int a[maxn]; 16 int n; 17 ll dp[maxn]; 18 int cnt[11]; 19 void solve() { 20 cin >> n; 21 dp[0] = 1; 22 for (int i = 1; i <= n; i++) { 23 cin >> a[i]; 24 //if(i == 1) continue; 25 memset(cnt, 0, sizeof cnt); 26 for (int j = 0; j < i; j++) { 27 cnt[a[i - j] ]++; 28 if(cnt[a[i - j] ] > 1) 29 break; 30 dp[i] = (dp[i] + dp[i - j - 1]) % mod; 31 } 32 //cout << i << " " << dp[i] << endl; 33 } 34 cout << dp[n] << endl; 35 } 36 int main() { 37 freopen("test.in", "r", stdin); 38 //freopen("test.out", "w", stdout); 39 ios::sync_with_stdio(0); 40 cin.tie(0); cout.tie(0); 41 solve(); 42 return 0; 43 }

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 << endl 10 typedef long long ll; 11 using namespace std; 12 typedef pair<int, int> pii; 13 const int maxn = 1e3 + 10; 14 int n; 15 int dp[510][510]; 16 int a[510]; 17 int s[510]; 18 int work(int left, int right) { 19 if(left > right) return 0; 20 if(left == right) return a[left]; 21 if(dp[left][right] != -1) return dp[left][right]; 22 int &res = dp[left][right]; 23 int t1 = a[left] + s[right] - s[left] - work(left + 1, right); 24 int t2 = a[right] + s[right - 1] - s[left - 1] - work(left, right - 1); 25 res = max(t1, t2); 26 return res; 27 } 28 void solve() { 29 memset(dp, -1, sizeof dp); 30 cin >> n; 31 for (int i = 1; i <= n; i++) { 32 cin >> a[i]; 33 s[i] = a[i] + s[i - 1]; 34 } 35 int t = work(1, n); 36 cout << t <<" " << s[n] - t << endl; 37 38 } 39 int main() { 40 freopen("test.in", "r", stdin); 41 //freopen("test.out", "w", stdout); 42 //ios::sync_with_stdio(0); 43 //cin.tie(0); cout.tie(0); 44 int _; cin >> _; 45 for (int i = 1; i <= _; i++) { 46 cout << "Case #" << i << ": "; 47 solve(); 48 } 49 50 return 0; 51 }

相关推荐