lxkk...

1.3万

lxkk...
4个月前
#include <bits/stdc++.h>
using namespace std;

int n, k;
unordered_map<string, vector<pair<string, int>>> g;
unordered_map<string, int> total;
unordered_map<string, bool> st;

int dfs(string ver, vector<string> &nodes)
{
st[ver] = true;
nodes.push_back(ver);

int sum =0;
for(auto edge : g[ver])
{
sum += edge.second;
string cur = edge.first;
if(!st[cur]) sum += dfs(cur, nodes);
}

return sum;
}

int main()
{
cin >> n >> k;
while(n --)
{
string a,b;
int t;
cin >> a >> b >> t;
g[a].push_back({b, t});
g[b].push_back({a, t});
total[a] += t;
total[b] += t;
}

vector<pair<string, int>> res;
for(auto item : total)
{
string ver = item.first;
vector<string> nodes;
int sum = dfs(ver, nodes) / 2;

if(nodes.size() > 2 && sum > k)
{
string boss = nodes[0];
for(string node : nodes)
if(total[boss] < total[node])
boss = node;
res.push_back({boss, nodes.size()});
}
}

sort(res.begin(), res.end());

cout << res.size() << endl;
for(auto item : res) cout << item.first << ' ' << item.second << endl;
}


lxkk...
4个月前
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int d[N][N], cnt[N], w[N][N], dist[N], sum[N], pre[N], n, m, S, T;
bool st[N];

void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
memset(sum, 0x3f, sizeof sum);

dist[S] = 0, sum[S] = 0;
for(int i = 0; i < n; i ++)
{
int t = -1;
for(int j = 0; j < n; j ++)
if(!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;

for(int j = 0; j < n; j ++)
{
if(dist[j] > dist[t] + d[t][j])
{
dist[j] = dist[t] + d[t][j];
sum[j] = sum[t] + w[t][j];
pre[j] = t;
}
else if(dist[j] == dist[t] + d[t][j])
{
if(sum[j] > sum[t] + w[t][j])
{
dist[j] = dist[t] + d[t][j];
sum[j] = min(sum[j], sum[t] + w[t][j]);
pre[j] = t;
}
}
}
}

}

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

memset(d, 0x3f, sizeof d);
memset(w, 0x3f, sizeof w);
for(int i = 0; i < m; i ++)
{
int a, b, c, e;
cin >> a >> b >> c >> e;
d[a][b] = d[b][a] = min(d[a][b], c);
w[a][b] = w[b][a] = min(w[a][b], e);
}

dijkstra();

vector<int> path;
for(int i = T; i != S; i = pre[i]) path.push_back(i);

cout << S;
for(int i = path.size() - 1; i >= 0; i --) cout << ' ' << path[i];

cout << ' ' << dist[T] << ' ' << sum[T] << endl;
}


lxkk...
4个月前
#include <iostream>
#include <cmath>
using namespace std;
string s;
string a[11] = {"zero","one","two","three","four","five","six","seven","eight","nine"};
int b[11];
int main()
{
cin>>s;
int sum = 0,len = (int)s.size();

for (int i = 0; i<len; i++) {
sum += (s[i] - '0');
}
int t = 0;
while (sum/10 > 0) {
int wei = sum % 10;
b[t++] = wei;
sum /= 10;
}
b[t] = sum;
int flag = 0;
for (int i = t; i>=0; i--) {
if(flag == 0)
{
cout<<a[b[i]];
flag = 1;
}
else
cout<<" "<<a[b[i]];
}
cout<<endl;
return 0;
}


lxkk...
7个月前
class Solution {
public:
bool containsPattern(vector<int>& a, int m, int k) {
int len = a.size();
for(int i = 0; i + m * k <= len; i ++)
{
bool flag = true;
for(int j = i; j < i + m * k; j ++)
{
if(a[j] != a[i + (j - i) % m])
{
flag = false;
break;
}
}

if(flag) return true;
}

return false;
}
};


lxkk...
8个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20, M = 1 << 20;
int n, f[M][N], w[N][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 < M; i ++)
for(int j = 0; j < n; j ++)
if(i >> j & 1)
{
for(int k = 0; k < n; k ++)
if(i - (1 << j) >> k & 1)
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
}

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


lxkk...
8个月前
#include <iostream>
using namespace std;

int main()
{
long long a, b, p;
cin >> a >> b >> p;
long long res = 0;
while(b)
{
if(b & 1) res = (long long)(res + a) % p;
a = (long long)(a + a) % p;
b >>= 1;
}

cout <<  res << endl;
}


lxkk...
8个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10010, M = 200010, INF = 0x3f3f3f3f;
int n, m, S, T, h[N], e[M], ne[M], idx, f[M], d[N], cur[N], q[N];

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

//宽搜1、有没有增广路； 2、建立分层图
bool bfs()
{
int hh = 0, tt = 0;
memset(d, -1, sizeof d);
q[0] = S, d[S] = 0, cur[S] = h[S];
while(hh <= tt)
{
int t = q[hh ++];
for(int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if(d[ver] == -1 && f[i])
{
d[ver] = d[t] + 1;
cur[ver] = h[ver];
if(ver == T) return true;
q[ ++ tt] = ver;
}
}
}

return false;
}

int find(int u, int limit)
{
if(u == T) return limit;
int flow = 0;
for(int i = cur[u]; ~i && flow < limit; i = ne[i])
{
cur[u] = i;
int ver = e[i];
if(d[ver] == d[u] + 1 && f[i])
{
int t = find(ver, min(f[i], limit - flow));
if(!t) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}

return flow;
}

int dinic()
{
int r = 0, flow;
while(bfs()) while(flow = find(S, INF)) r += flow;
return r;
}

int main()
{
cin >> n >> m >> S >> T;
memset(h, -1, sizeof h);

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

cout << dinic() << endl;
}


lxkk...
8个月前
#include <iostream>
#include <cstring>
#include <map>
#include <stack>

using namespace std;
const int P = 13331;
map<char, int>priority;
stack<char> op;
stack<int> num;

void eval()
{
char c = op.top(); op.pop();
int b = num.top(); num.pop();
int a = num.top(); num.pop();

if(c == '+') num.push((a + b) % P);
else if(c == '-') num.push(((a - b) % P + P) % P);
else if(c == '*') num.push(a * b % P);
else
{
int t = 1;
while(b --) t = t * a % P;
num.push(t);
}
}

int calc(string expr, int a)
{
op = stack<char>();
num = stack<int>();

for(int i = 0; i < expr.size(); i ++)
{
if(expr[i] == ' ') continue;
if(expr[i] >= '0' && expr[i] <= '9')
{
int j = i, number = 0;
while(j < expr.size() && expr[j] >= '0' && expr[j] <= '9')
{
number = number * 10 + expr[j] - '0';
j ++;
}
i = j - 1;
num.push(number);
}
else if (expr[i] == 'a') num.push(a);
else
{
char c = expr[i];
if(c == '(') op.push(c);
else if(c == ')')
{
while(op.top() != '(') eval();
op.pop();
}
else
{
while(op.size() && priority[op.top()] >= priority[c]) eval();
op.push(c);
}
}
}

while(op.size()) eval();

return num.top();
}

bool check(string expr1, string expr2)
{
for(int i = 0; i < 1000; i ++)
if(calc(expr1, i) != calc(expr2, i))
return false;

return true;
}

int main()
{
char ops[] = "(+-*^";
for(int i = 0; i < 5; i ++) priority[ops[i]] = i;

string expr, line;
getline(cin, expr);
int n; cin >> n; getchar();
//getline(cin, line);

for(int i = 0; i < n; i ++)
{
getline(cin, line);
if(check(expr, line)) printf("%c", 'A' + i);
}
}


lxkk...
8个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5e4 + 10;

int n, cir[N], e[N][2], sum[N];
bool st[N];

bool build()
{
cir[1] = 1;
st[1] = true;
for(int i = 2, last = 1, cur = e[1][0]; i <= n; i ++)
{
cir[i] = cur;
st[cur] = true;
int a = e[cur][0], b = e[cur][1];
if(a != last && b != last) return false;
if(a == last) last = cur, cur = b;
else last = cur, cur = a;
}

for(int i = 1; i <= n; i ++)
if(!st[i])
return false;

return true;
}

int work()
{
reverse(cir + 1, cir + n + 1);
memset(sum, 0, sizeof sum);

for(int i = 1; i <= n; i ++)
if(cir[i] >= i) sum[cir[i] - i] ++;
else sum[cir[i] + n - i] ++;

int res = 0;
for(int i = 0; i < n; i ++) res = max(res, sum[i]);

return res;
}

int main()
{
cin >> n;

for(int i = 1; i <= n; i ++) cin >> e[i][0] >> e[i][1];

if(!build()) puts("-1");
else
{

cout << n - max(work(), work()) << endl;
}
}


lxkk...
8个月前
#include <iostream>
#include <cstring>
#include <algorithm>

const int N = 10010, M = 110;
int m, w[N], stones[M], S, T, L, f[N];

using namespace std;

int main()
{
cin >> L >> S >> T >> m;

for(int i = 1; i <= m; i ++) cin >> stones[i];

if(S == T)
{
int res = 0;
for(int i = 1; i <= m; i ++)
if(stones[i] % S == 0)
res ++;

cout << res << endl;
}
else
{
sort(stones + 1, stones + m + 1);
for(int i = 1, last = 0, offset = 0; i <= m; i ++)
{
if(stones[i] - last > 100)
{
offset += stones[i] - last - 100;
}
last = stones[i];
stones[i] -= offset;
}

for(int i = 1; i <= m; i ++) w[stones[i]] = 1;

L = stones[m] + 10;
for(int i = 1; i <= L; i ++)
{
f[i] = M;
for(int j = S; j <= T; j ++)
if(i - j >= 0)
f[i] = min(f[i], f[i - j] + w[i]);
}

cout << f[L] << endl;
}
}