目录
A-小红的同余_牛客周赛 Round 51 (nowcoder.com)
思路：
代码：
B-小红的三倍数_牛客周赛 Round 51 (nowcoder.com)
思路：
代码：
C-小红充电_牛客周赛 Round 51 (nowcoder.com)
思路：
代码：
D-小红的 gcd_牛客周赛 Round 51 (nowcoder.com)
思路：
代码：
E-小红走矩阵_牛客周赛 Round 51 (nowcoder.com)
思路：
代码：
F-小红的数组_牛客周赛 Round 51 (nowcoder.com)
思路：
代码：
A-小红的同余_牛客周赛 Round 51 (nowcoder.com)
思路：
通过二分查找答案即可
代码：
#include<iostream>
using namespace std;
int m, ans;
int judge(int x)
{if ((2 * x) % m == 1)return 1;elsereturn 0;
}
int main()
{cin >> m;int l = 0, r = m;while (l < r){int mid = (1 + l + r) >> 1;if (judge(mid)){l = mid+1;ans = mid;}elser = mid-1;}cout << ans;
}B-小红的三倍数_牛客周赛 Round 51 (nowcoder.com)
思路：
为3的倍数的数有一个特点：各个位数相加的和为3的倍数，所以将所有数的各个位数加起来看和是否为3的倍数
代码：
#include<iostream>
using namespace std;
int n;
string s[110];
long long ans = 0;
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> s[i];long long sum = 0;for (int j = 0; j < s[i].length(); j++){sum += s[i][j] - '0';}ans += sum % 3;}if (ans % 3 == 0)cout << "YES";elsecout << "NO";
}C-小红充电_牛客周赛 Round 51 (nowcoder.com)
思路：
分两种情况讨论：第一种低于超级充电的触发条件，直接用C求即可；第二种高于超级充电触发条件，看是直接用B求所耗时间短 还是 先将电路用到低于超级充电触发条件然后用C求时间短。
代码：
#include<iostream>
using namespace std;
int main()
{double x, y, t, a, b, c;cin >> x >> y >> t >> a >> b >> c;double time;if (x <= t){time = (100 - x) * 1.0 / c;}else{double ans1= (100 - x) * 1.0 / b;double ans2=(x-t)/y+ (100 - t) * 1.0 / c;time = min(ans1, ans2);}printf("%.9lf", time);
}D-小红的 gcd_牛客周赛 Round 51 (nowcoder.com)
思路：
借用字符串来求，注意需要对每次求出来的值进行对b求余，不然会爆。
代码：
#include<iostream>
#define int long long
using namespace std;
int gcd(int a, int b)
{return b > 0 ? gcd(b, a % b) : a;
}
signed main()
{string a;int b;cin >> a >> b;int x=0;int n = a.length();for (int i = 0; i < n; i++){x *= 10;x += a[i] - '0';x %= b;}int ans = gcd(x, b);cout << ans;return 0;
} E-小红走矩阵_牛客周赛 Round 51 (nowcoder.com)
思路：
用二分法求答案，答案判断是否存在用深度搜索是否能走到终点
代码：
#include<iostream>
#include<queue>
#define int long long
using namespace std;
int n, m, k;
int s[510][510];
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };
int flag = 0;//标志是否能走通迷宫
typedef struct node
{int x, y;
}node;
node start, end1;
int bfs(int ans)
{queue<node> q;if(s[1][1]>ans)return 0;q.push({1,1});int book[510][510] = { 0 };book[1][1]=1;while (!q.empty()){int x = q.front().x;//取x坐标int y = q.front().y;//取y坐标q.pop();for (int i = 0; i < 4; i++)//遍历四个方向{int tx = x + dx[i];int ty = y + dy[i];if (tx<1 || ty<1 || tx>n || ty>n || book[tx][ty] == 1 || s[tx][ty] > ans)//是否越界，是否走过，是否可走continue;else{book[tx][ty] = 1;q.push({ tx,ty});if(tx==n&&ty==n)return 1;}}}return 0;
}
signed main()
{cin >> n ;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){cin >> s[i][j];}int l = 1, r = 1e9;while (l < r){int mid = (l + r) >> 1;if (bfs(mid)) r = mid;else l = mid + 1;}cout << l;return 0;
}F-小红的数组_牛客周赛 Round 51 (nowcoder.com)
思路：
用线段树存正数时的绝对值最大和负数时的绝对值最大，相当于建了两棵树。
需要加一句 ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) 不然会超时。
代码：
#include<iostream>
#define lc u<<1
#define rc u<<1|1
using namespace std;
const int N = 5e5 + 10;
typedef long long ll;
struct node {int l, r;ll sum, lm, rm, m;ll fsum, flm, frm, fm;
}tr[N << 2];
int n, q;
ll a[N], b[N];
void pushup(node& u, node& l, node& r)
{u.sum = l.sum + r.sum;u.lm = max(l.lm, l.sum + r.lm);u.rm = max(r.rm, r.sum + l.rm);u.m = max(l.m, max(r.m, l.rm + r.lm));u.fsum = l.fsum + r.fsum;u.flm = max(l.flm, l.fsum + r.flm);u.frm = max(r.frm, r.fsum + l.frm);u.fm = max(l.fm, max(r.fm, l.frm + r.flm));
}
void pushup(int u)
{pushup(tr[u], tr[lc], tr[rc]);
}
void build(int u, int l, int r)
{if (l == r)tr[u] = { l,l,a[l],a[l],a[l],a[l],b[l],b[l],b[l],b[l] };else {tr[u] = { l,r };int mid = (l + r) >> 1;build(lc, l, mid), build(rc, mid + 1, r);pushup(u);}
}
node query(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r)return tr[u];int mid = tr[u].l + tr[u].r >> 1;if (l > mid)return query(rc, l, r);else if (r <= mid)return query(lc, l, r);else {node res;node L = query(lc, l, r);node R = query(rc, l, r);pushup(res, L, R);return res;}
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];b[i] = -a[i];}cin >> q;build(1, 1, n);while (q--){int a, b;cin >> a >> b;node t = query(1, a, b);cout << max(t.m, t.fm) << '\n';}return 0;
}
