1001、Olympiad
维护前缀和就可以
AC代码：
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF 0x7fffffff
using namespace std;
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
", f[b] - f[a-1]);
}
return 0;
}
1002、Problem Killer
题目传送：HDU - 5328 - Problem Killer
维护两个指针一前一后移动，取最大的区间
AC代码：
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF 0x7fffffff
using namespace std;
int n;
LL a[1000005];
int main() {
int T;
scanf("%d", &T);
while(T --) {
scanf("%d", &n);
if(n == 0) {
printf("0
");
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
", ans);
}
return 0;
}
1012、ZZX and Permutations
题目传送：HDU - 5338 - ZZX and Permutations
解法：贪心+线段树+二分
首先要依照字典序贪心。能够找后继。也能够找之前的数，也能够找自己，可是要是最大的。且没有经过已经插入括号的区间
当中查询之前一段的最大值能够用线段树
而之前一段区间不能简单的取1~pos-1，由于须要考虑到已经加了括号的地方。这里能够用二分找那个区间的最左
二分是通过set的upper_bound实现的
由于调试了好久。。代码有点乱。。
AC代码：
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#define LL long long
#define INF 0x7fffffff
using namespace std;
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);
// for(int i = 1; i < 10; i ++) cout << Max[i] << " ";
for(int i = 1; i <= n; i ++) {//确定每个的终于位置
// cout << "lundao" << i << endl;
if(ans[i] != 0) continue;//该终于位置已经得出答案
//先去找当前能够得到的最大值
int 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] = 1;//表示已经被选
//更新
if(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;
}
// cout << "set ";
// for(set<int>::iterator it = st.begin(); it != st.end(); it ++) {
// cout << *it << " ";
// }
// cout << endl;
// for(int i = 1; i < n; i ++) {
// printf("%d ", ans[i]);
// }
// printf("%d
", ans[n]);
}
for(int i = 1; i < n; i ++) {
printf("%d ", ans[i]);
}
printf("%d
", ans[n]);
// cout << clock() << endl;
}
// cout << clock() << endl;
return 0;
}