首页 > 代码库 > Codeforces Round #267 (Div. 2)
Codeforces Round #267 (Div. 2)
A.George and Accommodation
题意：给定数组a,b，问b-a>=2有多少个
思路：直接模拟。。
B.Fedor and New Game
题意：给定m+1个n位以内的二进制数，求前m个有多少个跟第m+1的二进制下不同位数不超过k的个数
思路：直接模拟
C.George and Job
题意：给定n个数，求k个的段，每段有m个连续得数，使得和最大
思路：直接dp，注意long long不会超内存
1 /* 2 * Author: Yzcstc 3 * Created Time: 2014/9/18 23:24:07 4 * File Name: a.cpp 5 */ 6 #include<cstdio> 7 #include<iostream> 8 #include<cstring> 9 #include<cstdlib>10 #include<cmath>11 #include<algorithm>12 #include<string>13 #include<map>14 #include<set>15 #include<vector>16 #include<queue>17 #include<stack>18 #include<ctime>19 #define repf(i, a, b) for (int i = (a); i <= (b); ++i)20 #define repd(i, a, b) for (int i = (a); i >= (b); --i)21 #define M0(x) memset(x, 0, sizeof(x))22 #define Inf 0x7fffffff23 #define MP make_pair24 #define PB push_back25 #define eps 1e-826 #define pi acos(-1.0)27 typedef long long LL;28 using namespace std;29 long long dp[5001][5001], sum[10000];30 int a[10000], n, m, k;31 int main(){32 freopen("a.in", "r", stdin);33 freopen("a.out", "w", stdout);34 int n;35 while (scanf("%d%d%d", &n, &m, &k) != EOF){36 // M0(sum), M0(dp);37 for (int i = 1; i <= n; ++i)38 scanf("%d", &a[i]), sum[i] = sum[i-1] + a[i];39 for (int i = 1; i <= k; ++i){40 for (int j = 1; j <= n; ++j)41 if (j >= m) dp[i][j] = dp[i-1][j-m] + sum[j] - sum[j-m];42 for (int j = 1; j <= n; ++j)43 dp[i][j] = max(dp[i][j], dp[i][j-1]); 44 }45 long long ans = dp[k][n];46 cout << ans << endl;47 48 }49 return 0;50 }
D.Fedor and Essay
题意：给定m个单词组成的一段话，并给出n组单词的变换，问替换后这段话的’r‘字符最少是多少，如果相同，总长度最短更优。。输出r字符及长度
思路：很无聊的一道题，把变换看成有向边，单词看成点，那么就是一个图上的dp。。而且题目中还会出现环，还得缩点后才能dp。。略麻烦。。具体看代码吧。注意答案还是可能会超int。。然后比赛的时候莫名其妙的MlE了，赛后才发现是vector中用v.size()前没加int，以后要注意
1 /* 2 * Author: Yzcstc 3 * Created Time: 2014/9/19 0:08:06 4 * File Name: d.cpp 5 */ 6 #include<cstdio> 7 #include<iostream> 8 #include<cstring> 9 #include<cstdlib> 10 #include<cmath> 11 #include<algorithm> 12 #include<string> 13 #include<map> 14 #include<set> 15 #include<vector> 16 #include<queue> 17 #include<stack> 18 #include<ctime> 19 #define repf(i, a, b) for (int i = (a); i <= (b); ++i) 20 #define repd(i, a, b) for (int i = (a); i >= (b); --i) 21 #define M0(x) memset(x, 0, sizeof(x)) 22 #define Inf 0x7fffffff 23 #define MP make_pair 24 #define PB push_back 25 #define eps 1e-8 26 #define pi acos(-1.0) 27 #define M 1000007 28 typedef long long LL; 29 #define MXN 201010 30 using namespace std; 31 int hash[MXN], have[MXN], len[MXN]; 32 int ha[MXN], hlen[MXN]; 33 int n, m, tot; 34 char str[501010]; 35 map<int, int> mp; 36 vector<int> e[220000]; 37 38 void init(){ 39 scanf("%d", &n); 40 int sz; 41 mp.clear(); 42 for (int i = 1; i <= n; ++i){ 43 scanf("%s", &str); 44 sz = len[i] = strlen(str); 45 have[i] = hash[i] = 0; 46 for (int j = 0; j < sz; ++j){ 47 if (str[j] <= ‘Z‘) str[j] += 32; 48 have[i] += (str[j] == ‘r‘); 49 hash[i] = hash[i] * M + str[j]; 50 } 51 } 52 scanf("%d", &m); 53 tot = 0; 54 for (int i = 0; i < m; ++i){ 55 scanf("%s", str); 56 sz = strlen(str); 57 int tmp = 0, o = 0; 58 for (int j = 0; j < sz; ++j){ 59 if (str[j] <= ‘Z‘) str[j] += 32; 60 o += (str[j] == ‘r‘); 61 tmp = tmp * M + str[j]; 62 } 63 if (mp.find(tmp) == mp.end()){ mp[tmp] = ++tot; ha[tot] = o; hlen[tot] = sz; e[tot].clear(); } 64 int u = mp[tmp]; 65 scanf("%s", str); 66 tmp = 0, o = 0; 67 sz = strlen(str); 68 for (int j = 0; j < sz; ++j){ 69 if (str[j] <= ‘Z‘) str[j] += 32; 70 o += (str[j] == ‘r‘); 71 tmp = tmp * M + str[j]; 72 } 73 if (mp.find(tmp) == mp.end()){ mp[tmp] = ++tot; ha[tot] = o; hlen[tot] = sz; e[tot].clear(); } 74 int v = mp[tmp]; 75 e[u].push_back(v); 76 } 77 } 78 79 int dp[MXN][2]; 80 int Index; 81 stack<int> sta; 82 int dfn[MXN], low[MXN], col[MXN], color; 83 bool insta[MXN]; 84 void tarjan(int u){ 85 insta[u] = true; 86 dfn[u] = low[u] = ++Index; 87 sta.push(u); 88 for (int i = 0; i < (int)e[u].size(); ++i){ 89 int v = e[u][i]; 90 if (!dfn[v]){ 91 tarjan(v); 92 low[u] = min(low[u], low[v]); 93 } 94 else if (insta[v]) 95 low[u] = min(low[u], dfn[v]); 96 } 97 if (dfn[u] == low[u]){ 98 ++color; 99 while (1){100 int v = sta.top();101 insta[v] = false, col[v] = color;102 sta.pop();103 if (u == v) break;104 } 105 }106 }107 108 vector<int> E[220000];109 int haa[220000], hl[220000];110 void gao(){111 Index = color = 0;112 while (!sta.empty()) sta.pop();113 M0(dfn), M0(low), M0(col), M0(insta);114 for (int i = 1; i <= tot; ++i)115 if (!dfn[i]) tarjan(i); 116 for (int i = 0; i <= color; ++i)117 haa[i] = hl[i] = 100000000, E[i].clear();118 int v;119 for (int i = 1; i <= tot; ++i){120 if (ha[i] < haa[col[i]] || ha[i] == haa[col[i]] && hlen[i] < hl[col[i]])121 haa[col[i]] = ha[i], hl[col[i]] = hlen[i];122 for (int j = 0; j < (int)e[i].size(); ++j){123 v = e[i][j];124 if (col[i] != col[v]) E[col[i]].push_back(col[v]);125 }126 }127 }128 129 void dfs(int u){ 130 if (dfn[u]) return;131 dfn[u] = 1;132 dp[u][0] = haa[u], dp[u][1] = hl[u];133 for (int i = 0; i < (int)E[u].size(); ++i){134 int v = E[u][i];135 dfs(v);136 if (dp[v][0] < dp[u][0] || dp[u][0] == dp[v][0] && dp[v][1] < dp[u][1])137 dp[u][0] = dp[v][0], dp[u][1] = dp[v][1];138 }139 }140 141 void solve(){142 gao();143 M0(dfn);144 for (int i = 1; i <= color; ++i)145 if (!dfn[i]) dfs(i);146 long long ansx = 0, ansy = 0;147 for (int i = 1; i <= n; ++i){148 if (mp.find(hash[i]) == mp.end())149 ansx += have[i], ansy += len[i];150 else {151 int u = mp[hash[i]];152 ansx += dp[col[u]][0], ansy += dp[col[u]][1];153 }154 }155 printf("%I64d %I64d\n", ansx, ansy);156 }157 158 int main(){159 // freopen("a.in", "r", stdin);160 // freopen("a.out", "w", stdout);161 init();162 solve();163 return 0;164 }
E.Alex and Complicated Task
题意：给定n个数的数组a，求它的最长子序列b，使得对于序列中满足：对于任意k，b[4*k+1] = b[4*k+3],b[4*k+2]=b[4*k+4]
思路:本场比赛最好的一道题，思路也不难想，其实就是找最多的ABAB（A可等于B），存在很明显的贪心算法。。
从左到右，找到最靠近左边的ABAB序列。。然后就变成了如何最快的找到ABAB了。。
我用vector写了一个很复杂的方法，然后不知道怎么错了。。看了一下别人的，写的太巧了。。
具体看代码，可能要比我说的清楚点吧。。
1 /* 2 * Author: Yzcstc 3 * Created Time: 2014/9/19 16:35:50 4 * File Name: E.cpp 5 */ 6 #include<cstdio> 7 #include<iostream> 8 #include<cstring> 9 #include<cstdlib>10 #include<cmath>11 #include<algorithm>12 #include<string>13 #include<map>14 #include<set>15 #include<vector>16 #include<queue>17 #include<stack>18 #include<ctime>19 #define repf(i, a, b) for (int i = (a); i <= (b); ++i)20 #define repd(i, a, b) for (int i = (a); i >= (b); --i)21 #define M0(x) memset(x, 0, sizeof(x))22 #define Inf 0x7fffffff23 #define MP make_pair24 #define PB push_back25 #define x first26 #define y second27 #define N 55555528 using namespace std;29 typedef pair<int, int> pii;30 int n, a[N], t[N], pos[N], m;31 vector<int> ans;32 33 inline int mp(const int &x){34 return lower_bound(t, t + m, x) - t;35 }36 37 void init(){38 repf(i, 1, n)39 scanf("%d", &a[i]), t[i-1] = a[i];40 sort(t, t + n);41 m = unique(t, t + n) - t;42 }43 44 int lleft[N], f[N];45 int work(int st){46 stack<pii> sta;47 int s;48 repf(i, st, n){49 s = pos[i];50 if (f[s] != -1){51 ans.PB(t[f[s]]), ans.PB(a[i]), ans.PB(t[f[s]]), ans.PB(a[i]);52 repf(j, st, i) f[pos[j]] = -1;53 return i + 1;54 }55 if (lleft[s] >= st){56 while ((int)sta.size() > 0 && sta.top().y != lleft[s])57 f[sta.top().x] = s, sta.pop(); 58 }59 sta.push(MP(s, i));60 if (lleft[s] < st) lleft[s] = i;61 }62 return n + 1;63 }64 65 void solve(){66 ans.clear();67 for (int i = 1; i <= n; ++i) pos[i] = mp(a[i]);68 int i = 1;69 M0(lleft), memset(f, -1, sizeof(f));70 while (i <= n) i = work(i);71 printf("%d\n", (int)ans.size());72 for (int i = 0; i < (int)ans.size(); ++i)73 (int)ans.size() != i + 1 ? printf("%d ", ans[i]) : printf("%d\n", ans[i]);74 }75 76 int main(){77 // freopen("a.in", "r", stdin);78 // freopen("a.out", "w", stdout);79 while (scanf("%d", &n) != EOF){80 init();81 solve();82 }83 return 0;84 }
Codeforces Round #267 (Div. 2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。