2015 HSYIT代码暂存楼[0]

smileandyxu · 发表于 2016-4-19 20:20:15

P1882 [NOIP2000P4]单词接龙[code]#include <iostream>
#include <string>
using namespace std;
bool C[21][21]; ///i包含j C[i][j] || C[j][i] ...
int B[21][21];
string S[21];
int A[51];
int P[51];
char c;
int n, tmp, ans;
bool can(int i)
{
bool flag = false;
for (int j = 1; j <= n && (!flag); ++j)
if (P[j] <= 1 && B[A[i - 1]][j] > 0 && (!C[A[i - 1]][j]) && (!C[j][A[i - 1]]))
flag = true;
return flag;
}
void dfs(int i)
{
for (int k = 0; k < i; ++k) {
cout << S[A[k]] << " ";
cout << endl;
}
if (!can(i))
if (tmp > ans)
ans = tmp;
else {
for (int j = 1; j <= n; ++j) {
if (P[j] <= 1 && B[A[i - 1]][j] > 0 && (!C[A[i - 1]][j]) && (!C[j][A[i - 1]])) {
++P[j];
A[i] = j;
tmp += (S[j].size() - B[i][j]);
dfs(i + 1);
tmp -= (S[j].size() - B[i][j]);
--P[j];
}
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> S[i];
cin >> c;
for (int i = 1; i <= n - 1; ++i) {
for (int j = i + 1; j <= n; ++j) {
for (int k = 1; k <= S[i].size() - 1 && k <= S[j].size() - 1; ++k) {
if (S[i].substr(S[i].size() - k, k) == S[j].substr(0, k))
B[i][j] = k;
if (S[j].substr(S[j].size() - k, k) == S[i].substr(0, k))
B[j][i] = k;
}
if (S[i].size() >= S[j].size())
for (int k = 0; k + S[j].size() <= S[i].size(); ++k)
if (S[i].substr(k, S[j].size()) == S[j])
C[i][j] = true;
else
for (int k = 0; k + S[i].size() <= S[j].size(); ++k)
if (S[j].substr(k, S[i].size()) == S[i])
C[j][i] = true;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cout << B[i][j] << " ";
}
cout << endl;
}
for (int i = 1; i <= n; ++i) {
if (S[i][0] == c) {
A[0] = i;
tmp = S[i].size();
++P[i];
dfs(1);
--P[i];
}
}
cout << ans;
return 0;
}

复制代码

[/code]

smileandyxu · 发表于 2016-4-23 18:36:10

木棍分割

#include <cstdio>
#include <iostream>
#include <cctype>
#define INF 0x7fffffff
using namespace std;
inline int getint()
{
char c = getchar();
while (!isdigit(c))
c = getchar();
int x = 0;
while (isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
int F[50001][2];
int C[50001][2];
int A[50001];
int S[50001];
int m, n, l, d, r, len, ans;
int main()
{
n = getint();
m = getint();
for (int i = 1; i <= n; ++i) {
A[i] = getint();
S[i] = S[i - 1] + A[i];
if (A[i] > l)
l = A[i];
}
r = S[n];
len = INF;
d = (l + r) / 2;
while (l <= r) {
d = (l + r) / 2;
int cnt = 0;
int tmp = 0;
int maxlen = 0;
for (int i = 1; i <= n; ++i) {
if (tmp + A[i] > d) {
if (tmp > maxlen)
maxlen = tmp;
tmp = A[i];
++cnt;
}
else
tmp += A[i];
}
if (tmp > maxlen)
maxlen = tmp;
//cout << cnt << endl;
if (cnt <= m) {
if (maxlen < len)
len = maxlen;
r = d - 1;
}
else
l = d + 1;
}
printf("%d\40", len);
for (int i = 1; i <= n; ++i) {
if (S[i] <= len)
F[i][0] = 1;
}
cout << 0 << ":" << endl;
for (int i = 1; i <= n; ++i)
cout << F[i][0] << " ";
cout << endl;
for (int j = 1; j <= m; ++j) {
int p = j % 2;
int tmp = 0;
int pos = 1;
for (int i = 1; i <= j; ++i)
F[i][p ^ 1] = 0;
for (int i = j + 1; i <= n; ++i) {
for (int k = pos; k < i; ++k) {
if (S[i] - S[k] <= len) {
tmp += F[k][p ^ 1];
pos = k;
}
else
tmp -= F[k][p ^ 1];
}
F[i][p] = tmp;
tmp += F[i][p ^ 1];
}
cout << j << ":" << endl;
for (int i = 1; i <= n; ++i)
cout << F[i][p] << " ";
cout << endl;
}
/*for (int i = 1; i <= n; ++i)
printf("%d\40", F[i][m % 2]);*/
printf("\n");
printf("%d", ans);
return 0;
}

复制代码

smileandyxu · 发表于 2016-4-23 20:02:11

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;
struct edge {
int end;
int len;
};
struct data {
string way;
int len;
bool operator<(const data &x) const {
return len > x.len;
}
};
priority_queue<data> Q;
vector<edge> V[51];
data w;
bool B[51];
int A[51];
int m, n, k, a, b, cnt;
string change(int x)
{
string s;
do {
s += char((x % 10) + '0');
x /= 10;
} while (x > 0);
reverse(s.begin(), s.end());
return s;
}
void put(int x)
{
w.way += change(x);
w.way += '-';
}
void del()
{
string s = w.way;
int i = s.size() - 2;
while (s[i] != '-' && i >= 0);
--i;
w.way = s.substr(0, i + 1);
}
void add(int u, int v, int l)
{
edge tmp;
tmp.end = v;
tmp.len = l;
V[u].push_back(tmp);
}
void dfs(int p)
{
if (p == b) {
cout << w.way << endl;
Q.push(w);
++cnt;
}
else {
for (int i = 0; i != V[p].size(); ++i) {
if (!B[V[p][i].end]) {
B[V[p][i].end] = true;
put(V[p][i].end);
w.len += V[p][i].len;
dfs(V[p][i].end);
B[V[p][i].end] = false;
w.len -= V[p][i].len;
del();
}
}
}
}
int main()
{
cin >> n >> m >> k >> a >> b;
for (int i = 0, u, v, l; i != m; ++i) {
cin >> u >> v >> l;
add(u, v, l);
}
put(a);
B[a] = true;
dfs(a);
if (cnt < k)
cout << "No";
else {
for (int i = 1; i <= k - 1; ++i)
Q.pop();
cout << Q.top().way;
}
return 0;
}

复制代码

smileandyxu · 发表于 2016-4-30 20:46:26

#include <iostream>
#include <algorithm>
#include <vector>
#define INF 0x7fffffff
using namespace std;
inline int abs(int x)
{
return (x > 0 ? x : -x);
}
vector<int> V;
bool B[251];
int A[251];
int P[251];
int n, k, a, b, tmp, ans;
void cmn(int i)
{
if (i == k)
V.push_back(tmp);
else {
for (int j = (i == 0 ? 0 : P[i - 1]); j != n; ++j) {
if (!B[j]) {
B[j] = true;
P[i] = j;
tmp += A[j];
cmn(i + 1);
tmp -= A[j];
B[j] = false;
}
}
}
}
int main()
{
cin >> n >> k >> a >> b;
for (int i = 0; i != n; ++i)
cin >> A[i];
cmn(0);
sort(V.begin(), V.end());
for (int i = a; i <= b; ++i) {
vector<int>::iterator iter = lower_bound(V.begin(), V.end(), i);
tmp = INF;
if (iter != V.end()) {
tmp = min(tmp, abs(*iter - i));
}
--iter;
if (iter != V.end()) {
tmp = min(tmp, abs(*iter - i));
}
ans = max(ans, tmp);
}
cout << ans;
return 0;
}

复制代码

smileandyxu · 发表于 2016-4-30 21:49:22

#include <iostream>
#include <string>
#define INF 0x7fffffff
using namespace std;
struct stack {
char C[500001];
int top = 0;
int size() const {
return top;
}
bool empty() const {
return top == 0;
}
void pop() {
--top;
}
void push(char c) {
C[top] = c;
++top;
}
};
stack S;
string s;
int tot, tmp;
void dfs(int i)
{
if (i == s.size()) {
if (S.empty()) {
++tot;
if (tot == 1000000009)
tot = 0;
}
}
else if (s[i] == '?') {
if (!(!S.empty() && s[i - 1] == 'W')) {
S.push('B');
++tmp;
s[i] = 'B';
dfs(i + 1);
s[i] = '?';
--tmp;
S.pop();
}
if (!S.empty()) {
S.pop();
s[i] = 'W';
dfs(i + 1);
s[i] = '?';
S.push('B');
}
}
else {
if (s[i] == 'B') {
if ((!S.empty() && s[i - 1] == 'W') || tmp >= s.size() / 2)
return;
S.push('B');
++tmp;
dfs(i + 1);
S.pop();
--tmp;
}
else {
if (S.empty())
return;
S.pop();
dfs(i + 1);
S.push('B');
}
}
}
int main()
{
cin >> s;
if (s[0] == 'W')
cout << 0;
else {
S.push('B');
s[0] = 'B';
tmp = 1;
dfs(1);
cout << tot;
}
return 0;
}

复制代码

smileandyxu · 发表于 2016-5-3 13:51:16

#include <iostream>
#include <cstdio>
#include <cctype>
#define father(x) (x >> 1)
#define lchild(x) (x << 1)
#define rchild(x) (x << 1 | 1)
#define isleft(x) (x == ((x >> 1) << 1))
#define isright(x) (x == ((x >> 1) << 1) | 1)
#define INF 0x7fffffff
using namespace std;
inline int getint()
{
char c = getchar();
while (!isdigit(c))
c = getchar();
int x = 0;
while (isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
inline int max(int x, int y)
{
return (x > y ? x : y);
}
int T[4000001]; ///maximum
int A[4000001]; ///add
int L, R;
int m, n;
bool found;
int value(int x)
{
int a = T[x];
x = father(x);
while (x >= 1) {
a += A[x];
x = father(x);
}
return a;
}
void input()
{
n = getint();
m = getint();
L = 1;
while (L < n)
L <<= 1;
R = L + n - 1;
found = false;
for (int i = 0; i != L; ++i)
T[L + i] = -INF;
for (int i = 0; i != n; ++i) {
T[L + i] = getint();
T[L + i] = -T[L + i];
}
}
void build()
{
for (int i = L - 1; i >= 1; --i)
T[i] = max(T[lchild(i)], T[rchild(i)]);
}
bool add(int left, int right, int d)
{
int l = left;
int r = right;
bool flag = true;
while (l < r && flag) {
cout << l << " " << r << " " << value(l) + d << " " << value(r) + d << endl;
if (isleft(l) && isright(r)) {
l = father(l);
r = father(r);
}
else {
if (isright(l)) {
if (value(l) + d > 0)
flag = false;
l = father(l) + 1;
}
else {
l = father(l);
}
if (isleft(r)) {
if (value(r) + d > 0)
flag = false;
r = father(r) - 1;
}
else {
r = father(r);
}
}
}
if (l == r && value(l) + d > 0)
flag = false;
l = left;
r = right;
while (l < r && flag) {
if (isleft(l) && isright(r)) {
l = father(l);
r = father(r);
}
else if (isright(l)) {
A[l] += d;
l = father(l) + 1;
}
else if (isleft(r)) {
A[r] += d;
r = father(r) - 1;
}
}
if (l == r)
A[l] += d;
return flag;
}
int main()
{
input();
build();
for (int i = 0, d, s, t; i != m; ++i) {
d = getint();
s = getint();
t = getint();
if (!found) {
if (!add(L + s - 1, L + t - 1, d)) {
if (!found)
printf("-1\n");
found = true;
printf("%d\n", i + 1);
}
}
}
if (!found)
printf("0");
return 0;
}

复制代码

smileandyxu · 发表于 2016-5-3 15:54:59

#include <iostream>
#include <string>
using namespace std;
struct num {
int A[200] = {0};
int LEN = 200;
num operator+(num y)
{
int x = 0;
for (int i = 0; i != LEN; ++i) {
A[i] += y.A[i];
A[i] += x;
x = A[i] / 10;
A[i] %= 10;
}
return *this;
}
num operator*(int y)
{
int x = 0;
for (int i = 0; i != LEN; ++i) {
A[i] *= y;
A[i] += x;
x = A[i] / 10;
A[i] %= 10;
}
return *this;
}
void operator=(int y)
{
for (int i = 0; i != LEN && y > 0; ++i) {
A[i] = y % 10;
y /= 10;
}
}
void operator=(num y)
{
for (int i = 0; i != LEN; ++i)
A[i] = y.A[i];
}
};
num max(num x, num y)
{
int flag = 0;
for (int i = x.LEN - 1; i >= 0 && flag == 0; --i) {
if (x.A[i] > y.A[i])
flag = 1;
else
flag = -1;
}
return (flag == 1 ? x : y);
}
void input(num &x)
{
string tmp;
cin >> tmp;
for (int i = 0; i != tmp.size(); ++i)
x.A[i] = tmp[tmp.size() - i - 1] - '0';
}
void output(num x)
{
int i = x.LEN - 1;
while (i > 0 && x.A[i] == 0)
--i;
while (i >= 0) {
cout << x.A[i];
--i;
}
}
num F[101][101];
num A[101];
num ans;
int m, n;
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
input(A[j]);
for (int j = 1; j <= m; ++j)
for (int k = 1; k <= m; ++k)
F[j][k] = 0;
for (int l = 1; l <= m; ++l) {
for (int j = 1; j + l - 1 <= m; ++j) {
F[j][j + l - 1] = max(F[j][j + l - 2] * 2 + A[j + l - 1], F[j + 1][j + l - 1] * 2 + A[j]);
}
}
ans = ans + F[1][m];
}
output(ans * 2);
return 0;
}

复制代码

smileandyxu · 发表于 2016-5-10 20:16:11

#include <iostream>
#include <stack>
#define father(x) (x >> 1)
#define lchild(x) (x << 1)
#define rchild(x) ((x << 1) | 1)
#define isleft(x) (x == (x >> 1) << 1)
#define isright(x) (x == ((x >> 1) << 1) | 1)
using namespace std;
int T[800001];
int A[800001];
int L, R;
int n, q;
int value(int x)
{
int v = 0;
while (x >= 1) {
v += A[x];
x = father(x);
}
return v;
}
int query(int l, int r)
{
int v = 0;
while (l <= r) {
if (isleft(l) && isright(r)) {
l = father(l);
r = father(r);
}
else {
if (isright(l)) {
v += value(l) + T[l];
l = father(l) + 1;
}
else
l = father(l);
if (isleft(r)) {
v += value(r) + T[r];
r = father(r) - 1;
}
else
r = father(r);
}
}
}
void update(int x)
{
do {
x = father(x);
T[x] = T[lchild(x)] + T[rchild(x)];
} while (x >= 1);
}
void maintain(int x)
{
stack<int> S;
while (x > 1) {
S.push(isright(x));
x = father(x);
}
while (!S.empty()) {
A[lchild(x)] += A[x];
A[rchild(x)] += A[x];
A[x] = 0;
x = lchild(x) | (S.top());
S.pop();
}
}
void add(int l, int r, int x)
{
l = L + l - 1;
r = L + r - 1;
while (l <= r) {
if (isleft(l) && isright(r)) {
l = father(l);
r = father(r);
}
else {
if (isright(l)) {
A[l] += x;
maintain(l);
l = father(l) + 1;
}
else
l = father(l);
if (isleft(r)) {
A[r] += x;
maintain(r);
r = father(r) - 1;
}
else
r = father(r);
}
}
}
int main()
{
cin >> n;
L = 1;
while (L < n)
L <<= 1;
R = L * 2 - 1;
for (int i = 0; i != n; ++i) {
cin >> T[L + i];
update(L + i);
}
for (int i = 0, p, a, b, x; i != q; ++i) {
cin >> p >> a >> b;
if (p == 1) {
cin >> x;
add(a, b, x);
}
if (p == 2) {
cout << query(a, b) << endl;
}
}
return 0;
}

复制代码

smileandyxu · 发表于 2016-5-15 16:48:24

#include <iostream>
#include <stack>
#define father(x) (x >> 1)
#define lchild(x) (x << 1)
#define rchild(x) ((x << 1) | 1)
#define isleft(x) (x == ((x >> 1) << 1))
#define isright(x) (x == (((x >> 1) << 1) | 1))
using namespace std;
int T[800001];
int A[800001];
int L, R;
int n, q;
int height(int x)
{
int len = 0;
while (x >= 1) {
x = father(x);
++len;
}
return len - 1;
}
int width(int x)
{
int len = 1;
while (height(L) > height(x)) {
len <<= 1;
x = lchild(x);
}
return len;
}
void update(int x)
{
do {
x = father(x);
T[x] = T[lchild(x)] + T[rchild(x)];
} while (x >= 1);
}
void maintain(int x)
{
stack<int> S;
while (x > 1) {
S.push(isright(x));
x = father(x);
}
while (!S.empty()) {
A[lchild(x)] += A[x];
A[rchild(x)] += A[x];
T[lchild(x)] += A[x] * width(lchild(x));
T[rchild(x)] += A[x] * width(rchild(x));
A[x] = 0;
x = lchild(x) | (S.top());
S.pop();
}
}
void add(int l, int r, int x)
{
l = L + l - 1;
r = L + r - 1;
while (l <= r) {
if (isleft(l) && isright(r)) {
l = father(l);
r = father(r);
}
else {
if (isright(l)) {
A[l] += x;
T[l] += x * width(l);
update(l);
l = father(l) + 1;
}
else
l = father(l);
if (isleft(r)) {
A[r] += x;
T[r] += x * width(r);
for (int j = 1; j <= R; ++j)
update(r);
r = father(r) - 1;
}
else
r = father(r);
}
}
}
int query(int l, int r)
{
l = L + l - 1;
r = L + r - 1;
int v = 0;
while (l <= r) {
if (isleft(l) && isright(r)) {
l = father(l);
r = father(r);
}
else {
if (isright(l)) {
maintain(l);
v += T[l];
l = father(l) + 1;
}
else
l = father(l);
if (isleft(r)) {
maintain(r);
v += T[r];
r = father(r) - 1;
}
else
r = father(r);
}
}
}
int main()
{
cin >> n;
L = 1;
while (L < n)
L <<= 1;
R = L * 2 - 1;
for (int i = 0; i != n; ++i) {
cin >> T[L + i];
update(L + i);
}
cin >> q;
for (int i = 0, p, a, b, x; i != q; ++i) {
cin >> p >> a >> b;
if (p == 1) {
cin >> x;
add(a, b, x);
}
if (p == 2) {
cout << query(a, b) << endl;
}
}
return 0;
}

复制代码

smileandyxu · 发表于 2016-5-16 13:54:08

#include <iostream>
#include <cstdio>
#include <cctype>
#include <stack>
#define father(x) (x >> 1)
#define lchild(x) (x << 1)
#define rchild(x) ((x << 1) | 1)
#define isleft(x) (x == ((x >> 1) << 1))
#define isright(x) (x == (((x >> 1) << 1) | 1))
using namespace std;
inline int getint()
{
char c = getchar();
while (!isdigit(c))
c = getchar();
int x = 0;
while (isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
inline void putint(int x)
{
int tmp[20];
int i = 0;
do {
tmp[i] = x % 10;
x /= 10;
++i;
} while (x > 0);
--i;
while (i >= 0) {
putchar(tmp[i] + '0');
--i;
}
putchar('\n');
}
int T[800001];
int A[800001];
int L, R;
int n, q;
int height(int x)
{
int len = 0;
while (x >= 1) {
x = father(x);
++len;
}
return len - 1;
}
int width(int x)
{
int len = 1;
while (height(L) > height(x)) {
len <<= 1;
x = lchild(x);
}
return len;
}
void update(int x)
{
do {
x = father(x);
T[x] = T[lchild(x)] + T[rchild(x)];
} while (x > 1);
}
void maintain(int x)
{
stack<bool> S;
while (x > 1) {
S.push(isright(x));
x = father(x);
}
while (!S.empty()) {
A[lchild(x)] += A[x];
A[rchild(x)] += A[x];
T[lchild(x)] += A[x] * width(lchild(x));
T[rchild(x)] += A[x] * width(rchild(x));
A[x] = 0;
x = lchild(x) + int(S.top());
S.pop();
}
}
void add(int l, int r, int x)
{
l = L + l - 1;
r = L + r - 1;
while (l <= r) {
if (isleft(l) && isright(r)) {
l = father(l);
r = father(r);
}
else {
if (isright(l)) {
A[l] += x;
T[l] += x * width(l);
update(l);
l = father(l + 1);
}
else
l = father(l);
if (isleft(r)) {
A[r] += x;
T[r] += x * width(r);
update(r);
r = father(r - 1);
}
else
r = father(r);
}
}
}
int query(int l, int r)
{
l = L + l - 1;
r = L + r - 1;
int v = 0;
while (l <= r) {
if (isleft(l) && isright(r)) {
l = father(l);
r = father(r);
}
else {
if (isright(l)) {
maintain(l);
v += T[l];
l = father(l + 1);
}
else
l = father(l);
if (isleft(r)) {
maintain(r);
v += T[r];
r = father(r - 1);
}
else
r = father(r);
}
}
return v;
}
int main()
{
n = getint();
L = 1;
while (L < n)
L <<= 1;
R = L * 2 - 1;
for (int i = 0; i != n; ++i) {
T[L + i] = getint();
update(L + i);
}
q = getint();
for (int i = 0, p, a, b, x; i != q; ++i) {
p = getint();
a = getint();
b = getint();
if (p == 1) {
x = getint();
if (a != b)
add(a, b, x);
else {
T[L + a - 1] += x;
update(L + a - 1);
}
}
if (p == 2) {
putint(query(a, b));
}
}
return 0;
}
/*
12
9 899 6 5 7 2 4 4 3 59 78 116
6
1 1 9 11
2 6 9
1 7 7 4
1 5 8 10
2 5 7
2 1 12
*/
/*
12
9 899 6 5 7 2 4 4 3 59 78 116
5
1 1 9 11
2 6 9
1 5 8 10
2 5 7
2 1 12
*/

复制代码

		自动登录	找回密码
密码			立即注册