Clash Credenz 2014 Wild Card Round题解

A题

简单模拟。

 /*************************************************************************

     > File Name: A.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年09月01日 星期一 08时08分12秒

     > Propose:

  ************************************************************************/

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <string>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /*Let's fight!!!*/

 int n;

 string s;

 double a, f;

 int main(void) {

       while (cin >> n) {

         cin >> s;

         cin >> a >> f;

         double sum = 0.0;

         int m = (int)s.length();

         bool flag = true;

         for (int i = ; i < m; i++) {

             if (s[i] == 'L') sum -= a;

             else sum += a;

             if (sum >= f || sum <= -f) {flag = false; break;}

         }

         printf("%s\n", flag ? "YES" : "NO");

     }

     return ;

 }

B题

判断最大值和剩下的值的和的关系

 /*************************************************************************

     > File Name: B.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年09月01日 星期一 14时26分17秒

     > Propose:

  ************************************************************************/

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /*Let's fight!!!*/

 int n, m;

 int main(void) {

     ios::sync_with_stdio(false);

     while (cin >> m >> n) {

         long long sum = , t = -, a;

         for (int i = ; i < m; i++) cin >> a, t = max(t, a), sum += a;

         sum -= t;

         if (t > sum + ) cout << "NO\n";

         else cout << "YES\n";

     }

     return ;

 }

C题

模拟。

 /*************************************************************************

     > File Name: C.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年09月01日 星期一 14时32分40秒

     > Propose:

  ************************************************************************/

 #include <map>

 #include <cmath>

 #include <string>

 #include <vector>

 #include <cstdio>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /*Let's fight!!!*/

 int vis[];

 int main(void) {

       ios::sync_with_stdio(false);

       int n;

       while (cin >> n) {

         map<string, int> var;

         vector<string> s(n + );

         for (int i = ; i <= n; i++) cin >> s[i];

         memset(vis, , sizeof(vis));

         for (int i = ; i <= n; i++) {

             if (var.find(s[i]) == var.end()) var[s[i]] = ;

             else var[s[i]]++;

             if (!vis[var[s[i]]]) vis[var[s[i]]] = i;

         }

         for (int i = ; i <= n && vis[i]; i++) cout << i << ' ' << s[vis[i]] << endl;

     }

     return ;

 }

D题

从后往前计算，判断当前点在左上或者右上或者左下或者右下，然后分别乘以不同的系数，并且更新点的位置。

 /*************************************************************************

     > File Name: D.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年09月01日 星期一 14时56分31秒

     > Propose:

  ************************************************************************/

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /*Let's fight!!!*/

 int t, a, b, c, d, x, y;

 typedef long long LL;

 int main(void) {

       ios::sync_with_stdio(false);

     cin >> t;

     while (t--) {

           int n;

           cin >> n;

         cin >> a >> b >> c >> d;

         cin >> x >> y;

         int times = ;

         while ((<<times) < max(x, y)) times++;

         LL ans = ;

         while (times--) {

             if (x <= (<<times)) {

                   if (y <= (<<times)) ans *= a;

                 else ans *= b, y -= <<times;

             } else {

                   x -= <<times;

                   if (y <= (<<times)) ans *= c;

                 else ans *= d, y -= <<times;

             }

         }

         cout << ans << endl;

     }

     return ;

 }

E题

比赛时候没有过。可以先枚举角度（从０到2*pi，每次加1e-7，加多了就会ＷＡ），求得系数。

 /*************************************************************************

     > File Name: E.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年09月01日 星期一 15时34分16秒

     > Propose:

  ************************************************************************/

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /*Let's fight!!!*/

 int main(void) {

       /*double ans;

     ans=0.0;

     double pi = acos(-1.0);

     for (double i = 0.0; i < 2 * pi; i += 0.0000001)

     {

       ans += sqrt(5.0 - 4.0 * cos(i));

     }

     ans /= 2 * pi * 10000000;

     cout << ans << endl; */

     int r;

     while (cin >> r) cout << (int)(r * 2.12709) <<endl;

     return ;

 }

F题

因为y-x < 1e4，以此作为着手点。先去掉Ａi中大于y-x+1的系数，然后去重。

之后就转化为完全背包。

 /*************************************************************************

     > File Name: F.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年09月01日 星期一 19时14分48秒

     > Propose:

  ************************************************************************/

 #include <set>

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <fstream>

 #include <vector>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /*Let's fight!!!*/

 int n, x, y, dp[];

 int main(void) {

     ios::sync_with_stdio(false);

     while (cin >> n) {

         cin >> x >> y;

         int cnt = ;

         vector<int> a;

         for (int i = ; i <= n; i++) {

             int tmp;

             cin >> tmp;

             if (tmp <= y - x + ) a.push_back(tmp - );

         }

         sort(a.begin(), a.end());

         a.erase(unique(a.begin(), a.end()), a.end());

         cnt = a.size();

         memset(dp, 0x3f, sizeof(dp));

         int V = y - x;

         dp[] = ;

         for (int i = ; i < cnt; i++) {

             for (int j = a[i]; j <= V; j++) {

                   if (dp[j - a[i]] != 0x3f3f3f3f) dp[j] = min(dp[j], dp[j - a[i]] + a[i]);

             }

         }

         if (dp[V] == 0x3f3f3f3f) puts("IMPOSSIBLE");

         else puts("POSSIBLE");

     }

     return ;

 }

H题

给ｎ个不大于１e9的数，要求找出２个数使得这两个数进行没有进位的加法的结果最大。

思路：用Trie树维护每一个数，初始时树为空，没输入一个数，先在树中找某个数与之进行无进位加法可以得到的最大值，

更新最大值，然后将该数加进树中。

下面就是如何找到与某个数进行加法可以得到的最大值，从高位枚举到低位，肯定优先满足最高位最大，这样才能使得结果最大，

对于每一位，降序枚举进行加法可以得到的和，就是９到０，看能否满足，如果满足就跳出并判断下一位，并更新结果。

Accepted Code:

 /*************************************************************************

     > File Name: H.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年09月02日 星期二 20时27分32秒

     > Propose:

  ************************************************************************/

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 /*Let's fight!!!*/

 #define rep(i, n) for (int i = (0); i < (n); i++)

 #define per(i, n) for (int i = (n); i > 0; i--)

 #define FOR(i, n) for (int i = (1); i <= (n); i++)

 #define ROF(i, n) for (int i = (n); i >= (1); i--)

 const int MAX_N = ;

 int ch[MAX_N][], p[];

 struct Trie {

     int sz;

     Trie() {

         memset(ch[], -, sizeof(ch[]));

         sz = ;

     }

     void insert(int num) {

         int u = ;

         for (int i = ; i >= ; i--) {

             int id = num / p[i];

             if (id >= ) id %= ;

             if (ch[u][id] == -) {

                 memset(ch[sz], -, sizeof(ch[sz]));

                 ch[u][id] = sz++;

             }

             u = ch[u][id];

         }

     }

     int find_max(int num) {

         int u = , ans = ;

         for (int i = ; i >= ; i--) {

             int id = num / p[i];

             if (id >= ) id %= ;

             for (int j = ; j >= ; j--) {

                 int tmp = j - id;

                 tmp = (tmp + ) % ;

                 if (ch[u][tmp] != -) {

                     ans += p[i] * j;

                     u = ch[u][tmp];

                     break;

                 }

             }

         }

         return ans;

     }

 };

 int main(void) {

     ios_base::sync_with_stdio(false);

     p[] = ;

     FOR (i, ) p[i] = p[i - ] * ;

     int n;

     while (cin >> n) {

           Trie A;

           int ans = -, num;

           rep (i, n) {

             cin >> num;

             if (i != ) ans = max(ans, A.find_max(num));

             A.insert(num);

         }

         cout << ans << endl;

     }

     return ;

 }

巴特西

Clash Credenz 2014 Wild Card Round题解

最新文章

热门文章