题解
hut二面部分题解
qwq LV 5 @ 2025-10-26 20:23:21

引言

alt

题目里带 $red$ 的都是我出的，题目考点都较为简单，除了位运算(如果熟悉位运算trick的话其实也简单)，考点大致为排序差分模拟模拟+位运算

B-red的游戏时间

根据题意，我们只要将时间和时间名称按照字典序从小到大排序即可，直接sort一下就好了，这里用pair<string,string>直接省去重载的过程。难度: 500

代码：

#include <bits/stdc++.h>
#define lowbit(x) (x & - (x))
#define pii pair<int,int>
#define pil pair<int,long long>
#define pli pair<long long,int>
#define pss pair<string,string>
#define pll pair<long long,long long>
#define pdd pair<double,double>
#define MP make_pair
#define pb push_back
#define pf push_front
#define i64 long long
#define i128 __int128_t
#define ull unsigned long long
#define ld long double
#define ll long long
using namespace std; 
const int N = 3e4+100,M = 2e5+100,inf = 1e9,MOD=1e9+7,mod=998244353;
const long long INF = 1e18;
const double pi = 3.1415926535897932385,eps = 1e-9;
void solve(){
    int n;  cin >> n;
	vector<pair<string,string>>a(n+1);
	for (int i=1; i<=n; i++){
		string x,y;  cin >> x >> y;
		a[i] = {x,y};
	}
	sort(a.begin()+1,a.end());
	for (int i=1; i<=n; i++){
		cout << a[i].first << " " << a[i].second << "\n";
	}
}		 
int main(){  
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int _ = 1; //cin >> _;
	while(_--) solve();
	return 0;
}

E-red的咒语

差分前缀和模板题。读题很容易想到解法，我们根据q次操作区统计k个位置中各个带你的 $tol_i$ 就行。

如果你每次都从l遍历到r区累加，显然时间复杂度太高，会超时(TLE)。

回到问题本身，每次我们需要把 $[l,r]$ 区间内的所有位置都+1，其实相当于对第 $l$ 个位置+1 $pre_l$ ++,最后做一次前缀和即 $pre_i$ += $pre_{i-1}$ 是不是能是的 $[l,n]$ 内的所有数都+1,而由于我们只希望 $[l,r]$ 内的数+1,那么我们只需要 $pre_{r+1}$ --, 这样相当于把 $[r+1,n]$ 的+1部分抵消了。我们回到题目，那对于每一个 $[l,r]$ 我们都做以上的操作就能避免每次都从 $l$ 遍历到 $r$ ,复杂度由 $O(n)$ 变为 $O(1)$ ,之后模拟题意输出就行了。难度: 1200

代码：

#include <bits/stdc++.h>
#define lowbit(x) (x & - (x))
#define pii pair<int,int>
#define pil pair<int,long long>
#define pli pair<long long,int>
#define pss pair<string,string>
#define pll pair<long long,long long>
#define pdd pair<double,double>
#define MP make_pair
#define pb push_back
#define pf push_front
#define i64 long long
#define i128 __int128_t
#define ull unsigned long long
#define ld long double
#define ll long long
using namespace std; 
const int N = 3e4+100,M = 2e5+100,inf = 1e9,MOD=1e9+7,mod=998244353;
const long long INF = 1e18;
const double pi = 3.1415926535897932385,eps = 1e-9;
void solve(){
	int n,k,q;   cin >> n >> k >> q;
    vector<string>vec(n);
    for (int i=0; i<n; i++) cin >> vec[i];
    for (int i=0; i<n; i++) vec[i] = " " + vec[i];
    vector<int>sum(k+2);
    while(q--){
        int l,r;  cin >> l >> r;
        sum[l]++;  sum[r+1]--;
    }
    for (int i=1; i<=k; i++) sum[i] += sum[i-1];
    for (int i=1; i<=k; i++){
        cout << vec[sum[i]%n][i];
    }
}		 
int main(){  
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int _ = 1; //cin >> _;
	while(_--) solve();
	return 0;
}

D-red的属性克制

简单阐述一下题意,你会拿到包含w,f,g三种字母的字符串，这三种字符中两两之间都是存在克制关系的，题目要求我们输出最后剩下的字符。显然，由于不同字母之间一定是存在克制关系的，那么最后留下的字符一定只有一种。

从左往右遍历,记当前留下的字母为c,个数为cnt，下一个遇到的字母是 $s_i$ .

如果 $s_i$ 与字母c相同那么cnt++.

如果 $s_i$ 克制c，那么所有的字母c都会因为和 $s_i$ 接触而消失，最后留下的字母为 $s_i$ , cnt = 1.

如果 $s_i$ 被c克制,显然 $s_i$ 会因为直接接触而消失,此时对你留下的字母没有影响。

上述的三种关系就是解题的关键(其实是显然的，一眼看出来),接下来你只需要模拟这个过程就行了。这里提供两种方法，一种是用栈去模拟,一种是直接维护当前剩下的字母是哪种和个数。难度: 1000

代码一:栈

#include <bits/stdc++.h>
#define lowbit(x) (x & - (x))
#define pii pair<int,int>
#define pil pair<int,long long>
#define pli pair<long long,int>
#define pss pair<string,string>
#define pll pair<long long,long long>
#define pdd pair<double,double>
#define MP make_pair
#define pb push_back
#define pf push_front
#define i64 long long
#define i128 __int128_t
#define ull unsigned long long
#define ld long double
#define ll long long
using namespace std; 
const int N = 3e4+100,M = 2e5+100,inf = 1e9,MOD=1e9+7,mod=998244353;
const long long INF = 1e18;
const double pi = 3.1415926535897932385,eps = 1e-9;
void solve(){
    string s;  cin >> s;
    int n = s.size();
    stack<char>st;
    for (char i:s){
        if (st.empty()){
            st.push(i);
            continue;
        }
        if (st.top() == 'w'){
            if (i == 'f')continue;
            else if (i == 'g'){
                while(st.size() and st.top() == 'w'){
                    st.pop();
                }
                st.push(i);
            }
            else{
                st.push(i);
            }
        }
        else if (st.top() == 'f'){
            if (i == 'g')continue;
            else if (i == 'w'){
                while(st.size() and st.top() == 'f'){
                    st.pop();
                }
                st.push(i);
            }
            else {
                st.push(i);
            }
        }
        else if (st.top() == 'g'){
            if (i == 'w')continue;
            else if (i == 'f'){
                while(st.size() and st.top() == 'g'){
                    st.pop();
                }
                st.push(i);
            }
            else {
                st.push(i);
            }
        }
    }
    stack<char>ans;
    while(st.size()){
        ans.push(st.top());
        st.pop();
    }
    while(ans.size()){
        cout << ans.top();
        ans.pop();
    }
}		 
int main(){  
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int _ = 1; //cin >> _;
	while(_--) solve();
	return 0;
}

代码二:

#include <bits/stdc++.h>
#define lowbit(x) (x & - (x))
#define pii pair<int,int>
#define pil pair<int,long long>
#define pli pair<long long,int>
#define pss pair<string,string>
#define pll pair<long long,long long>
#define pdd pair<double,double>
#define MP make_pair
#define pb push_back
#define pf push_front
#define i64 long long
#define i128 __int128_t
#define ull unsigned long long
#define ld long double
#define ll long long
using namespace std; 
const int N = 3e4+100,M = 2e5+100,inf = 1e9,MOD=1e9+7,mod=998244353;
const long long INF = 1e18;
const double pi = 3.1415926535897932385,eps = 1e-9;
void solve(){
	string s;  cin >> s;
    int n = s.size();
    s = " " + s;
    char c = '#';  int cnt = 0;
    for (int i=1; i<=n; i++){
        if (cnt == 0){
            c = s[i];
            cnt = 1;
            continue;
        }
        if (s[i] == 'w'){
            if (c == 'f'){
                c = s[i];
                cnt = 1;
            }
            else if (c == 'w'){
                cnt++;
            }
        }
        else if (s[i] == 'g'){
            if (c == 'w'){
                c = s[i];
                cnt = 1;
            }
            else if (c == 'g'){
                cnt++;
            }
        }
        else {
            if (c == 'g'){
                c = s[i];
                cnt = 1;
            }
            else if (c == 'f'){
                cnt++;
            }
        }
    }
    for (int i=1; i<=cnt; i++){
        cout << c;
    }
}		 
int main(){  
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int _ = 1; //cin >> _;
	while(_--) solve();
	return 0;
}

C-red的位运算

分析一下题意，把没有用的背景都忽略了(出题人话真多)。题目所要我们求的是所有区间的区间&之和，区间|之和. 我们很容易想到朴素的解法,去枚举所有区间,然后算出每个区间的区间&和区间|求和就好了。好的，恭喜你会获得TLE. 题目给定 $n$ 的大小是 $10^5$ ,上述做法的时间复杂度是 $O(n^2)$ 的，当然不会给你通过(太暴力了,难怪....).

既然是位运算,我们当然要从每个数的二进制表示来分析. 熟悉二进制的trick的话你会对这种求和(算贡献)会比较敏感,因为二进制下一个数的每一位所带来的贡献都是独立的,所以我们可以把所有位都单独拿出来,去考虑当前位j能产生多少贡献. 我们来分析一个&案例.

你拿到两个二进制下的数分别为 1010(10) 0111(7) 10&7=2 我们观察发现10,7的二进制下只有第一位同时为一这个时候第一位能产生的贡献是 $2^1$ 而对于其他位都是 1&0=0,该位不会产生贡献.

那我们就能够顺理成章的知道在什么情况下才会有贡献了. 假定你现在要算的区间是 $[l,r]$ ,如果想要使得第j位有贡献,那区间 $[l,r]$ 内所有的数二进制的第j位必须为1.而其所产生的贡献为 $2^j$ . 同理对于区间|,只要区间 $[l,r]$ 内存在一个数二进制下第j位为1,那这个区间就能产生 $2^j$ 的贡献。

我们知道了逐位算贡献后，我们开始考虑怎么样算才能把每个区间都给算出来。

对于区间&从1开始枚举区间的右端点r,当前枚举到的右端点是r, 枚举 $a_r$ 的二进制下的每一位

如果二进制下 $a_r$ 的第j位是0,考虑选取左端点l $(l \le r)$ ，你会发现既然你 $a_r$ 第j位都位0了，我无论左端点怎么选,任何一个区间的第j位产生的贡献都是0,也就是说这种情况下以r为右端点第j为产生的贡献都是0.

如果二进制下 $a_r$ 的第j为是1,哎这个时候就完全有必要去考虑哪些区间第j位会产生贡献了。对于区间 $[l,r]$ 这个区间有贡献就意味着 $[l,r]$ 这个连续的区间里所有数的二进制第j位都是1.

假如 $a_i$ 二进制下的第j位为0,那么只要左端点 $l \le i$ 区间 $[l,r]$ 都不会产生贡献.此时能产生的贡献应该是 $2^j*(r-l)$

这启发我们要去在枚举的途中去维护离第i个数最近的二进制数为j的数的位置 $pos_{i,j}$ .对于区间&只要我知道当前离r最近的0在哪,就可以知道有多少个以r为右端点的区间第j位有贡献.

同理,对于区间|,如果 $a_r$ 第j位是1,那无论左端点在哪区间 $[l,r]$ 都会产生贡献,此时产生的贡献是 $2^j*r$ .

如果区间 $a_r$ 第j位为0,那我要找到离r左边最近的i,其中 $a_i$ 二进制第j位为1,此时对于 $l(i<l)$ ,区间 $[l,r]$ 的第j位产生的贡献都是0,而能产生贡献的区间 $l$ 满足 $l\le i$ ,所以此时的第j位能产生的贡献是 $2^j*i$ 。

至此,我们找到了解决这道题的方法. 简单总结一下,我们需要维护一个位置信息 $pos_{i,j,k}$ 表示离第i个数最近的二进制第j位为k的数的位置. 由于我们是从左往右枚举,代码中优化掉了一维.

通过这样的算贡献方法，我们成功把 $n^2$ ,优化到了 $nlogn$ 。难度: 1600

代码:

#include <bits/stdc++.h>
#define lowbit(x) (x & - (x))
#define pii pair<int,int>
#define pil pair<int,long long>
#define pli pair<long long,int>
#define pss pair<string,string>
#define pll pair<long long,long long>
#define pdd pair<double,double>
#define MP make_pair
#define pb push_back
#define pf push_front
#define i64 long long
#define i128 __int128_t
#define ull unsigned long long
#define ld long double
#define ll long long
using namespace std; 
const int N = 3e4+100,M = 2e5+100,inf = 1e9,MOD=1e9+7,mod=998244353;
const long long INF = 1e18;
const double pi = 3.1415926535897932385,eps = 1e-9;
void solve(){
	int n;  cin >> n;
	vector<int>a(n+1);
	vector cnt(n+1,vector<int>(31));
	for (int i=1; i<=n; i++){
		cin >> a[i];
		for (int j=0; j<31; j++){
			if (a[i]>>j&1){
				cnt[i][j]++;
			}
		}
	}
	i64 res1 = 0, res2 = 0;
	vector pos(31,vector<int>(2));
	for (int i=1; i<=n; i++){
		for (int j=0; j<31; j++){
			if (a[i]>>j&1){
				// 区间or
				res1 += 1ll*i*(1ll<<j);
				// 区间and
				int t = pos[j][0];
				res2 += 1ll*(i-t)*(1ll<<j);
				res2 %= mod;
				pos[j][1] = i;
			}
			else {
				int t = pos[j][1];
				res1 += 1ll*t*(1ll<<j);
				pos[j][0] = i;
				res1 %= mod;
			}
		}
	}
    cout << res2 << " " << res1 << "\n";
}		 
int main(){  
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int _ = 1; //cin >> _;
	while(_--) solve();
	return 0;
}

总结

这四个题实际上稍微有点难度的可能是red的位运算题，要求你熟悉二进制的算贡献经典套路，和算区间的一个小方法，其他的题都是比较板，稍微有一点思维的题，大家"应该"感觉挺简单的吧.

inqwq23 LV 3 SU @ 2025-10-28 15:29:16

qp
xiaorana LV 6 @ 2025-10-27 19:59:15

学长啊，学弟我啊，连题解也看不懂(ಥ﹏ಥ)

hut二面部分题解

引言

B-red的游戏时间

E-red的咒语

D-red的属性克制

C-red的位运算

总结

2 条评论

状态

开发

支持

关于

友情链接

hut二面部分题解

引言

B-red的游戏时间

E-red的咒语

D-red的属性克制

C-red的位运算

总结

2 条评论

状态

开发

支持

关于

友情链接

还没有账户？

登录