头像

dyxxx




离线:14小时前


最近来访(5)
用户头像
爱卢娜
用户头像
魔法恐龙
用户头像
Kazimierz
用户头像
Şʀɨꪜꫀ机智
用户头像
yangb


dyxxx
5天前

要计算cos(90°) 是90度不是90

std::cos(M_PI / 2); // M_PI 是c++ 内置的pi

或者

pi = std::acos(-1);
std::cos(pi / 2);

别手快写个

std::cos(90) 

像tm个大冤种




dyxxx
8天前

算法水平有一定进步之后回来看二分, 发现y总讲的是真的好

二分.png




dyxxx
9天前

输出连续(包括长度为1)串的个数
题目出自 abc143 - c

in:
10
aabbbbaaca
out:
5

in:
20
xxzaffeeeeddfkkkkllq
out:
10

void solve()
{ 
  /**** data ****/
  int n;
  std::cin >> n;
  std::string s;
  std::cin >> s;
  /**** core ****/
  std::unordered_map<int, int> hash;
  int cnt = 0;
  for (int i = 0, j = 0; i < n; ++ i) {
    hash[s[i]] ++;
    if (hash[s[i]] == 1) ++ cnt;
    while (s[i] != s[j]) {
      hash[s[j]] --;
      ++ j;
    }
  }
  std::cout << cnt << '\n';
}



dyxxx
10天前

int n = 二进制位数;

// 第一个 for 没问题, 就是 bit 从 0 到 2的n次方
for (int bit = 0; bit < (1 << n); ++ bit) { 
    // 这个就是看二进制比特串的每一位是什么
    // 原理就是 比如 10101 要知道第三位是什么
    // 其实就是 10101 & 00100
    // 如果第三位是 0 那么输出的就一定是 0
    // 反之会输出一个非0数(00100)
    // 可以看看基础课 位运算 那一块
    for (int i = 0; i < n; ++ i) {
        std::cout << (bit & (1 << i)) << ' '; 
    }
    std::cout << std::endl;
}




dyxxx
1个月前
# include <iostream> 
# include <vector>
# include <algorithm>
# include <cstring>
# include <iterator>
# include <string>
# include <unordered_map>
const int INF = 0x3f3f3f3f;

const int N = 100010;
const int M = 200010;

void solve()
{
  /**** data ****/
  int n, m;
  std::cin >> n >> m;
  std::vector<int> h(N, -1), e(M), ne(M), color(N);
  int idx = 0;
  auto add = [&] (int a, int b) -> void {
    e[idx] = b, ne[idx] = h[a], h[a] = idx, ++idx; 
  };
  for (int i = 0; i < m; ++ i) {
    int u, v;
    std::cin >> u >> v;
    add(u, v), add(v, u);
  }
  /**** core ****/
  auto dfs = [&] (auto dfs, int r, int c) -> bool {
    color[r] = c;
    for (int i = h[r]; i != -1; i = ne[i]) {
      int j = e[i];
      if (!color[j]) {
        bool ok = dfs(dfs, j, 3 - c);
        if (!ok) return false;
      } 
      else if (color[j] == c) {
        return false; 
      }
    }
    return true;
  };
  for (int i = 1; i <= n; ++ i) {
    if (!color[i]) {
      if (!dfs(dfs, i, 1)) {
        std::cout << "No" << std::endl;
        return;
      }
    }
  }
  std::cout << "Yes" << std::endl;
}

int main() 
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int tt;
  // std::cin >> tt;
  tt = 1;
  while (tt--) {
    solve();
  }
  return 0; 
} 





dyxxx
1个月前
# include <iostream> 
# include <vector>
# include <algorithm>
# include <cstring>
# include <iterator>
# include <string>
# include <unordered_map>
const int INF = 0x3f3f3f3f;

const int N = 510;
const int M = 100010;

void solve()
{
  /**** data ****/
  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<int> > g(N, std::vector<int>(N, INF));
  std::vector<int> isvis(N, 0), dist(N, INF);
  for (int i = 0; i < m; ++ i) {
    int u, v, w;
    std::cin >> u >> v >> w;
    g[u][v] = g[v][u] = std::min(g[u][v], w);
  }
  for (int i = 0; i < N; ++ i) { g[i][i] = 0; }
  /**** core ****/
  int ans = 0;
  for (int i = 0; i < n; ++ i )  {
    int t = -1;
    for (int j = 1; j <= n; ++ j) {
      if (!isvis[j] && (t == -1 || dist[j] < dist[t])) {
        t = j;
      }
    }
    if (i && dist[t] == INF) {
      std::cout << "impossible" << std::endl;
      return;
    }
    if (i && t != -1) ans += dist[t];
    if (t != -1) isvis[t] = 1;
    for (int j = 1; j <= n; ++j) {
      dist[j] = std::min(dist[j], g[t][j]);
    }
  }
  std::cout << ans << std::endl;
}

int main() 
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int tt;
  // std::cin >> tt;
  tt = 1;
  while (tt--) {
    solve();
  }
  return 0; 
} 




活动打卡代码 AcWing 854. Floyd求最短路

dyxxx
1个月前
# include <iostream> 
# include <vector>
# include <algorithm>
# include <cstring>
# include <iterator>
# include <string>
# include <unordered_map>
const int INF = 0x3f3f3f3f;

const int N = 210;
const int M = 100010;

void solve()
{
  /**** data ****/
  int n, m, k;
  std::cin >> n >> m >> k;
  std::vector<std::vector<int> > g(N, std::vector<int>(N, INF));
  for (int i = 0; i < N; ++ i) {g[i][i] = 0;}
  for (int i = 0; i < m; ++ i ) {
    int x, y, z;
    std::cin >> x >> y >> z;
    g[x][y] = std::min(g[x][y], z);
  }
  /**** core ****/
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i <=n; ++i ) {
      for (int j = 1; j <= n; ++j ) {
        g[i][j] = std::min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
  while (k--) {
    int x, y;
    std::cin >> x >> y;
    int ans = g[x][y];
    if (ans > INF / 2) std::cout << "impossible" << std::endl;
    else std::cout << ans <<std::endl;
  }
}

int main() 
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int tt;
  // std::cin >> tt;
  tt = 1;
  while (tt--) {
    solve();
  }
  return 0; 
} 




活动打卡代码 AcWing 851. spfa求最短路

dyxxx
1个月前
# include <iostream> 
# include <vector>
# include <algorithm>
# include <cstring>
# include <iterator>
# include <string>
# include <unordered_map>
const int INF = 0x3f3f3f3f;

const int N = 100010;
const int M = 100010;

void solve()
{
  /**** data ****/
  int n, m;
  std::cin >> n >> m; 
  std::vector<int> h(N, -1), e(N), ne(N), q(N), dist(N, INF), inque(N), w(N);   
  int idx = 0, ff = 0, rr = -1;
  auto add = [&] (int a, int b, int c) -> void  {
    e[idx] = b, ne[idx] = h[a], h[a] = idx, w[idx] = c;
    ++idx;
  };
  for (int i = 0; i < m; ++ i) { 
    int x, y, z;
    std::cin >> x >> y >> z;
    add(x, y, z);
  }
  /**** core ****/
  dist[1] = 0, q[++rr] = 1, inque[1] = 1;
  while (ff <= rr) {
    int t = q[ff ++];
    inque[t] = 0;
    for (int i = h[t]; i != -1; i = ne[i]) {
      int v = e[i];
      if (dist[t] + w[i] < dist[v]) {
        dist[v] = dist[t] + w[i];
        if (!inque[v]) {
          inque[v] = 1;
          q[++rr] = v;
        }
      }
    }
  }
  if (dist[n] > INF/2) std::cout << "impossible" << std::endl;
  else std::cout << dist[n] << std::endl;
}

int main() 
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int tt;
  // std::cin >> tt;
  tt = 1;
  while (tt--) {
    solve();
  }
  return 0; 
} 




活动打卡代码 AcWing 851. spfa求最短路

dyxxx
1个月前
# include <iostream> 
# include <vector>
# include <algorithm>
# include <cstring>
# include <iterator>
# include <string>
# include <unordered_map>
const int INF = 0x3f3f3f3f;

const int N = 100010;
const int M = 100010;

void solve()
{
  /**** data ****/
  int n, m;
  std::cin >> n >> m; 
  std::vector<int> h(N, -1), e(N), ne(N), q(N), dist(N, INF), inque(N), w(N);   
  int idx = 0, ff = 0, rr = -1;
  auto add = [&] (int a, int b, int c) -> void  {
    e[idx] = b, ne[idx] = h[a], h[a] = idx, w[idx] = c;
    ++idx;
  };
  for (int i = 0; i < m; ++ i) { 
    int x, y, z;
    std::cin >> x >> y >> z;
    add(x, y, z);
  }
  /**** core ****/
  dist[1] = 0, q[++rr] = 1, inque[1] = 1;
  while (ff <= rr) {
    int t = q[ff ++];
    inque[t] = 0;
    for (int i = h[t]; i != -1; i = ne[i]) {
      int v = e[i];
      if (dist[t] + w[i] < dist[v]) {
        dist[v] = dist[t] + w[i];
        if (!inque[v]) {
          inque[v] = 1;
          q[++rr] = v;
        }
      }
    }
  }
  if (dist[n] > INF/2) std::cout << "impossible" << std::endl;
  else std::cout << dist[n] << std::endl;
}

int main() 
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int tt;
  // std::cin >> tt;
  tt = 1;
  while (tt--) {
    solve();
  }
  return 0; 
} 





dyxxx
1个月前
# include <iostream> 
# include <vector>
# include <algorithm>
# include <cstring>
# include <iterator>
# include <string>
# include <unordered_map>
const int INF = 0x3f3f3f3f;

const int N = 550;
const int M = 100010;

struct Edges {
  int a, b, w;
}edges[M];

void solve()
{
  /**** data ****/
  int n, m, k;
  std::cin >> n >> m >> k;
  for (int i = 0; i < m; ++i ) {
    int a, b, w;
    std::cin >> a >> b >> w;
    edges[i] = {a, b, w};
  }
  std::vector<int> dist(N, INF);
  dist[1] = 0;
  std::vector<int> last_dist(dist);
  /**** core ****/
  for (int i = 0; i < k; ++i ) {
    last_dist = dist;
    for (int j = 0; j < m; ++j ) {
      dist[edges[j].b] = std::min(dist[edges[j].b], last_dist[edges[j].a] + edges[j].w);
    }
  }
  if (dist[n] < INF / 2) std::cout << dist[n] << std::endl;
  else std::cout << "impossible" << std::endl;
}

int main() 
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int tt;
  // std::cin >> tt;
  tt = 1;
  while (tt--) {
    solve();
  }
  return 0; 
}