牛客周赛 Round 51

A题：小红的同余

思路：

大水题

code：

inline void solve() {
     int m; cin >> m;
     cout << (m + 1) / 2 << endl;
	 return;
}

B题：小红的三倍数

思路：

一个数如果能够被三整除，那么其各位上的数之和肯定为三的倍数。

题目只是多了一个衔接操作，相当于一些数会乘上一些十的倍数，不影响整除性。

我们只要判断总和是否为三的倍数即可。

code：

inline void solve() {
     int n; cin >> n;
     int cur = 0;
     for (int i = 0; i < n; i ++ ) {
     	string s; cin >> s;
     	for (char c : s) cur += c - '0';
     }
     cout << (!(cur % 3) ? "YES\n" : "NO\n");
	 return;
}

C题：小红充电

思路：

分类讨论， 要想充满电，那你充电的时候肯定不会玩手机

因为有快充存在，还存在一种先玩手机到快充线进行快充充满的情况。

如果一开始就能快充，就直接快充

code：

inline void solve() {
	 double ans;
     double x, y, t, a, b, c; cin >> x >> y >> t >> a >> b >> c;
     if (x <= t) ans = (100 - x) / c;
     else {
     	ans = min((100 - x) / b, (x - t) / y + (100 - t) / c);
     }
     cout << fixed << setprecision(7) << ans << endl;
	 return;
}

D题：小红的gcd

思路：

辗转相除法

gcd(a, b) = gcd(b, a % b)

code:

inline void solve() {
     string s; int b;
     cin >> s >> b;
     int a = 0;
     for (char c : s) {
         a = ((ll)a * 10 + (c - '0')) % b;
     }
     cout << __gcd(b, a) << endl;
	 return;
}

E题：小红走矩阵

思路：

最短路

code：

struct node {
    int dis; 
    PII point;
    bool operator > (const node &a) const {
        return dis > a.dis;
    }
};
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
inline void solve() {
     int n; cin >> n;
     vectorint>> a(n + 1, vector<int>(n + 1));
     for (int i = 1; i <= n; i ++ ) {
     	for (int j = 1; j <= n; j ++ ) {
     		cin >> a[i][j];
     	}
     }
     priority_queue, greater> q;
     vectorint>> d(n + 1, vector<int>(n + 1, 1e9 + 7));
     q.push({0, {1, 1}});
     d[1][1] = a[1][1];
     mapint> vis;
     while (q.size()) {
         PII cur = q.top().point; q.pop();
         if (vis[cur]) continue;
         vis[cur] = 1;
         int x = cur.first, y = cur.second;
         for (int i = 0; i < 4; i ++ ) {
             int nx = x + dx[i], ny = y + dy[i];
             if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
                 if (d[nx][ny] > max(d[x][y], a[nx][ny])) {
                     d[nx][ny] = max(d[x][y], a[nx][ny]);
                     q.push({d[nx][ny], {nx, ny}});   
                 }
             }
         }
     }
     cout << d[n][n] << endl;
	 return;
}

F题：小红的数组 

思路：

区间问题，上线段树

不知道为啥，感觉写过了。

code：

const int N = 5e5 + 9;
struct node {
	int l, r;
	ll sum;
	ll mx, mn;
	ll lmx, rmx, lmn, rmn;
} tr[4 * N];
int a[N];
void pushup(node &T, node L, node R) {
	T.sum = L.sum + R.sum;
	T.lmx = max(L.lmx, L.sum + R.lmx);
	T.rmx = max(R.rmx, R.sum + L.rmx);
	T.lmn = min(L.lmn, L.sum + R.lmn);
	T.rmn = min(R.rmn, R.sum + L.rmn);
	T.mx = max({L.mx, R.mx, L.rmx + R.lmx});
	T.mn = min({L.mn, R.mn, L.rmn + R.lmn});
}
void pushup(int u) {
	node L = tr[u << 1], R = tr[u << 1 | 1];
	pushup(tr[u], L, R);
}
void build(int u, int l, int r) {
	tr[u] = {l, r};
	if (l == r) {
		tr[u] = {l, r, a[l], a[l], a[l], a[l], a[l], a[l], a[l]};
		return;
	}
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, 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(u << 1 | 1, l, r);
	if (r <= mid) return query(u << 1, l, r);
	node T;
	pushup(T, query(u << 1, l, r), query(u << 1 | 1, l, r));
	return T;
}
inline void solve() {
     int n; cin >> n;
     for (int i = 1; i <= n; i ++ ) cin >> a[i];
     build(1, 1, n);
     int q; cin >> q;
     while (q -- ) {
     	int l, r; cin >> l >> r;
     	node T = query(1, l, r);
     	cout << max(T.mx, abs(T.mn)) << endl;
     }
	 return;
}