#include<bits/stdc++.h>
using namespace std;
typedef struct LinkList{ int val; struct LinkList* next; };
void solve() { int n, m; cin >> n >> m; LinkList* list = new LinkList; if (!list)return; list->val = 1; list->next = nullptr;
LinkList* tail = list;
for (int i = 2; i <= n; i++) {
LinkList* node = new LinkList;
node->val = i;
node->next = nullptr;
tail->next = node;
tail = node;
}
tail->next = list;
LinkList* curr = list;
LinkList* pre = tail;
for (int i = 1; i < n;i++) {
for (int j = 1; j < m; j++) {
pre = curr;
curr = curr->next;
}
pre->next = curr->next;
delete curr;
curr = pre->next;
}
cout << pre->val << '\n';
}
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T=1; //cin >> T; while (T--) { solve(); } return 0; }
#include<bits/stdc++.h> #define int long long using namespace std;
void solve() { int n, k; cin >> n >> k; vector a(n + 1, 0); for (int i = 1; i <= n; i++) { cin >> a[i]; }
int ans = 1e18;
for (int i = 2; i + k - 1 < n; i++) {
int mmax1=a[1], mmin1 = a[1];
for (int j = 2; j <= i - 1; j++) {
mmax1 = max(mmax1, a[j]);
mmin1 = min(mmin1, a[j]);
}
int mmax2 = a[i + k], mmin2 = a[i + k];
for (int j = i + k+1; j <= n; j++) {
mmax2 = max(mmax2, a[j]);
mmin2 = min(mmin2, a[j]);
}
ans = min(ans, max(mmax1, mmax2) - min(mmin1, mmin2));
}
cout << ans << '\n';
}
signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T=1; //cin >> T; while (T--) { solve(); } return 0; }
#include #include #define int long long using namespace std;
void solve() { int n, m; cin >> n >> m; vector a(n + 1, 0); while (m--) { int f; cin >> f; if (f == 0) { int s, t, o, y; cin >> s >> t >> o >> y; for (int i = s; i <= t; i++) { if ((a[i]&1)==o) { a[i] += y; } } } else { int s, t; cin >> s >> t; int ans = 0; for (int i = s; i <= t; i++) { ans += a[i]; } cout << ans << '\n'; }
}
}
signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T=1; //cin >> T; while (T--) { solve(); } return 0; }
#include #include #define int long long using namespace std;
bool check(int mid, int t, int n,vector& k) { int cnt = 0; for (int i = 1; i <= n; i++) { cnt += mid/ k[i]; if (cnt >= t) { return true; } }
return false;
} void solve() { int n, t; cin >> n >> t; vector k(n + 1, 0); for (int i = 1; i <= n; i++) { cin >> k[i]; }
int left = 1, right = 1e18;
int ans = 1e18;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(mid,t,n,k)) {
ans = min(ans, mid);
right = mid - 1;
}
else {
left = mid + 1;
}
}
cout << ans << '\n';
}
signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T=1; //cin >> T; while (T--) { solve(); } return 0; }
#include #include #include #define int long long #define N 109 using namespace std;
char a[N][N];
int dir[8][2] = { {-1,0},{1,0},{0,-1},{0,1},{-1,-1 },{-1,1},{1,-1},{1,1} }; void solve(int n,int m) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } }
int ans = 0;
queue<pair<int, int>> q;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == '@') {
q.push({ i,j });
a[i][j] = '*';
ans++;
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
for (auto d : dir) {
int nx = x + d[0];
int ny = y + d[1];
if (nx<1 || nx>n || ny<1 || ny>m || a[nx][ny] == '*')continue;
a[nx][ny] = '*';
q.push({ nx,ny });
}
}
}
}
}
cout << ans << '\n';
} signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m;
cin >> n >> m;
while (m != 0) {
solve(n, m);
cin >> n >> m;
}
return 0;
}
#include #include #include #define N 100 #define int long long using namespace std;
int v, g; int a[N], b[N][N]; vector t; vector ans(N,0); int p = 1e18;
void dfs(int now,int cnt) {
if (now > g) {
bool flag = true;
for (int i = 1; i <= v; i++) {
if (a[i] > 0) {
flag = false;
}
}
if (flag&&cnt<p) {
p = cnt;
for (int i = 0; i < t.size(); i++) {
ans[i] = t[i];
}
}
return;
}
for (int i = 1; i <= v; i++) {
a[i] -= b[now][i];
}
t.push_back(now);
dfs(now + 1, cnt + 1);
for (int i = 1; i <= v; i++) {
a[i] += b[now][i];
}
t.pop_back();
dfs(now + 1, cnt);
} void solve() { cin >> v; for (int i = 1; i <= v; i++)cin >> a[i]; cin >> g;
for (int i = 1; i <= g; i++) {
for (int j = 1; j <= v; j++) {
cin >> b[i][j];
}
}
dfs(1,0);
cout << p << ' ';
for (int i = 0; i < p; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
} signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; //cin >> T; while (T--) { solve(); } return 0; }
分层图最短路 #include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
struct Edge { int to; int cost; };
struct Node { int dist; // 当前花费 int u; // 当前节点 int k; // 已经使用的免费次数
// 优先队列默认是大顶堆，我们需要小顶堆，所以重载小于号
bool operator>(const Node& other) const {
return dist > other.dist;
}
};
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, k, s, t;
cin >> n >> m >> k >> s >> t;
vector<vector<Edge>> adj(n);
int a, b, c;
for (int i = 0; i < m; ++i) {
cin >> a >> b >> c;
adj[a].push_back({ b,c });
adj[b].push_back({ a,c });
}
vector<vector<int>> dist(n, vector<int>(k + 1, INF));
vector<vector<bool>> vis(n, vector<bool>(k + 1, false));
// 优先队列存储 {花费, 当前点, 已用免费次数}
priority_queue<Node, vector<Node>, greater<Node>> q;
dist[s][0] = 0;
q.push({ 0, s, 0 });
while (q.size()) {
auto [d, u, used_k] = q.top();
q.pop();
if (vis[u][used_k]) continue;
vis[u][used_k] = true;
for (auto& [v, c] : adj[u]) {
//不使用免费票
if (dist[v][used_k] > d + c) {
dist[v][used_k] = d + c;
q.push({ dist[v][used_k], v, used_k });
}
if (used_k<k && dist[v][used_k + 1]>d) {
dist[v][used_k + 1] = d;
q.push({ dist[v][used_k + 1] ,v,used_k + 1 });
}
}
}
int ans = INF;
for (int i = 0; i <= k; ++i)ans = min(ans, dist[t][i]);
cout << ans << '\n';
return 0;
}