传送门
A 你也喜欢数学吗
B Middle
C 硬币游戏
D 松鼠回家
就是一个二分+最短路,二分答案,用二分的答案去跑最短路,跑最短路的时候要加限制条件,就是所经过的每个点所在的权值必须严格下于等于二分的答案,开个dis数组记录路径,最后判断终点 是否能够到达,记得把dis数组初始化为负无穷。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define endl '\n'
const int N = 10100;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;
using namespace std;
int n, m, st, ed, h;
int a[N];
int dis[N];
bool vis[N];
vector<PII> g[N];
void dijskra(int x) {
met_x(dis);
met_0(vis);
priority_queue<PII, vector<PII >, greater<PII>> pq;
dis[st] = 0;
pq.push({0, st});
while (pq.size()) {
auto t = pq.top();
pq.pop();
int node = t.se;
if (vis[node])continue;
vis[node] = true;
for (auto i: g[node]) {
if (dis[i.fi] > dis[node] + i.se && a[i.fi] <= x) {
dis[i.fi] = dis[node] + i.se;
pq.push({dis[i.fi], i.fi});
}
}
}
}
void solve() {
cin >> n >> m >> st >> ed >> h;
for (int i = 1; i <= n; i++) cin>>a[i];
while (m--) {
int x, y, z;
cin >> x >> y >> z;
g[x].emplace_back(y, z);
g[y].emplace_back(x, z);
}
int l = -1, r = 1e7 + 1;
while (l < r) {
int mid = l + r >> 1;
dijskra(mid);
if (dis[ed] <= h)r = mid;
else l = mid + 1;
}
if (l == -1 || l == 1e7 + 1)cout << -1 << endl;
else cout << l << endl;
}
int main() {
IOS;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}
E 动物朋友
求一段连续区间的和为给定的值,一眼就是双指针,但是总感觉我的这个双指针怪怪的,一个控制左边界,一个控制有边界,先预处理前缀和,当总和大于等于目标时,左边++,等于时将答案++,小于时把右边++,复杂度O(n)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define int long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define endl '\n'
const int N = 1000100;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;
using namespace std;
int a[N], s[N];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = a[i] + s[i-1];
}
int ans = 0;
//for(int i=1;i<=n;i++)cout<<s[i]<<' ';cout<<endl;
for (int i = 1, j = 1; i <= n && j <= n; ) {
int sum=s[j]-s[i-1];
if(sum>m)i++;
else if(sum==m)ans++,i++;
else j++;
}
cout << ans << endl;
}
int32_t main() {
//IOS;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}
F 松鼠排序
以前记得做过类似的题,结论就是遇到和下标不一样的九八目标值交换过来,最后答案就是最优的,但其实这题应该使用并查集来做,并查集的板子题
赛事AC的代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define endl '\n'
const int N = 200010;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
map<int, int> mp;
for (int i = 1; i <= n; i++)cin >> a[i], mp[a[i]] = i;
int ans = 0;
for (int i = 1; i <= n; i++) {
if (a[i] == i)continue;
else {
int x=a[i];
swap(a[i], a[mp[i]]);
mp[x]=mp[i];
mp[i]=i;
ans++;
}
}
cout << ans << endl;
}
int32_t main() {
IOS;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}
正解使用并查集
G Reverse
贪心的来做,就找连续一的个数最大的,两个加起来即可,注意坑点,如果开动态的vector要注意可能会出现全是零的情况要特判,不然会出现段错误的情况
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define int long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define endl '\n'
const int N = 200010;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;
using namespace std;
void solve() {
int n;
string s;
cin >> n >> s;
int cnt = 0;
vector<int> ans;
for (auto i: s) {
if (i == '1')cnt++;
else {
if (cnt == 0)continue;
ans.push_back(cnt);
cnt = 0;
}
}
if (cnt)ans.push_back(cnt);
//for (auto i: ans)cout << i << ' ';
sort(ans.begin(), ans.end());
int len=ans.size();
if(len==0)cout<<0<<endl;
else if (len == 1)cout << ans[len-1] << endl;
else cout << ans[len-2] + ans[len-1] << endl;
}
int32_t main() {
//IOS;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}
H 迷宫探险
因为权值只有两种情况,所以可以使用点单的BFS即可遇到弹射器的和不遇到分两种情况扩展即可,要注意不一定一个点制备走一次,可能会被走多次,所以不能直走一次,要根据距离来过更新 dis数组
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define endl '\n'
const int N = 200010;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<char>> g(n + 10, vector<char>(m + 10, 0));
vector<vector<bool>> vis(n + 10, vector<bool>(m + 10, 0));
vector<vector<int>> dis(n + 10, vector<int>(m + 10, INF));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
}
}
map<PII, int> pos;
int k;
cin >> k;
while (k--) {
int x, y, cnt;
cin >> x >> y >> cnt;
pos[{x, y}] = cnt;
}
queue<PII > q;
q.push({1, 1});
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vis[1][1] = true;
dis[1][1] = 0;
while (q.size()) {
auto t = q.front();
q.pop();
int x = t.fi;
int y = t.se;
for (int i = 0; i < 4; i++) {
int xx, yy;
if (g[x][y] == '.') {
xx = x + dx[i];
yy = y + dy[i];
} else if (g[x][y] == '*') {
xx = x + dx[i] * pos[{x, y}];
yy = y + dy[i] * pos[{x, y}];
}
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && g[xx][yy] != '#') {
if (g[x][y] == '.'&&dis[xx][yy] > dis[x][y] + 1)dis[xx][yy] = dis[x][y] + 1, q.push({xx, yy});
else if (g[x][y] == '*'&&dis[xx][yy] > dis[x][y])dis[xx][yy] = dis[x][y], q.push({xx, yy});;
}
}
}
if (dis[n][m] == INF)cout << -1 << endl;
else cout << dis[n][m] << endl;
}
int32_t main() {
IOS;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}
I 松鼠采松果
J 合唱比赛
去除一个最低分就是分数最高,去除一个最高分就是分数最低
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define endl '\n'
const int N = 200010;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;
using namespace std;
void solve() {
int n;
cin >> n;
ll sum = 0;
int mx = INT_MIN;
int mn = INT_MAX;
for (int i = 0; i<n; i++) {
int x;
cin >> x;
sum+=x;
mx = max(mx, x);
mn = min(mn, x);
}
printf("%.6f %.6f", (sum - mx) * 1.0 / (n - 1), (sum - mn) * 1.0 / (n - 1));
}
int32_t main() {
//IOS;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}
K 以撒和隐藏房间
按照题目意思模拟模拟就行注意只能有三个相邻房间
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define endl '\n'
const int N = 200010;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;
using namespace std;
int n,m ;
char g[1000][1000];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
bool check(int x,int y) {
int cnt = 0;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 0 || xx >= n || yy < 0 || yy >= m)continue;
if (g[xx][yy] == '2')return false;
if (g[xx][yy] == '1')cnt++;
}
if (cnt == 3)return true;
return false;
}
void solve() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> g[i][j];
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(g[i][j]=='0') {
if (check(i, j))ans++;
}
}
}
if (ans)cout << "YES" << endl << ans << endl;
else cout << "NO" << endl;
}
int32_t main() {
//IOS;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}
L 中位数
实际上分析完题目以后就是求一个数前面有多少个数,本质上就是一个单点修改和区间修改,使用二分加树状数组或者线段树也行,但这个题好像也可以使用对顶堆去维护,分别维护中位数两边的数的个数
二分+树状数组
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define endl '\n'
const int N = 1000010;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;
using namespace std;
int tr[N];
int a[N];
int n, m;
int lowbit(int x) {
return x & (-x);
}
void add(int x, int k) {
for (int i = x; i < N; i += lowbit(i))tr[i] += k;
}
int query(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i))
res += tr[i];
return res;
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i], add(a[i], 1);
while (m--) {
int p, x;
cin >> p >> x;
add(a[p], -1);
a[p] = x;
add(x, 1);
int l = 1, r = 1e6;
while (l < r) {
int mid = l + r >> 1;
if (query(mid) >= (n / 2 + 1))r = mid;
else l = mid + 1;
}
cout << l << endl;
}
}
int main() {
IOS;
int h_h = 1;
//cin >> h_h;
while (h_h--)solve();
return 0;
}