Andrew Stankevich's Contest (1)
打一半出门了，回来才补完了。。。各种大数又不能上java。。也是蛋疼无比
A：依据置换循环节非常easy得出要gcd(x, n) = 1而且x <= n / 2，那么把相应几种情况的最大值考虑一下就可以，各自是n % 2 = 1为n / 2, n % 4 = 0为n / 2 - 1，n % 4 = 2为n / 2 - 2
B：限制下限的最大流，建模方法为原来容量变成c - l，然后源点连到每一个点的下限和为正，每一个点下限和为负连到汇点，跑一下最大流，假设源点流出的所有满流就是有解，然后输出的时候仅仅要把相应的*流加上下限就可以
C：贪心，从叶子结点不断往上推，一有合适就用掉，然后把父结点标记一下用来推断就可以
D：就简单的矩阵相乘，因为要考虑复杂度，所以能够先算出没排的和，然后每一个位置分别乘上相应那排再累加就可以
E：矩阵高速幂，把两两关系确立后，建立矩阵跑一下高速幂就可以
F：几何题，推断有限视角和是否会形成-2pi，利用spfa判负环就可以
G：LIS，先按x从小到大，再按y从大到小排序，这样对y做lis就是答案，因为要输出路径，所以开一个dp数组记录下每一个位置的答案，然后在扫一遍随意输出一种方案就可以
H：高斯消元，和大白书上例题差点儿相同，全然平方数的每一个因子必定是偶数，这样就能够建立异或方程，然后计算出*便元个数x，那么答案就是2^x - 1
代码：
A:
#include <cstdio>
#include <cstring>
#include <iostream> using namespace std;
typedef long long ll;
const int MAXN = 2005; struct bign {
int len;
ll num[MAXN]; bign () {
len = 0;
memset(num, 0, sizeof(num));
}
bign (ll number) {*this = number;}
bign (const char* number) {*this = number;} void DelZero ();
void Put (); void operator = (ll number);
void operator = (char* number); bool operator < (const bign& b) const;
bool operator > (const bign& b) const { return b < *this; }
bool operator <= (const bign& b) const { return !(b < *this); }
bool operator >= (const bign& b) const { return !(*this < b); }
bool operator != (const bign& b) const { return b < *this || *this < b;}
bool operator == (const bign& b) const { return !(b != *this); } void operator ++ ();
void operator -- ();
bign operator + (const int& b);
bign operator + (const bign& b);
bign operator - (const int& b);
bign operator - (const bign& b);
bign operator * (const ll& b);
bign operator * (const bign& b);
bign operator / (const ll& b);
//bign operator / (const bign& b);
int operator % (const int& b);
}; /*Code*/ char str[2005]; int main() {
while (~scanf("%s", str)) {
bign sb;
sb = str;
bign ans;
if (sb % 2) ans = sb / 2;
else if (sb % 4 == 0) ans = sb / 2 - 1;
else ans = sb / 2 - 2;
ans.Put();
printf("\n");
}
return 0;
} /*********************************************/ void bign::DelZero () {
while (len && num[len-1] == 0)
len--; if (len == 0) {
num[len++] = 0;
}
} void bign::Put () {
for (int i = len-1; i >= 0; i--)
printf("%lld", num[i]);
} void bign::operator = (char* number) {
len = strlen (number);
for (int i = 0; i < len; i++)
num[i] = number[len-i-1] - '0';
DelZero ();
} void bign::operator = (ll number) { len = 0;
while (number) {
num[len++] = number%10;
number /= 10;
} DelZero ();
} bool bign::operator < (const bign& b) const {
if (len != b.len)
return len < b.len;
for (int i = len-1; i >= 0; i--)
if (num[i] != b.num[i])
return num[i] < b.num[i];
return false;
} void bign::operator ++ () {
int s = 1; for (int i = 0; i < len; i++) {
s = s + num[i];
num[i] = s % 10;
s /= 10;
if (!s) break;
} while (s) {
num[len++] = s%10;
s /= 10;
}
} void bign::operator -- () {
if (num[0] == 0 && len == 1) return; int s = -1;
for (int i = 0; i < len; i++) {
s = s + num[i];
num[i] = (s + 10) % 10;
if (s >= 0) break;
}
DelZero ();
} bign bign::operator + (const int& b) {
bign a = b;
return *this + a;
} bign bign::operator + (const bign& b) {
int bignSum = 0;
bign ans; for (int i = 0; i < len || i < b.len; i++) {
if (i < len) bignSum += num[i];
if (i < b.len) bignSum += b.num[i]; ans.num[ans.len++] = bignSum % 10;
bignSum /= 10;
} while (bignSum) {
ans.num[ans.len++] = bignSum % 10;
bignSum /= 10;
} return ans;
} bign bign::operator - (const int& b) {
bign a = b;
return *this - a;
} bign bign::operator - (const bign& b) {
ll bignSub = 0;
bign ans;
for (int i = 0; i < len || i < b.len; i++) {
bignSub += num[i];
if (i < b.len)
bignSub -= b.num[i];
ans.num[ans.len++] = (bignSub + 10) % 10;
if (bignSub < 0) bignSub = -1;
else bignSub = 0;
}
ans.DelZero();
return ans;
} bign bign::operator * (const ll& b) {
ll bignSum = 0;
bign ans; ans.len = len;
for (int i = 0; i < len; i++) {
bignSum += num[i] * b;
ans.num[i] = bignSum % 10;
bignSum /= 10;
} while (bignSum) {
ans.num[ans.len++] = bignSum % 10;
bignSum /= 10;
} return ans;
} bign bign::operator * (const bign& b) {
bign ans;
ans.len = 0; for (int i = 0; i < len; i++){
int bignSum = 0; for (int j = 0; j < b.len; j++){
bignSum += num[i] * b.num[j] + ans.num[i+j];
ans.num[i+j] = bignSum % 10;
bignSum /= 10;
}
ans.len = i + b.len; while (bignSum){
ans.num[ans.len++] = bignSum % 10;
bignSum /= 10;
}
}
return ans;
} bign bign::operator / (const ll& b) { bign ans; ll s = 0;
for (int i = len-1; i >= 0; i--) {
s = s * 10 + num[i];
ans.num[i] = s/b;
s %= b;
} ans.len = len;
ans.DelZero();
return ans;
} int bign::operator % (const int& b) { bign ans; int s = 0;
for (int i = len-1; i >= 0; i--) {
s = s * 10 + num[i];
ans.num[i] = s/b;
s %= b;
} return s;
}
B:
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std; const int MAXNODE = 205;
const int MAXEDGE = 210005; typedef int Type;
const Type INF = 0x3f3f3f3f; struct Edge {
int u, v;
Type cap, flow, low;
Edge() {}
Edge(int u, int v, Type cap, Type flow, Type low) {
this->u = u;
this->v = v;
this->cap = cap;
this->flow = flow;
this->low = low;
}
}; struct Dinic {
int n, m, s, t;
Edge edges[MAXEDGE];
int first[MAXNODE];
int next[MAXEDGE];
bool vis[MAXNODE];
Type d[MAXNODE];
int cur[MAXNODE];
vector<int> cut; void init(int n) {
this->n = n;
memset(first, -1, sizeof(first));
m = 0;
}
void add_Edge(int u, int v, Type cap, Type low) {
edges[m] = Edge(u, v, cap, 0, low);
next[m] = first[u];
first[u] = m++;
edges[m] = Edge(v, u, 0, 0, low);
next[m] = first[v];
first[v] = m++;
} bool bfs() {
memset(vis, false, sizeof(vis));
queue<int> Q;
Q.push(s);
d[s] = 0;
vis[s] = true;
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (int i = first[u]; i != -1; i = next[i]) {
Edge& e = edges[i];
if (!vis[e.v] && e.cap > e.flow) {
vis[e.v] = true;
d[e.v] = d[u] + 1;
Q.push(e.v);
}
}
}
return vis[t];
} Type dfs(int u, Type a) {
if (u == t || a == 0) return a;
Type flow = 0, f;
for (int &i = cur[u]; i != -1; i = next[i]) {
Edge& e = edges[i];
if (d[u] + 1 == d[e.v] && (f = dfs(e.v, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[i^1].flow -= f;
flow += f;
a -= f;
if (a == 0) break;
}
}
return flow;
} Type Maxflow(int s, int t) {
this->s = s; this->t = t;
Type flow = 0;
while (bfs()) {
for (int i = 0; i < n; i++)
cur[i] = first[i];
flow += dfs(s, INF);
}
return flow;
} bool solve(int s, int t, int tot) {
Maxflow(s, t);
for (int i = first[s]; i + 1; i = next[i]) {
if (edges[i].flow != edges[i].cap) return false;
}
printf("YES\n");
for (int i = 0; i < 2 * tot; i += 2)
printf("%d\n", edges[i].flow + edges[i].low);
return true;
} void MinCut() {
cut.clear();
for (int i = 0; i < m; i += 2) {
if (vis[edges[i].u] && !vis[edges[i].v])
cut.push_back(i);
}
}
} gao; const int N = 205; int n, m, M[N]; int main() {
while (~scanf("%d%d", &n, &m)) {
gao.init(n + 2);
int u, v, l, c;
memset(M, 0, sizeof(M));
for (int i = 0; i < m; i++) {
scanf("%d%d%d%d", &u, &v, &l, &c);
gao.add_Edge(u, v, c - l, l);
M[u] -= l;
M[v] += l;
}
for (int i = 1; i <= n; i++) {
if (M[i] > 0) gao.add_Edge(0, i, M[i], 0);
else if (M[i] < 0) gao.add_Edge(i, n + 1, -M[i], 0);
}
if (!gao.solve(0, n + 1, m)) printf("NO\n");
}
return 0;
}
C:
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <algorithm>
using namespace std; const int N = 500005; int n, fa[N], du[N], vis[N];
int out[N], on; int main() {
while (~scanf("%d", &n)) {
int f;
int ans = 0;
memset(du, 0, sizeof(du));
memset(vis, 0, sizeof(vis));
for (int i = 2; i <= n; i++) {
scanf("%d", &f);
fa[i] = f;
du[f]++;
}
on = 0;
queue<int> Q;
for (int i = 1; i <= n; i++) {
if (du[i] == 0)
Q.push(i);
}
while (!Q.empty()) {
int u = Q.front();
if (u == 1) break;
Q.pop();
if (!vis[u] && !vis[fa[u]]) {
vis[fa[u]] = 1;
out[on++] = u;
ans += 1000;
}
du[fa[u]]--;
if (du[fa[u]] == 0) Q.push(fa[u]);
}
sort(out, out + on);
printf("%d\n", ans);
for (int i = 0; i < on; i++)
printf("%d%c", out[i], i == on - 1 ? '\n' : ' ');
}
return 0;
}
D:
#include <cstdio>
#include <cstring> const int N = 10005;
const int M = 100005; int n, m, cnt[N];
int u[M], v[M]; int main() {
while (~scanf("%d%d", &n, &m)) {
long long ans = 0;
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < m; i++) {
scanf("%d%d", &u[i], &v[i]);
cnt[u[i]]++;
if (v[i] != u[i]) cnt[v[i]]++;
}
for (int i = 0; i < m; i++) {
ans += cnt[u[i]];
if (u[i] != v[i]) ans += cnt[v[i]];
}
printf("%lld\n", ans);
}
return 0;
}
E:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; typedef long long ll;
const ll MOD = 1000000000;
const int NUMLEN = 105; struct Bign {
ll num[NUMLEN];
int len; void init(char *str) {
for (int i = strlen(str) - 1; i >= 0; i--) {
if (str[i] == '0') str[i] = '9';
else {
str[i]--;
break;
}
}
if (str[0] == '0') {
int ca = strlen(str);
for (int i = 0; i < ca; i++)
str[i] = str[i + 1];
str[ca - 1] = '\0';
}
len = 0;
memset(num, 0, sizeof(num));
for (int i = strlen(str) - 1; i >= 0; i -= 9) {
for (int j = max(0, i - 8); j <= i; j++) {
num[len] = num[len] * 10 + str[j] - '0';
}
len++;
}
} ll div2() {
ll yu = 0;
for (int i = len - 1; i >= 0; i--) {
num[i] = num[i] + yu * MOD;
yu = num[i] % 2;
num[i] /= 2;
}
while (len > 1 && num[len - 1] == 0) len--;
return yu;
} bool iszero() {
if (len == 1 && num[0] == 0) return true;
return false;
} void print() {
for (int i = len - 1; i >= 0; i--) {
if (i != len - 1) printf("%09lld", num[i]);
else printf("%lld", num[i]);
}
}
} n; const int N = 105; char num[N];
int m, p, tot; struct mat {
int v[35][35];
mat() {memset(v, 0, sizeof(v));}
mat operator * (mat c) {
mat ans;
for (int k = 0; k < tot; k++) {
for (int i = 0; i < tot; i++) {
if (v[i][k] == 0) continue;
for (int j = 0; j < tot; j++) {
if (c.v[k][j] == 0) continue;
ans.v[i][j] = (ans.v[i][j] + v[i][k] * c.v[k][j]) % p;
}
}
}
return ans;
}
}; mat pow_mod(mat x, Bign k) {
mat ans;
for (int i = 0; i < tot; i++) ans.v[i][i] = 1;
while (!k.iszero()) {
ll sb = k.div2();
if (sb == 1) ans = ans * x;
x = x * x;
}
return ans;
} int main() {
while (~scanf("%s%d%d", num, &m, &p)) {
n.init(num);
tot = (1<<m);
mat A;
for (int i = 0; i < tot; i++) {
for (int j = 0; j < tot; j++) {
int flag = 1;
int st = 3;
for (int k = 0; k < m - 1; k++) {
int sb = (i&st)>>k;
if ((sb == 0 || sb == 3) && (i&st) == (j&st)) {
flag = 0;
break;
}
st <<= 1;
}
if (flag == 1) A.v[i][j] = 1;
}
}
A = pow_mod(A, n);
ll ans = 0;
for (int i = 0; i < tot; i++) {
for (int j = 0; j < tot; j++)
ans = (ans + A.v[i][j]) % p;
}
printf("%lld\n", ans);
}
return 0;
}
F:
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std; typedef double Type; const double eps = 1e-6;
const int MAXNODE = 305;
const int MAXEDGE = 100005; struct Edge {
int u, v;
Type dist;
Edge() {}
Edge(int u, int v, Type dist) {
this->u = u;
this->v = v;
this->dist = dist;
}
}; struct BellmanFrod {
int n, m;
Edge edges[MAXEDGE];
int first[MAXNODE];
int next[MAXEDGE];
bool inq[MAXNODE];
Type d[MAXNODE];
int p[MAXNODE];
int cnt[MAXNODE]; void init(int n) {
this->n = n;
memset(first, -1, sizeof(first));
m = 0;
} void add_Edge(int u, int v, Type dist) {
edges[m] = Edge(u, v, dist);
next[m] = first[u];
first[u] = m++;
} bool negativeCycle() {
queue<int> Q;
memset(inq, 0, sizeof(inq));
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; i++) {
d[i] = 0; inq[i] = true; Q.push(i);
} while (!Q.empty()) {
int u = Q.front();
Q.pop();
inq[u] = false;
for (int i = first[u]; i != -1; i = next[i]) {
Edge& e = edges[i];
if (d[e.v] > eps + d[u] + e.dist) {
d[e.v] = d[u] + e.dist;
p[e.v] = i;
if (!inq[e.v]) {
Q.push(e.v);
inq[e.v] = true;
if (++cnt[e.v] > n) return true;
}
}
}
}
return false;
}
} gao; const int N = 305; int n; struct Circle {
double x, y, r;
void read() {
scanf("%lf%lf%lf", &x, &y, &r);
}
} c[N], cc; double dis(Circle a, Circle b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
} int main() {
while (~scanf("%d", &n)) {
for (int i = 0; i < n; i++) c[i].read();
cc.read();
for (int i = 0; i < n; i++) {
c[i].x -= cc.x;
c[i].y -= cc.y;
c[i].r += cc.r;
}
cc.x = cc.y = 0;
gao.init(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (c[i].r + c[j].r - eps < dis(c[i], c[j])) continue;
double tmp = acos((c[i].x * c[j].x + c[i].y * c[j].y) / dis(c[i], cc) / dis(c[j], cc));
bool flag = (c[i].x * c[j].y - c[i].y * c[j].x) >= 0;
gao.add_Edge(i, j, flag ? tmp : -tmp);
gao.add_Edge(j, i, flag ? -tmp : tmp);
}
}
printf("%s\n", !gao.negativeCycle() ? "YES" : "NO");
}
return 0;
}
G:
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std; const int N = 100005;
int n;
struct Man {
int a, b, id;
} man[N]; bool cmp(Man a, Man b) {
if (a.a == b.a) return a.b > b.b;
return a.a < b.a;
} int dp[N], save[N], sn; bool judge(Man a, Man b) {
if (a.a <= b.a && a.b >= b.b) return false;
if (a.a >= b.a && a.b <= b.b) return false;
return true;
} int main() {
while (~scanf("%d", &n)) {
for (int i = 1; i <= n; i++) {
scanf("%d%d", &man[i].a, &man[i].b);
man[i].id = i;
}
sort(man + 1, man + n + 1, cmp);
memset(dp, 0, sizeof(dp));
sn = 0;
save[sn++] = 0;
for (int i = 1; i <= n; i++) {
int v = lower_bound(save, save + sn, man[i].b) - save;
save[v] = man[i].b;
if (v == sn) sn++;
dp[i] = v;
}
int sum = sn - 1;
printf("%d\n", sum);
int bo = 0;
for (int i = n; i >= 1; i--) {
if (dp[i] == sum) {
if (bo) printf(" ");
else bo = 1;
printf("%d", man[i].id);
sum--;
}
}
printf("\n");
}
return 0;
}
H:
#include <cstdio>
#include <cstring>
#include <iostream> using namespace std;
typedef long long ll;
const int MAXN = 2005; struct bign {
int len;
ll num[MAXN]; bign () {
len = 0;
memset(num, 0, sizeof(num));
}
bign (ll number) {*this = number;}
bign (const char* number) {*this = number;} void DelZero ();
void Put (); void operator = (ll number);
void operator = (char* number); bool operator < (const bign& b) const;
bool operator > (const bign& b) const { return b < *this; }
bool operator <= (const bign& b) const { return !(b < *this); }
bool operator >= (const bign& b) const { return !(*this < b); }
bool operator != (const bign& b) const { return b < *this || *this < b;}
bool operator == (const bign& b) const { return !(b != *this); } void operator ++ ();
void operator -- ();
bign operator + (const int& b);
bign operator + (const bign& b);
bign operator - (const int& b);
bign operator - (const bign& b);
bign operator * (const ll& b);
bign operator * (const bign& b);
bign operator / (const ll& b);
//bign operator / (const bign& b);
int operator % (const int& b);
}; /*Code*/ int prime[10005], pn = 0, vis[10005]; void getprime() {
for (int i = 2; i < 10000; i++) {
if (vis[i]) continue;
prime[pn++] = i;
for (int j = i * i; j < 10000; j += i)
vis[j] = 1;
}
} const int N = 105;
int m, n;
int A[N][N]; int gauss() {
int i = 0, j = 0, k, r, u;
while (i < m && j < n) {
r = i;
for (k = i; k < m; k++)
if (A[k][j]) {r = k; break;}
if (A[r][j]) {
if (r != i) for (int k = 0; k <= n; k++) swap(A[r][k], A[i][k]);
for (u = i + 1; u < m; u++) if (A[u][j])
for (k = i; k <= n; k++) A[u][k] ^= A[i][k];
i++;
}
j++;
}
return i;
} int main() {
getprime();
while (~scanf("%d%d", &m, &n)) {
memset(A, 0, sizeof(A));
int num;
for (int k = 0; k < n; k++) {
scanf("%d", &num);
for (int i = 0; i < m; i++) {
if (num % prime[i] == 0) {
int cnt = 0;
while (num % prime[i] == 0) {
num /= prime[i];
cnt++;
}
if (cnt % 2) A[i][k] = 1;
}
}
}
int sb = gauss();
bign ans = 1;
for (int i = 0; i < n - sb; i++) {
ans = ans + ans;
}
ans = ans - 1;
ans.Put();
printf("\n");
}
return 0;
} /*********************************************/ void bign::DelZero () {
while (len && num[len-1] == 0)
len--; if (len == 0) {
num[len++] = 0;
}
} void bign::Put () {
for (int i = len-1; i >= 0; i--)
printf("%lld", num[i]);
} void bign::operator = (char* number) {
len = strlen (number);
for (int i = 0; i < len; i++)
num[i] = number[len-i-1] - '0';
DelZero ();
} void bign::operator = (ll number) { len = 0;
while (number) {
num[len++] = number%10;
number /= 10;
} DelZero ();
} bool bign::operator < (const bign& b) const {
if (len != b.len)
return len < b.len;
for (int i = len-1; i >= 0; i--)
if (num[i] != b.num[i])
return num[i] < b.num[i];
return false;
} void bign::operator ++ () {
int s = 1; for (int i = 0; i < len; i++) {
s = s + num[i];
num[i] = s % 10;
s /= 10;
if (!s) break;
} while (s) {
num[len++] = s%10;
s /= 10;
}
} void bign::operator -- () {
if (num[0] == 0 && len == 1) return; int s = -1;
for (int i = 0; i < len; i++) {
s = s + num[i];
num[i] = (s + 10) % 10;
if (s >= 0) break;
}
DelZero ();
} bign bign::operator + (const int& b) {
bign a = b;
return *this + a;
} bign bign::operator + (const bign& b) {
int bignSum = 0;
bign ans; for (int i = 0; i < len || i < b.len; i++) {
if (i < len) bignSum += num[i];
if (i < b.len) bignSum += b.num[i]; ans.num[ans.len++] = bignSum % 10;
bignSum /= 10;
} while (bignSum) {
ans.num[ans.len++] = bignSum % 10;
bignSum /= 10;
} return ans;
} bign bign::operator - (const int& b) {
bign a = b;
return *this - a;
} bign bign::operator - (const bign& b) {
ll bignSub = 0;
bign ans;
for (int i = 0; i < len || i < b.len; i++) {
bignSub += num[i];
if (i < b.len)
bignSub -= b.num[i];
ans.num[ans.len++] = (bignSub + 10) % 10;
if (bignSub < 0) bignSub = -1;
else bignSub = 0;
}
ans.DelZero();
return ans;
} bign bign::operator * (const ll& b) {
ll bignSum = 0;
bign ans; ans.len = len;
for (int i = 0; i < len; i++) {
bignSum += num[i] * b;
ans.num[i] = bignSum % 10;
bignSum /= 10;
} while (bignSum) {
ans.num[ans.len++] = bignSum % 10;
bignSum /= 10;
} return ans;
} bign bign::operator * (const bign& b) {
bign ans;
ans.len = 0; for (int i = 0; i < len; i++){
int bignSum = 0; for (int j = 0; j < b.len; j++){
bignSum += num[i] * b.num[j] + ans.num[i+j];
ans.num[i+j] = bignSum % 10;
bignSum /= 10;
}
ans.len = i + b.len; while (bignSum){
ans.num[ans.len++] = bignSum % 10;
bignSum /= 10;
}
}
return ans;
} bign bign::operator / (const ll& b) { bign ans; ll s = 0;
for (int i = len-1; i >= 0; i--) {
s = s * 10 + num[i];
ans.num[i] = s/b;
s %= b;
} ans.len = len;
ans.DelZero();
return ans;
} int bign::operator % (const int& b) { bign ans; int s = 0;
for (int i = len-1; i >= 0; i--) {
s = s * 10 + num[i];
ans.num[i] = s/b;
s %= b;
} return s;
}