[NOI2024] 百万富翁

admin LV 10 SU @ 2026-5-13 17:09:18

题外话

CSP-J2 T2 都能挂分，T3 都能不会的蒟蒻来看 NOI 题凑热闹，还真搞出来个大概。

题目分析

子任务 $1$

对于任意两个数都在一次查询问完，注意 $(i,i)$ 这样不要出现， $(i,i-k)$ 也不要（重复），共 $\frac{n(n-1)}{2}$ 个数对。

后面都正常取最大即可。

子任务 $2$

~~理解错题半天，读错题了。~~

首先考虑用【子任务 $1$ 】部分的部分方法。一次全查完不可能，我们可以分次查。

不难想到分块的思想，可是每次分 $\sqrt n$ 块肯定 $s$ 会炸。

第一次 $k=\sqrt n$ ，就需要 $k\times\frac{k(k-1)}{2}=\frac{k^3-k^2}{2}$ 。又知道 $n=1000000,k=1000$ ，次数就是 $499500000$ ，第一次就炸了。

~~想到同学线段树偷懒大分块挂分~~，突然想到线段树。每次只需要 $\frac{n}{2}$ 次的 $s$ 消耗，经过计算，大约需要 $2^{20}=1048576$ 次，其实用类似时间复杂度的表示，是线性的 $n\times (\sum_{i=1}^{+\inf} \frac{1}{2^i})=n$ 。

但是需要 $t= \log_2^n$ 次，大约是 $20$ 估计压着 $11$ 分的部分分。

显然，最后一次可以用暴力性的方法，根据程序测算大约 $t=13$ ，是 $37$ 分。

接下来我们发现，每次序列一定是要除掉一个数（类似线段树或者“分块树”（就是分块之后继续分，而不是只分一次））。

我们根据以上两个部分分发现，通过调整每次除去的数可以得到综合了 $t,s$ 的答案。

于是我们考虑 DFS 每一个除去的数，由于我们不可能一次满分，每次不符合标准的都可以剪枝掉，但是标准要低一些，不是满分（似乎也可以 DP，但是我没想、写）。

DFS 代码

vector<int> vec,v; 
void dfs(int t,int s,int n){
	if(s<0)
		return;
	if(t>8){
		if(n>1)
			return;
		vec=v;
		for(auto p:vec)
			cout<<p<<' ';
		exit(0);
	}
	for(int i=2;i<=n;i++){
		v.push_back(i);
		dfs(t+1,s-(i*(i-1)/2)*(n/i)-((n%i)*((n%i)-1)/2),(bool)(n%i)+n/i);
		v.pop_back();
	}
}
signed main(){
	dfs(1,1100000,1000000);//放低标准
}

由于不是写题的程序，而是打表的，写的比较随意，请见谅。

跑出来之后是 2 2 2 2 3 6 19 183，也就是前四次按照线段树方式（就是每两个数一个块的“分块树”）。

然后我们在尽量小的对余数进行分块处理，甚至可以拆块（拆一些块，把余数均摊进去）。

但是经过计算（读者可以算一下不处理、直接暴力（这里指 $\frac{k(k-1)}{2}$ 次处理）处理余数的 $t,s$ 消耗），显然数变多了对后面不好。

于是我们考虑把余数均摊进前面的数中来。

前四次正常来；第五次先抽一个 $4$ 出来，剩下 $3$ 个一块（原因是余数是 $1$ ，把 $1$ 均摊进一个块中）；第六次抽 $7$ 个出来（同理）；第七次比较特殊，最后余数比较大（是 $14$ ，过半了），我们考虑把数量加一，即多加入一个 $19$ ，然后剩余的一个负数均摊为 $5$ 个 $-1$ 加进来（即很多 $19$ 加上五个 $18$ ）。

经过计算，符合题意（计算见【附表】）。

设 $f(x)$ 表示“暴力”处理 $x$ 个数的次数，即 $f(x)=\frac{x(x-1)}{2}$ 。

附表

$t$	$op$	$n$	$s$
$0$	$-$	$1000000$	$0$
$1$	$2$	$500000$
$2$		$250000$	$750000$
$3$		$125000$	$875000$
$4$		$62500$	$937500$
$5$	$3$	$20833$	$937500+20832\times f(3)+f(4)=937500+62502=1000002$
$6$		$3472$	$1000002+3471\times f(6)+f(7)=1000002+52086=1052088$
$7$	$19$	$183$	$1052088+5\times f(18)+178\times f(19)=1083291$
$8$	$183$	$1$	$1083291+f(183)=1099944$

这样我们就可以顺利拿到 $85$ 分。

代码

以下是我的 richest.cpp。

#include<bits/stdc++.h>
#include"richest.h"
using namespace std;
vector<int>ask(vector<int>a,vector<int>b);//声明
vector<int>get_division(vector<int>v,vector<int>division){//根据序列划分
    static int sum,tot,lmax;
    static vector<int>ret,a,b,c;
    static map<pair<int,int>,int>mp;
    ret.clear();
    a.clear(),b.clear(),mp.clear();//附录1
    sum=tot=0;//附录2
    for(auto p:division){//当前p个一块
        for(int i=sum;i<sum+p;i++)
        	for(int j=i+1;j<sum+p;j++)
        		a.push_back(v[i]),b.push_back(v[j]),mp[{v[i],v[j]}]=tot++;//两两询问
        sum+=p;
    }
    c=ask(a,b);
    sum=0;
    for(auto p:division){
    	lmax=v[sum];
    	for(int i=sum+1;i<sum+p;i++)
    		lmax=c[mp[{lmax,v[i]}]];
    	ret.push_back(lmax);//取当前块最大值
    	sum+=p;
	}
    return ret;
}
void test(vector<int>k){
    for(auto t:k)
    	cerr<<t<<' ';
    cerr<<'\n';
}
int richest(int n,int t,int s){
    if(n==1000){
        vector<int>v;
        for(int i=0;i<n;i++)
            v.push_back(i);
        return get_division(v,vector<int>(1,1000))[0];//一次性搞完
    }
    static vector<int>k,divi;
    k.clear(),divi.clear();
    for(int i=0;i<n;i++)
        k.push_back(i);
    for(int i=0;i<500000;i++)//1
        divi.push_back(2);
    k=get_division(k,divi);
    divi.clear();
    for(int i=0;i<250000;i++)//2
        divi.push_back(2);
    k=get_division(k,divi);
    divi.clear();
    for(int i=0;i<125000;i++)//3
        divi.push_back(2);
    k=get_division(k,divi);
    divi.clear();
    for(int i=0;i<62500;i++)//4
        divi.push_back(2);
    k=get_division(k,divi);
    divi.clear();
    divi.push_back(4);
    for(int i=0;i<20832;i++)//5
        divi.push_back(3);
    k=get_division(k,divi);
    divi.clear();
    divi.push_back(7);
    for(int i=0;i<3471;i++)//6
        divi.push_back(6);
    k=get_division(k,divi);
    divi.clear();
    for(int i=0;i<5;i++)//7
        divi.push_back(18);
    for(int i=0;i<178;i++)
        divi.push_back(19);
    k=get_division(k,divi);
    return get_division(k,vector<int>(1,183))[0];
}

divi 是划分序列每段的长度（和是当前序列长）。

附录

附录 $1$

static 让变量每次不重新创建，这样每次调用函数都不需要消耗整个 vector 的空间。

附录 $2$

sum 维护之前处理过的大小和，从而得到这次开始的下标。

附件内容

首先是头文件 richest.h（注释不是我写的）。

大致就是做好宏定义当标识，声明 richest,ask 函数，并引入 vector。

#ifndef RICHEST_H
#define RICHEST_H

#include <vector>

int richest(int N, int T, int S);

std::vector<int> ask(std::vector<int> i, std::vector<int> j);

#endif // RICHEST_H

接着是 grader.cpp 的代码，是交互库。

按照题目中的标准输入输入即可。 $R$ 通常可以乱输入一个数，最好不要超过 int。

#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
static int N, T, S, r, t, s;
static vector<int> W;
vector<int> ask(vector<int> i, vector<int> j) {
    ++t;
    if (t > T)
        throw string("Too many queries");
    if (i.size() != j.size())
        throw string("Invalid query: i and j must have the same size");
    int m = i.size();
    s += m;
    if (s > S)
        throw string("Too many total elements in queries");
    vector<int> res(m);
    for (int k = 0; k < m; k++) {
        if (i[k] < 0 || i[k] >= N || j[k] < 0 || j[k] >= N)
            throw string("Invalid query: index out of bounds");
        res[k] = W[i[k]] > W[j[k]] ? i[k] : j[k];
    }
    return res;
}

constexpr int Sub2_score = 85;

int main() {
    int R;
    cin >> N >> T >> S >> R;
    if (N <= 0 || T < 0 || S < 0 || R < 0) {
        cerr << "Invalid input for N, T, S or R" << endl;
        return 1;
    }
    mt19937_64 rng(R);
    W.resize(N);
    bool hasWrong = false;
    int maxt = 0, maxs = 0;
    for (int _ = 0; _ < 10; _++) {
        iota(W.begin(), W.end(), 0);
        shuffle(W.begin(), W.end(), rng);
        int answer = max_element(W.begin(), W.end()) - W.begin();
        try {
            r = -1; t = 0; s = 0;
            r = richest(N, T, S);
            if (r != answer)
                throw string("Wrong Answer");
            cout << r << ' ' << t << ' ' << s << " Correct (pretest)" << endl;
        } catch (const string& msg) {
            hasWrong = true;
            cout << r << ' ' << t << ' ' << s << ' ' << msg << endl;
        }
        maxt = max(maxt, t);
        maxs = max(maxs, s);
    }
    if (N == 1000 && T == 1 && S == 499500) {
        if (hasWrong) {
            cout << "Wrong Case 1, score: 0 / " << (100 - Sub2_score) << endl;
        } else {
            cout << "Correct (pretest) Case 1, score: " << (100 - Sub2_score) << " / " << (100 - Sub2_score) << endl;
        }
    } else if (N == 1000000 && T == 20 && S == 2000000) {
        if (hasWrong) {
            cout << "Wrong Case 2, score: 0 / " << Sub2_score << endl;
        } else {
            double ft = 1;
            if (maxt > 8)
                ft -= sqrt(maxt - 8) / 4;
            double gs = 1;
            if (maxs > 1099944) {
            	if (maxs < 1100044)
            		gs -= log10(maxs - 1099943) / 6;
            	else
            		gs -= 1.0 / 3 + pow(maxs - 1100043, 1.0 / 2) / 1500;
			}
            cout
                << (ft * gs >= 1 ? "Correct" : "Partially correct")
                << " (pretest) Case 2, score: "
                << to_string(int(Sub2_score * ft * gs))
                << " / " << Sub2_score;
        }
    } else {
        if (hasWrong) {
            cout << "Wrong" << endl;
        } else {
            cout << "Correct" << endl;
        }
    }
}

最后给出~~没啥用的~~ template_richest.cpp，是样例程序。

#include "richest.h"

int richest(int N, int T, int S) {
    ask({0, 2}, {1, 3});
    ask({0, 2, 3}, {1, 1, 1});
    return 1;
}

如何自测？

注意：以下内容不严谨。

把所有 #include "richest.h" 替换为 richest.h 的代码（包括交互库的）。

然后把交互库、主程序放在一起运行即可。

例如给出的 template_richest.cpp 的测试代码是：

//grader.cpp
#ifndef RICHEST_H
#define RICHEST_H

#include <vector>

int richest(int N, int T, int S);

std::vector<int> ask(std::vector<int> i, std::vector<int> j);

#endif // RICHEST_H
#include <bits/stdc++.h>
using namespace std;
static int N, T, S, r, t, s;
static vector<int> W;
vector<int> ask(vector<int> i, vector<int> j) {
    ++t;
    if (t > T)
        throw string("Too many queries");
    if (i.size() != j.size())
        throw string("Invalid query: i and j must have the same size");
    int m = i.size();
    s += m;
    if (s > S)
        throw string("Too many total elements in queries");
    vector<int> res(m);
    for (int k = 0; k < m; k++) {
        if (i[k] < 0 || i[k] >= N || j[k] < 0 || j[k] >= N)
            throw string("Invalid query: index out of bounds");
        res[k] = W[i[k]] > W[j[k]] ? i[k] : j[k];
    }
    return res;
}

constexpr int Sub2_score = 85;

int main() {
    int R;
    cin >> N >> T >> S >> R;
    if (N <= 0 || T < 0 || S < 0 || R < 0) {
        cerr << "Invalid input for N, T, S or R" << endl;
        return 1;
    }
    mt19937_64 rng(R);
    W.resize(N);
    bool hasWrong = false;
    int maxt = 0, maxs = 0;
    for (int _ = 0; _ < 10; _++) {
        iota(W.begin(), W.end(), 0);
        shuffle(W.begin(), W.end(), rng);
        int answer = max_element(W.begin(), W.end()) - W.begin();
        try {
            r = -1; t = 0; s = 0;
            r = richest(N, T, S);
            if (r != answer)
                throw string("Wrong Answer");
            cout << r << ' ' << t << ' ' << s << " Correct (pretest)" << endl;
        } catch (const string& msg) {
            hasWrong = true;
            cout << r << ' ' << t << ' ' << s << ' ' << msg << endl;
        }
        maxt = max(maxt, t);
        maxs = max(maxs, s);
    }
    if (N == 1000 && T == 1 && S == 499500) {
        if (hasWrong) {
            cout << "Wrong Case 1, score: 0 / " << (100 - Sub2_score) << endl;
        } else {
            cout << "Correct (pretest) Case 1, score: " << (100 - Sub2_score) << " / " << (100 - Sub2_score) << endl;
        }
    } else if (N == 1000000 && T == 20 && S == 2000000) {
        if (hasWrong) {
            cout << "Wrong Case 2, score: 0 / " << Sub2_score << endl;
        } else {
            double ft = 1;
            if (maxt > 8)
                ft -= sqrt(maxt - 8) / 4;
            double gs = 1;
            if (maxs > 1099944) {
            	if (maxs < 1100044)
            		gs -= log10(maxs - 1099943) / 6;
            	else
            		gs -= 1.0 / 3 + pow(maxs - 1100043, 1.0 / 2) / 1500;
			}
            cout
                << (ft * gs >= 1 ? "Correct" : "Partially correct")
                << " (pretest) Case 2, score: "
                << to_string(int(Sub2_score * ft * gs))
                << " / " << Sub2_score;
        }
    } else {
        if (hasWrong) {
            cout << "Wrong" << endl;
        } else {
            cout << "Correct" << endl;
        }
    }
}

//richest.cpp 
#ifndef RICHEST_H
#define RICHEST_H

#include <vector>

int richest(int N, int T, int S);

std::vector<int> ask(std::vector<int> i, std::vector<int> j);

#endif // RICHEST_H

int richest(int N, int T, int S) {
    ask({0, 2}, {1, 3});
    ask({0, 2, 3}, {1, 1, 1});
    return 1;
}

例如输入 4 100 100 1 得到的结果是：

1 2 5 Correct (pretest)
1 2 5 Wrong Answer
1 2 5 Wrong Answer
1 2 5 Wrong Answer
1 2 5 Correct (pretest)
1 2 5 Wrong Answer
1 2 5 Correct (pretest)
1 2 5 Correct (pretest)
1 2 5 Wrong Answer
1 2 5 Wrong Answer
Wrong

我的代码正确性验证

//grader.cpp
#ifndef RICHEST_H
#define RICHEST_H

#include <vector>

int richest(int N, int T, int S);

std::vector<int> ask(std::vector<int> i, std::vector<int> j);

#endif // RICHEST_H
#include <bits/stdc++.h>
using namespace std;
static int N, T, S, r, t, s;
static vector<int> W;
vector<int> ask(vector<int> i, vector<int> j) {
    ++t;
    if (t > T)
        throw string("Too many queries");
    if (i.size() != j.size())
        throw string("Invalid query: i and j must have the same size");
    int m = i.size();
    s += m;
    if (s > S)
        throw string("Too many total elements in queries");
    vector<int> res(m);
    for (int k = 0; k < m; k++) {
        if (i[k] < 0 || i[k] >= N || j[k] < 0 || j[k] >= N)
            throw string("Invalid query: index out of bounds");
        res[k] = W[i[k]] > W[j[k]] ? i[k] : j[k];
    }
    return res;
}

constexpr int Sub2_score = 85;

int main() {
    int R;
    cin >> N >> T >> S >> R;
    if (N <= 0 || T < 0 || S < 0 || R < 0) {
        cerr << "Invalid input for N, T, S or R" << endl;
        return 1;
    }
    mt19937_64 rng(R);
    W.resize(N);
    bool hasWrong = false;
    int maxt = 0, maxs = 0;
    for (int _ = 0; _ < 10; _++) {
        iota(W.begin(), W.end(), 0);
        shuffle(W.begin(), W.end(), rng);
        int answer = max_element(W.begin(), W.end()) - W.begin();
        try {
            r = -1; t = 0; s = 0;
            r = richest(N, T, S);
            if (r != answer)
                throw string("Wrong Answer");
            cout << r << ' ' << t << ' ' << s << " Correct (pretest)" << endl;
        } catch (const string& msg) {
            hasWrong = true;
            cout << r << ' ' << t << ' ' << s << ' ' << msg << endl;
        }
        maxt = max(maxt, t);
        maxs = max(maxs, s);
    }
    if (N == 1000 && T == 1 && S == 499500) {
        if (hasWrong) {
            cout << "Wrong Case 1, score: 0 / " << (100 - Sub2_score) << endl;
        } else {
            cout << "Correct (pretest) Case 1, score: " << (100 - Sub2_score) << " / " << (100 - Sub2_score) << endl;
        }
    } else if (N == 1000000 && T == 20 && S == 2000000) {
        if (hasWrong) {
            cout << "Wrong Case 2, score: 0 / " << Sub2_score << endl;
        } else {
            double ft = 1;
            if (maxt > 8)
                ft -= sqrt(maxt - 8) / 4;
            double gs = 1;
            if (maxs > 1099944) {
            	if (maxs < 1100044)
            		gs -= log10(maxs - 1099943) / 6;
            	else
            		gs -= 1.0 / 3 + pow(maxs - 1100043, 1.0 / 2) / 1500;
			}
            cout
                << (ft * gs >= 1 ? "Correct" : "Partially correct")
                << " (pretest) Case 2, score: "
                << to_string(int(Sub2_score * ft * gs))
                << " / " << Sub2_score;
        }
    } else {
        if (hasWrong) {
            cout << "Wrong" << endl;
        } else {
            cout << "Correct" << endl;
        }
    }
}
//richest.cpp
#ifndef RICHEST_H
#define RICHEST_H

#include <vector>

int richest(int N, int T, int S);

std::vector<int> ask(std::vector<int> i, std::vector<int> j);

#endif // RICHEST_H
#include<bits/stdc++.h>
using namespace std;
vector<int>ask(vector<int>a,vector<int>b);
vector<int>get_division(vector<int>v,vector<int>division){
    static int sum,tot,lmax;
    static vector<int>ret,a,b,c;
    static map<pair<int,int>,int>mp;
    ret.clear();
    a.clear(),b.clear(),mp.clear();
    sum=tot=0;
    for(auto p:division){
        for(int i=sum;i<sum+p;i++)
        	for(int j=i+1;j<sum+p;j++)
        		a.push_back(v[i]),b.push_back(v[j]),mp[{v[i],v[j]}]=tot++;
        sum+=p;
    }
    c=ask(a,b);
    sum=0;
    for(auto p:division){
    	lmax=v[sum];
    	for(int i=sum+1;i<sum+p;i++)
    		lmax=c[mp[{lmax,v[i]}]];
    	ret.push_back(lmax);
    	sum+=p;
	}
    return ret;
}
void test(vector<int>k){
    for(auto t:k)
    	cerr<<t<<' ';
    cerr<<'\n';
}
int richest(int n,int t,int s){
    if(n==1000){
        vector<int>v;
        for(int i=0;i<n;i++)
            v.push_back(i);
        return get_division(v,vector<int>(1,1000))[0];
    }
    static vector<int>k,divi;
    k.clear(),divi.clear();
    for(int i=0;i<n;i++)
        k.push_back(i);
    for(int i=0;i<500000;i++)//1
        divi.push_back(2);
    k=get_division(k,divi);
    divi.clear();
    for(int i=0;i<250000;i++)//2
        divi.push_back(2);
    k=get_division(k,divi);
    divi.clear();
    for(int i=0;i<125000;i++)//3
        divi.push_back(2);
    k=get_division(k,divi);
    divi.clear();
    for(int i=0;i<62500;i++)//4
        divi.push_back(2);
    k=get_division(k,divi);
    divi.clear();
    divi.push_back(4);
    for(int i=0;i<20832;i++)//5
        divi.push_back(3);
    k=get_division(k,divi);
    divi.clear();
    divi.push_back(7);
    for(int i=0;i<3471;i++)//6
        divi.push_back(6);
    k=get_division(k,divi);
    divi.clear();
    for(int i=0;i<5;i++)//7
        divi.push_back(18);
    for(int i=0;i<178;i++)
        divi.push_back(19);
    k=get_division(k,divi);
    return get_division(k,vector<int>(1,183))[0];
}

输入 #1：

1000 1 499500 1

输出 #1：

419 1 499500 Correct (pretest)
751 1 499500 Correct (pretest)
901 1 499500 Correct (pretest)
246 1 499500 Correct (pretest)
449 1 499500 Correct (pretest)
896 1 499500 Correct (pretest)
43 1 499500 Correct (pretest)
92 1 499500 Correct (pretest)
913 1 499500 Correct (pretest)
886 1 499500 Correct (pretest)
Correct (pretest) Case 1, score: 15 / 15

输入 #2：

1000000 20 2000000 1

输出 #2：

885942 8 1099944 Correct (pretest)
796018 8 1099944 Correct (pretest)
727483 8 1099944 Correct (pretest)
291388 8 1099944 Correct (pretest)
392425 8 1099944 Correct (pretest)
667129 8 1099944 Correct (pretest)
11164 8 1099944 Correct (pretest)
781119 8 1099944 Correct (pretest)
45059 8 1099944 Correct (pretest)
892089 8 1099944 Correct (pretest)
Correct (pretest) Case 2, score: 85 / 85

这里 $R$ 只是取了 $1$ ，正确性证明在【必读】部分。

另外：#2 可以输入 1000000 8 1099944 1。

ID

7389

时间

6000ms

内存

1512MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

题外话

题目分析

子任务 $1$

子任务 $2$

DFS 代码

附表

代码

附录

附录 $1$

附录 $2$

附件内容

如何自测？

我的代码正确性验证

信息

状态

开发

支持

关于

1 条题解

题外话

题目分析

子任务 111

子任务 222

DFS 代码

附表

代码

附录

附录 111

附录 222

附件内容

如何自测？

我的代码正确性验证

[NOI2024] 百万富翁

信息

状态

开发

支持

关于

还没有账户？

登录

子任务 $1$

子任务 $2$

附录 $1$

附录 $2$