CF331A1,331A2

链接：http://codeforces.com/problemset/problem/331/A1

题意：不翻译了。

思路：A1题数据范围小，暴力是可行的，我果断暴力了。不过，话说，除了暴力我还会什么。。。闲话少说。A2的话，采用线段树。不过我不会，哈哈哈。找了位仁兄的代码看了一下，思路比较巧妙，值得学习，虽然没有用到数据结构，但是可以解决。不过我忘记是哪位仁兄的了，你要是看到了的话，提醒我一下。就贴那位仁兄的代码吧。

#include <iostream>
#include <vector>
#include <map>using namespace std;#define INF 3000000000ll
map<int, int> last;
int a[300010];
long long sum[300010];
vector<int> v;
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];last[a[i]] = i;//记录下来了每个数字的最后出现的位置if (a[i] > 0)sum[i] = sum[i - 1] + a[i];elsesum[i] = sum[i - 1];}long long ans = -INF, d = 0;for (int i = 1; i <= n; i++){if (last[a[i]] != i)//不相等说明i和last[a[i]]是个符合要求的区间，比起双重循环降低复杂度啊{//a[i]的首位置是i，末位置是last[a[i]]long long k = sum[last[a[i]] - 1] - sum[i] + a[i] * 2;if (k > ans){ans = k;d = i;}}}for (int i = 1; i < d; i++)v.push_back(i);for (int i = d + 1; i <= last[a[d]] - 1; i++)if (a[i] < 0)v.push_back(i);for (int i = last[a[d]] + 1; i <= n; i++)v.push_back(i);cout << ans << " " << v.size() << endl;for (int i = 0; i < v.size(); i++)cout << v[i] << " ";
}

以后学了高级方法再来做一次吧。