2014 Multi-University Training Contest 9

这场已经无法在吐槽黄大队，整场比赛，黄大队没有一点状态。全场最水的一道题，让大队做，还WA了一次。哥在打了狂犬疫苗，依旧A了四题，大队真是坑啊。。。。

1001

$dp, dp[l][r] = Min(dp[i][j] + a[i-l+1] + a[r-j+1]), (1 <= i < j <= n)$

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

#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>
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define eps 1e-8
#define MAXN 5005
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], dp[MAXN][MAXN];
LL v[MAXN], L[MAXN], R[MAXN];

int gao(int l, int r)
{
    if (l > r) {
        return 0;
    }
    if (dp[l][r] >= 0) {
        return dp[l][r];
    }
    dp[l][r] = a[r - l + 1];
    int i = l, j = r;
    while (i < j) {
        LL ll = L[i] - L[l-1];
        LL rr = R[j] - R[r+1];
        if (ll == rr) {
            dp[l][r] = Min(dp[l][r], gao(i + 1, j - 1) + a[i - l + 1] + a[r - j + 1]);
            i ++, j --;
        } else if (ll > rr) {
            j --;
        } else if (ll < rr) {
            i ++;
        }
    }
    return dp[l][r];
}

void work()
{
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= N; i ++) {
        scanf("%lld", &v[i]);
    }
    for (int i = 1; i <= N; i ++) {
        scanf("%d", &a[i]);
    }
    L[0] = 0;
    for (int i = 1; i <= N; i ++) {
        L[i] = L[i - 1] + v[i];
    }
    R[N + 1] = 0;
    for (int i = N; i >= 1; i --) {
        R[i] = R[i + 1] + v[i];
    }
    for (int i = 1; i <= N; i ++) {
        dp[i][i] = a[1];
    }
    printf("%d\n", gao(1, N));
}
int main()
{
   // freopen("in", "r", stdin);
    while (scanf("%d", &N) != EOF) {
        if (N == 0) break;
        work();
    }
    return 0;
}

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

> File Name: 1001.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2014年08月19日星期二 13时36分39秒

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

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

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define eps 1e-8

#define MAXN 5005

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], dp[MAXN][MAXN];

LL v[MAXN], L[MAXN], R[MAXN];

int gao(int l, int r)

{

if (l > r) {

return 0;

}

if (dp[l][r] >= 0) {

return dp[l][r];

}

dp[l][r] = a[r - l + 1];

int i = l, j = r;

while (i < j) {

LL ll = L[i] - L[l-1];

LL rr = R[j] - R[r+1];

if (ll == rr) {

dp[l][r] = Min(dp[l][r], gao(i + 1, j - 1) + a[i - l + 1] + a[r - j + 1]);

i ++, j --;

} else if (ll > rr) {

j --;

} else if (ll < rr) {

i ++;

}

return dp[l][r];

}

void work()

{

memset(dp, -1, sizeof(dp));

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

scanf("%lld", &v[i]);

}

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

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

}

L[0] = 0;

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

L[i] = L[i - 1] + v[i];

}

R[N + 1] = 0;

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

R[i] = R[i + 1] + v[i];

}

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

dp[i][i] = a[1];

}

printf("%d\n", gao(1, N));

}

int main()

{

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

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

if (N == 0) break;

work();

}

return 0;

}

1002

预处理出所有数的因子。

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

#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>
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define eps 1e-8
#define MAXN 100005
#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;}
typedef vector <int> vi;
int n, s[MAXN], t[MAXN], a[MAXN], p[MAXN] = {}, pn, cnt, pos, b[MAXN], c[MAXN], f[MAXN], g[MAXN];
vi ans[MAXN], v;
map <int, int> ma;
pair<int, int> prim[20];

void dfs(int len, int val) {
    if (len == pn) {
        ans[pos].pb(val);
        return ;
    }
    for (int i = 0; i <= prim[len].y; i ++) {
        if (i == 0) {
            dfs(len + 1, val);
        } else {
            val *= prim[len].x;
            dfs(len + 1, val);
        }
    }
}

void init() {
    p[0] = p[1] = 1;
    for (int i = 2; i <= 100000; i ++) {
        if (p[i]) {
            continue;
        }
        for (int j = i << 1; j <= 100000; j += i) {
            p[j] = i;
        }
    }
    for (int i = 1; i <= 100000; i ++) {
        ans[i].clear();
    }
    for (int i = 1; i <= 100000; i ++) {
        v.clear(), ma.clear();
        if (i > 1) {
            int tmp = i;
            while (p[tmp]) {
                v.pb(p[tmp]);
                tmp = tmp / p[tmp];
            }
            v.pb(tmp);
        }
        for (int j = 0; j < v.size(); j ++) {
            ma[v[j]] ++;
        }
        cnt = pn = 0;
        for (map<int, int>::iterator it = ma.begin(); it != ma.end(); it ++) {
            prim[pn ++] = *it;
        }
        pos = i;
        dfs(0, 1);
    }
}

void work()
{
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
    }
    memset(s, 0, sizeof(s));
    memset(t, 0, sizeof(t));
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    for (int i = 1; i <= n; i ++) {
        if (s[a[i]]) {
            f[i] = s[a[i]];
        } else {
            f[i] = i;
        }
        for (int j = 0; j < ans[a[i]].size(); j ++) {
            s[ans[a[i]][j]] = i;
        }
        b[i] = a[f[i]];
    }
    for (int i = n; i >= 1; i --) {
        if (t[a[i]]) {
            g[i] = t[a[i]];
        } else {
            g[i] = i;
        }
        for (int j = 0; j < ans[a[i]].size(); j ++) {
            t[ans[a[i]][j]] = i;    
        }
        c[i] = a[g[i]];
    }
    LL lans = 0;
    for (int i = 1; i <= n; i ++) {
        lans = lans + (LL)b[i] * (LL)c[i];
    }
    cout << lans << endl;
}
int main()
{
    init();
    while (scanf("%d", &n) != EOF) {
        if (n == 0) break;
        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

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

> File Name: 1002.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2014年08月19日星期二 12时11分12秒

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

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

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define eps 1e-8

#define MAXN 100005

#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;}

typedef vector <int> vi;

int n, s[MAXN], t[MAXN], a[MAXN], p[MAXN] = {}, pn, cnt, pos, b[MAXN], c[MAXN], f[MAXN], g[MAXN];

vi ans[MAXN], v;

map <int, int> ma;

pair<int, int> prim[20];

void dfs(int len, int val) {

if (len == pn) {

ans[pos].pb(val);

return ;

}

for (int i = 0; i <= prim[len].y; i ++) {

if (i == 0) {

dfs(len + 1, val);

} else {

val *= prim[len].x;

dfs(len + 1, val);

}

void init() {

p[0] = p[1] = 1;

for (int i = 2; i <= 100000; i ++) {

if (p[i]) {

continue;

}

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

p[j] = i;

}

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

ans[i].clear();

}

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

v.clear(), ma.clear();

if (i > 1) {

int tmp = i;

while (p[tmp]) {

v.pb(p[tmp]);

tmp = tmp / p[tmp];

}

v.pb(tmp);

}

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

ma[v[j]] ++;

}

cnt = pn = 0;

for (map<int, int>::iterator it = ma.begin(); it != ma.end(); it ++) {

prim[pn ++] = *it;

}

pos = i;

dfs(0, 1);

}

void work()

{

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

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

}

memset(s, 0, sizeof(s));

memset(t, 0, sizeof(t));

memset(f, 0, sizeof(f));

memset(g, 0, sizeof(g));

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

if (s[a[i]]) {

f[i] = s[a[i]];

} else {

f[i] = i;

}

for (int j = 0; j < ans[a[i]].size(); j ++) {

s[ans[a[i]][j]] = i;

}

b[i] = a[f[i]];

}

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

if (t[a[i]]) {

g[i] = t[a[i]];

} else {

g[i] = i;

}

for (int j = 0; j < ans[a[i]].size(); j ++) {

t[ans[a[i]][j]] = i;

}

c[i] = a[g[i]];

}

LL lans = 0;

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

lans = lans + (LL)b[i] * (LL)c[i];

}

cout << lans << endl;

}

int main()

{

init();

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

if (n == 0) break;

work();

}

return 0;

}

1005

模拟题，有点烦，注意括号嵌套的情况。

/*************************************************************************
	> File Name: 1005.cpp
	> Author: skt
	> Mail: sktsxy@gmail.com 
	> Created Time: 2014¿?08¿?22¿? ¿?¿?¿? 00¿?18¿?14¿?
 ************************************************************************/

#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>
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define eps 1e-8
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 T;
string line;

struct Token {
    string Name;
    string Id;
    vector<string> Class;
    int Num;
    string Tag;
    
    Token() {
        Name = Id = Tag = "";
        Num = 0;
        Class.clear();
    }
    
    string Pre() {
        if (Name == "(" || Name == "") {
            return "";
        }
        string ans = "<" + Name;
        if (Id != "") {
            ans += " id=\"" + Id + "\"";
        }
        if (Class.size()) {
            ans += " class=\"";
            for (int i = 0; i < Class.size(); i ++) {
                if (i) ans += " ";
                ans += Class[i];
            }
            ans += "\"";
        }
        ans += ">";
        return ans;
    }

    string Last() {
        if (Name == "(" || Name == "") {
            return "";
        }
        return "</" + Name + ">";
    }
};

stack <Token> ss;

void gao()
{
    while (!ss.empty()) ss.pop();
    Token token = Token();
    int _Id = 0, _Class = 0, _Num = 0, num = 0;
    for (int i = 0; i < line.length(); i ++) {
        if (line[i] == '(') {
            if (token.Name != "") {
                if (_Num) {
                    token.Num = num;
                    num = 0;
                }
                token.Tag = token.Pre();
                ss.push(token);
            }
            num = _Num = _Class = _Id = 0;
            token = Token();
            token.Name = "(";
            ss.push(token);
            token = Token();
        } else if (line[i] == ')') {
            if (token.Name != "") {
                if (_Num) {
                    token.Num = num;
                }    
                token.Tag = token.Pre();
                ss.push(token);
            }
            num = _Num = _Class = _Id = 0;
            token = Token();
            string s = "";
            while (!ss.empty()) {
                Token tmp = ss.top();
                ss.pop();
                if (tmp.Name == "(") {
                    tmp.Tag = s;
                    tmp.Name = "";
                    ss.push(tmp);
                    break;
                }
                tmp.Tag += s;
                tmp.Tag += tmp.Last();
                string t = tmp.Tag;
                for (int i = 2; i <= tmp.Num; i ++) {
                    tmp.Tag = tmp.Tag + t;
                }
                s = tmp.Tag;
            }
        } else if (line[i] == '*') {
            _Num = 1; 
            num = _Class = _Id = 0;
        } else if (line[i] == '#') {
            _Id = 1;
            _Class = _Num = num = 0;
        } else if (line[i] == '.') {
            _Class = 1;
            _Num = _Id = num = 0;
            token.Class.pb("");
        } else if (line[i] == '>') {
            if (token.Name != "") {
                if (_Num) {
                    token.Num = num;
                }
                token.Tag = token.Pre();
                num = _Num = _Class = _Id = 0;
                ss.push(token);
            }
            token = Token();
        } else {
            if (_Num) {
                num = num * 10 + line[i] - '0';
            } else if (_Id) {
                token.Id += line[i];
            } else if (_Class) {
                token.Class[token.Class.size() - 1] += line[i];
            } else {
                token.Name += line[i];
                token.Num = 1;
            }
        }
    }
    if (token.Name != "") {
        if (_Num) {
            token.Num = num;
        }
        token.Tag = token.Pre();
        ss.push(token);
    }
    string ans = "";
    while (!ss.empty()) {
        Token top = ss.top();
        ss.pop();
        top.Tag = top.Tag + ans + top.Last();
        string tmp = top.Tag;
        for (int i = 2; i <= top.Num; i ++) {
            top.Tag += tmp;
        }
        ans = top.Tag;
    }
    cout << ans << endl;
}

void work()
{
    cin >> line;
    gao();
}
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

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

190

191

192

193

194

195

196

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

> File Name: 1005.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2014¿?08¿?22¿? ¿?¿?¿? 00¿?18¿?14¿?

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

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

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define eps 1e-8

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 T;

string line;

struct Token {

string Name;

string Id;

vector<string> Class;

int Num;

string Tag;

Token() {

Name = Id = Tag = "";

Num = 0;

Class.clear();

}

string Pre() {

if (Name == "(" || Name == "") {

return "";

}

string ans = "<" + Name;

if (Id != "") {

ans += " id=\"" + Id + "\"";

}

if (Class.size()) {

ans += " class=\"";

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

if (i) ans += " ";

ans += Class[i];

}

ans += "\"";

}

ans += ">";

return ans;

}

string Last() {

if (Name == "(" || Name == "") {

return "";

}

return "</" + Name + ">";

}

};

stack <Token> ss;

void gao()

{

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

Token token = Token();

int _Id = 0, _Class = 0, _Num = 0, num = 0;

for (int i = 0; i < line.length(); i ++) {

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

if (token.Name != "") {

if (_Num) {

token.Num = num;

num = 0;

}

token.Tag = token.Pre();

ss.push(token);

}

num = _Num = _Class = _Id = 0;

token = Token();

token.Name = "(";

ss.push(token);

token = Token();

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

if (token.Name != "") {

if (_Num) {

token.Num = num;

}

token.Tag = token.Pre();

ss.push(token);

}

num = _Num = _Class = _Id = 0;

token = Token();

string s = "";

while (!ss.empty()) {

Token tmp = ss.top();

ss.pop();

if (tmp.Name == "(") {

tmp.Tag = s;

tmp.Name = "";

ss.push(tmp);

break;

}

tmp.Tag += s;

tmp.Tag += tmp.Last();

string t = tmp.Tag;

for (int i = 2; i <= tmp.Num; i ++) {

tmp.Tag = tmp.Tag + t;

}

s = tmp.Tag;

}

} else if (line[i] == '*') {

_Num = 1;

num = _Class = _Id = 0;

} else if (line[i] == '#') {

_Id = 1;

_Class = _Num = num = 0;

} else if (line[i] == '.') {

_Class = 1;

_Num = _Id = num = 0;

token.Class.pb("");

} else if (line[i] == '>') {

if (token.Name != "") {

if (_Num) {

token.Num = num;

}

token.Tag = token.Pre();

num = _Num = _Class = _Id = 0;

ss.push(token);

}

token = Token();

} else {

if (_Num) {

num = num * 10 + line[i] - '0';

} else if (_Id) {

token.Id += line[i];

} else if (_Class) {

token.Class[token.Class.size() - 1] += line[i];

} else {

token.Name += line[i];

token.Num = 1;

}

if (token.Name != "") {

if (_Num) {

token.Num = num;

}

token.Tag = token.Pre();

ss.push(token);

}

string ans = "";

while (!ss.empty()) {

Token top = ss.top();

ss.pop();

top.Tag = top.Tag + ans + top.Last();

string tmp = top.Tag;

for (int i = 2; i <= top.Num; i ++) {

top.Tag += tmp;

}

ans = top.Tag;

}

cout << ans << endl;

}

void work()

{

cin >> line;

gao();

}

int main()

{

scanf("%d", &T);

while (T --) {

work();

}

return 0;

}

1006

矩阵乘法，求 $(A*B)^{N^2}$ ，转化一下， $A * (B * A) ^{N^2-1} * B$

/*************************************************************************
	> File Name: 1006.cpp
	> Author: skt
	> Mail: sktsxy@gmail.com 
	> Created Time: 2014年08月19日 星期二 14时06分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 <ctime>
#include <memory.h>
#include <cassert>
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define eps 1e-8
#define MAXN 1005
#pragma comment(linker,"/STACK:102400000,102400000")
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, K, A[MAXN][10], B[10][MAXN], C[15][15], ans[15][15], tmp[15][15];
int A1[MAXN][MAXN], B1[MAXN][MAXN];

void Matrix_Power(int a[][15], int b[][15])
{
    int c[MAXN][MAXN] = {};
    for (int i = 1; i <= K; i ++) {
        for (int j = 1; j <= K; j ++) {
            if (a[i][j]) {
                for (int k = 1; k <= K; k ++) {
                    c[i][k] += a[i][j] * b[j][k];
                }
            }
        }
    }
    for (int i = 1; i <= K; i ++) {
        for (int j = 1; j <= K; j ++) {
            a[i][j] = c[i][j] % 6;
        }
    }
}

void Power(int a1[][15], int m) {
    for (int i = 1; i <= K; i ++) {
        for (int j = 1; j <= K; j ++) {
            tmp[i][j] = a1[i][j];
        }
    }
    memset(ans, 0, sizeof(ans));
    for (int i = 1; i <= K; i ++) ans[i][i] = 1;
    while (m) {
        if (m & 1) Matrix_Power(ans, tmp);
        Matrix_Power(tmp, tmp);
        m >>= 1;
    }
    for (int i = 1; i <= K; i ++) {
        for (int j = 1; j <= K; j ++) {
            a1[i][j] = ans[i][j];
        }
    }
}

void work()
{
    memset(C, 0, sizeof(C));
    for (int i = 1; i <= N; i ++) {
        for (int j = 1; j <= K; j ++) {
            scanf("%d", &A[i][j]);
        }
    }
    for (int i = 1; i <= K; i ++) {
        for (int j = 1; j <= N; j ++) {
            scanf("%d", &B[i][j]);
        }
    }
    memset(C, 0, sizeof(C));
    for (int i = 1; i <= K; i ++) {
        for (int j = 1; j <= K; j ++) {
            for (int k = 1; k <= N; k ++) {
                C[i][j] += B[i][k] * A[k][j];
            }
            C[i][j] %= 6;
        }
    }
    Power(C, N * N - 1);
    memset(A1, 0, sizeof(A1));
    memset(B1, 0, sizeof(B1));
    for (int i = 1; i <= N; i ++) {
        for (int j = 1; j <= K; j ++) {
            for (int k = 1; k <= K; k ++) {
                A1[i][j] += A[i][k] * C[k][j];
            }
            A1[i][j] %= 6;
        }
    }
    int last = 0;
    for (int i = 1; i <= N; i ++) {
        for (int j = 1; j <= N; j ++) {
            for (int k = 1; k <= K; k ++) {
                B1[i][j] += A1[i][k] * B[k][j]; 
            }
            B1[i][j] %= 6;
            last += B1[i][j];
        }
    }
    printf("%d\n", last);
}
int main()
{
    while (scanf("%d %d", &N, &K) != EOF) {
        if (N == 0 && K == 0) break;
        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: 1006.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2014年08月19日星期二 14时06分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 <ctime>

#include <memory.h>

#include <cassert>

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define eps 1e-8

#define MAXN 1005

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

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, K, A[MAXN][10], B[10][MAXN], C[15][15], ans[15][15], tmp[15][15];

int A1[MAXN][MAXN], B1[MAXN][MAXN];

void Matrix_Power(int a[][15], int b[][15])

{

int c[MAXN][MAXN] = {};

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

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

if (a[i][j]) {

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

c[i][k] += a[i][j] * b[j][k];

}

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

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

a[i][j] = c[i][j] % 6;

}

void Power(int a1[][15], int m) {

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

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

tmp[i][j] = a1[i][j];

}

memset(ans, 0, sizeof(ans));

for (int i = 1; i <= K; i ++) ans[i][i] = 1;

while (m) {

if (m & 1) Matrix_Power(ans, tmp);

Matrix_Power(tmp, tmp);

m >>= 1;

}

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

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

a1[i][j] = ans[i][j];

}

void work()

{

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

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

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

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

}

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

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

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

}

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

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

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

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

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

}

C[i][j] %= 6;

}

Power(C, N * N - 1);

memset(A1, 0, sizeof(A1));

memset(B1, 0, sizeof(B1));

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

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

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

A1[i][j] += A[i][k] * C[k][j];

}

A1[i][j] %= 6;

}

int last = 0;

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

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

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

B1[i][j] += A1[i][k] * B[k][j];

}

B1[i][j] %= 6;

last += B1[i][j];

}

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

}

int main()

{

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

if (N == 0 && K == 0) break;

work();

}

return 0;

}

1009

DFS一下

/*************************************************************************
	> File Name: 1009.cpp
	> Author: skt
	> Mail: sktsxy@gmail.com 
	> Created Time: 2014年08月19日 星期二 13时04分46秒
 ************************************************************************/

#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>
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define eps 1e-8
#define MAXN 20
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 T, avg, N, a[MAXN], p1[MAXN], p2[MAXN];
int scale[] = {85, 80, 75, 70, 60};
int all[] = {15, 4, 4, 4, 9};
double gpa[] = {4.0, 3.5, 3.0, 2.5, 2.0};
double ans1, ans2;

void dfs(int pnt, int sum, int allow, int high) {
    if ((N - pnt) * 60 > sum) {
        return ;
    }
    if (pnt == N) {
        if (sum <= allow) {
            double ans = 0;
            for (int i = 0; i < pnt; i ++) {
                ans += gpa[p1[i]];
            }
            ans1 = Min(ans1, ans);
            ans2 = Max(ans2, ans);
        }
        return ;
    }
    for (int i = high; i <= 4; i ++) {
        p1[pnt] = i;     
        dfs(pnt + 1, sum - scale[i], allow + all[i], i);
    }
}

void work()
{
    scanf("%d %d", &avg, &N);
    ans1 = 1e18, ans2 = 0;
    dfs(0, avg * N, 0, 0);
    printf("%.4lf %.4lf\n", ans1 / (double)N, ans2 / (double)N);
}
int main()
{
    scanf("%d", &T);
    while (T --) {
        work();
    }
    return 0;
}

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

> File Name: 1009.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2014年08月19日星期二 13时04分46秒

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

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

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define eps 1e-8

#define MAXN 20

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 T, avg, N, a[MAXN], p1[MAXN], p2[MAXN];

int scale[] = {85, 80, 75, 70, 60};

int all[] = {15, 4, 4, 4, 9};

double gpa[] = {4.0, 3.5, 3.0, 2.5, 2.0};

double ans1, ans2;

void dfs(int pnt, int sum, int allow, int high) {

if ((N - pnt) * 60 > sum) {

return ;

}

if (pnt == N) {

if (sum <= allow) {

double ans = 0;

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

ans += gpa[p1[i]];

}

ans1 = Min(ans1, ans);

ans2 = Max(ans2, ans);

}

return ;

}

for (int i = high; i <= 4; i ++) {

p1[pnt] = i;

dfs(pnt + 1, sum - scale[i], allow + all[i], i);

}

void work()

{

scanf("%d %d", &avg, &N);

ans1 = 1e18, ans2 = 0;

dfs(0, avg * N, 0, 0);

printf("%.4lf %.4lf\n", ans1 / (double)N, ans2 / (double)N);

}

int main()

{

scanf("%d", &T);

while (T --) {

work();

}

return 0;

}

1010

积分题，没想到黄大队WA了20多次。看WA了那么多次，我就没看这题，结果发现就是简单的求积分。

$dh = \sqrt{V_2^2 - \frac{V_1^2 h^2}{R^2}}dt$

$dt = \frac{1}{\sqrt{V_2^2 - \frac{V_1^2 h^2}{R^2}}}dh$

/*************************************************************************
	> File Name: 1010.cpp
	> Author: skt
	> Mail: sktsxy@gmail.com 
	> Created Time: 2014年08月20日 星期三 00时14分00秒
 ************************************************************************/

#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>
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define eps 1e-8
#define PI acos(-1.0)
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 T;
double V1, V2, R, D, w, x;

void work()
{
    scanf("%lf %lf %lf %lf", &V1, &V2, &R, &D);
    w = V1 / R;
    double t = asin(w * R / V2) / w;
    x = V2 * t;
    if (x <= D) {
        printf("Wake up to code\n");
    } else {
        printf("Why give up treatment\n");
    }
}
int main()
{
    scanf("%d", &T);
    while (T --) {
        work();
    }
    return 0;
}

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

> File Name: 1010.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2014年08月20日星期三 00时14分00秒

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

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

using namespace std;

#define LL long long

#define pb push_back

#define mp make_pair

#define eps 1e-8

#define PI acos(-1.0)

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 T;

double V1, V2, R, D, w, x;

void work()

{

scanf("%lf %lf %lf %lf", &V1, &V2, &R, &D);

w = V1 / R;

double t = asin(w * R / V2) / w;

x = V2 * t;

if (x <= D) {

printf("Wake up to code\n");

} else {

printf("Why give up treatment\n");

}

int main()

{

scanf("%d", &T);

while (T --) {

work();

}

return 0;

}

1011

水题，被黄大队WA了一次。。

/*************************************************************************
	> File Name: 1011.cpp
	> Author: skt
	> Mail: sktsxy@gmail.com 
	> Created Time: 2014年08月19日 星期二 17时13分30秒
 ************************************************************************/

#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>
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 N, M, K, l, r, d;
LL l1[MAXN], add[MAXN], h1[MAXN];

struct Node {
    int L, D;

    bool operator < (const Node a) const {
        return L < a.L;
    }
} p1[MAXN], p2[MAXN];

struct ENode {
    LL h;
    int x;
    bool operator < (const ENode a) const {
        return x < a.x;
    }
} e[MAXN];

void work()
{
    memset(l1, 0, sizeof(l1));
    memset(h1, 0, sizeof(h1));
    memset(add, 0, sizeof(add));
    scanf("%d", &M);
    for (int i = 1; i <= M; i ++) {
        scanf("%d %d %d", &l, &r, &d);
        p1[i].L = l, p1[i].D = d;
        p2[i].L = r + 1, p2[i].D = -d;
    }
    scanf("%d", &K);
    for (int i = 1; i <= K; i ++) {
        scanf("%I64d %d", &e[i].h, &e[i].x);
    }
    sort(p1 + 1, p1 + 1 + M);
    sort(p2 + 1, p2 + 1 + M);
    sort(e + 1, e + 1 + K);
    for (int i = 1; i <= M; i ++) {
        l1[p1[i].L] += p1[i].D;
    }
    for (int i = 1; i <= M; i ++) {
        l1[p2[i].L] += p2[i].D;
    }
    for (int i = 1; i <= N; i ++) {
        add[i] = add[i-1] + l1[i];
    }
    for (int i = N; i >= 1; i --) {
        h1[i] = h1[i + 1] + add[i];
    }
    int ans = 0;
    for (int i = 1; i <= K; i ++) {
        if (h1[e[i].x] < e[i].h) {
            ans ++;
        }
    }
    printf("%d\n", ans);
}
int main()
{
    while (scanf("%d", &N) != EOF) {
        if (N == 0) break;
        work();
    }
    return 0;
}

100

101

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

> File Name: 1011.cpp

> Author: skt

> Mail: sktsxy@gmail.com

> Created Time: 2014年08月19日星期二 17时13分30秒

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

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

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 N, M, K, l, r, d;

LL l1[MAXN], add[MAXN], h1[MAXN];

struct Node {

int L, D;

bool operator < (const Node a) const {

return L < a.L;

}

} p1[MAXN], p2[MAXN];

struct ENode {

LL h;

int x;

bool operator < (const ENode a) const {

return x < a.x;

}

} e[MAXN];

void work()

{

memset(l1, 0, sizeof(l1));

memset(h1, 0, sizeof(h1));

memset(add, 0, sizeof(add));

scanf("%d", &M);

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

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

p1[i].L = l, p1[i].D = d;

p2[i].L = r + 1, p2[i].D = -d;

}

scanf("%d", &K);

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

scanf("%I64d %d", &e[i].h, &e[i].x);

}

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

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

sort(e + 1, e + 1 + K);

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

l1[p1[i].L] += p1[i].D;

}

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

l1[p2[i].L] += p2[i].D;

}

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

add[i] = add[i-1] + l1[i];

}

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

h1[i] = h1[i + 1] + add[i];

}

int ans = 0;

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

if (h1[e[i].x] < e[i].h) {

ans ++;

}

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

}

int main()

{

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

if (N == 0) break;

work();

}

return 0;

}

StillKeepTry

我是依旧在努力

2014 Multi-University Training Contest 9

1001

1002

1005

1006

1009

1010

1011

Leave a Reply Cancel reply