题解 | 牛客小白月赛107 题解更新至 F 题

Cidoai的吃饭

https://ac.nowcoder.com/acm/contest/98241/A

牛客小白月赛107 题解更新至 F 题

Preface

真的，原谅我 $D$ 题到最后都没有懂，只能无奈把他跳了。。。

我会在代码一些有必要的地方加上注释，签到题可能一般就不会写了.

以下是代码火车头：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <iomanip>
#define endl '\n'
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rep2(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;

template<typename T>
void cc(const vector<T> &tem) {
    for (const auto &x: tem) cout << x << ' ';
    cout << endl;
}

template<typename T>
void cc(const T &a) { cout << a << endl; }

template<typename T1, typename T2>
void cc(const T1 &a, const T2 &b) { cout << a << ' ' << b << endl; }

template<typename T1, typename T2, typename T3>
void cc(const T1 &a, const T2 &b, const T3 &c) { cout << a << ' ' << b << ' ' << c << endl; }

void cc(const string &s) { cout << s << endl; }

void fileRead() {
#ifdef LOCALL
    freopen("D:\\AADVISE\\Clioncode\\untitled2\\in.txt", "r", stdin);
    freopen("D:\\AADVISE\\Clioncode\\untitled2\\out.txt", "w", stdout);
#endif
}

void kuaidu() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); }

inline int max(int a, int b) {
    if (a < b) return b;
    return a;
}

inline double max(double a, double b) {
    if (a < b) return b;
    return a;
}

inline int min(int a, int b) {
    if (a < b) return a;
    return b;
}

inline double min(double a, double b) {
    if (a < b) return a;
    return b;
}

void cmax(int &a, const int &b) { if (b > a) a = b; }
void cmin(int &a, const int &b) { if (b < a) a = b; }
void cmin(double &a, const double &b) { if (b < a) a = b; }
void cmax(double &a, const double &b) { if (b > a) a = b; }
using PII = pair<int, int>;
using i128 = __int128;
using vec_int = std::vector<int>;
using vec_char = std::vector<char>;
using vec_double = std::vector<double>;
using vec_int2 = std::vector<std::vector<int> >;
using que_int = std::queue<int>;

Problem A. Cidoai 的吃饭

怎么总是 $wa$ 签到呢，忘记输入 $n$ 了 $23333$

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
 
//--------------------------------------------------------------------------------
//struct or namespace:
 
//--------------------------------------------------------------------------------
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    //cin >> T;
    while (T--) {
        int a, b, c;
        cin >> n;
        cin >> a >> b >> c;
        int ans = 0;
        ans += n / a;
        n %= a;
        ans += n / b;
        n %= b;
        ans += n / c;
        cc(ans);
 
    }
    return 0;
}
 
/*
 
 
*/

Problem B. Cidoai 的听歌

能够直观的想到和最大值和最小值有关。

稍微写一下，能知道操作次数一定是两者的差值，然后因为是先加再减，所以最后的数字就是两者的中值向上取整。

//--------------------------------------------------------------------------------
const int N = 1e6 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
int A[N];
//--------------------------------------------------------------------------------
//struct or namespace:
 
 
//--------------------------------------------------------------------------------
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    //cin >> T;
    while (T--) {
        cin >> n;
        // set<int> S;
        int sum = 0;
        int mmin = INF, mmax = -INF;
        rep(i, 1, n) {
            int a;
            cin >> a;
            // A[i] = a;
            // sum += a;
            // S.insert(a);
            cmin(mmin, a);
            cmax(mmax, a);
        }
        cc(mmax - mmin, (mmax + mmin + 1) / 2);
 
    }
    return 0;
}
 
/*
 
 
*/

Problem C. Cidoai 的植物

感觉莫名的一道题，简单模拟就好了。因为 $m$ 的范围很小，所以直接开 $m$ 个数组用来记录哪一位空着就好了。

不过这种输入的数据方式还是比较少见的，挺好玩的，还可以避免输入的超时问题。

//--------------------------------------------------------------------------------
const int N = 2e4 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
vec_int A[210];
int D[N][210];
//--------------------------------------------------------------------------------
//struct or namespace:
 
//--------------------------------------------------------------------------------
unsigned seed;
 
unsigned rnd() {
    unsigned ret = seed;
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return ret;
}
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    //cin >> T;
    while (T--) {
        int k;
        cin >> n >> m >> k >> seed;
        rep(i, 1, m) {
            rep(j, 1, n) A[i].push_back(j);
        }
        rep(i, 1, k) {
            int a = (rnd() % 2) + 1;
            int b, c;
            if (a == 1) {
                b = (rnd() % m) + 1;
                c = (rnd() % (n * m)) + 1;
                for (auto &x: A[b]) {
                    D[x][b] = c;
                }
                A[b].clear();
            }
            else {
                b = (rnd() % n) + 1;
                c = (rnd() % (m)) + 1;
                // D[b][c] = 0;
                A[c].push_back(b);
            }
        }
        rep(j, 1, m) {
            for (auto &x: A[j]) D[x][j] = 0;
        }
        int ans = 0;
        rep(i, 1, n) {
            rep(j, 1, m) {
                ans ^= D[i][j] * ((i - 1) * m + j);
            }
        }
        cc(ans);
 
    }
    return 0;
}
 
/*
 
 
*/

Problem E. Cidoai 的可乐

既然是希望点权和最小，那么我们先按照点权从小到大排序。从前往后枚举，假设第一个点的点权是 $3$ ，那么我们就和最后三个点连起来，然后继续这样，就这样直到最后连了 $n-1$ 个边就结束了。

//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
 
struct node {
    int val;
    int lim;
};
 
node A[N];
 
//--------------------------------------------------------------------------------
//struct or namespace:
 
//--------------------------------------------------------------------------------
 
signed main() {
    fileRead();
    kuaidu();
    T = 1;
    //cin >> T;
    while (T--) {
        cin >> n;
        rep(i, 1, n) {
            cin >> A[i].val;
        }
        rep(i, 1, n) cin >> A[i].lim;
        sort(A + 1, A + n + 1, [&](const node &q1, const node &q2) {
            return q1.val < q2.val;
        });
        int las = n - 1;
        int ans = 0;
        rep(i, 1, n) {
            ans += min(las, A[i].lim) * A[i].val;
            las -= min(las, A[i].lim);
            if (las <= 0) break;
 
 
        }
        cc(ans);
 
    }
    return 0;
}
 
/*
 
 
*/

Problem F. Cidoai 的自恋

这个题比较有趣，有点那种最大上升序列和最大下降序列的感觉，但是有加了一些别的限制。

以下讨论的最大上升序列都是针对于本题的最大上升序列，即是满足本题限制的。

先考虑上升序列，如果我们按照给的点从左往右的顺序去考虑求出来我们每一个权值对应的最大上升序列，我们当前枚举到了点 $i$ ，去考虑前一个小于当前点的最后的最大上升序列，这样就能够知道了这个点的权值对应的上升序列长度。以上做法是 $O(n*logn)$ ，由于本题 $n$ 的范围很大，所以感觉不太能行。（其实勉勉强强说不定）然后再最后做一个前缀应该就差不多了。（口胡结束）

后来看了题解，发现枚举权值会更好。还是先考虑单侧，权值每一次自增，做一次单调栈就好了。牛牛

相反的位置也相似处理一下，然后最后取一个 $pre_i{} suf_{i}$ 的 $min$ 就好了

//--------------------------------------------------------------------------------
const int N = 5e6 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
int k;
int vis[N];
//--------------------------------------------------------------------------------
//struct or namespace:
struct node {
	int pos;
	int val;
};

// vector<node> A;
// vec_int A;
int top;
int st[N], pre[N], suf[N];
//--------------------------------------------------------------------------------

unsigned seed;

unsigned rnd() {
	unsigned ret = seed;
	seed ^= seed << 13;
	seed ^= seed >> 17;
	seed ^= seed << 5;
	return ret;
}

signed main() {
	fileRead();
	kuaidu();
	T = 1;
	//cin >> T;
	while (T--) {
		cin >> n >> k >> seed;
		rep(i, 1, k) {
			int x = (rnd() % n) + 1;
			if (vis[x] > 0) continue;
			vis[x] = i;
			// A.push_back(x);
		}
		rep(i, 1, n) {
			if (vis[i]) {
				int pos1 = vis[i];
				while (top and pos1 < st[top]) top--;
				st[++top] = pos1;
				pre[i] = top;
			}
			else pre[i] = top;
		}
		top = 0;
		rep2(i, n, 1) {
			if (vis[i]) {
				int pos1 = vis[i];
				while (top and pos1 < st[top]) top--;
				st[++top] = pos1;
				suf[i] = top;
			}
			else suf[i] = top;
		}
		int id = 0;
		rep(i, 1, n) {
			if (vis[i]) continue;
			if (id == 0) id = i;
			else {
				if (suf[id] + pre[id] > suf[i] + pre[i]) id = i;
			}
		}
		cc(id);

	}
	return 0;
}

/*


*/