题解 | #小沙の好客#
小沙の好客
https://ac.nowcoder.com/acm/contest/46813/A
首先来一段赛前采访：
注意：第三第四指的是第三或者第四简单！
沙烬在2022年寒假集训营（第二场）中立下了50个人AK的flag，然而，只有江莉一人AK（所以一个江莉等于50个人）。
然后评价一下题目：和我想象中的一样毒瘤！
小沙毒瘤！
小沙毒瘤！！
小沙毒瘤！！！
接下来是题解时间！
A 小沙の好客
签到题，前缀和，二分
尽可能取小于 的最大的 个最优。
那么从大到小排序后就是取一段连续的区间，区间求和也就是前缀和。那么每次查询就是从比小于等于 的最多 个商品的价值和，不能取到 个则只能取到最后一个。由于查询数量过多，要用二分进行查找，可以直接 lower_bound 。
注意开 long long ，有笨蛋忘记了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
int T = 1;
while(T--){
LL n,q;
cin>>n>>q;
vector<LL> a(n+1);
auto s = a;
for(int i=1;i<=n;i++){
cin>>a[i];
}
a[0] = 2e9;
a.push_back(0);
sort(a.begin(), a.end(), greater());
for(int i=1;i<=n;i++){
s[i] = s[i-1] + a[i];
}
while(q--){
LL k,x;
cin>>k>>x;
int t = lower_bound(a.begin(), a.end(),x, greater()) - a.begin();
if(t>=n) cout<<0<<endl;
else{
int r = min(t+k-1,n);
cout<<s[r]-s[t-1]<<endl;
}
}
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60686036
B 小沙の博弈
签到题，贪心
字典序最小，那每次拿一个石子就可以了，如果共有偶数个石子就是平局，否则小沙会比小雅多一个，小雅赢。
也就是说，这个游戏小沙不可能能赢（这就是家庭弟位吗？建议以后用这个游戏决定谁做家务！）。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main(){
int T = 1;
while(T--){
int n;
cin>>n;
if(n&1) cout<<"Yaya-win!"<<endl;
else cout<<"win-win!"<<endl;
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60686386
C 小沙の不懂
中等题，防（工口姐姐）AK（的）题
但其实嘤嘤赛后也被 hack 了，hack 如下：
上图也讲了大致的做法，就是把前导零提取出来后，再加一点特判就行。
假代码就不放了（不懂啊，这我是真的不懂）。
D 小沙の赌气
中等题，STL战神，阅读理解
怎么有人这么菜的？
不用攻略就过不了关的？
怎么还有两个？
怎么两个人玩游戏的？
怎么两个人不一起玩游戏的？
怎么这两个人不玩分手厨房的？
嘤嘤の赌气！
用一个数据结构记录有哪些道具，并按照左端点从小到大排序，然后每次新获得一个道具时，就从前往后看能用哪些道具（一关可以重复过，无所谓的），用完后删除道具，最后到了哪里。
这个数据结构可以选择，map，set，priority_queue 等。
注意：有卧龙凤雏第一关都过不去，所以初始化的时候需要为0，而不是1。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main(){
int T = 1;
while(T--){
int n;
cin>>n;
vector<PII> sj(n+1),yy=sj;
for(int i=1;i<=n;i++){
int l,r;
cin>>l>>r;
sj[i] = {l,r};
}
for(int i=1;i<=n;i++){
int l,r;
cin>>l>>r;
yy[i] = {l,r};
}
int a = 0 , b = 0;
map<PII,int> L,R;
for(int i=1;i<=n;i++){
L[sj[i]]++;
R[yy[i]]++;
while(L.size()){
auto [l,r] = L.begin()->first;
if(l>a+1) break;
a = max(a,r);
L.erase(L.begin());
}
while(R.size()){
auto [l,r] = R.begin()->first;
if(l>b+1) break;
b = max(b,r);
R.erase(R.begin());
}
if(a==b) cout<<"win_win!"<<endl;
else if(a>b) cout<<"sa_win!"<<endl;
else cout<<"ya_win!"<<endl;
cout<<abs(a-b)<<endl;
}
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60696966
E 小沙の印章
防AK题（防嘤嘤AK的题），构造，诈骗题
怎么那么喜欢环，裴坚吗？
只要你不知道这是个环，你就会了。。。。。
嘤嘤卡了一个小时，赛后 jls 说了一句冒泡排序，嘤嘤就会了。。。。。
关键是，我一直是 (1 2)，(3 4)，(5 6)；(2 3)，(4 5)，(6 1) 这样轮流换，然后可以做到用奇数遇见所有偶数。但只要把 (6 1) 的交换去掉，就出结果了QAQ（战死沙场）
冒泡排序，冒一遍就可以看出来，确实都碰见了一遍，虽然不知道为什么，然后代码也非常简单。
1 2 3 4 5 6
2 1 4 3 6 5
2 4 1 6 3 5
4 2 6 1 5 3
4 6 2 5 1 3
6 4 5 2 3 1
6 5 4 3 2 1
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main(){
int T = 1;
while(T--){
int n;
cin>>n;
cout<<n<<endl;
vector<int> a(n+2,-1);
for(int i=1;i<=n;i++){
a[i] = i;
}
for(int i=1;i<=n;i++){
if(n&1) cout<<n/2<<endl;
else{
if(i&1) cout<<n/2<<endl;
else cout<<n/2-1<<endl;
}
for(int i=1;i<=n;i++){
if(a[i]<a[i+1]){
cout<<a[i]<<" "<<a[i+1]<<endl;
swap(a[i],a[i+1]);
i++;
}
}
}
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60724757
F 小沙の串串
困难题，贪心
题解好难不会写！
首先，由于操作顺序是任意的，所以我们的操作可以当成直接删掉一个字母，在字母池中加入一个字母。等所有操作结束后，再把字母池进行从大到小排序后丢在新字符串末尾。
那么现在我们就需要删除 个字母，使得剩下的字符串字典序最大。
字典序最大的字母挪到最前面挤成一堆肯定是最优的，若都挪完了，那么接下来就是挪动字典序次大的字母。若挪不到（操作次数不足），那么肯定要把第一个挪不到前面的大字母尽可能往前挪，也就是剩下的操作一定要在这个大字母之前进行（根据字典序的定义进行贪心，显然（不会证明，去看毒瘤沙的证明）更优）。
也就是说的剩下的操作只会在把前面挤成一堆的大字母去掉，再把当前的大字母和后面的其他字母去掉后剩下的字符串中进行。剩下的操作方式依旧是删除字母，使得剩下的字典序最大，也就是重复上述操作。
比如，字符串为 cadbcada ，操作次数为 3 ，首先尝试把最大的字母 d 挤成一堆，第一个 d 要往前挪需要操作两次，字符串就会变成 dbcada 。接下来是把第二个 d 挪到前面，需要 3 次操作，但操作次数只剩 1 次，所有剩下 1 次操作我们一定会在 bca 中进行。bca 中的最大字母为 c ，将 c 挪到最前恰好需要 1 次操作，字符串变成 ca ，操作结束。接下来把字符串进行还原，首先最前面堆在一起后被去掉的大字母为 d ，然后中间一段为 ca ，大字母和后面的其他字母为 da ，字母池为 cba ，拼接起来就是 dcadbca 。
但有时候操作次数并不会用完，如上例的字符串，若操作次数为 4 ，最后那个操作进行完之后，我们会发现 ca 是不会进行 1 次操作的，所以我们还需要在剩余的字符串中，从小到大的删除字母，也就是删掉 a ，只保留 c ，这样可以使整体字典序尽可能大（因为后面还有 d 和其他字母）。再按照上例拼接则是 dcdabcaa 。
cadbcada 3
dbcada ca
d bca da ca //前面已固定的 要操作的 后面无影响的 字母池
d ca da cab
dcadacba
cadbcada 4
dacada ca
d bca da ca
d ca da cab
d c da caba
dcdacbaa
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main(){
int T = 1;
while(T--){
int n,k;
cin>>n>>k;
string s;
cin>>s;
if(k>=n){
sort(s.begin(), s.end(), greater());
cout<<s<<endl;
continue;
}
vector<int> b(n+1,1); //记录字符是否被删除
s = "{" + s;
string t;
int r = n;
for(int j='z';j>='b';j--){
for(int i=1;i<=r;i++){
if(b[i] && s[i]==j){
int l = i;
for(;l>0;l--){
if(s[l-1]>=j) break;
}
if(l>0){
if(k>=i-l){
for(int j=l;j<i;j++){
b[j] = 0;
t += s[j];
}
k -= i-l;
}
else r = i;
}
}
}
}
for(int j='a';j<='z';j++){
for(int i=1;i<=r;i++){
if(b[i] && k>0 && s[i]==j){
t += s[i];
k--;
b[i] = 0;
}
}
}
for(int i=1;i<=n;i++){
if(b[i]) cout<<s[i];
}
sort(t.begin(), t.end(), greater());
cout<<t<<endl;
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60708325
G 小沙の编码
防AK题，二分图匹配
我使用的图匹配是网络流，匈牙利算法（牛头人算法）不知道可不可以过。
与 二进制下仅有一位不同的数，最多只有 个，然后把这些数与 进行对比是否也只有一位不同，且没在已知的位置出现过，若满足，则将第 个位置向满足的数字连一条容量为 1 的有向边。
然后从超级源点向所有奇数位置连一条容量为 1 的边，所有没给定的数字向超级汇点连一条容量为 1 的边，然后跑一遍最大流，再找一下割边，把数字填进位置，就可以了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class Dinic{
public:
struct edge{
int to; //到达点
T flow; //边权流量
int re; //反向边下标
};
vector<vector<edge>> ve;
vector<vector<int>> true_edge;
vector<int> deep, cur; //深度，以及弧优化
int n,S,E;
Dinic(int n,int S,int E) : n(n) , S(S) , E(E){
ve.resize(n+1);
}
void add(int u,int v,T w){
true_edge.pb({u, v, (int)ve[u].size()}); //正向边及下标，用于求最小割
ve[u].pb({v, w, (int)ve[v].size()}); //正向边
ve[v].pb({u, 0, (int)ve[u].size()-1}); //反向边
}
bool bfs(){
deep = move(vector<int>(n+1,0)); //初始化，因为每次 bfs 后 deep 不一定相同
cur = move(vector<int>(n+1,0)); //弧优化归 0
queue<int> q;
q.push(S);
deep[S] = 1;
while(q.size()){
auto u = q.front();
q.pop();
if(u==E) return true; //可达，则有增广路，存在流量
for(auto &[i,j,k] : ve[u]){
if(deep[i] || !j) continue;
deep[i] = deep[u] + 1;
q.push(i);
}
}
return false;
}
T dfs(int u,T in){
if(u==E) return in; //增广路最终的有效流量
T out = 0; //流出的流量
for(int i=cur[u];i<ve[u].size();i++){ //从还有流量的边开始走
auto &[v,flow,re] = ve[u][i];
cur[u] = i; //更新弧优化
if(!flow || deep[v]!=deep[u]+1) continue;
T res = dfs(v , min(in,flow)); //向下一层流量限制为获得的流量和可输出的流量中小的那一个
flow -= res; //本条边可输出的流量减少了 res
ve[v][re].flow += res; //反向路径可输出流量增加了 res
in -= res; //获得的流量消耗了 res
out += res; //当前结点可输出的流量增加了 res
if(!in) break; //获得流量消耗完了，没必要往下走了
}
if(!out) deep[u] = 0; //当前结点输出不了流量了，下次不用进来了
return out; //返回输出的流量
}
T max_flows(){
T sum = 0;
while(bfs()){
sum += dfs(S,1e9);
}
return sum;
}
vector<pair<int,int>> min_cuts(){
vector<pair<int,int>> ans;
for(auto &v : true_edge){ //v[0]~v[2] 分别记录有向边起点，终点，边的下标
if(!ve[v[0]][v[2]].flow) //当正向边流量为0时，说明是最小割
ans.pb({v[0],v[1]});
}
return ans;
}
};
int main(){
int T = 1;
while(T--){
int n;
cin>>n;
vector<int> a(n+1);
map<int,int> mp;
map<int,int> mi;
for(int i=1;i<=n;i*=2){
mi[i]++;
}
for(int i=0;i<n;i+=2){
cin>>a[i];
mp[a[i]]++;
}
int S = 0;
int E = n*2+1;
Dinic<int> dinic(n*2+2,S,E);
for(int i=1;i<n;i+=2){
for(int j=0;j<=20;j++){
int t = a[i-1] ^ (1<<j);
if(!mp.count(t) && t<n){
if(i+1>=n) dinic.add(i,t+n,1);
else if(mi.count(a[i+1]^t)) dinic.add(i,t+n,1);
}
}
}
for(int i=1;i<=n;i+=2){
dinic.add(S,i,1);
}
for(int i=0;i<n;i++){
if(!mp.count(n)) dinic.add(i+n,E,1);
}
int ans = dinic.max_flows();
auto v = dinic.min_cuts();
for(auto &[x,y] : v){
if(x==S || y==E) continue;
a[x] = y-n;
}
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60713811
H 小沙の店铺
签到题，模拟，阅读理解，猜题意
你看懂了，再猜一下题意，再模拟一下，就可以了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
int T = 1;
while(T--){
LL x,y,k,n,T;
LL ans = 0;
cin>>x>>y>>k>>n>>T;
LL sum = 0;
for(int i=1,j=n;i<=n;i++,j--){
ans += x*j;
sum += j;
x += sum/k*y;
sum %= k;
if(ans>=T){
cout<<i<<endl;
return 0;
}
}
cout<<-1<<endl;
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60688830
I 小沙の金银阁
中等题，阅读理解
看了半天，没懂写的什么玩意儿。。。。。。。。。。
要想不亏，那么每一场下注必须是前面所有场的和，那么至少会是 总和为 ，随便整几场就没了，所以大于 51 场一定无解直接不用考虑。并且根据这个式子，第一天要下注 。
考虑优化，那么某一场要赢更多的话，就在这场加 ，那么其之后的场次必须也要加 ，也是指数级别。并且根据题目，前面加优于后面加，所以加的肯定不会太多（每个位置最多就加一次 ），直接从前往后暴力就可以。
代码如下：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
int T = 1;
while(T--){
int n;
LL m;
cin>>n>>m;
if(n==1){
cout<<m<<endl;
continue;
}
if(n==2){
cout<<m/2<<" "<<m-m/2<<endl;
continue;
}
if(n>51){
cout<<-1<<endl;
continue;
}
if((1ll<<(n-1))>m){
cout<<-1<<endl;
continue;
}
LL l = m>>(n-1);
vector<LL> a(n+1);
a[1] = a[2] = l;
LL sum = l*2;
for(int i=3;i<=n;i++){
a[i] = a[i-1]<<1;
sum += a[i];
}
for(int i=1;i<=n;i++){
int t = n - i + 1;
while(sum+(1ll<<t-1)<=m){
sum += 1ll<<t-1;
LL k = 1;
a[i] += k;
for(int j=i+1;j<=n;j++){
a[j] += k;
k *= 2;
}
}
}
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60700696
J 小沙の最短路
防AK题，构造
目前整个寒假集训营唯一防住吉他英雄（波门）AK的题，谁是毒瘤心里有数。
这题是暑假的一道巨hard题转变来的，当时讨论了很久，没有结果，然后小沙搞了个这个简化版，大概知道解法，但一开始犯了个很傻逼的错误，导致初始值搞错了还是构造出了问题，且代码也难写。
转圈圈就可以了，让我想到了一首歌：恋爱脑 （梗门！）。
（快去看契约之吻和孤独摇滚！）
粉色的是起点（鼠标画画真难受），最短路就是全转一遍，也就是 。
由于一开始构造出错了，导致代码写的比较长，可以看看jiangly的，他的比较短（单纯指代码）。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main(){
int T = 1;
while(T--){
int n;
cin>>n;
vector a(n+10,vector<int>(n+10,-1));
int x = n/2+1;
int y = n+1>>1;
cout<<x<<" "<<y<<endl;
vector<PII> d = {{0,1} , {-1,0} , {0,-1} , {1,0}};
int t = 2;
int now = 2;
a[x][y] = 0;
a[x][y+1] = 0;
a[x-1][y+1] = 1;
a[x-1][y] = 2;
x--;
for(int i=1;i<n*n;i++){
int ne = (t+1)%4;
int xx = x + d[ne].first;
int yy = y + d[ne].second;
if(a[xx][yy]<0){
t = ne;
ne = (t+1)%4;
}
else{
if((a[xx][yy]+1)%3 == now || a[xx][yy] == now) now = (now+1)%3;
xx = x + d[t].first;
yy = y + d[t].second;
}
a[x][y] = now;
x = xx;
y = yy;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
cout<<n*n-1<<endl;
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60718436
K 小沙の抱团 easy
签到题，人类智慧
结论就是，每次喊 即可，因为这样留下的人最少。
重复操作，直至人数小于等于 2 即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
int T = 1;
while(T--){
LL n;
cin>>n;
int ans = 0;
while(n>2){
ans++;
n = n/2+1;
}
cout<<ans<<endl;
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60683945
L 小沙の抱团 hard
中等题，DP
维护剩余 人所需花费的最小代价，由于人数不会变多，所以从大到小枚举转移。
值得注意的是：最后不一定只剩两人，有可能更多！
代码如下：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
int T = 1;
while(T--){
int n,m;
cin>>n>>m;
vector<PLL> a(m);
for(auto &[x,y] : a){
cin>>x>>y;
}
if(n<=2){
cout<<0<<endl;
continue;
}
vector<LL> dp(n+1,1e18);
dp[n] = 0;
for(int i=n;i>=2;i--){
for(auto &[x,y] : a){
if(y>=i) continue;
int t = i/y*y;
dp[t] = min(dp[t] , dp[i] + x);
}
}
LL ans = 1e17;
for(int i=2;i<=n;i++){
if(dp[i]<ans){
ans = dp[i];
break;
}
}
cout<<ans<<endl;
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60691414
终于写完了，写了四个多小时，累死我了！（感觉不如再打一场比赛）
本来是不打算写的，但是大家都战死沙场了，非常有戏剧性，所以想写一篇吐槽一下（然后就挖下了大坑）。这个比赛结果结合赛前采访，咱又可以迫害小沙一年啦！嘿嘿！
吐槽归吐槽，玩梗归玩梗，迫害归迫害，但小沙出的题还是不错的（不考虑阅读理解的话！），每一题都有坑点，我几乎就没有不罚时的题，11题13发罚时（有笨逼一直忘记 long long ），三个11题的选手恰好各卡一道题。
不知道下下次见到小沙是什么时候，想他！（下次应该是EC，他应该会去的吧，但是没见过他对象，不知道EC会不会一起来）
投递百度等公司10个岗位 >
我现在也只有一个保底
太难了
