3764

mjd
scc

Kazimierz

huangbq

kaggle

xxxxx123

4_SS.
Carson_cyc

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

int n;
const int N = 5010;
int q[N];
int cnt[N], res[N];

int main()
{
cin>> n;
for(int i = 1; i <= n; i++)
cin>> q[i];
for(int i = 1; i <= n; i++)
{
memset(cnt, 0, sizeof cnt);
int mx = 0, id;
for(int j = i; j <= n; j++)
{
cnt[q[j]] ++;
int t = cnt[q[j]];
if(t > mx || t == mx && id > q[j])
mx = t, id = q[j];
res[id] ++;
}
}
for(int i = 1; i <= n; i++)
cout<< res[i] << " ";
return 0;
}


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

const int N = 810, M = 3000, INF = 0x3f3f3f3f;
int n, m, p;
int id[N];
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[N];
bool st[N];

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int spfa(int start)  // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
{
int hh = 0, tt = 1;
memset(dist, 0x3f, sizeof dist);
dist[start] = 0;
q[0] = start;
st[start] = true;

//循环队列
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;

for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
int res = 0;
for(int i = 0; i < n; i++)
{
int j = id[i];
if(dist[j] == INF)
return INF;
res += dist[j];
}
return res;
}

int main()
{
cin>> n >> p >> m;
for(int i = 0; i < n; i++)
cin>> id[i];
memset(h, -1, sizeof h);
for(int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
}

int res = INF;
for(int i = 1; i <= p; i++)
res = min(res, spfa(i));

cout<< res << endl;
return 0;
}


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

const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int d[N][N];

int main()
{
cin>> n >> m;

for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i == j)  d[i][j] = 0;
else    d[i][j] = INF;

for(int i = 1; i <= m; i++)
{
int a, b, c;
cin>> a >> b >> c;
d[a][b] = d[b][a] = min(d[a][b], c);
}

for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

int res = 0;
for(int i = 1; i <= n; i++)
if(d[1][i] == 0x3f3f3f3f)
{
res = -1;
break;
}
else
res = max(res, d[1][i]);
cout<< res << endl;
return 0;
}


#### 朴素版Dijkstra，堆优化版Dijkstra，spfa都可以写

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

const int N = 2510, M = 6200*2+10;
int n, m, S, T;
int h[N], w[M], e[M], ne[M], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[S] = 0;
queue<int> que;
que.push(S);

while(que.size())
{
int t = que.front();
que.pop();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if(!st[j])
{
que.push(j);
st[j] = true;
}
}
}
}
return dist[T];
}

int main()
{
cin>> n >> m >> S >> T;
memset(h, -1, sizeof h);
while(m--)
{
int a, b, c;
cin>> a >> b >> c;
}

spfa();
cout<< dist[T];
return 0;
}


//从前N个物品中选，体积要尽可能大
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 35, M = 2e4+10;
int v[N];
int f[N][M]; //从前n个物品中选，体积是m

int main()
{
int m, n;
cin>> m >> n;
for (int i = 1; i <= n; i ++ )
cin>> v[i];
for (int i = 1; i <= n; i ++ )
{
for(int j = 1; j <= m; j++)
{
f[i][j] = f[i-1][j];
if(j >= v[i])
f[i][j] = max(f[i][j], f[i-1][j-v[i]] + v[i]);
}
}
cout<< m - f[n][m];
return 0;
}


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

const int N = 1010;
int T[N], w[N];
int f[N][N];

int main()
{
int t, m;
cin>> t >> m; //采药时间，药材数目

for(int i = 1; i <= m; i++)
cin>> T[i] >> w[i];
//1~m, 1~t
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= t; j++)
{
if(T[i] > j)
f[i][j] = f[i-1][j];
else
f[i][j] = max(f[i-1][j], f[i-1][j-T[i]] + w[i]);
}
}
cout<< f[m][t];
return 0;
}


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

typedef pair<int, int> PII;

const int N = 50010;
int n;
PII cow[N];

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

sort(cow, cow + n);

int res = -2e9, sum = 0;
for (int i = 0; i < n; i ++ )
{
int s = cow[i].first - cow[i].second, w = cow[i].second;
res = max(res, sum - s);
sum += w;
}

printf("%d\n", res);
return 0;
}



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

typedef long long LL;

const int N = 100010;
int n;
int t[N];

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

sort(t, t + n);
reverse(t, t + n);

LL res = 0;
for (int i = 0; i < n; i ++ ) res += t[i] * i;

printf("%lld\n", res);
return 0;
}


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

const int N = 100010;
int n;
int a[N];
int q[N];

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

int len = 0;
for (int i = 0; i < n; i ++ )
{
int l = 0, r = len;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (q[mid] < a[i]) l = mid;
else r = mid - 1;
}
len = max(len, r + 1);
q[r + 1] = a[i];
}

printf("%d\n", len);
return 0;
}


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

const int N = 20, M = 1 << N;
int n;
int w[N][N];
int f[M][N];

int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
cin >> w[i][j];

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

for (int i = 0; i < 1 << n; i ++ )
for (int j = 0; j < n; j ++ )
if (i >> j & 1)
for (int k = 0; k < n; k ++ )
if (i >> k & 1)
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);

cout << f[(1 << n) - 1][n - 1];
return 0;
}