### 算法1

#### C++ 代码

#include<iostream>
#include<cstring>
#include<string>
using namespace std;

const int N = 1010;

int f[N][N];

int n;

string s;

int main()
{
memset(f, 0x3f, sizeof f);
cin >> s;
int len = s.size();
for(int i = 0; i < len; ++ i)
f[i][i] = 0;
for(int k = 2; k <= len; ++ k)
for(int i = 0; i < len; ++ i)
{
int j = i - k + 1;
if(j < 0) continue;
int &v = f[j][i];
int l = j, r = i;
while(s[l] == s[r]) -- r, ++ l;
if(l > r) v = 0;
else
{
v = min(v, f[l][r]);
v = min(v, f[j + 1][i] + 1);
v = min(v, f[j][i - 1] + 1);
}
}
printf("%d", f[0][len - 1]);
return 0;
}


### 算法1

#### C++ 代码

#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 2500;

PII mp[5000010];

int st[5000010];

int mi[N];

int n;

int main()
{
cin >> n;
int maxv = sqrt(n);
for(int i = 1; i <= maxv; ++ i)
mi[i] = i * i;
for(int i = 0; i <= maxv; ++ i)
for(int j = i; j <= maxv; ++ j)
if(mi[i] + mi[j] <= n && !st[mi[i] + mi[j]])
{
mp[mi[i] + mi[j]] = {i, j};
st[mi[i] + mi[j]] = 1;
}
int a, b, c, d;
for(int i = 0; i <= maxv; ++ i)
for(int j = i; j <= maxv; ++ j)
if(st[n - mi[i] - mi[j]])
{
PII t = mp[n - mi[i] - mi[j]];
a = i, b = j, c = t.x, d = t.y;
printf("%d %d %d %d", a, b, c, d);
return 0;
}
return 0;
}


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

using namespace std;

const int N = 10;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int g[N][N];

int stat[N][N];

int bstat[N][N];

int isvst[N][N];

string s;

set<string> st;

int sum;

int res;

class CHK
{
public:
int sum, cnt;
};

struct Point{
int x, y, w;
bool operator<(Point &b){
return w < b.w;
}
}points[N * N];

int idx;

int n, m;

CHK flood(int i, int j)
{
int sum = g[i][j], cnt = 1;
isvst[i][j] = 1;
CHK v = {sum, cnt};
for(int k = 0; k < 4; ++ k)
{
int ix = i + dx[k], iy = j + dy[k];
if(ix < 0 || iy < 0 || ix >= n || iy >= m) continue;
if(isvst[ix][iy]) continue;
if(stat[ix][iy] != stat[i][j]) continue;
CHK rt = flood(ix, iy);
v.cnt += rt.cnt, v.sum += rt.sum;
}
return v;
}

void fld(int i, int j)
{
isvst[i][j] = true;
for(int k = 0; k < 4; ++ k)
{
int ix = i + dx[k], iy = j + dy[k];
if(ix < 0 || iy < 0 || ix >= n || iy >= m)  continue;
if(stat[ix][iy] != stat[i][j]) continue;
if(isvst[ix][iy]) continue;
fld(ix, iy);
}
}

int getpart()
{
int partnum = 0;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
if(!isvst[i][j])
{
fld(i, j);
partnum ++;
}
return partnum;
}

bool check(int cnt)
{
memset(isvst, 0, sizeof isvst);
int part = getpart();
if(part != 2) return false;
memset(isvst, 0, sizeof isvst);
CHK v = flood(0, 0);
if((v.sum == sum / 2) && (v.cnt == cnt || (v.cnt == m * n - cnt)))
return true;
return false;
}

void dfs(int curs, int cnt)
{
if(st.count(s)) return;
if(cnt >= res) return;
if(curs >= sum / 2)
{
if(check(cnt)){
//int temp = res;
res = min(res, stat[0][0] ? cnt : (n * m - cnt));
//if(res < temp) memcpy(bstat, stat, sizeof stat);
}
return;
}
st.insert(s);
for(int i = 0; i < m * n; ++ i)
{
if(s[i] == '0')
{
int x = points[i].x, y = points[i].y;
s[i] = s[i] + 1;
stat[x][y] = 1;
dfs(curs + g[x][y], cnt + 1);
s[i] = s[i] - 1;
stat[x][y] = 0;
}
}
}

int main()
{
scanf("%d%d", &m, &n);
for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
{
cin >> g[i][j];
sum += g[i][j];
}
for(int i = 0; i < m * n; ++ i)
s += '0';

for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
points[idx ++ ] = {i, j, g[i][j]};
sort(points, points + m * n);
res = 0x3f3f3f3f;
dfs(0, 0);
if(res < 0x3f3f3f3f) printf("%d\n", res);
else printf("%d", 0);
/*  for(int i = 0; i < n; ++ i)
{
for(int j = 0; j < m; ++ j)
printf("%d ", bstat[i][j]);
printf("\n");
}*/
return 0;
}


### 算法1

##### floodfill
#include<iostream>
#include<cstring>
using namespace std;

const int N = 1010;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

char g[N][N];

bool st[N][N];

int n;

bool dfs(int x, int y)
{
st[x][y] = true;
bool tag1 = true;
bool tag2 = false;
for(int k = 0; k < 4; ++ k)
{
int ix = x + dx[k], iy =  y + dy[k];
if(ix < 0 || iy < 0 || ix >= n || iy >= n) continue;
if(g[ix][iy] == '.')
{
tag2 = true;
continue;
}
if(st[ix][iy]) continue;
if(g[ix][iy] == '#')
{
tag1 &= dfs(ix, iy);
}
}
return tag1 && tag2;
}

int main()
{
cin >> n;
int cnt = 0;
for(int i = 0; i < n; ++ i)
scanf("%s", g[i]);
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j)
if(g[i][j] == '#' && !st[i][j])
if(dfs(i, j)) ++ cnt;
printf("%d", cnt);
return 0;
}


### 算法1 2-sat算法，思路分分钟，写代码20分钟，然而各种细节调了一下午

#### C++ 代码

#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;

#define a first
#define b second

typedef pair<int, int> PII;

const int N = 210, M = 10010;

PII edges[M];

int st[2 * M]; // is in loop

//tarjan
int dfn[M * 2], low[M * 2], ts, stk[M * 2], top, ins[M * 2];
int id[M * 2], cnt;

int h[M * 2], e[2000010], ne[2000010], idx;

int mp[N];

int n, m;

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool is_cross(int i, int j)//check if two edges cross
{
int ia = mp[edges[i].a], ib = mp[edges[i].b];
if(ia > ib) swap(ia, ib);
int ja = mp[edges[j].a], jb = mp[edges[j].b];
if(ja > jb) swap(ja, jb);
if(ia < ja && ib < jb && ib > ja) return true;
if(ja < ia && jb < ib && jb > ia) return true;
return false;
}

void tarjan(int u)
{
dfn[u] = low[u] = ++ ts;
stk[++ top ] = u, ins[u] = true;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if(ins[j]) low[u] = min(dfn[j], low[u]);
}
if(dfn[u] == low[u])
{
++ cnt;
int k;
do{
k = stk[top --];
ins[k] = false;
id[k] = cnt;
}while(k != u);
}
}

int main()
{
int t;
scanf("%d", &t);
while(t --)
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
memset(st, 0, sizeof st);
memset(mp, 0, sizeof mp);
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(id, 0, sizeof id);
ts = 0, cnt = 0;
idx = 0;
for(int i = 1; i <= m; ++ i)
{
int a, b;
scanf("%d%d", &a, &b);
edges[i] = {a, b};
}
for(int i = 1; i <= n; ++ i)
{
int x;
scanf("%d", &x);
mp[x] = i;
}
if(m > (n * 3 - 6))
{
puts("NO");
continue;
}
for(int i = 1; i <= m; ++ i)
{
int a = edges[i].a, b = edges[i].b;
if((abs(mp[a] - mp[b]) == 1) || (abs(mp[a] - mp[b]) == n - 1))
st[i] = true, st[i + m] = true;
}
//for(int i = 1; i <= m; ++ i)
//  printf("%d %d %d %d\n", i, edges[i].a, edges[i].b, st[i]);
for(int i = 1; i <= m; ++ i)
if(st[i]) continue;
else
for(int j = 1; j < i; ++ j)
if(st[j]) continue;
else if(is_cross(i, j))
{
//printf("%d %d\n", i, j);
}
for(int i = 1; i <= 2 * m; ++ i)
if(!st[i] && !dfn[i])
tarjan(i);
bool tag = true;
//for(int i = 1; i <= 2 * m; ++ i)
//  printf("%d ", id[i]);
for(int i = 1; i <= m; ++ i)
if(!st[i] && id[i] == id[i + m])
{
tag = false;
break;
}
if(tag) printf("YES\n");
else printf("NO\n");
}
return 0;
}


#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;

#define a first
#define b second

typedef pair<int, int> PII;

const int N = 210, M = 10010;

PII edges[M];

int st[M]; // is in loop

//tarjan
int dfn[M * 2], low[M * 2], ts, stk[M * 2], top, ins[M * 2];
int id[M * 2], cnt;

int h[M * 2], e[97000010], ne[97000010], idx;

int mp[N];

int n, m;

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool is_cross(int i, int j)//check if two edges cross
{
int ia = mp[edges[i].a], ib = mp[edges[i].b];
if(ia > ib) swap(ia, ib);
int ja = mp[edges[j].a], jb = mp[edges[j].b];
if(ja > jb) swap(ja, jb);
if(ia < ja && ib < jb && ib > ja) return true;
if(ja < ia && jb < ib && jb > ia) return true;
return false;
}

void tarjan(int u)
{
dfn[u] = low[u] = ++ ts;
stk[++ top ] = u, ins[u] = true;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if(ins[j]) low[u] = min(dfn[j], low[u]);
}
if(dfn[u] == low[u])
{
++ cnt;
int k;
do{
k = stk[top --];
ins[k] = false;
id[k] = cnt;
}while(k != u);
}
}

int main()
{
int t;
scanf("%d", &t);
while(t --)
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
memset(st, 0, sizeof st);
memset(mp, 0, sizeof mp);
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(id, 0, sizeof id);
ts = 0, cnt = 0;
for(int i = 1; i <= m; ++ i)
{
int a, b;
scanf("%d%d", &a, &b);
edges[i] = {a, b};
}
for(int i = 1; i <= n; ++ i)
{
int x;
scanf("%d", &x);
mp[x] = i;
}

for(int i = 1; i <= m; ++ i)
{
int a = edges[i].a, b = edges[i].b;
if((abs(mp[a] - mp[b]) == 1) || (abs(mp[a] - mp[b]) == n - 1))
st[i] = true, st[i + m] = true;
}
//for(int i = 1; i <= m; ++ i)
//  printf("%d %d %d %d\n", i, edges[i].a, edges[i].b, st[i]);
for(int i = 1; i <= m; ++ i)
if(st[i]) continue;
else
for(int j = 1; j < i; ++ j)
if(st[j]) continue;
else if(is_cross(i, j))
{
//printf("%d %d\n", i, j);
}
for(int i = 1; i <= 2 * m; ++ i)
if(!st[i] && !dfn[i])
tarjan(i);
bool tag = true;
//for(int i = 1; i <= 2 * m; ++ i)
//  printf("%d ", id[i]);
for(int i = 1; i <= m; ++ i)
if(!st[i] && id[i] == id[i + m])
{
tag = false;
break;
}
if(tag) printf("YES\n");
else printf("NO\n");
}
return 0;
}


#include<iostream>
#include<cstring>
using namespace std;

typedef long long LL;

const int N = 11;

LL f[N][N * N][1 << N];

int lowbit(int x)
{
return x & -x;
}

int count1(int x)
{
int res = 0;
for(int i = x; i; i -= lowbit(i))
res ++;
return res;
}

int n, k;

int main()
{
cin >> n >> k;
for(int i = 0; i <= k; ++ i)
for(int j = 0; j < 1 << n; ++ j)
if(((j << 1) & j) || ((j >> 1) & j)) continue;
else f[1][i][j] = count1(j) == i ? 1 : 0;
for(int i = 2; i <= n; ++ i)
for(int j = 0; j <= k; ++ j)
for(int t = 0; t < 1 << n; ++ t)
if(((t << 1) & t) || ((t >> 1) & t))
continue;
else if(j >= count1(t))
{
for(int h = 0; h < 1 << n; ++ h)
if(((h << 1) & h) || ((h >> 1) & h)) continue;
else if((h & t) || ((h << 1) & t) || ((h >> 1) & t)) continue;
else f[i][j][t] += f[i - 1][j - count1(t)][h];
}
LL res = 0;
for(int i = 0; i < 1 << n; ++ i)
res += f[n][k][i];
cout << res;
return 0;
}


### 算法1

#### C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 10;

int n;

int g[5][7];

int st[5][7];

struct op{
int x, y, t;
}path[N], res[N];

int idx;

bool is_leaf()
{
bool tag = true;
for(int i = 0; i < 5; ++ i)
if(g[i][0])
tag = false;
return tag;
}

bool check_line(int x, int y)
{
int len = 1;
for(int i = 1; x - i >= 0; ++ i)
if(g[x - i][y] == g[x][y]) ++ len; else break;

for(int i = 1; x + i < 5; ++ i)
if(g[x + i][y] == g[x][y]) ++ len; else break;

return len >= 3;
}

void set_line(int x, int y)
{
st[x][y] = 1;
for(int i = 1; x - i >= 0; ++ i)
if(g[x - i][y] == g[x][y]) st[x - i][y] = 1; else break;

for(int i = 1;x + i < 5; ++ i)
if(g[x + i][y] == g[x][y]) st[x + i][y] = 1; else break;
}

bool check_col(int x, int y)
{
int len = 1;
for(int i = 1; y - i >= 0; ++ i)
if(g[x][y - i] == g[x][y]) ++ len; else break;

for(int i = 1; y + i < 7; ++ i)
if(g[x][y + i] == g[x][y]) ++ len; else break;

return len >= 3;
}

void set_col(int x, int y)
{
st[x][y] = 1;
for(int i = 1; y - i >= 0; ++ i)
if(g[x][y - i] == g[x][y]) st[x][y - i] = 1; else break;

for(int i = 1; y + i < 7; ++ i)
if(g[x][y + i] == g[x][y]) st[x][y + i] = 1; else break;
}

void mark()
{
memset(st, 0, sizeof st);
for(int i = 0; i < 5; ++ i)
for(int j = 0; j < 7; ++ j)
{
if(!g[i][j]) continue;
if(check_line(i, j)) set_line(i, j);
if(check_col(i, j)) set_col(i, j);
}
}

int remove()
{
int cnt = 0;
for(int i = 0; i < 5; ++ i)
for(int j = 0; j < 7; ++ j)
if(st[i][j])
g[i][j] = 0, ++ cnt;
return cnt;
}

void processing(int arr[])
{
int i = 0, j = 0;
while(i < 7 && arr[i]) ++ i, ++ j;
while(j < 7)
{
if(arr[j]) swap(arr[i], arr[j]), ++ i, ++ j;
else ++ j;
}
}

void drop()
{
for(int i = 0; i < 5; ++ i)
processing(g[i]);
}

void update()//1 右移  -1 左移
{
mark();
if(!remove()) return;
drop();
update();
}

bool dfs(int x, int y, int t, int k)
{
int bg[5][7];
memcpy(bg, g, sizeof g);
if(k > n) return false;
if(x + t < 0 || x + t >= 5) return false;
swap(g[x][y], g[x + t][y]);
drop();//!!!!!!
update();
path[idx ++ ] = {x, y, t};
if(is_leaf() && k == n)
{
memcpy(res, path, sizeof res);
memcpy(g, bg, sizeof g);
-- idx;
return true;
}
for(int i = 0; i < 5; ++ i)
for(int j = 0; j < 7; ++ j)
if(g[i][j])
{
if(dfs(i, j, 1, k + 1))
{
memcpy(g, bg, sizeof bg);
-- idx;
return true;
}
if(i > 0 && !g[i - 1][j])
if(dfs(i, j, -1, k + 1))
{
memcpy(g, bg, sizeof bg);
-- idx;
return true;
}
}
memcpy(g, bg, sizeof bg);
-- idx;
return false;
}

int main()
{

cin >> n;
for(int i = 0; i < 5; ++ i)
{
for(int j = 0; j < 8; ++ j)
{
int x;
cin >> x;
if(!x) break;
g[i][j] = x;
}
}

bool tag = false;
for(int i = 0; i < 5; ++ i)
{
for(int j = 0; j < 7; ++ j)
{
if(g[i][j])
{
if(dfs(i, j, 1, 1)){ tag = true; break; }
if(i > 0 && !g[i - 1][j])
if(dfs(i, j, -1, 1))
{ tag = true; break; }
}
}
if(tag) break;
}

if(tag)
{
for(int i = 0; i < n; ++ i)
printf("%d %d %d\n", res[i].x, res[i].y, res[i].t);
}
else printf("%d", -1);

return 0;
}


#include<iostream>
#include<cstring>
#include<bitset>
using namespace std;

const int N = 310, M = 610;

bitset<310> infect;

int n, p;

int res;

int h[N], ne[M], e[M], idx;

int d[N], q[N];

int cut[M];//当前边是否已被切断

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int ext()
{
int num = 0;
bitset<310> temp;
for(int u = 1; u <= n; ++ u)
{
if(!infect[u]) continue;
for(int i = h[u]; ~i; i = ne[i])
{
if(cut[i]) continue;
int j = e[i];
if(!infect[j])
{
++ num;
temp[j] = 1;
}
}
}
infect |= temp;
return num;
}

int inc()
{
int num = 0;
for(int u = 1; u <= n; ++ u)
{
if(!infect[u]) continue;
for(int i = h[u]; ~i; i = ne[i])
{
if(cut[i]) continue;
int j = e[i];
if(!infect[j])
{
++ num;
}
}
}
return num;
}

void dfs(int cnt)
{
if(cnt >= res) return;
if(inc() == 0)
{
res = cnt;
return;
}
for(int u = 1; u <= n; ++ u)
{
if(!infect[u]) continue;
for(int i = h[u]; ~i; i = ne[i])
{
if(cut[i]) continue;
int j = e[i];
//if(d[j] < d[u]) continue;
if(infect[j]) continue;
cut[i] = true;
bitset<310> bake = infect;
int num = ext();
//cout << infect << endl;
//cout << num << endl;
dfs(cnt + num);
cut[i] = false;
infect = bake;
}
}
}

int main()
{
scanf("%d%d", &n, &p);
infect[1] = 1;
memset(h, -1, sizeof h);
for(int i = 0; i < p; ++ i)
{
int a, b;
scanf("%d%d", &a, &b);
}
//bfs();
res = 0x3f3f3f3f;
dfs(1);
printf("%d", res);
return 0;
}


#include<iostream>
#include<cstring>
using namespace std;

const int N = 9;

int g[N][N];
int res[N][N];
int st[10];

string s;

int get(int x, int y)
{
memset(st, 0, sizeof st);
for(int i = 0; i < 9; ++ i)
if(g[x][i]) st[g[x][i]] = true;
for(int i = 0; i < 9; ++ i)
if(g[i][y]) st[g[i][y]] = true;
for(int i = x / 3 * 3; i < x / 3 * 3 + 3; ++ i)
for(int j = y / 3 * 3; j < y / 3 * 3 + 3; ++ j)
if(g[i][j]) st[g[i][j]] = true;
int res = 0;
for(int i = 1; i <= 9; ++ i)
if(!st[i])
++ res;
return res;
}

bool check(int x, int y, int k)
{
bool tag = true;
for(int i = 0; i < 9; ++ i)
if(g[x][i] == k) tag = false;
for(int i = 0; i < 9; ++ i)
if(g[i][y] == k) tag = false;
for(int i = x / 3 * 3; i < x / 3 * 3 + 3; ++ i)
for(int j = y / 3 * 3; j < y / 3 * 3 + 3; ++ j)
if(g[i][j] == k)
tag = false;
return tag;
}

bool dfs(int x, int y, int k, int cnt)
{
if(!check(x, y, k)) return false;
if(cnt == 0)
{
g[x][y] = k;
memcpy(res, g, sizeof res);
g[x][y] = 0;
return true;
}
g[x][y] = k;
int nx = 0, ny = 0;
int t = 0x3f3f3f3f;
for(int i = 0; i < 9; ++ i)
for(int j = 0; j < 9; ++ j)
{
if(!g[i][j] && get(i, j) < t)
t = get(i, j), nx = i, ny = j;
}
for(int i = 1; i <= 9; ++ i)
if(dfs(nx, ny, i, cnt - 1))
{
g[x][y] = 0;
return true;
}
g[x][y] = 0;
return false;
}

int main()
{
while(cin >> s, s != "end")
{
int cnt = 81;
memset(g, 0, sizeof g);
for(int i = 0; i < 81; ++ i)
if(s[i] != '.') g[i / 9][i % 9] = s[i] - '0', -- cnt;
int x = 0, y = 0;
int t = 0x3f3f3f3f;
for(int i = 0; i < 9; ++ i)
for(int j = 0; j < 9; ++ j)
{
if(!g[i][j] && get(i, j) < t)
t = get(i, j), x = i, y = j;
}
for(int i = 1; i <= 9; ++ i)
if(dfs(x, y, i, cnt - 1))
break;
for(int i = 0; i < 9; ++ i)
for(int j = 0; j < 9; ++ j)
printf("%d", res[i][j]);
printf("\n");
}
return 0;