#题解激励#ACGO第6次排位赛题解

userId_undefined

一只姜（AAAAAA级遗址）

秩序白银

2024-04-01 10:55:55

发布于：浙江

122阅读
0回复
0点赞

本次排位赛难度较大，作者也不太能理解，有些题目可能只会给出代码，也有些题目会只给出思路

T1 上一个排列

传送门

此题大意就是字典序排列，但是字典序的大小被改变了，成为了特殊的字典序。

首先输入初始字典序排列originorigin,比如1 5 4 3 2，那么代表在这个特殊字典序中1是最大的，5其次，然后是4、3、2

那么我们只需要写出输出某个序列的上一个字典序的序列的代码，然后把参数设为originorigin的元素即可(奇奇怪怪的)

code:

#include<bits/stdc++.h>
using namespace std;
std::vector<int> s(500001);  
std::vector<int> nextPermutation(std::vector<int>& arr) {  
    int n = arr.size();  
    int i = n - 2;  
    while (i >= 0 ) {  
        int ss,bs;
        for(int l=1;l<=n;l++){
            if(s[l]==arr[i]) ss=l;
        }
        for(int l=1;l<=n;l++){
            if(s[l]==arr[i+1]) bs=l;
        }
        if(ss<=bs) --i;
        else break;
    }  
    if (i < 0) {  
        return {};  
    }  
      
    int j = n - 1;  
    while (j>=0) {  
        int ss,bs;
        for(int l=1;l<=n;l++){
            if(s[l]==arr[j]) ss=l;
        }
        for(int l=1;l<=n;l++){
            if(s[l]==arr[i]) bs=l;
        }
        if(ss>=bs) --j;
        else break;  
    }  
    std::swap(arr[i], arr[j]);  
    std::reverse(arr.begin() + i + 1, arr.end());  
    return arr;  
}  
  
int main() {  
    int n;  
    std::cin >> n;  
    std::vector<int> arr(n);  
    for(int i=1;i<=n;i++) cin>>s[i];
    for (int i = 0; i < n; ++i) {  
        std::cin >> arr[i];  
    }  
    std::vector<int> next = nextPermutation(arr);  
    
        for(int num : next){  
            std::cout<<num<<" ";  
        }  
        std::cout << std::endl;  
    
    return 0;  
}

T2 危在旦夕的国王

传送门

此题为纯模拟题，没有其它的变化，只是模拟国际象棋中国王被n个棋子包围，判断情况

我们只需要把每种棋子可以走到的地方用函数枚举出来，将那些地方设为1，然后判断国王的情况即可

模拟题代码较复杂，作者也懒得写可以参考官方题解

T3 测试机器人

传送门

此题本质上就是求本质上就是求多源无权有向图最短路，当然要注意，当机器人循环的时候会RE

code（奇奇怪怪的）:

#include<bits/stdc++.h>
using namespace std;
#define int long long

int n,****[130];
char ch[200010];
bool flag[200010];
int ori[200010],st[200010];
int f1[200010][22],f2[100010][22],f3[100010];

void dfs(int x){
	if(flag[x]&&(!st[x]||st[x]==-1)){st[x]=-1;return;}
	int t=x+ori[x];flag[x]=1;
	if(t<1||t>n){st[x]=1;return;}
	dfs(t);st[x]=(st[t]==-1?-1:st[t]+1);return;
}
int queryx(int l, int r){
    int k=log2(r-l+1);
    return max(f1[l][k],f1[r-(1<<k)+1][k]);
}
int queryn(int l, int r){
    int k=log2(r-l+1);
    return min(f2[l][k],f2[r-(1<<k)+1][k]);
}

signed main(){
	cin>>n>>m;
	scanf("%s",ch+1);
	mp['R']=1,mp['G']=2,mp['B']=-3;
	for(int i=1;i<=n;i++) ori[i]=mp[ch[i]];
	for(int i=1;i<=n;i++){
		if(!flag[i])dfs(i);
		if(st[i]>0) f1[i][0]=f2[i][0]=st[i],f3[i]=f3[i-1];
		else f1[i][0]=0,f2[i][0]=1e9,f3[i]=f3[i-1]+1;
	}
	for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j-1)<=n;i++){
            f1[i][j]=max(f1[i][j-1],f1[i+(1<<j-1)][j-1]);
        }
    }
	for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j-1)<=n;i++){
            f2[i][j]=min(f2[i][j-1],f2[i+(1<<j-1)][j-1]);
        }
    }
    while(m--){
    	int x,y;
    	cin>>x>>y;
    	if(f3[y]-f3[x-1]==y-x+1) cout<<"-1 -1\n";
    	else cout<<queryn(x,y)<<' '<<queryx(x,y)<<endl;
    }
	return 0;
}

T4 股票购买方案数

传送门

很明显，这是一道树状数组求顺序对问题，大家应该都很熟悉，这道也属于简单题

code（还是奇奇怪怪的）:

#include<bits/stdc++.h>
using namespace std;
#define int long long

int n,ans,s,c[500010];

int lowbit(int x){return x&(-x);}
void add(int x, int y){for(int i=x;i<=5e5;i+=lowbit(i))c[i]+=y;}
int query(int x){int sum=0;while(x)sum+=c[x],x-=lowbit(x);return sum;}

signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>s,ans+=query(s-1),add(s,1);
	cout<<ans;
	return 0;
}

T5 寻找特别之数

传送门

此题大部分同学都能拿到180分，错误原因是超时（我也是）
此题是一道DP题，只需将n转化为字符串s并反转

此题我也是赛后才想出来，于是借鉴官方的代码：
code：

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

constexpr int N = 18;
constexpr int M = 3;

namespace DigitDp {
    string s;
    int n;

    i64 dp[N + 1][M][2];

    void init() {
        memset(dp, -1, sizeof dp);
    }

    i64 dfs(int i, int r, int one, int isLim) {
        if (i < 0) return r == 0 and one;
        if (!isLim and dp[i][r][one] != -1)
            return dp[i][r][one];
        i64 res = 0;
        int hi = (isLim ? s[i] - '0' : 9);
        for (int d = 0; d <= hi; ++d)
            res += dfs(i-1, (r*10+d)%3, one|(d==1), isLim and d == hi);
        if (isLim) return res;
        return dp[i][r][one] = res;
    }

    i64 calc(i64 x) {
        init();
        s = to_string(x);
        reverse(begin(s), end(s));
        n = s.size();
        return dfs(n - 1, 0, 0, true);
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    DigitDp::init();
    int _; cin >> _;
    while (_--) {
        i64 l, r;
        cin >> l >> r;
        i64 lo = DigitDp::calc(l - 1);
        i64 hi = DigitDp::calc(r);
        cout << hi - lo << '\n';
    }
    return 0;
}

T6 眼红的同学

传送门

此题大部分同学也能拿到100分，错误原因仍然是超时（我还是）

此题可以使用树状数组求逆序对，大家发现，与第4题的树状数组求顺序对都属于树状数组

当然也可以使用分治算法（这个是看官方的题解的）

code(任然借鉴官方的）：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 3e5 + 5;
int maximum;
int n, ans[MAXN];
int L[MAXN], R[MAXN];
int bit[MAXN << 1];
// x, y, z 记录学生成绩。
// id记录学生编号。
// ans记录学生的嫉妒值。
// val记录这个学生的最高成绩，即 max(x, y, z)。
struct student{
    int x, y, z;
    int id, ans, val;
} arr[MAXN];

// 根据第一关键字排序
bool cmp1(student a, student b){
    if (a.x != b.x) return a.x > b.x;
    if (a.y != b.y) return a.y > b.y;
    return a.z > b.z;
}

// 根据第二关键字排序。
bool cmp2(student a, student b){
    if (a.y != b.y) return a.y > b.y;
    if (a.z != b.z) return a.z > b.z;
    return a.x > b.x;
}

// 三个数取最大值。
inline int max(int a, int b, int c){
    return max(a, max(b, c));
}

// lowbit获取低位二进制1的操作。
inline int lowbit(int k) {
    return k & (-k);
}

// 数状数组但点增加操作。
void add(int x, int val){
    for (int i=x; i<=maximum; i+=lowbit(i))
        bit[i] += val;
    return ;
}

// 数状数组区间查询操作。
int query(int x){
    int ans = 0;
    for (int i=x; i; i-=lowbit(i)) 
        ans += bit[i];
    return ans;
}

// CDQ分治应该是可以AK的。
// 分治闭区间[L,R]
void cdq(int l, int r){
    // 将大问题拆解成小问题：
    if (l >= r || L[r] == L[l]) return ;
    int mid = L[(l + r) >> 1];
    // 以mid为中线，将左右两边分开。
    // 保证左边的任意x严格小于右边。
    if (arr[mid].x == arr[mid+1].x) mid--;
    if (mid < l) {
        // 往右边寻找中点
        mid = R[(l + r) >> 1];
        if (mid + 1 > r) return ;
    }
    
    cdq(l, mid); cdq(mid+1, r);
    
    // 分别对左半边和右半边按照第二关键字进行排序。
    sort(arr+l, arr+mid+1, cmp2);
    sort(arr+mid+1, arr+r+1, cmp2);
    
    // 统计答案：
    int j = l;
    for (int i=mid+1; i<=r; i++){
        while (j <= mid && arr[j].y > arr[i].y){
            add(arr[j].z, arr[j].val);
            j++;
        }
        arr[i].ans += query(maximum) -  query(arr[i].z);
    }
    // 恢复树状数组
    for (int i=l; i<j; i++)
        add(arr[i].z, -arr[i].val);
    return ;
}

int main(){
    // 数据输入
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i=1; i<=n; i++){
        int x, y, z;
        cin >> x >> y >> z;
        maximum = max(maximum, max(x, y, z));
        arr[i] = (student){x, y, z, i, 0, max(x, y, z)};
    }

    sort(arr+1, arr+1+n, cmp1);
    
    // 排序好之后计算L和R数组。
    // 通过使用L数组记录相同x值第一次出现的位置。
    for (int i=1; i<=n; i++){
        if (arr[i].x != arr[i-1].x) L[i] = i;
        else L[i] = L[i-1];
    }
    
    // 相同地，处理R数组。
    for (int i=n; i>=1; i--){
        if (arr[i].x != arr[i+1].x) R[i] = i;
        else R[i] = R[i+1];
    }
    
    cdq(1, n);  // 分治。
    for (int i=1; i<=n; i++) ans[arr[i].id] += arr[i].ans;  // 答案统计。
    for (int i=1; i<=n; i++) cout << ans[i] << endl;  // 答案输出。
    return 0;
}

欢迎各位大佬、萌新们加入！

加入“中国”团队点我

userId_undefined
去预览
0/2000

全部评论 4

热门讨论