2015 ACM/ICPC Asia Regional Changchun Online

这场过了7题,自己过了5题,慢慢不上

大概是个模拟题,不过旗神才开始不知道被卡哪里了

/*************************************************************************
    > File Name: 1001.cpp
    > Author: skt
    > Mail: sktsxy@gmail.com
    > Created Time: 2015年09月13日 星期日 10时11分48秒
 ************************************************************************/

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <complex>
#include <cassert>
// #pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define MAXN 150005
template <typename T> inline void checkMax(T &a, T b) {a = a>b?a:b;}
template <typename T> inline void checkMin(T &a, T b) {a = a<b?a:b;}
typedef pair<int, int> PII;
typedef vector<int> vi;
const double PI = acos(-1.0);
const double eps = 1e-8;
int T, K, M, Q;

struct Node {
    string name;
    int pos, value;
    bool operator < (const Node &next) const {
        if (value == next.value) {
            return next.pos < pos;
        }
        return value < next.value;
    }
} p[MAXN];

map<int, int> mymap;

int num[MAXN];

priority_queue < Node > PQ;

string ans[MAXN];

void work() {
    while (!PQ.empty()) PQ.pop();
    memset(num, 0, sizeof(num));
    cin >> K >> M >> Q;
    for (int i = 1; i <= K; i ++) {
        cin >> p[i].name >> p[i].value;
        p[i].pos = i;
    }
    for (int i = 1; i <= M; i ++) {
        int t, p;
        cin >> t >> p;
        num[t] += p;
    }
    int id = 1;
    for (int i = 1; i <= K; i ++) {
        PQ.push(p[i]);
        if (num[i] > 0) {
            while (!PQ.empty() && num[i]) {
                Node now = PQ.top(); PQ.pop();
                ans[id] = now.name;
                id ++;
                num[i] --;
            }
        }
    }
    while (!PQ.empty()) {
        Node now = PQ.top(); PQ.pop();
        ans[id ++] = now.name;
    }
    if (Q == 0) {
        cout << endl;
    }
    for (int i = 1; i <= Q; i ++) {
        int q;
        cin >> q;
        string now = ans[q];
        cout << now << " \n"[i == Q];
    }
}
int main() {
#ifdef __SKT__
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin >> T;
    while (T --) {
        work();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

/*************************************************************************

> File Name: 1001.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2015年09月13日星期日 10时11分48秒

************************************************************************/

#include <cstring>

#include <vector>

#include <list>

#include <map>

#include <set>

#include <deque>

#include <stack>

#include <queue>

#include <bitset>

#include <algorithm>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <complex>

#include <cassert>

// #pragma comment(linker,"/STACK:102400000,102400000")

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define x first

#define y second

#define MAXN 150005

template <typename T> inline void checkMax(T &a, T b) {a = a>b?a:b;}

template <typename T> inline void checkMin(T &a, T b) {a = a<b?a:b;}

typedef pair<int, int> PII;

typedef vector<int> vi;

const double PI = acos(-1.0);

const double eps = 1e-8;

int T, K, M, Q;

struct Node {

string name;

int pos, value;

bool operator < (const Node &next) const {

if (value == next.value) {

return next.pos < pos;

}

return value < next.value;

}

} p[MAXN];

map<int, int> mymap;

int num[MAXN];

priority_queue < Node > PQ;

string ans[MAXN];

void work() {

while (!PQ.empty()) PQ.pop();

memset(num, 0, sizeof(num));

cin >> K >> M >> Q;

for (int i = 1; i <= K; i ++) {

cin >> p[i].name >> p[i].value;

p[i].pos = i;

}

for (int i = 1; i <= M; i ++) {

int t, p;

cin >> t >> p;

num[t] += p;

}

int id = 1;

for (int i = 1; i <= K; i ++) {

PQ.push(p[i]);

if (num[i] > 0) {

while (!PQ.empty() && num[i]) {

Node now = PQ.top(); PQ.pop();

ans[id] = now.name;

id ++;

num[i] --;

}

while (!PQ.empty()) {

Node now = PQ.top(); PQ.pop();

ans[id ++] = now.name;

}

if (Q == 0) {

cout << endl;

}

for (int i = 1; i <= Q; i ++) {

int q;

cin >> q;

string now = ans[q];

cout << now << " \n"[i == Q];

}

int main() {

#ifdef __SKT__

freopen("in", "r", stdin);

#endif

ios::sync_with_stdio(false);

cin >> T;

while (T --) {

work();

}

return 0;

}

1002

我的锅,水题,被我忘了初始化

/*************************************************************************
    > File Name: 1002.cpp
    > Author: skt
    > Mail: sktsxy@gmail.com
    > Created Time: 2015年09月13日 星期日 09时16分49秒
 ************************************************************************/

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <complex>
#include <cassert>
// #pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define MAXN 10005
template <typename T> inline void checkMax(T &a, T b) {a = a>b?a:b;}
template <typename T> inline void checkMin(T &a, T b) {a = a<b?a:b;}
typedef pair<int, int> PII;
typedef vector<int> vi;
const double PI = acos(-1.0);
const double eps = 1e-8;
int T, P, M, deg[MAXN];

bool vis[MAXN];

LL a[MAXN];

struct Edge {
    int v, next;
} p[MAXN * 20];

int head[MAXN], cnt;

void init() {
    memset(vis, 0, sizeof(vis));
    memset(deg, 0, sizeof(deg));
    memset(p, 0, sizeof(p));
    fill(head, head + MAXN, -1);
    cnt = 0;
}

void addEdge(int u, int v) {
    p[cnt].v = v;
    p[cnt].next = head[u];
    head[u] = cnt ++;
}

void Topo() {
    queue <int> Q;
    for (int i = 1; i <= P; i ++) {
        if (deg[i] < 2) {
            Q.push(i);
            vis[i] = true;
        }
    }
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        deg[u] --;
        for (int i = head[u]; i != -1; i = p[i].next) {
            int v = p[i].v;
            if (!vis[v]) {
                deg[v] --;
                if (deg[v] <= 1) {
                    Q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

void dfs(int u, LL &sum, int &cnt) {
    vis[u] = true;
    sum += a[u];
    cnt ++;
    for (int i = head[u]; i != -1; i = p[i].next) {
        int v = p[i].v;
        if (!vis[v]) {
            dfs(v, sum, cnt);
        }
    }
}


void work() {
    init();
    scanf("%d %d", &P, &M);
    for (int i = 1; i <= P; i ++) {
        scanf("%I64d", &a[i]);
    }
    for (int i = 1; i <= M; i ++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
        deg[u] ++, deg[v] ++;
    }
    Topo();
    LL ans = 0LL;
    for (int i = 1; i <= P; i ++) {
        int cnt = 0;
        LL sum = 0;
        if (!vis[i]) {
            dfs(i, sum, cnt);
            if (cnt & 1) {
                ans += sum;
            }
        }
    }
    cout << ans << endl;
}
int main() {
    scanf("%d", &T);
    while (T --) {
        work();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

/*************************************************************************

> File Name: 1002.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2015年09月13日星期日 09时16分49秒

************************************************************************/

#include <cstring>

#include <vector>

#include <list>

#include <map>

#include <set>

#include <deque>

#include <stack>

#include <queue>

#include <bitset>

#include <algorithm>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <complex>

#include <cassert>

// #pragma comment(linker,"/STACK:102400000,102400000")

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define x first

#define y second

#define MAXN 10005

template <typename T> inline void checkMax(T &a, T b) {a = a>b?a:b;}

template <typename T> inline void checkMin(T &a, T b) {a = a<b?a:b;}

typedef pair<int, int> PII;

typedef vector<int> vi;

const double PI = acos(-1.0);

const double eps = 1e-8;

int T, P, M, deg[MAXN];

bool vis[MAXN];

LL a[MAXN];

struct Edge {

int v, next;

} p[MAXN * 20];

int head[MAXN], cnt;

void init() {

memset(vis, 0, sizeof(vis));

memset(deg, 0, sizeof(deg));

memset(p, 0, sizeof(p));

fill(head, head + MAXN, -1);

cnt = 0;

}

void addEdge(int u, int v) {

p[cnt].v = v;

p[cnt].next = head[u];

head[u] = cnt ++;

}

void Topo() {

queue <int> Q;

for (int i = 1; i <= P; i ++) {

if (deg[i] < 2) {

Q.push(i);

vis[i] = true;

}

while (!Q.empty()) {

int u = Q.front();

Q.pop();

deg[u] --;

for (int i = head[u]; i != -1; i = p[i].next) {

int v = p[i].v;

if (!vis[v]) {

deg[v] --;

if (deg[v] <= 1) {

Q.push(v);

vis[v] = true;

}

void dfs(int u, LL &sum, int &cnt) {

vis[u] = true;

sum += a[u];

cnt ++;

for (int i = head[u]; i != -1; i = p[i].next) {

int v = p[i].v;

if (!vis[v]) {

dfs(v, sum, cnt);

}

void work() {

init();

scanf("%d %d", &P, &M);

for (int i = 1; i <= P; i ++) {

scanf("%I64d", &a[i]);

}

for (int i = 1; i <= M; i ++) {

int u, v;

scanf("%d %d", &u, &v);

addEdge(u, v);

addEdge(v, u);

deg[u] ++, deg[v] ++;

}

Topo();

LL ans = 0LL;

for (int i = 1; i <= P; i ++) {

int cnt = 0;

LL sum = 0;

if (!vis[i]) {

dfs(i, sum, cnt);

if (cnt & 1) {

ans += sum;

}

cout << ans << endl;

}

int main() {

scanf("%d", &T);

while (T --) {

work();

}

return 0;

}

1006

后缀数组,直接搞,题意不清,写错两个地方,WA了6次

/*************************************************************************
    > File Name: 1006.cpp
    > Author: skt
    > Mail: sktsxy@gmail.com
    > Created Time: 2015年09月13日 星期日 11时27分20秒
 ************************************************************************/

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <complex>
#include <cassert>
// #pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define MAXN 40005
template <typename T> inline void checkMax(T &a, T b) {a = a>b?a:b;}
template <typename T> inline void checkMin(T &a, T b) {a = a<b?a:b;}
typedef pair<int, int> PII;
typedef vector<int> vi;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int INF = 0x3fffffff;
int T, N;

char str[MAXN], str1[MAXN];

int sa[MAXN], r[MAXN], Rank[MAXN], height[MAXN], Wa[MAXN], Wb[MAXN], Wv[MAXN], Ws[MAXN];

int cmp(int *r, int a, int b, int l) {
    return r[a] == r[b] && r[a + l] == r[b + l];
}
void calheight(int *r, int *sa, int n) {
    int i, j, k = 0;
    for (i = 0; i < n; height[Rank[i ++]] = k)
    for (k ? k -- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; k ++);
}
void da(int *r, int *sa, int n, int m) {
    int i, j, p, *x = Wa, *y = Wb, *t;
    for (i = 0; i < m; i ++) Ws[i] = 0;
    for (i = 0; i < n; i ++) Ws[x[i] = r[i]] ++;
    for (i = 1; i < m; i ++) Ws[i] += Ws[i - 1];
    for (i = n - 1; i >= 0; i --) sa[-- Ws[x[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
        for (p = 0, i = n - j; i < n; i ++) y[p ++] = i;
        for (i = 0; i < n; i ++) if (sa[i] >= j) y[p ++] = sa[i] - j;
        for (i = 0; i < n; i ++) Wv[i] = x[y[i]];
        for (i = 0; i < m; i ++) Ws[i] = 0;
        for (i = 0; i < n; i ++) Ws[Wv[i]] ++;
        for (i = 1; i < m; i ++) Ws[i] += Ws[i - 1];
        for (i = n - 1; i >= 0; i --) sa[-- Ws[Wv[i]]] = y[i];
        for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i ++) {
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p ++;
        }
    }
    for (int i = 0; i < n; i ++) Rank[sa[i]] = i;
    calheight(r, sa, n - 1);
}

int gao1(int n) {
    memset(sa, 0, sizeof(sa));
    for (int i = 0; i < n; i ++) {
        r[i + n] = r[i] = str[i] - 'a' + 1;
    }
    n *= 2;
    r[n] = 0;
    da(r, sa, n + 1, 200);
    int maxindex;
    for (int i = n; i >= 1; i --) {
        if (sa[i] < N) {
            maxindex = i; break;
        }
    }
    int smallindex = sa[maxindex], h = height[maxindex];
    for (int i = maxindex - 1; i >= 1; i --) {
        h = min(height[i + 1], h);
        if (sa[i] < N) {
            if (h >= N) {
                smallindex = min(smallindex, sa[i]);
            }
        }
    }
    return smallindex; 
}

int gao2(int n) {
    memset(sa, 0, sizeof(sa));
    for (int i = 0; i < n; i ++) {
        r[i + n] = r[i] = str1[i] - 'a' + 1;
    }
    n *= 2;
    r[n] = 0;
    da(r, sa, n + 1, 200);
    int maxindex;
    for (int i = n; i >= 1; i --) {
        if (sa[i] < N) {
            maxindex = i; break;
        }
    }
    int smallindex = sa[maxindex], h = height[maxindex];
    for (int i = maxindex - 1; i >= 1; i --) {
        h = min(height[i + 1], h);
        if (sa[i] < N) {
            if (h >= N) {
                smallindex = max(smallindex, sa[i]);
            }
        }
    }
    return smallindex;
}

void work() {
    memset(str, 0, sizeof(str));
    scanf("%d", &N);
    scanf("%s", str);
    for (int i = N; i < 2 * N; i ++) {
        str[i] = str[i - N];
    }
    int clockwise = gao1(N);
    for (int i = 0, j = N - 1; i < N; i ++, j --) {
        str1[i] = str1[i + N] = str[j];
    }
    int rclockwise = gao2(N);
    rclockwise = N - 1 - rclockwise;
    bool big = false, small = false;
    for (int i = 0; i < N; i ++) {
        int a = clockwise + i;
        if (a > N) a -= N;
        int b = rclockwise - i;
        if (b < 0) b += N;
        if (str[a] < str[b]) {
            big = true;
            break;
        } else if (str[a] > str[b]) {
            small = true;
            break;
        }
    }
    /*
    if (big) {
        printf("%d %d\n", rclockwise + 1, 1); return ;
    } else {
        printf("%d %d\n", clockwise + 1, 0); return ;
    }*/

    if (!small && !big) {
        if (rclockwise < clockwise) {
            printf("%d %d\n", rclockwise + 1, 1);
        } else {
            printf("%d %d\n", clockwise + 1, 0);
        }
        return ;
    }
    if (small) {
        printf("%d %d\n", clockwise + 1, 0); return ;
    } 
    if (big) {
        printf("%d %d\n", rclockwise + 1, 1); return ;
    }
}
int main() {
#ifdef __SKT__
    freopen("in", "r", stdin);
#endif
    scanf("%d", &T);
    while (T --) {
        work();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

/*************************************************************************

> File Name: 1006.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2015年09月13日星期日 11时27分20秒

************************************************************************/

#include <cstring>

#include <vector>

#include <list>

#include <map>

#include <set>

#include <deque>

#include <stack>

#include <queue>

#include <bitset>

#include <algorithm>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <complex>

#include <cassert>

// #pragma comment(linker,"/STACK:102400000,102400000")

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define x first

#define y second

#define MAXN 40005

template <typename T> inline void checkMax(T &a, T b) {a = a>b?a:b;}

template <typename T> inline void checkMin(T &a, T b) {a = a<b?a:b;}

typedef pair<int, int> PII;

typedef vector<int> vi;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int INF = 0x3fffffff;

int T, N;

char str[MAXN], str1[MAXN];

int sa[MAXN], r[MAXN], Rank[MAXN], height[MAXN], Wa[MAXN], Wb[MAXN], Wv[MAXN], Ws[MAXN];

int cmp(int *r, int a, int b, int l) {

return r[a] == r[b] && r[a + l] == r[b + l];

}

void calheight(int *r, int *sa, int n) {

int i, j, k = 0;

for (i = 0; i < n; height[Rank[i ++]] = k)

for (k ? k -- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; k ++);

}

void da(int *r, int *sa, int n, int m) {

int i, j, p, *x = Wa, *y = Wb, *t;

for (i = 0; i < m; i ++) Ws[i] = 0;

for (i = 0; i < n; i ++) Ws[x[i] = r[i]] ++;

for (i = 1; i < m; i ++) Ws[i] += Ws[i - 1];

for (i = n - 1; i >= 0; i --) sa[-- Ws[x[i]]] = i;

for (j = 1, p = 1; p < n; j *= 2, m = p) {

for (p = 0, i = n - j; i < n; i ++) y[p ++] = i;

for (i = 0; i < n; i ++) if (sa[i] >= j) y[p ++] = sa[i] - j;

for (i = 0; i < n; i ++) Wv[i] = x[y[i]];

for (i = 0; i < m; i ++) Ws[i] = 0;

for (i = 0; i < n; i ++) Ws[Wv[i]] ++;

for (i = 1; i < m; i ++) Ws[i] += Ws[i - 1];

for (i = n - 1; i >= 0; i --) sa[-- Ws[Wv[i]]] = y[i];

for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i ++) {

x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p ++;

}

for (int i = 0; i < n; i ++) Rank[sa[i]] = i;

calheight(r, sa, n - 1);

}

int gao1(int n) {

memset(sa, 0, sizeof(sa));

for (int i = 0; i < n; i ++) {

r[i + n] = r[i] = str[i] - 'a' + 1;

}

n *= 2;

r[n] = 0;

da(r, sa, n + 1, 200);

int maxindex;

for (int i = n; i >= 1; i --) {

if (sa[i] < N) {

maxindex = i; break;

}

int smallindex = sa[maxindex], h = height[maxindex];

for (int i = maxindex - 1; i >= 1; i --) {

h = min(height[i + 1], h);

if (sa[i] < N) {

if (h >= N) {

smallindex = min(smallindex, sa[i]);

}

return smallindex;

}

int gao2(int n) {

memset(sa, 0, sizeof(sa));

for (int i = 0; i < n; i ++) {

r[i + n] = r[i] = str1[i] - 'a' + 1;

}

n *= 2;

r[n] = 0;

da(r, sa, n + 1, 200);

int maxindex;

for (int i = n; i >= 1; i --) {

if (sa[i] < N) {

maxindex = i; break;

}

int smallindex = sa[maxindex], h = height[maxindex];

for (int i = maxindex - 1; i >= 1; i --) {

h = min(height[i + 1], h);

if (sa[i] < N) {

if (h >= N) {

smallindex = max(smallindex, sa[i]);

}

return smallindex;

}

void work() {

memset(str, 0, sizeof(str));

scanf("%d", &N);

scanf("%s", str);

for (int i = N; i < 2 * N; i ++) {

str[i] = str[i - N];

}

int clockwise = gao1(N);

for (int i = 0, j = N - 1; i < N; i ++, j --) {

str1[i] = str1[i + N] = str[j];

}

int rclockwise = gao2(N);

rclockwise = N - 1 - rclockwise;

bool big = false, small = false;

for (int i = 0; i < N; i ++) {

int a = clockwise + i;

if (a > N) a -= N;

int b = rclockwise - i;

if (b < 0) b += N;

if (str[a] < str[b]) {

big = true;

break;

} else if (str[a] > str[b]) {

small = true;

break;

}

if (big) {

printf("%d %d\n", rclockwise + 1, 1); return ;

} else {

printf("%d %d\n", clockwise + 1, 0); return ;

}*/

if (!small && !big) {

if (rclockwise < clockwise) {

printf("%d %d\n", rclockwise + 1, 1);

} else {

printf("%d %d\n", clockwise + 1, 0);

}

return ;

}

if (small) {

printf("%d %d\n", clockwise + 1, 0); return ;

}

if (big) {

printf("%d %d\n", rclockwise + 1, 1); return ;

}

int main() {

#ifdef __SKT__

freopen("in", "r", stdin);

#endif

scanf("%d", &T);

while (T --) {

work();

}

return 0;

}

1007

全场唯一正常题,4分钟就过了

/*************************************************************************
    > File Name: 1001.cpp
    > Author: skt
    > Mail: sktsxy@gmail.com
    > Created Time: 2015年09月13日 星期日 08时59分59秒
 ************************************************************************/

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <complex>
#include <cassert>
// #pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define MAXN 1005
template <typename T> inline void checkMax(T &a, T b) {a = a>b?a:b;}
template <typename T> inline void checkMin(T &a, T b) {a = a<b?a:b;}
typedef pair<int, int> PII;
typedef vector<int> vi;
const double PI = acos(-1.0);
const double eps = 1e-8;
int T, N, Q, a[MAXN];

void work() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i ++) {
        scanf("%d", &a[i]);
    }
    scanf("%d", &Q);
    for (int i = 1; i <= Q; i ++) {
        int l, r;
        scanf("%d %d", &l, &r);
        int ans = 0;
        for (int i = l; i <= r; i ++) {
            ans = max(ans, a[i]);
        }
        cout << ans << endl;
    }
}
int main() {
    scanf("%d", &T);
    while (T --) {
        work();
    }
    return 0;
}

/*************************************************************************

> File Name: 1001.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2015年09月13日星期日 08时59分59秒

************************************************************************/

#include <cstring>

#include <vector>

#include <list>

#include <map>

#include <set>

#include <deque>

#include <stack>

#include <queue>

#include <bitset>

#include <algorithm>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <complex>

#include <cassert>

// #pragma comment(linker,"/STACK:102400000,102400000")

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define x first

#define y second

#define MAXN 1005

template <typename T> inline void checkMax(T &a, T b) {a = a>b?a:b;}

template <typename T> inline void checkMin(T &a, T b) {a = a<b?a:b;}

typedef pair<int, int> PII;

typedef vector<int> vi;

const double PI = acos(-1.0);

const double eps = 1e-8;

int T, N, Q, a[MAXN];

void work() {

scanf("%d", &N);

for (int i = 1; i <= N; i ++) {

scanf("%d", &a[i]);

}

scanf("%d", &Q);

for (int i = 1; i <= Q; i ++) {

int l, r;

scanf("%d %d", &l, &r);

int ans = 0;

for (int i = l; i <= r; i ++) {

ans = max(ans, a[i]);

}

cout << ans << endl;

}

int main() {

scanf("%d", &T);

while (T --) {

work();

}

return 0;

}

1008

妈呀,又是我的锅,写错一个下表,白WA3次

/*************************************************************************
    > File Name: 1008.cpp
    > Author: skt
    > Mail: sktsxy@gmail.com
    > Created Time: 2015年09月13日 星期日 10时37分51秒
 ************************************************************************/

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <complex>
#include <cassert>
// #pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define MAXN 1005 
template <typename T> inline void checkMax(T &a, T b) {a = a>b?a:b;}
template <typename T> inline void checkMin(T &a, T b) {a = a<b?a:b;}
typedef pair<int, int> PII;
typedef vector<int> vi;
const double PI = acos(-1.0);
const double eps = 1e-8;
int T, N, Q;

int l[MAXN], a[MAXN], q[MAXN];

bool vis[MAXN];

pair<int, int> p[MAXN];

void search(int now, int left, int all) {
    if (left != 0) {
        p[now].first = now + 1;
        search(now + 1, l[now + 1], left);
    }
    if (left + 1 + 1 <= all) {
        int rightnum = now + left + 1;
        p[now].second = rightnum;
        search(rightnum, l[rightnum], all - 1 - left);
    }
}

vector<int> v;

string ans[MAXN];

void dfs(int u) {
    int goal = a[u];
    if (vis[goal]) {
        ans[goal] = "";
        for (int i = 0; i < v.size(); i ++) {
            if (v[i] == 1) {
                ans[goal] = ans[goal] + "E";
            } else {
                ans[goal] = ans[goal] + "W";
            }
        }
        ans[goal] = ans[goal] + "\n";
    }
    if (p[u].first) {
        v.push_back(1);
        dfs(p[u].first);
        v.pop_back();
    }
    if (p[u].second) {
        v.push_back(2);
        dfs(p[u].second);
        v.pop_back();
    }
}

void work() {
    v.clear();
    memset(vis, 0, sizeof(vis));
    memset(l, 0, sizeof(l));
    memset(p, 0, sizeof(p));
    scanf("%d", &N);
    for (int i = 1; i <= N; i ++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= N; i ++) {
        int leftnum = 0;
        for (int j = i + 1; j <= N; j ++) {
            if (a[j] > a[i]) {
                break;
            } else {
                leftnum ++;
            }
        }
        l[i] = leftnum;
    }
    search(1, l[1], N);
    scanf("%d", &Q);
    for (int i = 1; i <= Q; i ++) {
        scanf("%d", &q[i]);
        vis[q[i]] = true;
    }
    dfs(1);
    for (int i = 1; i <= Q; i ++) {
        int goal = q[i];
        cout << ans[goal]; 
    }
}
int main() {
#ifdef __SKT__
    freopen("in", "r", stdin);
#endif
    scanf("%d", &T);
    while (T --) {
        work();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

/*************************************************************************

> File Name: 1008.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2015年09月13日星期日 10时37分51秒

************************************************************************/

#include <cstring>

#include <vector>

#include <list>

#include <map>

#include <set>

#include <deque>

#include <stack>

#include <queue>

#include <bitset>

#include <algorithm>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <complex>

#include <cassert>

// #pragma comment(linker,"/STACK:102400000,102400000")

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define x first

#define y second

#define MAXN 1005

template <typename T> inline void checkMax(T &a, T b) {a = a>b?a:b;}

template <typename T> inline void checkMin(T &a, T b) {a = a<b?a:b;}

typedef pair<int, int> PII;

typedef vector<int> vi;

const double PI = acos(-1.0);

const double eps = 1e-8;

int T, N, Q;

int l[MAXN], a[MAXN], q[MAXN];

bool vis[MAXN];

pair<int, int> p[MAXN];

void search(int now, int left, int all) {

if (left != 0) {

p[now].first = now + 1;

search(now + 1, l[now + 1], left);

}

if (left + 1 + 1 <= all) {

int rightnum = now + left + 1;

p[now].second = rightnum;

search(rightnum, l[rightnum], all - 1 - left);

}

vector<int> v;

string ans[MAXN];

void dfs(int u) {

int goal = a[u];

if (vis[goal]) {

ans[goal] = "";

for (int i = 0; i < v.size(); i ++) {

if (v[i] == 1) {

ans[goal] = ans[goal] + "E";

} else {

ans[goal] = ans[goal] + "W";

}

ans[goal] = ans[goal] + "\n";

}

if (p[u].first) {

v.push_back(1);

dfs(p[u].first);

v.pop_back();

}

if (p[u].second) {

v.push_back(2);

dfs(p[u].second);

v.pop_back();

}

void work() {

v.clear();

memset(vis, 0, sizeof(vis));

memset(l, 0, sizeof(l));

memset(p, 0, sizeof(p));

scanf("%d", &N);

for (int i = 1; i <= N; i ++) {

scanf("%d", &a[i]);

}

for (int i = 1; i <= N; i ++) {

int leftnum = 0;

for (int j = i + 1; j <= N; j ++) {

if (a[j] > a[i]) {

break;

} else {

leftnum ++;

}

l[i] = leftnum;

}

search(1, l[1], N);

scanf("%d", &Q);

for (int i = 1; i <= Q; i ++) {

scanf("%d", &q[i]);

vis[q[i]] = true;

}

dfs(1);

for (int i = 1; i <= Q; i ++) {

int goal = q[i];

cout << ans[goal];

}

int main() {

#ifdef __SKT__

freopen("in", "r", stdin);

#endif

scanf("%d", &T);

while (T --) {

work();

}

return 0;

}

1009 多重背包

/*************************************************************************
	> File Name: hdu5445.cpp
	> Author: skt
	> Mail: sktsxy@gmail.com
	> Created Time: 2015年10月29日 星期四 23时02分45秒
 ************************************************************************/

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <complex>
#include <cassert>
// #pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define MAXN 205
#define MAXM 105005
template <typename T> inline void checkMax(T &a, T b) {a = a>b?a:b;}
template <typename T> inline void checkMin(T &a, T b) {a = a<b?a:b;}
typedef pair<int, int> PII;
typedef vector<int> vi;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int INF = 0x3fffffff;
int T, N, M, P, V1, V2;

struct Dessert {
    int t, u, v;
} dessert[MAXN];

struct Truck {
    int x, y, z;
} truck[MAXN];

int Volume[MAXM], Money[MAXM];

void ZeroOnePack(int cost, int weight, int type) {
    if (type == 1) {
        for (int i = V1; i >= cost; i --) {
            Volume[i] = max(Volume[i], Volume[i - cost] + weight);
        }
    } else {
        for (int i = V2; i >= cost; i --) {
            Money[i] = min(Money[i], Money[i - cost] + weight);
        }
    }
}

void CompletePack(int cost, int weight, int type) {
    if (type == 1) {
        for (int i = cost; i <= V1; i ++) {
            Volume[i] = max(Volume[i], Volume[i - cost] + weight);
        }
    } else {
        for (int i = cost; i <= V2; i ++) {
            Money[i] = min(Money[i], Money[i - cost] + weight);
        }
    }
}

void MultiplePack(int cost, int weight, int amount, int type) {
    int V;
    if (type == 1) {
        V = V1;
    } else {
        V = V2;
    }
    if (cost * amount >= V) {
        CompletePack(cost, weight, type);
        return ;
    }
    int k = 1;
    while (k < amount) {
        ZeroOnePack(k * cost, k * weight, type);
        amount = amount - k;
        k *= 2;
    }
    ZeroOnePack(amount * cost, amount * weight, type);
}

void work() {
    scanf("%d %d %d", &N, &M, &P);
    for (int i = 1; i <= N; i ++) {
        scanf("%d %d %d", &dessert[i].t, &dessert[i].u, &dessert[i].v);
    }
    for (int i = 1; i <= M; i ++) {
        scanf("%d %d %d", &truck[i].x, &truck[i].y, &truck[i].z);
    }
    fill(Volume, Volume + MAXM, - INF);
    fill(Money, Money + MAXM, INF);
    V1 = 50000, V2 = P + 1000;
    Volume[0] = 0;
    Money[0] = 0;
    for (int i = 1; i <= M; i ++) {
        MultiplePack(truck[i].y, truck[i].x, truck[i].z, 1);   
    }
    for (int i = 1; i <= N; i ++) {
        MultiplePack(dessert[i].t, dessert[i].u, dessert[i].v, 2);
    }
    int smallV = INF;
    for (int i = P; i <= V2; i ++) {
        smallV = min(smallV, Money[i]);
    }
    if (smallV == INF) {
        printf("TAT\n"); return ;
    }
    int ans = INF;
    for (int i = 1; i <= V1; i ++) {
        if (Volume[i] >= smallV) {
            ans = min(ans, i);
        }
    }
    if (ans == INF) {
        printf("TAT\n"); return ;
    } else {
        printf("%d\n", ans);
    }
}
int main() {
#ifdef __SKT__
    freopen("in", "r", stdin);
#endif
    scanf("%d", &T);
    while (T --) {
        work();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

/*************************************************************************

> File Name: hdu5445.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2015年10月29日星期四 23时02分45秒

************************************************************************/

#include <cstring>

#include <vector>

#include <list>

#include <map>

#include <set>

#include <deque>

#include <stack>

#include <queue>

#include <bitset>

#include <algorithm>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <complex>

#include <cassert>

// #pragma comment(linker,"/STACK:102400000,102400000")

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define x first

#define y second

#define MAXN 205

#define MAXM 105005

template <typename T> inline void checkMax(T &a, T b) {a = a>b?a:b;}

template <typename T> inline void checkMin(T &a, T b) {a = a<b?a:b;}

typedef pair<int, int> PII;

typedef vector<int> vi;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int INF = 0x3fffffff;

int T, N, M, P, V1, V2;

struct Dessert {

int t, u, v;

} dessert[MAXN];

struct Truck {

int x, y, z;

} truck[MAXN];

int Volume[MAXM], Money[MAXM];

void ZeroOnePack(int cost, int weight, int type) {

if (type == 1) {

for (int i = V1; i >= cost; i --) {

Volume[i] = max(Volume[i], Volume[i - cost] + weight);

}

} else {

for (int i = V2; i >= cost; i --) {

Money[i] = min(Money[i], Money[i - cost] + weight);

}

void CompletePack(int cost, int weight, int type) {

if (type == 1) {

for (int i = cost; i <= V1; i ++) {

Volume[i] = max(Volume[i], Volume[i - cost] + weight);

}

} else {

for (int i = cost; i <= V2; i ++) {

Money[i] = min(Money[i], Money[i - cost] + weight);

}

void MultiplePack(int cost, int weight, int amount, int type) {

int V;

if (type == 1) {

V = V1;

} else {

V = V2;

}

if (cost * amount >= V) {

CompletePack(cost, weight, type);

return ;

}

int k = 1;

while (k < amount) {

ZeroOnePack(k * cost, k * weight, type);

amount = amount - k;

k *= 2;

}

ZeroOnePack(amount * cost, amount * weight, type);

}

void work() {

scanf("%d %d %d", &N, &M, &P);

for (int i = 1; i <= N; i ++) {

scanf("%d %d %d", &dessert[i].t, &dessert[i].u, &dessert[i].v);

}

for (int i = 1; i <= M; i ++) {

scanf("%d %d %d", &truck[i].x, &truck[i].y, &truck[i].z);

}

fill(Volume, Volume + MAXM, - INF);

fill(Money, Money + MAXM, INF);

V1 = 50000, V2 = P + 1000;

Volume[0] = 0;

Money[0] = 0;

for (int i = 1; i <= M; i ++) {

MultiplePack(truck[i].y, truck[i].x, truck[i].z, 1);

}

for (int i = 1; i <= N; i ++) {

MultiplePack(dessert[i].t, dessert[i].u, dessert[i].v, 2);

}

int smallV = INF;

for (int i = P; i <= V2; i ++) {

smallV = min(smallV, Money[i]);

}

if (smallV == INF) {

printf("TAT\n"); return ;

}

int ans = INF;

for (int i = 1; i <= V1; i ++) {

if (Volume[i] >= smallV) {

ans = min(ans, i);

}

if (ans == INF) {

printf("TAT\n"); return ;

} else {

printf("%d\n", ans);

}

int main() {

#ifdef __SKT__

freopen("in", "r", stdin);

#endif

scanf("%d", &T);

while (T --) {

work();

}

return 0;

}

StillKeepTry

我是依旧在努力

2015 ACM/ICPC Asia Regional Changchun Online

Leave a Reply Cancel reply