Problem A
解方程ax mod 9973=b就行，方程不会解，再加一句废话：ax mod a=0，凑成一个线性同余方程组，套模板。
#include <stdio.h>
#include <string.h>
class Congruent_Linear_Equation_Group {
private:
#define MAX_GROUP_SIZE 10
int groupSize;
long long dis;
long long A[MAX_GROUP_SIZE], M[MAX_GROUP_SIZE];
long long gcd(long long a, long long b) {
long long k;
while (b != 0) {
k = b;
b = a % b;
a = k;
}
return a;
}
/* * * * * * * * * *
* a,b=>x,y *
* ax+by=gcd(a,b) *
* * * * * * * * * */
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
long long ans, t;
if (b == 0) {
x = 1;
y = 0;
return a;
} else {
ans = extended_gcd(b, a % b, x, y);
t = x;
x = y;
y = t - (a / b) * y;
}
return ans;
}
public:
Congruent_Linear_Equation_Group() {
groupSize = 0;
}
void clear() {
groupSize = 0;
}
void addEquation(long long a, long long m) {
if (m == 0) {
return;
}
A[groupSize] = a;
M[groupSize++] = m;
}
// => Possible solution,not minium positive solution
long long getSolution() {
long long at = A[0], mt = M[0], ap, mp, x, y, z;
for (int i = 1; i < groupSize; i++) {
ap = A[i];
mp = M[i];
if ((at - ap) % gcd(mt, mp) != 0) {
return -1;
}
/* * * * * * * * * * * * *
* x=mt*y+at *
* x=mp*z+ap *
* => at-ap=mp*z-mt*y *
* * * * * * * * * * * * */
extended_gcd(mp, -1 * mt, z, y);
// => mp*z-mt*y=gcd(mp,-mt)
z = z * (at - ap) / gcd(mp, -mt);
x = mp * z + ap;
mt = mt * mp / gcd(mt, mp);
if (x <= 0) {
x = x % mt + mt;
}
at = x;
}
dis = mt;
return x;
}
long long getNextSolution(long long x) {
return x + dis;
}
};
Congruent_Linear_Equation_Group CLEG;
char str[100005];
int h[100005];
int main() {
int n, a, b;
while (scanf("%d", &n) != EOF) {
scanf("%s", str);
h[0] = 1;
int k = strlen(str);
for (int i = 0; i < k; i++) {
h[i + 1] = h[i] * (str[i] - 28) % 9973;
}
for (int i = 0; i < n; i++) {
scanf("%d%d", &a, &b);
CLEG.clear();
CLEG.addEquation(0, h[a - 1]);
CLEG.addEquation(h[b], 9973);
printf("%d
", (CLEG.getSolution() / h[a - 1]) % 9973);
}
}
return 0;
}
Problem B
看样例像是斐波那契，试了一下居然真是，至于为啥就没再想了。
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#ifndef BIGNUM
#define BIGNUM
class BigNum {
#define MAXSIZEOFBIGNUM 500
#define BASE 10
#define DLEN 1
public:
int Len;
int d[MAXSIZEOFBIGNUM];
public:
BigNum(void);
BigNum(const int);
BigNum(const char *);
BigNum(const BigNum &);
BigNum & operator = (const BigNum &);
void clear(void);
friend istream& operator>>(istream&, BigNum&);
friend ostream& operator<<(ostream&, BigNum&);
bool operator == (const BigNum &) const;
bool operator > (const BigNum &) const;
bool operator < (const BigNum &) const;
bool operator >= (const BigNum &) const;
bool operator <= (const BigNum &) const;
BigNum operator + (const BigNum &) const;
BigNum operator - (const BigNum &) const;
BigNum operator * (const BigNum &) const;
BigNum operator / (const BigNum &) const;
BigNum operator % (const BigNum &) const;
void operator ++ (void);
void operator -- (void);
BigNum operator + (const int &) const;
BigNum operator - (const int &) const;
BigNum operator * (const int &) const;
BigNum operator / (const int &) const;
int operator % (const int &) const;
BigNum operator ^ (const int &) const;
~BigNum() {}
};
BigNum::BigNum() {
Len = 0;
memset(d, 0, sizeof(d));
}
BigNum::BigNum(const int ops) {
int x = ops;
Len = 0;
memset(d, 0, sizeof(d));
while (x) {
Len++;
d[Len] = x % BASE;
x /= BASE;
}
}
BigNum::BigNum(const char * ops) {
int L = strlen(ops) - 1, b = 0;
memset(d, 0, sizeof(d));
while (ops[b] == '0') {
b++;
}
Len = 0;
while (L - b + 1 >= DLEN) {
int x = 0;
for (int i = L - DLEN + 1; i <= L; i++) {
x = x * 10 + ops[i] - '0';
}
Len++;
d[Len] = x;
L -= DLEN;
}
int x = 0;
for (int i = b; i <= L; i++) {
x = x * 10 + ops[i] - '0';
}
Len++;
d[Len] = x;
}
BigNum::BigNum(const BigNum &ops) : Len(ops.Len) {
memset(d, 0, sizeof(d));
for (int i = 1; i <= Len; i++) {
d[i] = ops.d[i];
}
}
BigNum & BigNum::operator = (const BigNum &ops) {
memset(d, 0, sizeof(d));
Len = ops.Len;
for (int i = 1; i <= Len; i++) {
d[i] = ops.d[i];
}
return *this;
}
void BigNum::clear(void) {
for (int i = 1; i <= MAXSIZEOFBIGNUM - 2; i++) {
if (d[i] < 0) {
d[i] += BASE;
d[i + 1]--;
}
if (d[i] >= BASE) {
d[i] -= BASE;
d[i + 1]++;
}
}
for (int i = MAXSIZEOFBIGNUM - 1; i >= 1; i--)
if (d[i] > 0) {
Len = i;
return;
}
Len = 0;
}
istream& operator>>(istream &in, BigNum &ops) {
char str[MAXSIZEOFBIGNUM + 100];
in >> str;
int L = strlen(str), b = 0;
while (str[b] == '0') {
b++;
}
ops.Len = 0;
for (int i = L - 1; i >= b; i--) {
ops.Len++;
ops.d[ops.Len] = str[i] - '0';
}
return in;
}
ostream& operator<<(ostream& out, BigNum& ops) {
for (int i = ops.Len; i >= 1; i--) {
out << ops.d[i];
}
if (ops.Len == 0) {
out << "0";
}
return out;
}
bool BigNum::operator == (const BigNum &ops) const {
if (Len != ops.Len) {
return false;
}
for (int i = Len; i >= 1; i--)
if (d[i] != ops.d[i]) {
return false;
}
return true;
}
bool BigNum::operator > (const BigNum &ops) const {
if (Len < ops.Len) {
return false;
} else if (Len > ops.Len) {
return true;
} else {
for (int i = Len; i >= 1; i--)
if (d[i] < ops.d[i]) {
return false;
} else if (d[i] > ops.d[i]) {
return true;
}
}
return false;
}
bool BigNum::operator < (const BigNum &ops) const {
if (Len < ops.Len) {
return true;
} else if (Len > ops.Len) {
return false;
} else {
for (int i = Len; i >= 1; i--)
if (d[i] < ops.d[i]) {
return true;
} else if (d[i] > ops.d[i]) {
return false;
}
}
return false;
}
bool BigNum::operator >= (const BigNum &ops) const {
if (Len < ops.Len) {
return false;
} else if (Len > ops.Len) {
return true;
} else {
for (int i = Len; i >= 1; i--)
if (d[i] < ops.d[i]) {
return false;
} else if (d[i] > ops.d[i]) {
return true;
}
}
return true;
}
bool BigNum::operator <= (const BigNum &ops) const {
if (Len < ops.Len) {
return true;
} else if (Len > ops.Len) {
return false;
} else {
for (int i = Len; i >= 1; i--)
if (d[i] < ops.d[i]) {
return true;
} else if (d[i] > ops.d[i]) {
return false;
}
}
return true;
}
BigNum BigNum::operator + (const BigNum &ops) const {
BigNum ret(*this);
for (int i = 1; i <= ops.Len; i++) {
ret.d[i] += ops.d[i];
}
ret.clear();
return ret;
}
BigNum BigNum::operator - (const BigNum &ops) const {
BigNum ret(*this);
for (int i = ops.Len; i >= 1; i--) {
ret.d[i] -= ops.d[i];
}
ret.clear();
return ret;
}
BigNum BigNum::operator * (const BigNum &ops) const {
BigNum ret, now(*this);
for (int i = 1; i <= now.Len; i++)
for (int j = 1; j <= ops.Len; j++) {
ret.d[i + j - 1] += now.d[i] * ops.d[j];
}
for (int i = 1; i <= MAXSIZEOFBIGNUM - 2; i++)
if (ret.d[i] >= BASE) {
ret.d[i + 1] += ret.d[i] / BASE;
ret.d[i] %= BASE;
}
for (int i = MAXSIZEOFBIGNUM - 1; i >= 1; i--)
if (ret.d[i] > 0) {
ret.Len = i;
break;
}
return ret;
}
BigNum BigNum::operator / (const BigNum &ops) const {
BigNum now = (*this), div, mod;
div.Len = now.Len;
mod.Len = 0;
for (int j = now.Len; j >= 1; j--) {
mod.Len++;
for (int p = mod.Len; p >= 2; p--) {
mod.d[p] = mod.d[p - 1];
}
mod.d[1] = now.d[j];
while (mod >= ops) {
div.d[j]++;
mod = mod - ops;
}
if (mod.Len == 1 && mod.d[1] == 0) {
mod.Len--;
}
}
div.clear();
mod.clear();
return div;
}
BigNum BigNum::operator % (const BigNum &ops) const {
BigNum now = (*this), div, mod;
div.Len = now.Len;
mod.Len = 0;
for (int j = now.Len; j >= 1; j--) {
mod.Len++;
for (int p = mod.Len; p >= 2; p--) {
mod.d[p] = mod.d[p - 1];
}
mod.d[1] = now.d[j];
while (mod >= ops) {
div.d[j]++;
mod = mod - ops;
}
if (mod.Len == 1 && mod.d[1] == 0) {
mod.Len--;
}
}
div.clear();
mod.clear();
return mod;
}
void BigNum::operator ++ (void) {
d[1]++;
for (int i = 1; i <= MAXSIZEOFBIGNUM - 2; i++)
if (d[i] >= BASE) {
d[i] -= BASE;
d[i + 1]++;
} else {
break;
}
if (d[Len + 1] > 0) {
Len++;
}
}
void BigNum::operator -- (void) {
d[1]--;
for (int i = 1; i <= MAXSIZEOFBIGNUM - 2; i++)
if (d[i] < 0) {
d[i] += BASE;
d[i + 1]--;
} else {
break;
}
if (d[Len] == 0) {
Len--;
}
}
BigNum BigNum::operator + (const int & ops) const {
BigNum ret = (*this);
ret.d[1] += ops;
ret.clear();
return ret;
}
BigNum BigNum::operator - (const int & ops) const {
BigNum ret = (*this);
ret.d[1] -= ops;
ret.clear();
return ret;
}
BigNum BigNum::operator * (const int & ops) const {
BigNum ret(*this);
for (int i = 1; i <= ret.Len; i++) {
ret.d[i] *= ops;
}
for (int i = 1; i <= MAXSIZEOFBIGNUM - 2; i++)
if (ret.d[i] >= BASE) {
ret.d[i + 1] += ret.d[i] / BASE;
ret.d[i] %= BASE;
}
for (int i = MAXSIZEOFBIGNUM - 1; i >= 1; i--)
if (ret.d[i] > 0) {
ret.Len = i;
return ret;
}
ret.Len = 0;
return ret;
}
BigNum BigNum::operator / (const int & ops) const {
BigNum ret;
int down = 0;
for (int i = Len; i >= 1; i--) {
ret.d[i] = (d[i] + down * BASE) / ops;
down = d[i] + down * BASE - ret.d[i] * ops;
}
ret.Len = Len;
while (ret.d[ret.Len] == 0 && ret.Len > 1) {
ret.Len--;
}
return ret;
}
int BigNum::operator % (const int &ops) const {
int mod = 0;
for (int i = Len; i >= 1; i--) {
mod = ((mod * BASE) % ops + d[i]) % ops;
}
return mod;
}
BigNum BigNum::operator ^ (const int &ops) const {
BigNum t, ret(1);
if (ops == 0) {
return ret;
}
if (ops == 1) {
return *this;
}
int m = ops, i;
while (m > 1) {
t = *this;
for (i = 1; (i << 1) <= m; i <<= 1) {
t = t * t;
}
m -= i;
ret = ret * t;
if (m == 1) {
ret = ret * (*this);
}
}
return ret;
}
#endif
BigNum f[205];
int main() {
int n;
f[0] = f[1] = 1;
for (int i = 2; i <= 200; i++) {
f[i] = f[i - 1] + f[i - 2];
}
while (scanf("%d", &n) != EOF) {
cout << f[n] << endl;
}
return 0;
}
Problem C
字典树
#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define maxn 3111111
struct node {
int num;
int next[26], fa;
}tree[maxn];
char op[33], a[33];
int root, cnt;
void New (int c, int fa) {
tree[c].num = 0;
tree[c].fa = fa;
memset (tree[c].next, -1, sizeof tree[c].next);
return ;
}
void Insert () {
int l = strlen (a);
int p = root;
for (int i = 0; i < l; i++) {
int id = a[i]-'a';
if (tree[p].next[id] == -1) {
tree[p].next[id] = ++cnt;
New (cnt, p);
}
p = tree[p].next[id];
tree[p].num++;
}
return ;
}
int Search () {
int l = strlen (a);
int p = root;
for (int i = 0; i < l; i++) {
int id = a[i]-'a';
if (tree[p].next[id] == -1) {
return 0;
}
p = tree[p].next[id];
}
return tree[p].num;
}
void Delete () {
int l = strlen (a);
int p = root;
for (int i = 0; i < l; i++) {
int id = a[i]-'a';
if (tree[p].next[id] == -1) {
return ;
}
p = tree[p].next[id];
}
int ans = tree[p].num;
while (tree[p].fa != -1) {
tree[p].num -= ans;
p = tree[p].fa;
}
p = root;
for (int i = 0; i < l; i++) {
int id = a[i]-'a';
if (tree[tree[p].next[id]].num == 0) {
tree[p].next[id] = -1;
return ;
}
p = tree[p].next[id];
}
return ;
}
int main () {
//freopen ("in.txt", "r", stdin);
int n;
scanf ("%d", &n);
root = cnt = 0;
New (root, -1);
while (n--) {
scanf ("%s%s", op, a);
if (op[0] == 'i') {
Insert ();
}
else if (op[0] == 'd') {
Delete ();
}
else if (op[0] == 's') {
int ans = Search ();
printf ("%s
", ans ? "Yes" : "No");
}
}
return 0;
}
Problem D
map
#include <stdio.h>
#include <string>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
map<string, int> mp;
int main() {
int n;
scanf("%d", &n);
std::ios::sync_with_stdio(false);
cin.tie(0);
string s;
for (int i = 0; i < n; i++) {
cin >> s;
sort(s.begin(), s.begin() + s.length());
cout << mp[s]++ << endl;
}
return 0;
}
Problem E
大小小大中间找，大大小小找不着。
#include<cstdio>
#include<string>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e3 + 10;
map<string, int> M;
char s[maxn * 100];
string x, y;
int n, t, z, f;
struct point
{
int l[31], r[31], flag;
void read()
{
flag = 1;
for (int i = 1; i <= 30; i++) l[i] = -10001, r[i] = 10001;
gets(s);
for (int i = 0; s[i]; )
{
if (s[i] == ' ' || s[i] == ',') { i++; continue; }
x = ""; y = ""; z = 0; f = 1;
while (s[i] != ' ') x += s[i++];
while (s[i] == ' ') ++i;
while (s[i] != ' ') y += s[i++];
while (s[i] == ' ') ++i;
if (s[i] == '-') ++i, f = -1;
while (s[i] >= '0'&&s[i] <= '9') z = z * 10 + s[i++] - '0';
z = z*f;
int now = M[x];
if (!now) now = M[x] = ++t;
if (y == "<") r[now] = min(r[now], z - 1);
else if (y == ">") l[now] = max(l[now], z + 1);
else if (y == "<=") r[now] = min(r[now], z);
else if (y == ">=") l[now] = max(l[now], z);
else l[now] = max(l[now], z), r[now] = min(r[now], z);
if (l[now] > r[now]) flag = 0;
}
}
}a[maxn];
bool check(point a, point b)
{
if (a.flag + b.flag != 2) return false;
for (int i = 1; i <= t; i++)
{
if (max(a.l[i], b.l[i]) > min(a.r[i], b.r[i])) return false;
}
return true;
}
int main()
{
while (scanf("%d", &n) != EOF)
{
gets(s);
M.clear(); t = 0;
for (int i = 1; i <= n; i++) a[i].read();
for (int i = 1; i <= n; i++)
{
int flag = 0;
for (int j = 1; j < i; j++)
{
if (check(a[i], a[j]))
{
if (flag) printf(" ");
printf("%d", j);
flag = 1;
}
}
if (!flag) printf("unique");
printf("
");
}
}
return 0;
}