Fatin

back

1.1万

_三七_
ICE_TEA

mushanyu
WJYY
Kole
nothing_sybs
ggkkpp

StarLi9ht
KylinLzw

4607wjq
AC天
Evander.Liam
o樱桃小完犊子o

Fatin
1个月前

Fatin
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int mod = 47;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);

string a, b;
cin >> a >> b;

long long x = 1, y = 1;
for (int i = 0;i < a.size();i ++) x = x * (a[i] - 'A' + 1) % mod;
for (int i = 0;i < b.size();i ++) y = y * (b[i] - 'A' + 1) % mod;

if (x == y) puts("GO");
else puts("STAY");
return 0;
}


Fatin
4个月前

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 510;
bool st[N];
int g[N][N],dist[N];
int n, m;

int dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[1] = 0;

for (int i = 1; i <= n; i ++ )
{
int t = -1;//这个记得写进循环里边，因为每次都要贪心最近的那个编号

for (int j = 1; j <= n; j ++ )
if (! st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if (t == n) break;
st[t] = true;

for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j],dist[t] + g[t][j]);

}

if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);

memset(g, 0x3f,sizeof g);
cin >> n >> m;

while (m -- )
{
int a, b, d;
cin >> a >> b >> d;
g[a][b] = min(g[a][b], d);
}

cout << dijkstra() << "\n";
return 0;
}


Fatin
4个月前

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;

int h[N],e[N],ne[N],idx;
int q[N],d[N];
int n, m;

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

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

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

return tt == n - 1;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);

memset(h, -1, sizeof h);

cin >> n >> m;
while (m -- )
{
int a, b;
cin >> a >> b;
d[b] ++;
}

if(topsort())
{
for (int i = 0; i < n; i ++ )
cout << q[i] << ' ';
puts("");
}
else puts("-1");

return 0;
}


Fatin
4个月前

cy

Fatin
4个月前

cy

Fatin
4个月前

b[l] += c;
b[r + 1] -= c; //这里记得＋1，要等下标跑出去的时候才减掉它

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2e5 + 10;

int a[N];
int n, m, k;

int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);

cin >> n >> m >> k;
while (n -- )
{
int ti, ci;
cin >> ti >> ci;
int l = ti - k - ci + 1,r = ti - k;
if(r > 0)
{
a[max(1,l)] ++;
a[r + 1] --;
}
}

for (int i = 1; i <= N; i ++ ) a[i] += a[i - 1];

while (m -- )
{
int t;
cin >> t;
cout << a[t] << "\n";
}

return 0;
}


Fatin
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 33, M = 300010;

int n, x;
int w[N], f[M];

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

int sum = 0;
for (int i = 0; i < n; i ++ )
{
scanf("%d", &w[i]);
sum += w[i];
}

int m = sum - x;
for (int i = 0; i < n; i ++ )
for (int j = m; j >= w[i]; j -- )
f[j] = max(f[j], f[j - w[i]] + w[i]);

printf("%d\n", sum - f[m]);
return 0;
}



Fatin
4个月前

dfs要处理好末尾情况和普通情况的协调，要提起归纳好
bfs要处理好特殊情况的返回

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int h[N],e[N],ne[N],idx;
int d[N],q[N];
int n, m;

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

int bfs()
{
int hh = 0,tt = 0;
q[0] = 1;
memset(d, - 1,sizeof d);
d[1] = 0;

while (hh <= tt)
{
int t = q[hh ++];
for (int i = h[t];i != -1;i = ne[i])
{
int j = e[i];
if(d[j] == -1)
{
d[j] = d[t] + 1;
q[++ tt] = j;
}
}
}

return d[n];
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);

memset(h, -1, sizeof h);

cin >> n >> m;
while (m -- )
{
int a, b;
cin >> a >> b;
}

cout << bfs() << "\n";
return 0;
}


Fatin
4个月前
#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;

int h[N],ne[2 * N],e[2 * N];
int idx;
bool st[N];
int n;
int ans = N;

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

int dfs(int u)
{
int res = 0;
st[u] = true; //标记这个点已经成为父亲，所以遍历的时候不会穿过这个节点

int sum = 1; //这个sum是给后面求头顶上面那一堆连通图准备的

for (int i = h[u];i != -1;i = ne[i]) //h[i]存的是门牌
{
int j = e[i]; //e[i]存的才是点本身
if(!st[j])
{
int s = dfs(j);
//到这里下面的那些数据已经处理好了，s返回的是子树的结点数
res = max(res , s); //去掉没用的数据，只取子树连接点数最大的那个
sum += s; //这个sum先加起来，依然是给头顶那一堆准备的
}

}

res = max(res, n - sum);
ans = min(ans, res); //每次都更新一下答案

return sum; //这里返回的是子树的大小，这样上面的父亲就可以继续sum += s;来运作这个递归
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);

memset(h, -1, sizeof h);

cin >> n; //有n个节点，树没有环，可以移动任意两个最后能归于一条线，那就是n - 1条边
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
cin >> a >> b;