1001、Olympiad
题目传送：HDU – 5327 – Olympiad
维护前缀和即可
AC代码：
;int f[100005];bool fun(int x) {int num[10];memset(num, 0, sizeof(num));while(x) {if(num[x % 10] > 0) return false;num[x % 10] = 1;x /= 10;}return true;}void init() {for(int i = 1; i < 100005; i ++) {f[i] += f[i-1];if(fun(i)) f[i] ++;}}int main() {int T;init();scanf(“%d”, &T);while(T –) {int a, b;scanf(“%d %d”, &a, &b);printf(“%d\n”, f[b] – f[a-1]);}return 0;}
1002、Problem Killer
题目传送：HDU – 5328 – Problem Killer
维护两个指针一前一后移动，，取最大的区间
AC代码：
;int n;LL a[1000005];int main() {int T;scanf(“%d”, &T);while(T –) {scanf(“%d”, &n);if(n == 0) {printf(“0\n”);continue;}for(int i = 0; i < n; i ++) {scanf(“%I64d”, &a[i]);}int ans = 0;int st = 0;int ed = 1;while(st < n) {while(a[ed] – a[ed-1] == a[st + 1] – a[st] && ed < n) {ed ++;}ans = max(ans, ed – st);st ++;if(st >= ed) ed ++;}st = 0;ed = 1;while(st < n) {while(a[st] && a[ed] && a[ed] * a[st] == a[ed-1] * a[st+1] && ed < n) {ed ++;}ans = max(ans, ed – st);st ++;if(st >= ed) ed ++;}printf(“%d\n”, ans);}return 0;}
1012、ZZX and Permutations
题目传送：HDU – 5338 – ZZX and Permutations
解法：贪心+线段树+二分
首先要按照字典序贪心，可以找后继，也可以找之前的数，也可以找自己，但是要是最大的，且没有经过已经插入括号的区间
其中查询之前一段的最大值可以用线段树
而之前一段区间不能简单的取1~pos-1，因为需要考虑到已经加了括号的地方，这里可以用二分找那个区间的最左
二分是通过set的upper_bound实现的
因为调试了好久。。代码有点乱。。
AC代码：
;const int maxn = 100005;int getPos[maxn];int a[maxn];int ans[maxn];int vis[maxn];int n;int Max[maxn << 2]; int cnt;int lazy[maxn << 2];void pushdown(int rt, int m) {if(lazy[rt] != -1) {lazy[rt << 1] = lazy[rt << 1 | 1] = lazy[rt];Max[rt << 1] = lazy[rt];Max[rt << 1 | 1] = lazy[rt];lazy[rt] = -1;}} void build(int l, int r, int rt) {lazy[rt] = -1;if(l == r) {Max[rt] = a[cnt ++];return;}int mid = (l + r) >> 1;build(l, mid, rt << 1);build(mid + 1, r, rt << 1 | 1);Max[rt] = max(Max[rt << 1], Max[rt << 1 | 1]); } int query(int L, int R, int l, int r, int rt) {if(L <= l && r <= R) {return Max[rt];}pushdown(rt, r – l + 1);int ret = 0;int mid = (l + r) >> 1;if(L <= mid) ret = max(ret, query(L, R, l, mid, rt << 1));if(R >= mid + 1) ret = max(ret, query(L, R, mid + 1, r, rt << 1 | 1));return ret; } void update(int L, int R, int c, int l, int r, int rt) {if(L <= l && r <= R) {Max[rt] = c;lazy[rt] = c;return;}pushdown(rt, r – l + 1);int mid = (l + r) >> 1;if(L <= mid) update(L, R, c, l, mid, rt << 1);if(R >= mid + 1) update(L, R, c, mid + 1, r, rt << 1 | 1);Max[rt] = max(Max[rt << 1], Max[rt << 1 | 1]);}set<int> st;int main() {// freopen(“in.txt”, “r”, stdin);int T;scanf(“%d”, &T);while(T –) {scanf(“%d”, &n);memset(vis, 0, sizeof(vis));memset(ans, 0, sizeof(ans));st.clear();for(int i = 1; i <= n; i ++) {scanf(“%d”, &a[i]);getPos[a[i]] = i;}cnt = 1;build(1, n, 1);(ans[i] != pos = getPos[i];//cout << i << ” weiyu ” << pos << endl;int ma = 0;//二分int l = 0;if(i != 1) {set<int>::iterator it = st.upper_bound(pos);if (it == st.begin()) {l = 0;}else {–it;l = *it;}}l ++;//cout << “zuoduandian ” << l << endl;if(pos != 1 && l != 0 && l <= pos – 1) ma = query(l, pos – 1, 1, n, 1);if(pos + 1 <= n && !vis[a[pos + 1]]) ma = max(ma, a[pos + 1]);if(!vis[i]) {//没被选的时候 ma = max(ma, i);}//cout << “xuanze ” << ma << endl;//cout << ma << endl;ans[i] = ma;update(getPos[ma], getPos[ma], 0, 1, n, 1);vis[ma] = (getPos[ma] < pos) {st.insert(pos);st.insert(getPos[ma]);//cout<< “fangjin ” << pos << ” ” << getPos[ma] << endl;update(getPos[ma], pos, 0, 1, n, 1);//cout << i << ” “;for(int j = getPos[ma]; j < pos; j ++) {ans[a[j]] = a[j + 1];vis[a[j + 1]] = 1;//被选 //cout << a[j] << ” “;}//cout << ” biaoji” << endl;}}for(int i = 1; i < n; i ++) {printf(“%d “, ans[i]);}printf(“%d\n”, ans[n]);//cout << clock() << endl;};}
有时我们选择改变，并非经过深思熟虑，而更像是听见了天地间冥冥中的呼唤，
