Educational Codeforces Round 9

DUANG: http://codeforces.com/contest/632

倒着推

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int main(){
 5     int n, m;
 6     cin >> n >> m;
 7     stack<string> s;
 8     while(!s.empty()) s.pop();
 9     for(int i = 0; i < n; ++i){
10         string ss;
11         cin >> ss;
12         s.push(ss);
13     }
14     ll ans = 0;
15     ll apple = 0;
16     while(!s.empty()){
17         string ss = s.top();
18         s.pop();
19         if(ss == "halfplus"){
20             ++apple;
21             ans += apple * m / 2;
22             apple <<= 1;
23         }
24         else{
25             ans += apple * m / 2;
26             apple <<= 1;
27         }
28     }
29     cout << ans << endl;
30     return 0;
31 }

前后扫两遍差点T.............

更好的解法是维护两个前缀和: http://www.cnblogs.com/qscqesze/p/5236749.html

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 const int MAXN = 5e5+5;
 6 ll origin[MAXN] = {0};
 7 char str[MAXN];
 8 
 9 int main(){
10     int n;
11     scanf("%d", &n);
12     ll ans = 0;
13     ll tmp = 0;
14     ll ttl = 0;
15     for(int i = 0; i < n; ++i) cin >> origin[i];
16     getchar();
17     for(int i = 0; i < n; ++i){
18         scanf("%c", &str[i]);
19         if(str[i] == 'B')
20             ttl += origin[i];
21     }
22     ans = ttl;
23     tmp = ttl;
24     for(int i = 0; i < n; ++i){
25         if(str[i] == 'A') tmp += origin[i];
26         else tmp -= origin[i];
27         ans = max(ans, tmp);
28     }
29     tmp = ttl;
30     for(int i = n-1; i >= 0; --i){
31         if(str[i] == 'A') tmp += origin[i];
32         else tmp -= origin[i];
33         ans = max(ans, tmp);
34     }
35     printf("%I64d
", ans);
36     return 0;
37 }

排序输出脑残排序函数写错了...

#include <bits/stdc++.h>
using namespace std;

vector<string> ss;

bool cmp(string a, string b){
    return a + b < b + a;
}
int main(){
    ios::sync_with_stdio(false);
    //while(true){
        ss.clear();
        int n;
        cin >> n;
        cin.get();
        for(int i = 0; i < n; ++i){
            string s;
            cin >> s;
            ss.push_back(s);
        }
        sort(ss.begin(), ss.end(), cmp);
        for(int i = 0; i < n; ++i) cout << ss[i];
        cout << endl;
    //}
    return 0;
}

去除大于m 的然后用类似于筛法的东西跑一边各个数因子的个数

http://www.cnblogs.com/qscqesze/p/5236807.html

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int MAXN = 1e6+7;
 5 int origin[MAXN];
 6 int cnt[MAXN];
 7 int dp[MAXN];
 8 
 9 int main(){
10     int n, m;
11     scanf("%d %d", &n, &m);
12     for(int i = 1; i <= n; ++i){
13         scanf("%d", &origin[i]);
14         if(origin[i] <= m) cnt[origin[i]]++;
15     }
16     for(int i = 1; i <= m; ++i)
17         for(int j = i; j <= m; j+=i)
18             dp[j] += cnt[i];
19     int lcm = 1, ans = 0;
20     for(int i = 1; i <= m; ++i){
21         if(dp[i] > ans){
22             ans = dp[i];
23             lcm = i;
24         }
25     }
26     printf("%d %d
", lcm, ans);
27     for(int i = 1; i <= n; ++i)
28         if(lcm % origin[i] == 0)
29             printf("%d ", i);
30     puts("");
31     return 0;
32 }

E F还不敢碰