2014 Multi-University Training Contest 5

补上

1001

求逆序数

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

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define eps 1e-8
#define MAXN 100005
template <typename T> inline T Max(T a, T b) {return a>b?a:b;}
template <typename T> inline T Min(T a, T b) {return a<b?a:b;}
int a[MAXN], c[MAXN], n, k;
LL ans;

void MergeSort(int l, int r) 
{
    if (r - l > 1) {
        int mid = (r + l) >> 1;
        MergeSort(l, mid);
        MergeSort(mid + 1, r);
        int tmp = l, i, j;
        for (i = l, j = mid+1; i <= mid && j <= r;) {
            if (a[i] > a[j]) {
                c[tmp ++] = a[j ++];
                ans = ans + mid - i + 1;
            } else {
                c[tmp ++] = a[i ++];
            }
        }
        for (; j <= r; j ++) {
            c[tmp ++] = a[j];
        }
        for (; i <= mid; i ++) {
            c[tmp ++] = a[i];
        }
    } else {
        if (a[r] < a[l]) {
            ans ++;
            c[l] = a[r], c[r] = a[l];
        } else {
            c[l] = a[l], c[r] = a[r];
        }
    }
    for (int i = l; i <= r; i ++) {
        a[i] = c[i];
    }
}

void work()
{
    ans = 0;
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
    }
    MergeSort(1, n);
    cout << (ans >= k ? (ans - k) : 0) << endl;
}
int main()
{
    while (scanf("%d %d", &n, &k) != EOF) {
        work();
    }
    return 0;
}

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

> File Name: 1001.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2014年08月08日星期五 16时05分13秒

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

#include <cstdio>

#include <algorithm>

#include <iostream>

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define eps 1e-8

#define MAXN 100005

template <typename T> inline T Max(T a, T b) {return a>b?a:b;}

template <typename T> inline T Min(T a, T b) {return a<b?a:b;}

int a[MAXN], c[MAXN], n, k;

LL ans;

void MergeSort(int l, int r)

{

if (r - l > 1) {

int mid = (r + l) >> 1;

MergeSort(l, mid);

MergeSort(mid + 1, r);

int tmp = l, i, j;

for (i = l, j = mid+1; i <= mid && j <= r;) {

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

c[tmp ++] = a[j ++];

ans = ans + mid - i + 1;

} else {

c[tmp ++] = a[i ++];

}

for (; j <= r; j ++) {

c[tmp ++] = a[j];

}

for (; i <= mid; i ++) {

c[tmp ++] = a[i];

}

} else {

if (a[r] < a[l]) {

ans ++;

c[l] = a[r], c[r] = a[l];

} else {

c[l] = a[l], c[r] = a[r];

}

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

a[i] = c[i];

}

void work()

{

ans = 0;

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

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

}

MergeSort(1, n);

cout << (ans >= k ? (ans - k) : 0) << endl;

}

int main()

{

while (scanf("%d %d", &n, &k) != EOF) {

work();

}

return 0;

}

1002

LCA出个各个路径的深度,贪心思路,深度从深往浅.

/*************************************************************************
	> File Name: 1002.cpp
	> Author: skt
	> Mail: sktsxy@gmail.com 
	> Created Time: 2014年10月12日 星期日 00时14分26秒
 ************************************************************************/

#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 <ctime>
#include <memory.h>
#include <cassert>
// #pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define PI acos(-1.0)
#define eps 1e-8
#define x first
#define y second
#define MAXN 100005
template <typename T> inline T Max(T a, T b) {return a>b?a:b;}
template <typename T> inline T Min(T a, T b) {return a<b?a:b;}
typedef pair<int, int> PII;
typedef vector<int> vi;
int N, M, u, v, f[MAXN], dep[MAXN];
bool vis[MAXN];

PII a[MAXN];

int head[MAXN], cnt;
struct Edge {
    int v, next;
} p[MAXN << 1];

int qhead[MAXN], qcnt;
struct QEdge {
    int v, next, id;
} qp[MAXN << 1];

void init() {
    memset(qp, 0, sizeof(qp));
    fill(qhead, qhead + MAXN, -1);
    qcnt = 0;
    memset(p, 0, sizeof(p));
    fill(head, head + MAXN, -1);
    cnt = 0;
    memset(vis, false, sizeof(vis));
    memset(dep, 0, sizeof(dep));
    for (int i = 1; i <= N; i ++) {
        f[i] = i;
    }
}

int father(int x) {
    if (f[x] == x) return x;
    return f[x] = father(f[x]);
}

void Union(int x, int y) {
    int fx = father(x);
    int fy = father(y);
    f[fx] = fy;
}

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

void addQEdge(int u, int v, int id) {
    qp[qcnt].v = v;
    qp[qcnt].next = qhead[u];
    qp[qcnt].id = id;
    qhead[u] = qcnt ++;
}

void dfs(int u, int h) {
    f[u] = u;
    vis[u] = true;
    dep[u] = h;
    for (int i = head[u]; i != -1; i = p[i].next) {
        int v = p[i].v;
        if (!vis[v]) {
            dfs(v, h + 1);
            f[v] = u;
        }
    }
    for (int i = qhead[u]; i != -1; i = qp[i].next) {
        int v = qp[i].v;
        if (vis[v]) {
            int id = qp[i].id;
            a[id].y = father(v);
            a[id].x = dep[a[id].y];
        }
    }
}

struct Node {
    int h, root, u, v;

    Node() {}

    Node(int _h, int _root, int _u, int _v):h(_h), root(_root), u(_u), v(_v) {}
        
    bool operator < (const Node next) const {
        return h < next.h;
    }  
};

Node b[MAXN];

void gao(int u, int h) {
    if (dep[u] < h) return ;
    vis[u] = true;
    for (int i = head[u]; i != -1; i = p[i].next) {
        int v = p[i].v;
        if (!vis[v]) {
            gao(v, h);
        }
    }
}

void work()
{
    init();
    for (int i = 1; i < N; i ++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }
    for (int i = 1; i <= M; i ++) {
        scanf("%d %d", &u, &v);
        addQEdge(u, v, i);
        addQEdge(v, u, i);
        b[i].u = u, b[i].v = v;
    }
    for (int i = 1; i <= N; i ++) {
        if (!vis[i]) {
            dfs(i, 1);
        }
    }
    for (int i = 1; i <= N; i ++) {
        b[i].root = a[i].y;
        b[i].h = a[i].x;
    }
    sort(b + 1, b + 1 + M);
    int cnt = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = M; i >= 1; i --) {
        if (vis[b[i].u] || vis[b[i].v]) continue;
        gao(b[i].root, b[i].h);
        cnt ++;
    }
    cout << cnt << endl;
}
int main()
{
    while (scanf("%d %d", &N, &M) != EOF) {
        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

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

> File Name: 1002.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2014年10月12日星期日 00时14分26秒

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

#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 <ctime>

#include <memory.h>

#include <cassert>

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

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define PI acos(-1.0)

#define eps 1e-8

#define x first

#define y second

#define MAXN 100005

template <typename T> inline T Max(T a, T b) {return a>b?a:b;}

template <typename T> inline T Min(T a, T b) {return a<b?a:b;}

typedef pair<int, int> PII;

typedef vector<int> vi;

int N, M, u, v, f[MAXN], dep[MAXN];

bool vis[MAXN];

PII a[MAXN];

int head[MAXN], cnt;

struct Edge {

int v, next;

} p[MAXN << 1];

int qhead[MAXN], qcnt;

struct QEdge {

int v, next, id;

} qp[MAXN << 1];

void init() {

memset(qp, 0, sizeof(qp));

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

qcnt = 0;

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

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

cnt = 0;

memset(vis, false, sizeof(vis));

memset(dep, 0, sizeof(dep));

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

f[i] = i;

}

int father(int x) {

if (f[x] == x) return x;

return f[x] = father(f[x]);

}

void Union(int x, int y) {

int fx = father(x);

int fy = father(y);

f[fx] = fy;

}

void addEdge(int u, int v) {

p[cnt].v = v;

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

head[u] = cnt ++;

}

void addQEdge(int u, int v, int id) {

qp[qcnt].v = v;

qp[qcnt].next = qhead[u];

qp[qcnt].id = id;

qhead[u] = qcnt ++;

}

void dfs(int u, int h) {

f[u] = u;

vis[u] = true;

dep[u] = h;

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

int v = p[i].v;

if (!vis[v]) {

dfs(v, h + 1);

f[v] = u;

}

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

int v = qp[i].v;

if (vis[v]) {

int id = qp[i].id;

a[id].y = father(v);

a[id].x = dep[a[id].y];

}

struct Node {

int h, root, u, v;

Node() {}

Node(int _h, int _root, int _u, int _v):h(_h), root(_root), u(_u), v(_v) {}

bool operator < (const Node next) const {

return h < next.h;

}

};

Node b[MAXN];

void gao(int u, int h) {

if (dep[u] < h) return ;

vis[u] = true;

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

int v = p[i].v;

if (!vis[v]) {

gao(v, h);

}

void work()

{

init();

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

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

addEdge(u, v);

addEdge(v, u);

}

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

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

addQEdge(u, v, i);

addQEdge(v, u, i);

b[i].u = u, b[i].v = v;

}

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

if (!vis[i]) {

dfs(i, 1);

}

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

b[i].root = a[i].y;

b[i].h = a[i].x;

}

sort(b + 1, b + 1 + M);

int cnt = 0;

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

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

if (vis[b[i].u] || vis[b[i].v]) continue;

gao(b[i].root, b[i].h);

cnt ++;

}

cout << cnt << endl;

}

int main()

{

while (scanf("%d %d", &N, &M) != EOF) {

work();

}

return 0;

}

1005

太坑，这题本身数据太水，然后比赛时配合出了问题。。。在做这题，被黄大队喊去做1009了。

一种方法是设置上下界，通过控制上下界来控制。

/*************************************************************************
    > File Name: 1005.cpp
    > Author: skt
    > Mail: sktsxy@gmail.com 
    > Created Time: 2014年08月05日 星期二 12时51分10秒
 ************************************************************************/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <stack>
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define eps 1e-8
#define MAXN 1000005
#define x first
#define y second
template <typename T> inline T Max(T a, T b) {return a>b?a:b;}
template <typename T> inline T Min(T a, T b) {return a<b?a:b;}
const int INF = 0x3fffffff;
int len, a[MAXN], up[MAXN], down[MAXN];
char s[MAXN];

void work()
{
    len = strlen(s);
    if (len == 0) {
        printf("Unique\n"); 
        return ;
    } else if (len & 1) {
        printf("None\n"); 
        return ;
    } else {
        up[len] = down[len] = 0;
        for (int i = len - 1; i >= 0; i --) {
            up[i] = -INF, down[i] = INF;
            if (s[i] == '?') {
                up[i] = Max(up[i], up[i+1] + 1);
                down[i] = Min(down[i], down[i+1] - 1);
            } else if (s[i] == '(') {
                up[i] = Max(up[i], up[i+1] - 1);
                down[i] = Min(down[i], down[i+1] - 1);
            } else {
                up[i] = Max(up[i], up[i+1] + 1);
                down[i] = Min(down[i], down[i+1] + 1);
            }
            if (down[i] < 0) {
                down[i] += 2;
            }
            if (up[i] < 0) {
                printf("None\n"); return ;
            }
        }
        if (down[0] > 0) {
            printf("None\n"); return ;
        }
        int delta = 0;
        for (int i = 0; i < len; i ++) {
            if (s[i] == '(') {
                delta ++;
            } else if (s[i] == ')') {
                delta --;
            } else {
                int flag = 0;
                if (delta && down[i+1] <= delta - 1 && delta - 1 <= up[i+1]) {
                    flag |= 1;
                }
                if (down[i+1] <= delta + 1 && delta + 1 <= up[i+1]) {
                    flag |= 2;
                }
                if (flag == 3) {
                    printf("Many\n"); return ;
                } else if (flag == 1) {
                    delta --;
                } else {
                    delta ++;
                }
            }
        }
        printf("Unique\n"); return ;
    }
}
int main()
{
    while (gets(s)) {
        work();
    }
    return 0;
}

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

> File Name: 1005.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2014年08月05日星期二 12时51分10秒

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

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <iostream>

#include <vector>

#include <map>

#include <set>

#include <string>

#include <stack>

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define eps 1e-8

#define MAXN 1000005

#define x first

#define y second

template <typename T> inline T Max(T a, T b) {return a>b?a:b;}

template <typename T> inline T Min(T a, T b) {return a<b?a:b;}

const int INF = 0x3fffffff;

int len, a[MAXN], up[MAXN], down[MAXN];

char s[MAXN];

void work()

{

len = strlen(s);

if (len == 0) {

printf("Unique\n");

return ;

} else if (len & 1) {

printf("None\n");

return ;

} else {

up[len] = down[len] = 0;

for (int i = len - 1; i >= 0; i --) {

up[i] = -INF, down[i] = INF;

if (s[i] == '?') {

up[i] = Max(up[i], up[i+1] + 1);

down[i] = Min(down[i], down[i+1] - 1);

} else if (s[i] == '(') {

up[i] = Max(up[i], up[i+1] - 1);

down[i] = Min(down[i], down[i+1] - 1);

} else {

up[i] = Max(up[i], up[i+1] + 1);

down[i] = Min(down[i], down[i+1] + 1);

}

if (down[i] < 0) {

down[i] += 2;

}

if (up[i] < 0) {

printf("None\n"); return ;

}

if (down[0] > 0) {

printf("None\n"); return ;

}

int delta = 0;

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

if (s[i] == '(') {

delta ++;

} else if (s[i] == ')') {

delta --;

} else {

int flag = 0;

if (delta && down[i+1] <= delta - 1 && delta - 1 <= up[i+1]) {

flag |= 1;

}

if (down[i+1] <= delta + 1 && delta + 1 <= up[i+1]) {

flag |= 2;

}

if (flag == 3) {

printf("Many\n"); return ;

} else if (flag == 1) {

delta --;

} else {

delta ++;

}

printf("Unique\n"); return ;

}

int main()

{

while (gets(s)) {

work();

}

return 0;

}

然后，当时，我的做法是模拟栈的思路，其实快敲出来了。先用全'('和')'来判断是否为None。个数为奇数也为None。然后就用栈的方法来模拟，最后就是剩余'?'的个数，=0时，就是Unique，> 2时就是Many，关键是两个时，就用判断这两个是否被包围过，被包围过就是Many，否则就是Unique。

/*************************************************************************
    > File Name: 1005.cpp
    > Author: skt
    > Mail: sktsxy@gmail.com 
    > Created Time: 2014年08月06日 星期三 19时23分26秒
 ************************************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <queue>
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define eps 1e-8
#define MAXN 1000005
template <typename T> inline T Max(T a, T b) {return a>b?a:b;}
template <typename T> inline T Min(T a, T b) {return a<b?a:b;}
char s[MAXN]; 
int len;
stack <int> ss;
stack < pair <int, int> > sp;

void work()
{
    len = strlen(s);
    if (len & 1) {
        printf("None\n"); return ;
    }
    if (len == 0) {
        printf("Unique\n"); return ;
    }
    while (!ss.empty()) {
        ss.pop();
    }
    for (int i = 0; i < len; i ++) {
        if (s[i] != ')') {
            ss.push(1);
        } else {
            if (ss.empty()) {
                printf("None\n"); return ;
            } else {
                ss.pop();
            }
        }
    }
    while (!ss.empty()) {
        ss.pop();
    }
    for (int i = len - 1; i >= 0; i --) {
        if (s[i] != '(') {
            ss.push(1);
        } else {
            if (ss.empty()) {
                printf("None\n"); return ;
            } else {
                ss.pop();
            }
        }
    }
    while (!sp.empty()) {
        sp.pop();
    }
    for (int i = 1; i <= len; i ++) {
        if (s[i-1] == '(') {
            sp.push(mp(i, 0));
        } else if (s[i-1] == '?') {
            if (sp.empty()) {
                sp.push(mp(0, 1));
            } else {
                pair <int, int> top = sp.top();
                if (top.x > 0) {
                    sp.push(mp(0, 1));
                } else if (top.x == 0) {
                    top.y ++;
                    sp.pop();
                    sp.push(top);
                }
            }
        } else if (s[i-1] == ')') {
            pair <int, int> next = mp(i, 0);
            int flag = 0;
            while (!sp.empty()) {
                pair <int, int> top = sp.top();
                sp.pop();
                if (top.x > 0) {
                    if (top.y == 0) {
                        flag = 1;
                        break;
                    } else {
                        next.y += top.y;
                    }
                } else {
                    next.y += top.y;
                }
            }
            if (!flag) {
                next.y --;
            }
            if (next.y) {
                sp.push(next);
            }
        }
    }
    if (sp.empty()) {
        printf("Unique\n"); return ;
    } else {
        vector < pair <int, int> > vec;
        vec.clear();
        while (!sp.empty()) {
            vec.pb(sp.top());
            sp.pop();
        }
        int num = 0;
        for (int i = 0; i < vec.size(); i ++) {
            if (vec[i].x != 0 && vec[i].y == 0) {
                num --;
            } else {
                num += vec[i].y;
            }
            if (sp.empty()) {
                sp.push(vec[i]);
            } else {
                if (vec[i].x != 0 && vec[i].y == 0) {
                    pair <int, int> next = vec[i];
                    while (!sp.empty()) {
                        pair <int, int> top = sp.top();
                        sp.pop();
                        next.y += top.y;
                    }
                    if (next.y > 1) {
                        next.y --;
                        sp.push(next);
                    }
                } else {
                    sp.push(vec[i]);
                }
            }
        }
        if (sp.empty()) {
            printf("Unique\n"); return ;
        }
        if (num > 2) {
            printf("Many\n"); return ;
        } 
        while (!sp.empty()) {
            pair <int, int> top = sp.top();
            if (top.x > 0 && top.y == 2) {
                printf("Many\n"); return ;
            }
            sp.pop();
        }
        printf("Unique\n");
    }
}
int main()
{
    while (gets(s)) {
        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

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

> File Name: 1005.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2014年08月06日星期三 19时23分26秒

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

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cmath>

#include <vector>

#include <cstring>

#include <map>

#include <set>

#include <stack>

#include <queue>

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define x first

#define y second

#define eps 1e-8

#define MAXN 1000005

template <typename T> inline T Max(T a, T b) {return a>b?a:b;}

template <typename T> inline T Min(T a, T b) {return a<b?a:b;}

char s[MAXN];

int len;

stack <int> ss;

stack < pair <int, int> > sp;

void work()

{

len = strlen(s);

if (len & 1) {

printf("None\n"); return ;

}

if (len == 0) {

printf("Unique\n"); return ;

}

while (!ss.empty()) {

ss.pop();

}

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

if (s[i] != ')') {

ss.push(1);

} else {

if (ss.empty()) {

printf("None\n"); return ;

} else {

ss.pop();

}

while (!ss.empty()) {

ss.pop();

}

for (int i = len - 1; i >= 0; i --) {

if (s[i] != '(') {

ss.push(1);

} else {

if (ss.empty()) {

printf("None\n"); return ;

} else {

ss.pop();

}

while (!sp.empty()) {

sp.pop();

}

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

if (s[i-1] == '(') {

sp.push(mp(i, 0));

} else if (s[i-1] == '?') {

if (sp.empty()) {

sp.push(mp(0, 1));

} else {

pair <int, int> top = sp.top();

if (top.x > 0) {

sp.push(mp(0, 1));

} else if (top.x == 0) {

top.y ++;

sp.pop();

sp.push(top);

}

} else if (s[i-1] == ')') {

pair <int, int> next = mp(i, 0);

int flag = 0;

while (!sp.empty()) {

pair <int, int> top = sp.top();

sp.pop();

if (top.x > 0) {

if (top.y == 0) {

flag = 1;

break;

} else {

next.y += top.y;

}

} else {

next.y += top.y;

}

if (!flag) {

next.y --;

}

if (next.y) {

sp.push(next);

}

if (sp.empty()) {

printf("Unique\n"); return ;

} else {

vector < pair <int, int> > vec;

vec.clear();

while (!sp.empty()) {

vec.pb(sp.top());

sp.pop();

}

int num = 0;

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

if (vec[i].x != 0 && vec[i].y == 0) {

num --;

} else {

num += vec[i].y;

}

if (sp.empty()) {

sp.push(vec[i]);

} else {

if (vec[i].x != 0 && vec[i].y == 0) {

pair <int, int> next = vec[i];

while (!sp.empty()) {

pair <int, int> top = sp.top();

sp.pop();

next.y += top.y;

}

if (next.y > 1) {

next.y --;

sp.push(next);

}

} else {

sp.push(vec[i]);

}

if (sp.empty()) {

printf("Unique\n"); return ;

}

if (num > 2) {

printf("Many\n"); return ;

}

while (!sp.empty()) {

pair <int, int> top = sp.top();

if (top.x > 0 && top.y == 2) {

printf("Many\n"); return ;

}

sp.pop();

}

printf("Unique\n");

}

int main()

{

while (gets(s)) {

work();

}

return 0;

}

1009

Java大数，

要求： $f(x) = \sum_{i=1}^{n-1} i\oplus(n-i)$

公式如下:

n = 2k + 1, $f(n) = 4f(k) + 6k$

n = 2k, $f(n) = 2f(k) + 2f(k-1) + 4k - 4$

一项可以通过另一项算出来。。

import java.io.File;
import java.io.FileInputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

import javax.jws.Oneway;

/** 
 * @author: skt E-mail:sktsxy@gmai.com
 * @Create：Aug 5, 2014 1:09:25 PM 
 * @filename: Main.java
 */

public class Main {
    
    static BigInteger n1;
    
    static HashMap<BigInteger, BigInteger> hash;
    
    static BigInteger two = BigInteger.valueOf(2l);
    
    static BigInteger tmp, t1, t2;

    static BigInteger four = BigInteger.valueOf(4l);
    
    static BigInteger six = BigInteger.valueOf(6l);
    
    static BigInteger gao(BigInteger n) {
        if (hash.containsKey(n)) {
            return hash.get(n);
        }
        if (n.equals(BigInteger.ONE)) {
            return BigInteger.ZERO;
        } else if (n.equals(BigInteger.ZERO)) {
            return BigInteger.ZERO;
        } else if (n.equals(two)) {
            t1 = BigInteger.ZERO;
            t2 = BigInteger.ZERO;
            return BigInteger.ZERO;
        } else if (n.equals(BigInteger.valueOf(3l))) {
            return BigInteger.valueOf(6l);
        } else {
            if (!n.testBit(0)) {
                BigInteger twon = n.divide(two);
                
                BigInteger ttwon = twon.divide(two);
                
                BigInteger a, b;
                
                if (twon.testBit(0)) { // n 为 ji
                    a = gao(twon.subtract(BigInteger.ONE));
                    BigInteger tmp1 = t1;
                    b = tmp1.multiply(four).add(ttwon.multiply(six));
                    t1 = b;
                    t2 = a;
                } else {
                    a = gao(twon);
                    BigInteger tmp1 = t2;
                    b = tmp1.multiply(four).add(ttwon.subtract(BigInteger.ONE).multiply(six));
                    t1 = a;
                    t2 = b;
                }
                
                BigInteger c = twon.multiply(four).subtract(four);
                
                a = a.multiply(two);
                b = b.multiply(two);
                
                tmp = a.add(b).add(c);
                hash.put(n, tmp);
                return tmp;
            } else {
                BigInteger twon = n.divide(two);
                BigInteger a = gao(twon);
                BigInteger b = twon.multiply(six);
                a = a.multiply(four);
                tmp = a.add(b);
                hash.put(n, tmp);
                return tmp;
            }
        }
    }
    
    public static void work(Scanner in, PrintWriter out) {
        hash = new HashMap<BigInteger, BigInteger>();
        n1 = in.nextBigInteger();
        out.println(gao(n1).toString());
    }
    
    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        while (in.hasNext()) {
            work(in, out);
        }
        in.close();
        out.close();
    }
}

100

101

102

import java.io.File;

import java.io.FileInputStream;

import java.io.PrintWriter;

import java.math.BigInteger;

import java.util.HashMap;

import java.util.Map;

import java.util.Scanner;

import javax.jws.Oneway;

/**

* @author: skt E-mail:sktsxy@gmai.com

* @Create：Aug 5, 2014 1:09:25 PM

* @filename: Main.java

public class Main {

static BigInteger n1;

static HashMap<BigInteger, BigInteger> hash;

static BigInteger two = BigInteger.valueOf(2l);

static BigInteger tmp, t1, t2;

static BigInteger four = BigInteger.valueOf(4l);

static BigInteger six = BigInteger.valueOf(6l);

static BigInteger gao(BigInteger n) {

if (hash.containsKey(n)) {

return hash.get(n);

}

if (n.equals(BigInteger.ONE)) {

return BigInteger.ZERO;

} else if (n.equals(BigInteger.ZERO)) {

return BigInteger.ZERO;

} else if (n.equals(two)) {

t1 = BigInteger.ZERO;

t2 = BigInteger.ZERO;

return BigInteger.ZERO;

} else if (n.equals(BigInteger.valueOf(3l))) {

return BigInteger.valueOf(6l);

} else {

if (!n.testBit(0)) {

BigInteger twon = n.divide(two);

BigInteger ttwon = twon.divide(two);

BigInteger a, b;

if (twon.testBit(0)) { // n 为 ji

a = gao(twon.subtract(BigInteger.ONE));

BigInteger tmp1 = t1;

b = tmp1.multiply(four).add(ttwon.multiply(six));

t1 = b;

t2 = a;

} else {

a = gao(twon);

BigInteger tmp1 = t2;

b = tmp1.multiply(four).add(ttwon.subtract(BigInteger.ONE).multiply(six));

t1 = a;

t2 = b;

}

BigInteger c = twon.multiply(four).subtract(four);

a = a.multiply(two);

b = b.multiply(two);

tmp = a.add(b).add(c);

hash.put(n, tmp);

return tmp;

} else {

BigInteger twon = n.divide(two);

BigInteger a = gao(twon);

BigInteger b = twon.multiply(six);

a = a.multiply(four);

tmp = a.add(b);

hash.put(n, tmp);

return tmp;

}

public static void work(Scanner in, PrintWriter out) {

hash = new HashMap<BigInteger, BigInteger>();

n1 = in.nextBigInteger();

out.println(gao(n1).toString());

}

public static void main(String[] args) throws Exception {

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

while (in.hasNext()) {

work(in, out);

}

in.close();

out.close();

}

1010

水题，矩阵乘法优化下就行了。

/*************************************************************************
    > File Name: 1010.cpp
    > Author: skt
    > Mail: sktsxy@gmail.com 
    > Created Time: 2014年08月05日 星期二 21时22分03秒
 ************************************************************************/

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define eps 1e-8
#define MAXN 805
template <typename T> inline T Max(T a, T b) {return a>b?a:b;}
template <typename T> inline T Min(T a, T b) {return a<b?a:b;}
int n, A[MAXN][MAXN], B[MAXN][MAXN], C[MAXN][MAXN];

void work()
{
    memset(C, 0, sizeof(C));
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            scanf("%d", &A[i][j]);
            A[i][j] %= 3;
        }
    }
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            scanf("%d", &B[i][j]);
            B[i][j] %= 3;
        }
    }
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            if (A[i][j]) {
                for (int k = 1; k <= n; k ++) {
                    C[i][k] += (A[i][j] * B[j][k]);
                }
            }
        }
    }
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            if (j > 1) printf(" ");
            printf("%d", C[i][j] % 3);
        }
        printf("\n");
    }
}
int main()
{
    while (scanf("%d", &n) != EOF) {
        work();
    }
    return 0;
}

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

> File Name: 1010.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2014年08月05日星期二 21时22分03秒

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

#include <cstdio>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define eps 1e-8

#define MAXN 805

template <typename T> inline T Max(T a, T b) {return a>b?a:b;}

template <typename T> inline T Min(T a, T b) {return a<b?a:b;}

int n, A[MAXN][MAXN], B[MAXN][MAXN], C[MAXN][MAXN];

void work()

{

memset(C, 0, sizeof(C));

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

for (int j = 1; j <= n; j ++) {

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

A[i][j] %= 3;

}

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

for (int j = 1; j <= n; j ++) {

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

B[i][j] %= 3;

}

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

for (int j = 1; j <= n; j ++) {

if (A[i][j]) {

for (int k = 1; k <= n; k ++) {

C[i][k] += (A[i][j] * B[j][k]);

}

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

for (int j = 1; j <= n; j ++) {

if (j > 1) printf(" ");

printf("%d", C[i][j] % 3);

}

printf("\n");

}

int main()

{

while (scanf("%d", &n) != EOF) {

work();

}

return 0;

}

StillKeepTry

我是依旧在努力

2014 Multi-University Training Contest 5

1001

1002

1005

1009

1010

Leave a Reply Cancel reply