match和walk當場AC，travel不會，所以不貼了～
clear:
[cpp]
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#define uns unsigned
#define int64 long long
#ifdef WIN32
#define fmt64 "%I64d"
#else
#define fmt64 "%lld"
#endif
#define oo 0x13131313
#define REP(i, n) for (i = 0; i < (n); ++i)
using namespace std;
int A, B, C, D;
bool a[18][300][300];
char sum[300][300];
int mark, vst[300], cp[300], ans = oo;
struct edge { int t; edge *n; } edges[500], *adj = edges, *lst[300];
bool getbool()
{
char c = getchar();
for (; c != '0' && c != '1'; c = getchar());
return c == '1';
}
bool hun(int x)
{
for (edge *e = lst[x]; e; e = e->n)
if (vst[e->t] != mark)
if (vst[e->t] = mark, !cp[e->t] || hun(cp[e->t]))
return cp[e->t] = x, 1;
return 0;
}
void check(int base)
{
int i, j, res = 0;
adj = edges, memset(lst, 0, sizeof lst);
for (i = 1; i <= B; ++i)
for (j = 1; j <= C; ++j)
if (sum[i][j])
*adj = (edge){j, lst[i]}, lst[i] = adj++;
memset(cp, 0, sizeof cp);
for (i = 1; i <= B; ++i)
++mark, res += hun(i);
if (res + base < ans)
ans = res + base;
}
void dfs(int x, int base)
{
if (x > A) return check(base);
dfs(x + 1, base);
int i, j;
for (i = 1; i <= B; ++i)
for (j = 1; j <= C; ++j)
sum[i][j] -= a[x][i][j];
dfs(x + 1, base + 1);
for (i = 1; i <= B; ++i)
for (j = 1; j <= C; ++j)
sum[i][j] += a[x][i][j];
}
int main()
{
int i, j, k;
for (scanf("%d", &D); D--; ) {
scanf("%d%d%d", &A, &B, &C);
int mini = min(A, min(B, C));
memset(sum, 0, sizeof sum);
for (i = 1; i <= A; ++i)
for (j = 1; j <= B; ++j)
for (k = 1; k <= C; ++k)
if (A == mini)
sum[j][k] += a[i][j][k] = getbool();
else if (B == mini)
sum[i][k] += a[j][i][k] = getbool();
else
sum[i][j] += a[k][i][j] = getbool();
if (B == mini)
swap(A, B);
else if (C == mini)
swap(A, C), swap(B, C);
ans = oo;
dfs(1, 0);
printf("%d\n", ans);
}
}
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#define uns unsigned
#define int64 long long
#ifdef WIN32
#define fmt64 "%I64d"
#else
#define fmt64 "%lld"
#endif
#define oo 0x13131313
#define REP(i, n) for (i = 0; i < (n); ++i)
using namespace std;
int A, B, C, D;
bool a[18][300][300];
char sum[300][300];
int mark, vst[300], cp[300], ans = oo;
struct edge { int t; edge *n; } edges[500], *adj = edges, *lst[300];
bool getbool()
{
char c = getchar();
for (; c != '0' && c != '1'; c = getchar());
return c == '1';
}
bool hun(int x)
{
for (edge *e = lst[x]; e; e = e->n)
if (vst[e->t] != mark)
if (vst[e->t] = mark, !cp[e->t] || hun(cp[e->t]))
return cp[e->t] = x, 1;
return 0;
}
void check(int base)
{
int i, j, res = 0;
adj = edges, memset(lst, 0, sizeof lst);
for (i = 1; i <= B; ++i)
for (j = 1; j <= C; ++j)
if (sum[i][j])
*adj = (edge){j, lst[i]}, lst[i] = adj++;
memset(cp, 0, sizeof cp);
for (i = 1; i <= B; ++i)
++mark, res += hun(i);
if (res + base < ans)
ans = res + base;
}
void dfs(int x, int base)
{
if (x > A) return check(base);
dfs(x + 1, base);
int i, j;
for (i = 1; i <= B; ++i)
for (j = 1; j <= C; ++j)
sum[i][j] -= a[x][i][j];
dfs(x + 1, base + 1);
for (i = 1; i <= B; ++i)
for (j = 1; j <= C; ++j)
sum[i][j] += a[x][i][j];
}
int main()
{
int i, j, k;
for (scanf("%d", &D); D--; ) {
scanf("%d%d%d", &A, &B, &C);
int mini = min(A, min(B, C));
memset(sum, 0, sizeof sum);
for (i = 1; i <= A; ++i)
for (j = 1; j <= B; ++j)
for (k = 1; k <= C; ++k)
if (A == mini)
sum[j][k] += a[i][j][k] = getbool();
else if (B == mini)
sum[i][k] += a[j][i][k] = getbool();
else
sum[i][j] += a[k][i][j] = getbool();
if (B == mini)
swap(A, B);
else if (C == mini)
swap(A, C), swap(B, C);
ans = oo;
dfs(1, 0);
printf("%d\n", ans);
}
}
seq:
[cpp]
#include <cstdio>
#ifdef WIN32
#define fmt64 "%I64d"
#else
#define fmt64 "%lld"
#endif
#define int64 long long
using namespace std;
int64 N, K, M, P;
int64 fpm (int64 a, int64 b)
{
int64 res = 1;
for (; b; b >>= 1, a = a * a % P)
if (b & 1) res = res * a % P;
return res;
}
int main ()
{
freopen ("seq.in", "r", stdin);
freopen ("seq.out", "w", stdout);
scanf (fmt64 fmt64 fmt64 fmt64, &N, &K, &M, &P);
N %= P;
printf (fmt64"\n", (N * fpm(M, K - 1) % P - (M + 1) * M / 2 % P * (K - 1) % P * fpm(M, K - 2) % P + P) % P);
}
#include <cstdio>
#ifdef WIN32
#define fmt64 "%I64d"
#else
#define fmt64 "%lld"
#endif
#define int64 long long
using namespace std;
int64 N, K, M, P;
int64 fpm (int64 a, int64 b)
{
int64 res = 1;
for (; b; b >>= 1, a = a * a % P)
if (b & 1) res = res * a % P;
return res;
}
int main ()
{
freopen ("seq.in", "r", stdin);
freopen ("seq.out", "w", stdout);
scanf (fmt64 fmt64 fmt64 fmt64, &N, &K, &M, &P);
N %= P;
printf (fmt64"\n", (N * fpm(M, K - 1) % P - (M + 1) * M / 2 % P * (K - 1) % P * fpm(M, K - 2) % P + P) % P);
}
cake:
[cpp]
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#define uns unsigned
#define int64 long long
#ifdef WIN32
#define fmt64 "%I64d"
#else
#define fmt64 "%lld"
#endif
#define oo 0x13131313
#define REP(i, n) for (i = 0; i < (n); ++i)
#define maxn (40 * 40 * 40 + 5)
#define dual(e) (edges + (((e) - edges) ^ 1))
using namespace std;
struct edge { int t, f; edge *n; };
edge edges[maxn * 10], *adjc = edges, *adj[maxn];
int P, Q, R, D, tot, S, T, ans;
int p[45][45][45], v[45][45][45], q[maxn], dis[maxn];
void link (int u, int v, int f)
{
if (u && v) {
*adjc = (edge) {v, f, adj[u]}, adj[u] = adjc++;
*adjc = (edge) {u, 0, adj[v]}, adj[v] = adjc++;
}
}
bool bfs ()
{
int h, t;
memset (dis, 0, sizeof dis), dis[S] = 1;
for (q[h = t = S] = -1; ~h; h = q[h])
for (edge *e = adj[h]; e; e = e->n)
if (e->f && !dis[e->t]) {
dis[e->t] = dis[h] + 1;
t = q[t] = e->t, q[t] = -1;
}
return dis[T];
}
int dfs (int u, int f)
{
if (u == T) return f;
int l = f;
for (edge *e = adj[u]; e; e = e->n)
if (e->f && dis[e->t] == dis[u] + 1) {
int x = dfs (e->t, min(e->f, f));
e->f -= x, dual (e)->f += x, f -= x;
if (!f) return l;
}
return dis[u] = -1, l - f;
}
int main ()
{
freopen ("cake.in", "r", stdin);
freopen ("cake.out", "w", stdout);
int i, j, k;
scanf ("%d%d%d%d", &P, &Q, &R, &D);
for (k = 1; k <= R; ++k)
for (i = 1; i <= P; ++i)
for (j = 1; j <= Q; ++j) {
scanf ("%d", v[i][j] + k);
p[i][j][k] = ++tot;
}
S = ++tot, T = ++tot;
for (i = 1; i <= P; ++i)
for (j = 1; j <= Q; ++j) {
link (S, p[i][j][1], oo);
p[i][j][R + 1] = T;
for (k = 1; k <= R; ++k) {
link (p[i][j][k], p[i][j][k + 1], v[i][j][k]);
if (k > D) {
link (p[i][j][k], p[i + 1][j][k - D], oo);
link (p[i][j][k], p[i - 1][j][k - D], oo);
link (p[i][j][k], p[i][j + 1][k - D], oo);
link (p[i][j][k], p[i][j - 1][k - D], oo);
}
}
}
for (; bfs (); )
ans += dfs (S, oo);
printf ("%d\n", ans);
}
