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