## 【POJ-1007】DNA Sorting【树状数组求逆序对】

【POJ-1007】DNA Sorting【树状数组求逆序对】

Solution:

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int LIM = 30;
int bitree[LIM];

void update(int pos) {
for (; pos < LIM; pos += pos & (-pos))
bitree[pos]++;
}

int query(int pos) {
int ret = 0;
for (; pos > 0; pos -= pos & (-pos))
ret += bitree[pos];
return ret;
}

struct Node {
string str;
int cnt;
bool operator < (const Node &n) const {
return cnt < n.cnt;
}
};
vector<Node> dat;

int main(void) {
ios::sync_with_stdio(false);
// cin.tie(NULL);
int n, m;
Node tmp;
while (cin >> n >> m) {
dat.clear();
for (int i = 0; i < m; i++) {
cin >> tmp.str;
tmp.cnt = 0;
memset(bitree, 0, sizeof bitree);
for (int j = n - 1; j >= 0; j--) {
tmp.cnt += query(tmp.str[j] - 'A' + 1);
// cout << query(tmp.str[j] - 'A' + 1) << endl;
update(tmp.str[j] - 'A' + 2);
}
dat.push_back(tmp);
}
sort(dat.begin(), dat.end());
for (int i = 0; i < m; i++) {
cout << dat[i].str << '\n';
// cout << dat[i].cnt << '\n';
}
}
return 0;
}


## 【CodeForces-258A】Little Elephant and Bits【贪心】

【CodeForces-258A】Little Elephant and Bits【贪心】

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
string str;
cin >> str;
int n = str.size();
string tmp = "", a, b;
bool flag = true;
int pos = 0;
for (int i = 0; i < n; i++) {
if (flag && str[i] == '0') {
flag = false;
continue;
}
if (str[i] == '1') pos = i;
tmp += str[i];
}
a = tmp;
tmp = "";
for (int i = 0; i < n; i++) {
if (i == pos && str[i] == '1') continue;
tmp += str[i];
}
b = tmp;
if (b.size() == n || a.size() != n && a > b)
cout << a << "\n";
else
cout << b << "\n";
return 0;
}


## 【CodeForces-1029D】Concatenated Multiples

【CodeForces-1029D】Concatenated Multiples

Solution:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
const int LIM = 2e5 + 10;
const int LENGTH = 11;
LL data[LIM], digits[LIM];
LL table[LENGTH];
vector<LL> remain[LENGTH];

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
LL n, k;
cin >> n >> k;
table[0] = 1;
for (int i = 1; i < LENGTH; i++)
table[i] = table[i - 1] * 10 % k;
for (int i = 0; i < n; i++) {
cin >> data[i];
LL tmp = data[i];
digits[i] = 0;
while (tmp) {
tmp /= 10, digits[i]++;
}
remain[digits[i]].push_back(data[i] % k);
}
for (int i = 0; i < LENGTH; i++)
sort(remain[i].begin(), remain[i].end());
LL ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < LENGTH; j++) {
LL rem = data[i] * table[j] % k;
vector<LL>::iterator l = lower_bound(remain[j].begin(), remain[j].end(), rem ? k - rem : 0);
vector<LL>::iterator r = upper_bound(remain[j].begin(), remain[j].end(), rem ? k - rem : 0);
ans += r - l;
if (j == digits[i] && (rem ? k - rem : 0) == data[i] % k) ans--;
}
}
cout << ans << "\n";
return 0;
}

rem ? k – rem : 0这个写起来太麻烦了，按照题解的做法，可以改成：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
const int LIM = 2e5 + 10;
const int LENGTH = 11;
LL data[LIM], digits[LIM];
LL table[LENGTH];
vector<LL> remain[LENGTH];

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
LL n, k;
cin >> n >> k;
table[0] = 1;
for (int i = 1; i < LENGTH; i++)
table[i] = table[i - 1] * 10 % k;
for (int i = 0; i < n; i++) {
cin >> data[i];
LL tmp = data[i];
digits[i] = 0;
while (tmp) {
tmp /= 10, digits[i]++;
}
remain[digits[i]].push_back(data[i] % k);
}
for (int i = 0; i < LENGTH; i++)
sort(remain[i].begin(), remain[i].end());
LL ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < LENGTH; j++) {
LL rem = data[i] * table[j] % k;
vector<LL>::iterator l = lower_bound(remain[j].begin(), remain[j].end(), (k - rem) % k);
vector<LL>::iterator r = upper_bound(remain[j].begin(), remain[j].end(), (k - rem) % k);
ans += r - l;
if (j == digits[i] && (rem + data[i] % k) % k == 0) ans--;
}
}
cout << ans << "\n";
return 0;
}


## 【CodeForces-807C】Success Rate【二分】

【CodeForces-807C】Success Rate【二分】

Solution:

#include <iostream>

using namespace std;

typedef long long LL;

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t;
LL x, y, p, q;
cin >> t;
while (t--) {
LL cnt = 0;
cin >> x >> y >> p >> q;
if ((p == q && x != y) || (p == 0 && x != 0)) {
cout << -1 << "\n";
continue;
}
LL diff = y - x;
LL d2 = q - p;
LL l = 1, r = 1e9;
while (l < r) {
LL mid = (l + r) >> 1;
if (mid * d2 < diff || mid * p < x) l = mid + 1;
else r = mid;
}
cout << l * (q - p) - y + x + l * p - x << "\n";
}
return 0;
}


## 【CodeForces-1029F】Multicolored Markers

【CodeForces-1029F】Multicolored Markers

Solution:

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

typedef long long LL;

inline LL mini(LL a, LL b) {return a < b ? a : b;}

vector<LL> boxa, boxb;

int main(void) {
LL a, b;
scanf("%lld%lld", &a, &b);
LL area = a + b;
LL lim = sqrt(a);
for (int i = 1; i <= lim; i++) {
if (a % i == 0) boxa.push_back(i);
}
lim = sqrt(b);
for (int i = 1; i <= lim; i++) {
if (b % i == 0) boxb.push_back(i);
}
lim = sqrt(area);
// cout << lim << endl;
LL ans = 0x3f3f3f3f3f3f3f3f;
for (int i = 1; i <= lim; i++) {
if (area % i) continue;
LL tmp = area / i;
for (int j = 0; j < boxa.size(); j++) {
if (boxa[j] <= i && a / boxa[j] <= tmp) {
ans = mini((i + tmp) * 2, ans);
break;
}
}
for (int j = 0; j < boxb.size(); j++) {
if (boxb[j] <= i && b / boxb[j] <= tmp) {
ans = mini((i + tmp) * 2, ans);
break;
}
}
}
printf("%lld\n", ans);
return 0;
}


## 【UVA-1597】Searching the Web【字符串拆分+STL的简单应用】

【UVA-1597】Searching the Web【字符串拆分+STL的简单应用】

Solution:

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <sstream>
#include <cctype>
#define DBG

using namespace std;

struct Centence {
string str;
int idx;
int pos;
};

vector<Centence> datas;
struct cmp {
bool operator()(const int a, const int b) const {
if (datas[a].idx != datas[b].idx) return datas[a].idx < datas[b].idx;
else if (datas[a].pos != datas[b].pos) return datas[a].pos < datas[b].pos;
return a < b;
}
};

inline void tolow(string &str) {
for (int i = 0; i < str.size(); i++)
if (isalpha(str[i])) str[i] = tolower(str[i]);
}
string in, out;
int cut_i;
inline bool cutstr(const string s) {
if (s != "") in = s, cut_i = 0;
if (cut_i == in.size()) return false;
out = "";
for (int cnt = 0; cut_i < in.size() && cnt < 2; cut_i++) {
if (cnt == 0 && isalpha(in[cut_i])) cnt = 1;
else if (cnt == 1 && !isalpha(in[cut_i])) cnt = 2;
if (cnt == 1) out += in[cut_i];
}
if (out == "") return false;
else return true;
}

map<string, set<int, cmp> > wordIdx;

int main(void) {
ios::sync_with_stdio(false);
// cin.tie(NULL);
int n, m;
cin >> n;
string tmp, t;
Centence c;
int cnt = 0;
getline(cin, tmp);
for (int i = 0; cnt < n; i++) {
getline(cin, tmp);
if (tmp == "**********") {
cnt++;
i--;
continue;
}
c.str = tmp, c.idx = cnt, c.pos = i;
datas.push_back(c);
stringstream ss;
ss << tmp;
while (ss >> t) {
tolow(t);
cutstr(t);
do {
if (!wordIdx.count(out)) wordIdx[out] = set<int, cmp>();
wordIdx[out].insert(datas.size() - 1);
} while (cutstr(""));
}
}
cin >> m;
string str;
getline(cin, str);
bool flag = true;
while (m--) {
getline(cin, str);
stringstream ss;
ss << str;
t = "";
ss >> tmp >> t;
flag = true;
if (t == "AND") {
ss >> t;
tolow(tmp), tolow(t);
set<int, cmp> sa, sb, sc;
sa = wordIdx[tmp], sb = wordIdx[t];
for (int x : sa)
for (int y : sb)
if (datas[x].idx == datas[y].idx) sc.insert(x), sc.insert(y);
int pre;
if (sc.empty()) cout << "Sorry, I found nothing.\n";
else pre = datas[*sc.begin()].idx;
for (auto x : sc) {
if (datas[x].idx != pre) cout << "----------\n";
pre = datas[x].idx;
cout << datas[x].str << "\n";
}
cout << "==========\n";
} else if (t == "OR") {
ss >> t;
tolow(tmp), tolow(t);
set<int, cmp> sa, sb;
sa = wordIdx[tmp], sb = wordIdx[t];
for (int x : sb) sa.insert(x);
int pre;
if (sa.empty()) cout << "Sorry, I found nothing.\n";
else pre = datas[*sa.begin()].idx;
for (auto x : sa) {
if (datas[x].idx != pre) cout << "----------\n";
pre = datas[x].idx;
cout << datas[x].str << "\n";
}
cout << "==========\n";
} else if (tmp == "NOT") {
tolow(t);
set<int, cmp> sa = wordIdx[t];
set<int> sb;
for (int x : sa) {
sb.insert(datas[x].idx);
}
int pre;
if (sb.size() == n) cout << "Sorry, I found nothing.\n";
else {
bool flag = false;
for (int i = 0; i < datas.size(); i++) {
if (sb.count(datas[i].idx)) continue;
if (flag && datas[i].idx != pre) cout << "----------\n";
else flag = true;
pre = datas[i].idx;
cout << datas[i].str << "\n";
}
}
cout << "==========\n";
} else {
tolow(tmp);
set<int, cmp> sa = wordIdx[tmp];
int pre;
if (sa.empty()) cout << "Sorry, I found nothing.\n";
else pre = datas[*sa.begin()].idx;
for (auto x : sa) {
if (datas[x].idx != pre) cout << "----------\n";
pre = datas[x].idx;
cout << datas[x].str << "\n";
}
cout << "==========\n";
flag = false;
}
}
return 0;
}


## 【codeforces-1020A】New Building for SIS

【codeforces-1020A】New Building for SIS

1.一栋楼上，不用考虑楼之间通道位置，直接去对应楼层。

2.楼与楼之间，如果两个位置都不在有通道的楼层，应当都寻找最近的通道楼层，耗时应当是两边各自到这个楼层的时间+穿越几栋楼的时间；如果任意一个位置在有通道的楼层，无论选择如何去目标位置，竖直方向最短距离都是两层的差值。

#include <iostream>
#include <cmath>

using namespace std;

inline bool inRange(int x, int a, int b) {
return x >= a && x <= b;
}

int main(void) {
int n, h, a, b, k, f1, t1, f2, t2;
scanf("%d%d%d%d%d", &n, &h, &a, &b, &k);
while (k--) {
scanf("%d%d%d%d", &t1, &f1, &t2, &f2);
if (t1 == t2) {
printf("%d\n", abs(f1 - f2));
} else {
if (inRange(f1, a, b) || inRange(f2, a, b))
printf("%d\n", abs(f1 - f2) + abs(t1 - t2));
else
printf("%d\n", min(abs(f1 - a) + abs(f2 - a), abs(f1 - b) + abs(f2 - b))
+ abs(t1 - t2));
}
}
return 0;
}


## 【UVA-10087】The Tajmahal of ++Y2k【幻方构造】

【UVA-10087】The Tajmahal of ++Y2k【幻方构造】

Solution:

#include <iostream>

using namespace std;

typedef long long LL;
const int LIM = 101;
struct Matrix {
int v[LIM][LIM];
int size;
};

inline LL getSum(LL n) {
return n * (n * n + 1) / 2;
}

Matrix odd_msquare(int n) {
Matrix ret = {{0}, n};
int lim = n * n;
int r = 0, c = n / 2;
for (int i = 1; i <= lim; i++) {
ret.v[r][c] = i;
int nr = (r - 1 + n) % n;
int nc = (c + 1 + n) % n;
if (ret.v[nr][nc]) r++;
else r = nr, c = nc;
}
return ret;
}

inline void swap(int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
}

Matrix m4_msquare(int n) {
Matrix ret = {{0}, n};
int crt = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ret.v[i][j] = crt;
crt++;
}
}
int lim = n / 2;
for (int i = 0; i < lim; i += 4) {
for (int j = 0; j < n; j += 4) {
if (i + 2 == lim && j > lim) break;
if (j + 2 == lim && i + 2 == lim) {
for (int k = 0; k < 2; k++) {
for (int m = 0; m < 4; m++) {
if (k == m || k == 4 - m - 1)
swap(ret.v[i + k][j + m], ret.v[n - 1 - (i + k)][n - 1 - (j + m)]);
}
}
} else {
for (int k = 0; k < 4; k++) {
for (int m = 0; m < 4; m++) {
if (k == m || k == 4 - m - 1)
swap(ret.v[i + k][j + m], ret.v[n - 1 - (i + k)][n - 1 - (j + m)]);
}
}
}
}
}
return ret;
}

Matrix m4p2_msquare(int n) {
int m = (n - 2) / 4;
Matrix tmp = odd_msquare(n / 2), ret = {{0}, n};
for (int i = 0; i < tmp.size; i++)
for (int j = 0; j < tmp.size; j++)
tmp.v[i][j] = tmp.v[i][j] * 4 - 4;
for (int i = 0; i <= m; i++) {
for (int j = 0; j < tmp.size; j++) {
ret.v[i << 1][j << 1] = 4 + tmp.v[i][j];
ret.v[i << 1][(j << 1) + 1] = 1 + tmp.v[i][j];
ret.v[(i << 1) + 1][j << 1] = 2 + tmp.v[i][j];
ret.v[(i << 1) + 1][(j << 1) + 1] = 3 + tmp.v[i][j];
}
}
ret.v[m << 1][tmp.size - 1] = 1 + tmp.v[m][tmp.size >> 1];
ret.v[m << 1][tmp.size] = 4 + tmp.v[m][tmp.size >> 1];
ret.v[(m << 1) + 1][tmp.size - 1] = 2 + tmp.v[m][tmp.size >> 1];
ret.v[(m << 1) + 1][tmp.size] = 3 + tmp.v[m][tmp.size >> 1];
for (int j = 0; j < tmp.size; j++) {
ret.v[(m + 1) << 1][j << 1] = 1 + tmp.v[m + 1][j];
ret.v[(m + 1) << 1][(j << 1) + 1] = 4 + tmp.v[m + 1][j];
ret.v[((m + 1) << 1) + 1][j << 1] = 2 + tmp.v[m + 1][j];
ret.v[((m + 1) << 1) + 1][(j << 1) + 1] = 3 + tmp.v[m + 1][j];
}
ret.v[(m + 1) << 1][tmp.size - 1] = 4 + tmp.v[m + 1][tmp.size >> 1];
ret.v[(m + 1) << 1][tmp.size] = 1 + tmp.v[m + 1][tmp.size >> 1];
ret.v[((m + 1) << 1) + 1][tmp.size - 1] = 2 + tmp.v[m + 1][tmp.size >> 1];
ret.v[((m + 1) << 1) + 1][tmp.size] = 3 + tmp.v[m + 1][tmp.size >> 1];
for (int i = m + 2; i < tmp.size; i++) {
for (int j = 0; j < tmp.size; j++) {
ret.v[i << 1][j << 1] = 1 + tmp.v[i][j];
ret.v[i << 1][(j << 1) + 1] = 4 + tmp.v[i][j];
ret.v[(i << 1) + 1][j << 1] = 3 + tmp.v[i][j];
ret.v[(i << 1) + 1][(j << 1) + 1] = 2 + tmp.v[i][j];
}
}
return ret;
}

int main(void) {
LL s;
int n;
Matrix ans;
while (~scanf("%d%lld", &n, &s)) {
if (n == 1) printf("%10lld\n", s);
else if (n == 2) printf("You can't be like Shahjahan!\n");
else {
LL diff = s - getSum(n);
if (diff % n) printf("You can't be like Shahjahan!\n");
else {
LL add = diff / n;
if (n % 2) {
ans = odd_msquare(n);
} else {
if (n % 4) ans = m4p2_msquare(n);
else ans = m4_msquare(n);
}
for (int i = 0; i < ans.size; i++) {
for (int j = 0; j < ans.size; j++) {
if (j) putchar(' ');
}
putchar('\n');
}
}
}
putchar('\n');
}
return 0;
}


Solution:

Part 1.当k是偶数时，则$$a_k = a_{k – 1} \times 2 = a_{k – 1} + 2 \times a_{k – 2} + 1$$。

Part 2.当k是奇数时，则$$a_k = a_{k – 1} \times 2 +1 = a_{k – 1} + 2 \times a_{k – 1} + 1$$。

#include <iostream>

using namespace std;

typedef long long LL;
LL MOD;
struct Matrix {
LL t[3][3];
Matrix operator * (const Matrix & m) const {
Matrix ret = {0};
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
ret.t[i][j] = (ret.t[i][j] + t[i][k] * m.t[k][j]) % MOD;
}
}
}
return ret;
}
};

const Matrix BASE = {{1, 2, 1, 1, 0, 0, 0, 0, 1}};

Matrix powMod(int pow, Matrix m) {
Matrix ret = {{1, 0, 0, 0, 1, 0, 0, 0, 1}};
while (pow) {
if (pow & 1) ret = ret * m;
m = m * m;
pow >>= 1;
}
return ret;
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
LL n;
while (cin >> n >> MOD) {
if (n == 1) cout << 1 % MOD << "\n";
else if (n == 2) cout << 2 % MOD << "\n";
else {
Matrix trans = powMod(n - 2, BASE);
LL ans = (trans.t[0][0] * 2 + trans.t[0][1] * 1 + trans.t[0][2]) % MOD;
cout << ans << "\n";
}
}
return 0;
}


## 【HDU-5015】233 Matrix【矩阵快速幂】

【HDU-5015】233 Matrix【矩阵快速幂】

Solution：

1.发现可以通过每一列的值推出下一列的值。

2.注意到0没有贡献于最终结果，是题设故意设计的一个坑。

#include <iostream>

using namespace std;

typedef long long LL;
const LL MOD = 10000007;
const int LIM = 15;
struct Matrix {
LL t[LIM][LIM];
int size;
Matrix operator * (const Matrix & m) const {
Matrix ret = {{0}, size};
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
for (int k = 0; k < size; k++) {
ret.t[i][j] = (ret.t[i][j] + t[i][k] * m.t[k][j]) % MOD;
}
}
}
return ret;
}
};

Matrix buildBase(int size) {
Matrix ret = {{0}, size};
ret.t[size - 1][size - 1] = 1;
for (int i = size - 2; i >= 0; i--) {
ret.t[i][0] = 10;
ret.t[i][size - 1] = 1;
for (int j = 1; j <= i; j++)
ret.t[i][j] = 1;
}
return ret;
}

Matrix powMod(int pow, Matrix m) {
Matrix ret = {{0}, m.size};
for (int i = 0; i < ret.size; i++)
ret.t[i][i] = 1;
while (pow) {
if (pow & 1) ret = ret * m;
m = m * m;
pow >>= 1;
}
return ret;
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
LL n, m;
LL ori[LIM];
while (cin >> n >> m) {
ori[0] = 23;
ori[n + 1] = 3;
for (int i = 1; i <= n; i++) cin >> ori[i];
if (m == 0) cout << ori[n] << "\n";
else {
Matrix trans = powMod(m, buildBase(n + 2));
LL ans = 0;
for (int i = 0; i <= n + 1; i++)
ans = (ans + trans.t[n][i] * ori[i]) % MOD;
cout << ans << "\n";
}
}
return 0;
}