TopCoder SRM 634 Div.2[ABC]
ACM
题目地址: TopCoder SRM 634
赛后做的，感觉现场肯定做不出来Orz，简直不能多说。
题意：
问序列中有几个完全大于旁边的峰。
分析：
傻逼题，不多说。
代码：
/** Author: illuz <iilluzen>* File: one.cpp* Create Date: 2014-09-26 21:01:23* Descripton: */#include <cstdio>#include <vector>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define repf(i,a,b) for(int i=(a);i h) { int ret = 0, sz = h.size(); if (sz == 1) { return 1; } if (sz == 2) { return h[0] != h[1]; } if (h[0] > h[1]) ret++; if (h[sz - 1] > h[sz - 2]) ret++; // cout h[i - 1] && h[i] > h[i + 1]) ret++, i++; } return ret; }};int main() { // ios_base::sync_with_stdio(0); MountainRanges a; int n, t; vector<int> v; cin >> n; while (n--) { cin >> t; v.push_back(t); } cout <br> <br> <p></p> <p class="sycode"> </p> <h2> Level Two-ShoppingSurveyDiv2【数学】</h2> <p> 题意： <br> 你在做一项调查，一共有N人参加了调查，你得到了一份调查结果，就是每样东西有几个人买过。 <br> 现在你只有这份调查结果，即：第i个物品有s[i]个人买过。 <br> 问你最少有几个人全部东西都买过。</p> <p> 分析：</p> <p> 我们可以考虑有多少人次的东西没人买，即每样东西本来应该N人全都有买的，没人买就是sum(N - s[i])。 <br> 这时候我们可以把这些东西尽量分配给每个人，那么剩下的人就是没办法只能全买的了，也就是最少的。如果够分(N >= sum(N - s[i]))，那所有人都有可能没买全了。</p> <p> 代码：</p> <p> </p> <pre name="code" class="sycode">/** Author: illuz <iilluzen>* File: two.cpp* Create Date: 2014-09-26 22:36:58* Descripton: */#include <cstdio>#include <vector>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define repf(i,a,b) for(int i=(a);i s) { int sz = s.size(), sum = 0; repf (i, 0, sz - 1) sum += s[i]; int t = N - (N * sz - sum); if (t v; cin >> n >> m; repf (i, 0, m - 1) { cin >> t; v.push_back(t); } ShoppingSurveyDiv2 a; cout <br> <br> <p></p> <p class="sycode"> </p> <h2> Level Three-SpecialStrings【构造】</h2> <p> 题意： <br> 设定一种特殊的串 <br> 1. 01串 <br> 2. 从任何位置把它分为两个前后串，前面的字典序总是小于后面的。</p> <p> 现在给出一个保证特殊的串，问你同个长度下的字典序的下一个串是什么，如果是最后一个就返回空。</p> <p> 分析：</p> <p> 很明显，这个串必须是字典序的下一个，也就是这个01串是要进位的，所以我们先给它+1，即把最后一个0变成1，后面都变成X表示未知。 <br> 以01101111011110111作为例子，变化后就是01101111011111XXX了。</p> <p> 后面全放0能符合条件2吗？很明显不能</p> <p> 我们先考虑修改点的前面部分。 <br> 由于修改之前的那部分都已经严格遵守条件2了，而原先那个0的位置被变成1，所以：以前面的位置作为分割点的话，后半串是比原来变得更大了，所以前面部分不需要更改。</p> <p> 主要问题在后面部分，我们已修改点为分割点，还是按刚才那个例子，前后串就变成01101111011111和XXX了。 <br> 那么后面的X串就要比前面大了，由于要是下一个字典序，所以X串直接可以拷前面部分，然后+1就行了。</p> <p> 如何证明这个串在分割点为后面时，也能符合条件2呢，很明显，由于后面部分是完全复制前面的+1，所以分割点在后面跟分割点在后面是一样的，前面的是已经保证符合条件2的，所以后面肯定没问题。想一下就明白了。</p> <p> 这样一来，这个串就求出来了。</p> <p> 代码：</p> <p> </p> <pre name="code" class="sycode">/** Author: illuz <iilluzen>* File: three.cpp* Create Date: 2014-09-26 21:57:10* Descripton: */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define repf(i,a,b) for(int i=(a);i= 0; i--) { if (s[i] == '0') { pos = i; break; } } if (pos == 0) return ""; s[pos] = '1'; repf (i, pos + 1, len - 1) s[i] = s[i - pos - 1]; for (int i = len - 1; i >= 0; i--) { if (s[i] == '0') { s[i] = '1'; return s; } } }};int main() { // ios_base::sync_with_stdio(0); SpecialStrings a; string s; cin >> s; cout <br> <br> <p></p> <p class="sycode"> <br> </p> </algorithm></iostream></cstring></cstdio></iilluzen>
