237Rookie

3347

ansLLL

ljlhandsome

Browsy
ᝰE᥊ρꫀᥴℸ²⁰.

7天前

//嗷嗷嗷
//dfs, 剪枝

#### C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 500;//多开一点， 最后一天加30会爆
int day[N];
int d[N];
int money[3];
int n;
int res = 0x3f3f3f3f;
void dfs (int u, int v)//u是要走哪一天了，v是到这一天的钱数（不一定是最小的）
{
if (v >= d[u]) return;//剪枝
d[u] = v;//存导这一天的最少钱
if (u > day[n])//全走完辣，开始判断
{
res = min (v, res);
return;
}
int t = lower_bound (day + 1, day + 1 + n, u) - day;//二分找到该走哪一天了
dfs (day[t] + 1, v + money[0]);
dfs (day[t] + 7, v + money[1]);
dfs (day[t] + 30, v + money[2]);
}
int main ()
{
memset (d, 0x3f, sizeof d);
cin >> n;
for (int i = 1; i <= n; i ++) cin >> day[i];
day[n + 1] = 400;
for (int i = 0; i < 3; i ++) cin >> money[i];
dfs (day[0], 0);
cout << res;
return 0;
}


7天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 500;
int day[N];
int d[N];
int money[3];
int n;
int res = 0x3f3f3f3f;
void dfs (int u, int v)
{
if (v >= d[u]) return;
d[u] = v;
if (u > day[n])
{
res = min (v, res);
return;
}
int t = lower_bound (day + 1, day + 1 + n, u) - day;
dfs (day[t] + 1, v + money[0]);
dfs (day[t] + 7, v + money[1]);
dfs (day[t] + 30, v + money[2]);
}
int main ()
{
memset (d, 0x3f, sizeof d);
cin >> n;
for (int i = 1; i <= n; i ++) cin >> day[i];
day[n + 1] = 400;
for (int i = 0; i < 3; i ++) cin >> money[i];
dfs (day[0], 0);
cout << res;
return 0;
}


9天前
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 14;
int f[N];
bool st[N];
int n;
int res = 0;
bool check (int x)
{
int t = sqrt (x);
if (t * t == x) return true;
else return false;
}
void dfs (int u, int v)
{
if (u == n)
{
res ++;
return;
}
for (int i = 1; i <= n; i ++)
{
if (i > 1 && !st[i] && !st[i - 1] && f[i] == f[i - 1]) continue;
//为了避免重复，相同的数下标小的一定在下标大的前面（排序过了）
//即如果前面的数跟我一样，但是他没被使用，那么我也不能使用
if (!st[i])
{
if (check (f[i] + v))
{
st[i] = 1;
dfs (u + 1, f[i]);
st[i] = 0;
}
}
}
}
int main ()
{
cin >> n;
for (int i = 1; i <= n; i ++) cin >> f[i];
sort (f + 1, f + 1 + n);
for (int i = 1; i <= n; i ++)
{
if (i > 1 && f[i] == f[i - 1]) continue;
st[i] = 1;
dfs (1, f[i]);
st[i] = 0;
}
cout << res;
return 0;
}


9天前
#include <iostream>
#include <cstring>
using namespace std;
const int N = 210;
bool st[N];
int f[N], d[N];
int n;
int A;
struct point
{
int a, b, c;
}op[N];
int main ()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
scanf ("%d%d", &f[i], &d[i]);
f[i] *= 2;
if (!d[i]) A = i;
}
for (int t = 0; t < 200; t ++)
{
memset (op, 0, sizeof op);
for (int i = 1; i <= n; i ++)
{
if (!st[i]) f[i] += d[i];
if (f[i] < 2 || f[i] > 198)
{
if (i == A)
{
cout << t / 2 + 1;
return 0;
}
st[i] = 1;
}
else
{
if (!op[f[i]].a) op[f[i]].a = i;
else if (!op[f[i]].b) op[f[i]].b = i;
else op[f[i]].c = i;
}
}
for (int i = 2; i <= 198; i ++)
{
if (op[i].a && op[i].b && op[i].c)
{
if (!d[op[i].a]) swap (d[op[i].b], d[op[i].c]);
else if (!d[op[i].b]) swap (d[op[i].a], d[op[i].c]);
else swap (d[op[i].a], d[op[i].b]);
}
else if (op[i].a && op[i].b) swap (d[op[i].a], d[op[i].b]);
}
}
printf ("Cannot fall!");
return 0;
}


22天前
#include <iostream>

using namespace std;

int n;
bool check (int x)
{
if (x < 2) return false;
if (x == 2) return true;
for (int i = 2; i <= x / i; i ++)
if (x % i == 0) return false;
return true;
}
int solve (int x)
{
for (int i = x + 1; 1; i ++)
if (check (i))
{
if (check (i - 6) || check (i + 6)) return i;
}
}
int main ()
{
cin >> n;
if (check (n))
{
if (check (n - 6)) cout << "Yes" << endl << n - 6;
else if (check (n + 6)) cout << "Yes" << endl << n + 6;
else
{
cout << "No" << endl;
cout << solve (n);
}
}
else
{
puts ("No");
cout << solve (n);
}
return 0;
}


29天前
#include <iostream>

using namespace std;
const int N = 104708;
int res[N];
bool st[N];
int T;
int cnt = 1;
void check ()
{
for (int i = 2; i <= N; i ++)
{
if (!st[i]) res[cnt ++] = i;
for (int j = 1; res[j] <= N / i; j ++)
{
st[res[j] * i] = true;
if (i % res[j] == 0) break;
}
}
}
int main ()
{
check ();
//cout << cnt << endl;
int x;
while (cin >> x) printf ("%d\n", res[x]);
return 0;
}


30天前
//闰年：（是4的倍数且不是100的倍数）或 是400的倍数
#include <iostream>

using namespace std;
int a, b;
int check (int x)
{
int res = 0;
int year = x / 10000;
for (int i = 1; i < year; i ++)
{
if ((i % 4 == 0 && i % 100 != 0) || i % 400 == 0) res += 366;
else res += 365;
}
int cnt = year * 10000;
int month = (x - cnt) / 100;
for (int i = 1; i < month; i ++)
if (i == 2)
{
if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) res += 29;
else res += 28;
}
else if (i == 4 || i == 6 || i == 9 || i == 11) res += 30;
else res += 31;
res += x - cnt - month * 100;
//cout << year << ' ' << month << ' ' << x - cnt - month * 100<< ' ' << res << endl;
return res;
}
int main ()
{
while (cin >> a >> b)
{
if (a > b) swap (a, b);
printf ("%d\n", check (b) - check (a) + 1);
}
return 0;
}


1个月前
#include <iostream>

using namespace std;
int f[6][6];
bool st[6][6];
int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
int n, m, a, b;
int res = 0x3f3f3f3f;
void dfs (int x, int y, int v, int w)
{
if (x == a && y == b)
{
res = min (res, v);
return;
}
if (v >= res) return;
for (int i = 0; i < 4; i ++)
{
int da = x + dx[i], db = y + dy[i];
if (da >= 0 && db >= 0 && da < 6 && db < 6 && !st[da][db])
{
st[da][db] = true;
dfs (da, db, v + w * f[da][db], (w * f[da][db]) % 4 + 1);
st[da][db] = false;
}
}
}
int main ()
{
for (int i = 0; i < 6; i ++)
for (int j = 0; j < 6; j ++)
scanf ("%d", &f[i][j]);
cin >> n >> m >> a >> b;
dfs (n, m, 0, 1);
cout << res;
return 0;
}


1个月前
#include <iostream>

using namespace std;
const int N = 510;
int f[N][N];
int n;
int main ()
{
cin >> n;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
scanf ("%d", &f[i][j]);
int res = 0;
for (int k = n; k >= 2; k --)
for (int i = 1; i <= n; i ++)
for (int j = i + 1; j <= n; j ++)
{
f[i][j] = f[j][i] = min (f[i][j], f[i][k] + f[k][j]);
if (i >= k && j >= k) res += f[i][j] * 2;
}
cout << res;

return 0;
}


1个月前
#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e4 + 10, M = 131;
char a[N], b[N];
unordered_set<ULL> s;
int n, m;
ULL s1[N], s2[N], p[N];
bool check (int u)
{
s.clear ();
for (int i = 1; i + u - 1 <= n; i ++)
{
int op = i;
int j;
for (j = i; j < i + u; j ++)
if (a[j] >= '0' && a[j] <= '9')
{
i = j;
break;
}
if (j == op + u) s.insert (s1[op + u - 1] - s1[op - 1] * p[u]);
}
for (int i = 1; i + u - 1 <= m; i ++)
{
int op = i;
int j;
for (j = i; j < i + u; j ++)
if (b[j] >= '0' && b[j] <= '9')
{
i = j;
break;
}
if (j == op + u && s.count (s2[op + u - 1] - s2[op - 1] * p[u])) return true;
}
return false;
}
int main ()
{
cin >> a + 1 >> b + 1;
n = strlen (a + 1), m = strlen (b + 1);
p[0] = 1;
for (int i = 1; i <= max (n, m); i ++)
{
p[i] = p[i - 1] * M;
if (i <= n) s1[i] = s1[i - 1] * M + a[i];
if (i <= m) s2[i] = s2[i - 1] * M + b[i];
}
int l = 0, r = min (n, m);
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check (mid)) l = mid;
else r = mid - 1;
}
cout << l;
return 0;
}