10.8万

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 130;

int n, res;
int g[N][N];

//  上左下右
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
void dfs(int x, int y, int dir, int step)
{
if(x < 1 or x > n or y < 1 or y > n or g[x][y])  return;

int a, b;
stack<PII> stk;
while(true)
{
g[x][y] = 2;
step ++;
stk.push({x, y});

a = x + dx[dir], b = y + dy[dir];
if(a > n or a < 1 or b > n or b < 1 or g[a][b])  break;
x = a, y = b;
}
res = max(res, step);
if(g[a][b] != 2)
{
for(int i = 0; i < 4; i ++)
{
int a = x + dx[i], b = y + dy[i];
dfs(a, b, i, step);
}
}
while(stk.size())
{
int x = stk.top().x, y = stk.top().y;  stk.pop();
g[x][y] = 0;
}
}

int main()
{
int m;
scanf("%d%d", &n, &m);
while(m --)
{
char s[20];
scanf("%s", s);
int x = 0, y = s[0] - 'A' + 1;
for(int i = 1; s[i]; i ++)  x = x * 10 + s[i] - '0';
g[x][y] = 1;
}

dfs(1, 1, 2, 0);
dfs(1, 1, 3, 0);

printf("%d\n", res);

return 0;
}


#### 有向图的强连通分量

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010, M = N << 1;

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

int n;

int dfn[N], low[N], tot;
int id[N], cnt;
int q[N], tt = -1;
bool st[N];

void tarjan(int u)
{
dfn[u] = low[u] = ++ tot;
q[++ tt] = u;
st[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(st[j])
low[u] = min(low[u], dfn[j]);
}

if(dfn[u] == low[u])
{
++ cnt;
int y;
do{
y = q[tt --];
st[y] = false;
id[y] = cnt;
}while(y != u);
}
}

int din[N], dout[N];

int main()
{
memset(h, -1, sizeof h);

scanf("%d", &n);
for(int i = 1; i <= n; i ++)
{
int x;
}

for(int i = 1; i <= n; i ++)
if(!dfn[i])  tarjan(i);

for(int i = 1; i <= n; i ++)
for(int j = h[i]; ~j; j = ne[j])
{
int k = e[j];
int a = id[i], b = id[k];
if(a != b)  dout[a] ++, din[b] ++;
}

int x = 0, y = 0;
for(int i = 1; i <= cnt; i ++)
{
if(!din[i])  x ++;
if(!dout[i])  y ++;
}
printf("%d\n%d\n", x, cnt == 1 ? 0 : max(x, y));
return 0;
}


#### DP

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 1010;

bool st[N][N];
int f[N][N];

int main()
{
int n, k;
scanf("%d%d", &n, &k);
while(k --)
{
int x, y;
scanf("%d%d", &x, &y);
st[x][y] = true;
}

int res = 0;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(st[i][j])  continue;
else
{
f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;
res = max(res, f[i][j]);
}
printf("%d\n", res);
return 0;
}


#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 110, M = 20010, INF = 0x3f3f3f3f;

int v[N];
int f[N][M];

vector<int> res, path;
void dfs(int i, int j)
{
if(!i)
{
if(!res.size() or path < res)  res = path;
return;
}
if(f[i][j] == f[i - 1][j])  dfs(i - 1, j);
path.push_back(v[i]);
for(int k = j - v[i]; k >= 0; k -= v[i])
if(f[i][j] == f[i - 1][k] + 1)  dfs(i - 1, k);
path.pop_back();
}

int main()
{
int n, m;
scanf("%d%d", &m, &n);
for(int i = 1; i <= n; i ++)  scanf("%d", &v[i]);

sort(v + 1, v + n + 1, greater<int>());

memset(f, 0x3f, sizeof f);
f[0][0] = 0;

for(int i = 1; i <= n; i ++)
{
for(int k = 0; k < v[i]; k ++)
{
int t = f[i - 1][k];
for(int j = k; j <= m; j += v[i])
{
f[i][j] = min(f[i - 1][j], t + 1);
t = min(t, f[i - 1][j]);
}
}
}
printf("%d ", f[n][m]);
dfs(n, m);
for(int i : res)  printf("%d ", i);
return 0;
}


#include<cstdio>
#include<cstring>

const int N = 12, M = 1e6;

int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}

int a[N];
bool f[M];
int main()
{
int n;
scanf("%d", &n);

int d = 0;
for(int i = 0; i < n; i ++)  scanf("%d", &a[i]),  d = gcd(d, a[i]);

if(d > 1)  return 0 * puts("0");

f[0] = true;
for(int i = 0; i < n; i ++)
for(int j = a[i]; j < M; j ++)
f[j] |= f[j - a[i]];

int res = 0;
for(int i = 0; i < M; i ++)
if(!f[i])  res = i;
printf("%d\n", res);
return 0;
}


1个月前

#### 模拟

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int check(int n)
{
static int st[10];
memset(st, 0, sizeof st);

string s;
while(n)
{
int t = n % 10;
if(st[t])  return false;
st[t] = true;
s += '0' + t;
n /= 10;
}
reverse(s.begin(), s.end());

n = s.size();
memset(st, 0, sizeof st);

int p = 0, times = n;
while(times --)
{
int m = s[p] - '0';
while(m --)  p = (p + 1) % n;
if(st[p])  return false;
st[p] = true;
}
return p == 0;
}

int main()
{
int n;
scanf("%d", &n);
while(!(check( ++ n)));
printf("%d\n", n);
return 0;
}


1个月前

#### 01背包

#include<cstdio>
#include<cstring>

typedef long long LL;

const int N = 40 * 40;

LL f[N];

int main()
{
int n;
scanf("%d", &n);

if((1 + n) * n / 2 % 2)  return 0 * puts("0");

int m = (1 + n) * n / 4;

f[0] = 1;
for(int i = 1; i <= n; i ++)
for(int j = m; j >= i; j --)
f[j] += f[j - i];

printf("%lld\n", f[m] / 2);
return 0;
}


1个月前

#### 拓扑排序DP

const int N = 100010, M = 200010;

int h[N], e[M], ne[M], idx;
int d[N];
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
d[b] ++;
}

int q[N], n;
bool topsort()
{
int hh = 0, tt = -1;
for(int i = 0; i < n; i ++)
if(!d[i])  q[ ++ tt] = i;

while(hh <= tt)
{
int u = q[hh ++];
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if( -- d[j] == 0)  q[ ++ tt] = j;
}
}
return tt == n - 1;
}

int f[N][26];       //  到i位置j颜色出现了几次
class Solution {
public:
int largestPathValue(string colors, vector<vector<int>>& edges) {
memset(h, -1, sizeof h);
memset(d, 0, sizeof d);
idx = 0,  n = colors.size();

for(auto &v : edges)
{
int a = v[0], b = v[1];
}

if(!topsort())  return -1;

int res = 0;
memset(f, 0, sizeof f);
for(int l = 0; l < n; l ++)
{
int u = q[l];
f[u][colors[u] - 'a'] ++;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
for(int k = 0; k < 26; k ++)
{
f[j][k] = max(f[j][k], f[u][k]);
}
}
for(int k = 0; k < 26; k ++)  res = max(res, f[u][k]);
}
return res;
}
};


1个月前

#### 二分&RMQ

typedef long long LL;

const int N = 100010, mod = 1e9 + 7;

int n, m;
int a[N];
LL sum[N];
int f[N][18];

void init()
{
sum[0] = 0;
for(int i = 1; i <= n; i ++)  sum[i] = sum[i - 1] + a[i];
for(int j = 0; j < 18; j ++)
for(int i = 1; i + (1 << j) - 1 <= n; i ++)
if(!j)  f[i][j] = a[i];
else  f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}

int query(int l, int r)
{
int k = log2(r - l + 1);
return min(f[l][k], f[r - (1 << k) + 1][k]);
}

class Solution {
public:
int maxSumMinProduct(vector<int>& nums) {

n = nums.size();
for(int i = 1; i <= n; i ++)  a[i] = nums[i - 1];
init();

LL res = 0;
for(int i = 1; i <= n; i ++)
{
int l = 1, r = i;
while(l < r)
{
int mid = l + r >> 1;
if(query(mid, i) >= a[i])  r = mid;
else  l = mid + 1;
}
int left = l;

l = i, r = n;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(query(i, mid) >= a[i])  l = mid;
else  r = mid - 1;
}
l = left;

res = max(res, (sum[r] - sum[l - 1]) * a[i]);
}

int ans = res % mod;
return ans;
}
};


1个月前

#### 二分

class Solution {
public:
int maxDistance(vector<int>& a, vector<int>& b) {

int res = 0;
for(int i = 0; i < a.size(); i ++)
{
if(i + 1 >= b.size())  break;
int l = i, r = b.size() - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(b[mid] >= a[i])  l = mid;
else  r = mid - 1;
}
res = max(res, l - i);
}
return res;
}
};