Andrew Stankevich's Contest (1)
打一半出門了，回來才補完了。。。各種大數又不能上java。。也是蛋疼無比
A：根據置換循環節很容易得出要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
#include
#include
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
#include
#include
#include
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 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 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
#include
#include
#include
#include
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 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
#include
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
#include
#include
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<>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
#include
#include
#include
#include
#include
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 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
#include
#include
#include
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
#include
#include
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;
}
