ICPC训练赛补题集

ICPC训练赛补题集

---

D - Fast and Fat (负重越野)

原题链接：原题链接
题意：体重大的背体重小的速度不变，体重小的背体重大的速度会变化，变化$vi-(wj-wi)$程度。有T组数据，有多组测试数据。第一行输入一个整数T 表示测试数据组数，对于每组测试数据：
第一行输入一个整数n表示队员人数。
对于接下来n行，第$i$行输入两个整数$v_i$和$w_i$,表示速度和体重的大小。
The optimal strategy for the sample test case is shown as follows:

• Let member $1$ carry member $4$. As $w_1>w_4$, member $1$’s speed remains unchanged, which is still $10$.
• Let member $3$ carry member $2$. As $w_3<w_2$, member $3$’s speed will decrease by $w_2-w_3=2$ and becomes $10-2=8$.
• Member $5$ shall move alone. His/Her speed is $9$.
  So the answer is $8$.
  思路：利用二分的方法，二分答案，尽量往右找，最后输出$l$的值就是答案。主要思想是check函数里面的内容，主要就是找出来速度低于mid的，判断它们是否能被背起来达到速度最小是mid，速度大于mid的都是来背或者不背其它人的。当速度小于mid的人数大于速度大于等于mid的人时，这个mid一定不能用，要$return0$掉。而且还要判断能否通过别人背起来达到mid的速度。

#include <bits/stdc++.h>
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N = 1e5+5;
//int a[N],b[N];
int n;
vector<PII> a;
int check(int mid)
{priority_queue <int> b,c;//这里用到的优先队列会从大到小自动排序。for (int i=0;i<n;i++){if (a[i].fi>=mid){b.push(a[i].fi+a[i].se);}else {c.push(a[i].se);}}if (b.size()<c.size()) return 0;while (b.size()&&c.size()){if (b.top()-c.top()>=mid){b.pop();c.pop();}else return 0;}if (!c.empty()) return 0;return 1;}void solve ()
{	a.clear();//注意这里一定要清空vector的值cin>>n;for (int i=1;i<=n;i++){int x,y;cin>>x>>y;a.push_back({x,y});//这里用vector加pair的方式存入两个变量，也可以用结构体啥的}int l=0,r=1e9+1,mid;//标准二分答案板子while (l<r){int mid=l+r+1>>1;if (check(mid)) l=mid;else r=mid-1;}cout<<l<<'\n';
}signed main ()
{IOS;int T =1;cin>>T;while(T--) solve ();return 0;
}

---

I-路径规划

原题链接：此处跳转
 刚拿到这一题的时候一点思路都没有，更别说能想到是二分的方法来写了。但是看完答案过后“柳暗花明又一村”，豁然开朗。因为有最大的字眼，所以就用二分？反正这一题用二分是正解。
题意：给出$n\times m$的序列， 从左上角走到右下角找到最大的$MEX$，$MEX$是路径中没出现的最小非负整数，例如路径中的数字为“0 2 4 5 6”，那么$MEX$的值就是1，因为1没有出现过。因此我们就要找出来最大的$MEX$的值；
 思路：因为范围比较大 $1\le n,m\le 10^6$, $1\le n\times m\le 10^6$ 所以我们用一般的二维数组肯定是存不了的，会爆掉，我们这里用到cin>>a[i*m+j]（i为行，j为列）这样的方式给数组存进来。输入问题解决之后就要用到很奇妙的思维了，因为要求最大的mex，我们这里可以用二分的思想，尽量向右找，然后输出l即可。那么check函数该怎么写？怎么写？怎么写？问三遍。这里的思维很奇妙，我们知道如果要让一个数符合标准，例如3，让3成为最小的没出现过的数，我们就要找到它之前的所有数字“0 1 2 ”都要找到，那么重中之重就是能不能找到这几个数字。因为只能向右和向下走，那么我们可以定义一个k来存储位置，判断能不能往下一个方向出发。例如:

bool check (int x)
{int k=0;//定义一个kfor (int i=0;i<n;i++){for (int j=0;j<m;j++){if (a[i*m+j]<x)//找小于x的数字{if (k>j) return false;//如果走不到这个位置，无法到达就肯定不符合条件，二分return掉k=j;//更改位置}}}return true;//如果都符合条件就return true
}

 加上二分的模板之后就能轻松AC了，主要还是要知道这是一到二分的题目，看不出来那这道题还写个集贸，直接寄了吧

#include <bits/stdc++.h>
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N = 1e6+5;
int a[N],b[N];
int n,m;
bool check (int x)
{int k=0;for (int i=0;i<n;i++){for (int j=0;j<m;j++){if (a[i*m+j]<x){if (k>j) return false;k=j;}}}return true;
}void solve ()
{cin>>n>>m;for (int i=0;i<n;i++){for (int j=0;j<m;j++)cin>>a[i*m+j];}int l=0,r=n*m,mid;while (l<r){int mid=l+r+1>>1;if (check(mid)) l=mid;else r=mid-1;}cout<<l<<'\n';
}signed main ()
{IOS;int T =1;cin>>T;while(T--) solve ();return 0;
}

---

G. Inscryption(邪恶铭刻)

 原题链接：点击此处
 题意：有T组数据，每组数据有一个n，接下来有n个数据

如图所示，一些题目要求。分别用1 -1 0 来表示。
 这道题我们写了好久没有写出来，果真还是太菜了，看完别人的代码感觉好简单，但是这种思路我们肯定也想不到。
 思路：用sum来表示总共的攻击力，用cnt来表示有多少人，用choice来表示可以反悔多少次。这个反悔很奇妙，真的太妙了。因为0可以变成1或者-1.假设我们就让0变成-1，因为尽量变成-1才会让平均数最大。假设先变成-1，再往后看，如果后面行不通了，就反悔回来，sum++，cnt++，choice–。主要思想看代码

#include <bits/stdc++.h>
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N = 1e5+5;
int a[N],b[N];
void solve ()
{int n;cin>>n;int flag=0;int sum=1,cnt=1,choice=0;for (int i=1;i<=n;i++){int x;cin>>x;if (x==1) sum++,cnt++;//这种情况只能sum++，cnt++else if (x==-1){if (cnt>1) cnt--;//为-1的时候cnt--，sum不用减，因为牺牲了，但攻击力给别人了else if (choice>=1) sum++,cnt++,choice--;//如果cnt不大于1那么看看是否能反悔，能反悔就可以，否则输出-1else flag=1;}else {if (cnt>1) cnt--,choice++;//假设变成-1else sum++,cnt++;//变成1}}int k=__gcd(sum,cnt);if (flag==1) cout<<"-1"<<'\n';	else cout<<sum/k<<' '<<cnt/k<<'\n';//约分，直接求出最大公约数再除以他们就ok了，但是手写gcd函数会更快
}signed main ()
{IOS;int T =1;cin>>T;while(T--) solve ();return 0;
}

 感觉就是考了一个思维，没想到我们却写的如此稀碎，能写对的也就最大公约数的函数了。怎么办呢？？？？
还是 cai jiu duo lian吧

---

NEW Houses

原题链接 ：点击这里
 题意 ：给出了每个人的自己住和有领居一起住的满意度，问有n个人，m个房间改怎么安排才能使这n个人满意度最大
这就是一个贪心的问题，将满意度最大的安排起来使大家的满意度最大。
因为没有领居的话他能占两格或者三格，所以我们就要注重注意一下这没有领居的人，我们先给这些人的位置安排好，有领居的人的位置就好安排了。那么怎么安排n个人独居的人数呢？
我们可以发现，当n=m的时候是没有能一个人住的。我们设sum为能独居的人数，我们通过计算可以得知出来sum在各个情况下的值

if(n==m) sum=0;
else if (m>=2*n-1) sum=n;
else sum=m-n;
知道了各个情况下的最多能有多少个独居人数就可以进行下面的操作

• 这里特判一下当n==1的时候，直接输出独居的满意度即可
  以下代码是输入的代码，定义一个结构体存入数据，如果独居满意度大于有领居的时候将他们存入定义的vector数组里面，类型为结构体类型，类似于pair。因为这样的数据可能独居可能合居，所以不能单纯只存入一个数据。再将只能合居的人存入另一个vector（类型为int）数组里面；

for (int i=1;i<=n;i++){cin>>ss[i].a>>ss[i].b;if (ss[i].b-ss[i].a>0){a.push_back(ss[i]);}else b.push_back(ss[i].a);}

整体思路就是先将独居的放入房间，再放合居的人，但是特判一下当只有一个不能独居的时候，是让他独居，还是和独居的人合居，这要进行一次判断。其他的就直接把独居的人数的满意度加起来，保证不能超过sum个独居的人数，再加以优化

#include <bits/stdc++.h>
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N = 5e5+5;struct node
{int a,b;
}ss[N];bool cmp (node q,node w)
{return (q.b-q.a)>(w.b-w.a);
}void solve ()
{vector<node> a;vector<int>b;int n,m;cin>>n>>m;int sum=0;if(n==m) sum=0;else if (m>=2*n-1) sum=n;else sum=m-n;if (n==1){int x,y;cin>>x>>y;cout<<y<<'\n';return ;}for (int i=1;i<=n;i++){cin>>ss[i].a>>ss[i].b;if (ss[i].b-ss[i].a>0){a.push_back(ss[i]);}else b.push_back(ss[i].a);}sort(a.begin(),a.end(),cmp);if (a.size()==n-1&&sum==n){sum-=2;int ans1=0;for (auto i : a){if (sum){ans1+=i.b;sum--;}else {ans1+=i.a;}}for (auto i : b)ans1+=i;int ans2 =0;for (int i=1;i<=n;i++)ans2+=ss[i].b;cout<<max(ans1,ans2)<<'\n';}else {int ans=0;for (auto i : a){if (sum){ans+=i.b;sum--;}else {ans+=i.a;}}for (auto i : b)ans+=i;cout<<ans<<'\n';}
}signed main ()
{IOS;int T =1;cin>>T;while(T--) solve ();return 0;
}

---

雪中楼(西安交通大学)

一道构造题，难度不大，值得好好看一看

---

又是一道我们写了好久都没有写出来的题，比赛的时候我们想的了好久都没有A出来，真的太伤心了，我们的思路简直就是清朝老兵的方法，太笨了，代码实现老麻烦了。我们思路是根据给出的序列求出来原序列，再根据原序列排序输出。。。。交了好几次都WA掉了。赛后我们发现别人的思路真好。
从后往前遍历数组，根据题意就可以把序列进行一些转换，就直接省去了求原序列的操作，真的很方便。进行数列的转移操作，整体转移，用双重vector实现。

#include <bits/stdc++.h>
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N = 2e5+5;
int a[N];
vector<int>b[N];//开双重vector可以将序列进行转移操作
void solve ()
{int n;cin>>n;for (int i=1;i<=n;i++){cin>>a[i];b[i].push_back(i);//先用数组存入下标}for (int i=n;i>=0;i--){if (a[i]==0)//如果为0的话，证明此时已经是最小的了，直接输出这一部分就可以了{for (auto j : b[i]){cout<<j<<' ';}}else //如果不为零将b[i]部分都存到b[a[i]]部分{for (auto j : b[i])//遍历存入b[a[i]].push_back(j);}}
}signed main ()
{IOS;int T =1;
//	cin>>T;while(T--) solve ();return 0;
}

看完答案豁然开朗，看答案之前我是生死难料，模拟了好久硬是没搞出来，果然还是方法不对啊
多练，多找找写题的感觉，我就还不行了这种题一直不会写

L.BracketGeneration

 题意：给出最终的序列，让你从序列（）变到最终序列可以有多少种不同的操作，序列分为2种情况：
 1.是向最右边加一个括号$()$
 2.是选择区间[L,R]，向区间外加括号$()$。
怎么求出来一共有几种变换方案
 思路：先遍历一遍***字符串，标记字符‘)’，如果它前面有’('与它匹配就标记1，否则就标记0
由此我们可以得知样例2给出的例子((()())()())(())可以标记成11211212，然后从后往前将出现2的地方res=cnt
再将最后结果取模即可

#include<bits/stdc++.h>
#define int long long 
#define endl "\n"
#define fi first
#define se second
#define PII pair<int,int> 
using namespace std;
const int N=1e6+5;
int a[N];
int mod=998244353;
void solve(){string s;cin >> s;stack<int> st;vector<int> v;//存入1和2操作的序列for(int i=0;i<s.size();++i){if(s[i]=='(') st.push(i);else{if(st.top()==i-1) v.push_back(1);//若括号相邻，则是操作1else v.push_back(2);//反之则为操作2st.pop();}}reverse(v.begin(),v.end());int ans=1;for(int i=0;i<v.size();++i){if(v[i]==2){ans*=(i+1);//ans乘以当前可支配的括号数量（即为下标i+1）ans%=mod;} 		}cout << ans << endl;return ;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T=1;//cin >>T;while(T--) solve();return 0;
}

E - Checksum

---

 ICPC训练赛的一道题，感觉还不错，难度不是很大。感觉考到了一个小小的思维。
题意：给出$n$组数据，每组数据下包含两个整数$n,k$，第二行输入一个长度为n的01串A，找到一个01串B长度为k，将A和B中1的个数相加得到D，将D转化成2进制，判断D与B是否一样，如果一样的话输出最小的B，否则输出None
 思路：B的长度为0到k，那么B中1的个数为0到k个，因为A中1的个数是已知的，所以我们D的大小是差不多已知的，我们循环0到k可以算出来D的大小，再每次将D的大小写成2进制。
 注意！这里有很重要一点，就是如何判断B中0和1的位置关系。只要我们这样写下去模拟几次就会发现，其实我们并不用关注B中的排列位置，当我们2进制下的D中1的个数和B中1的个数相同二者就是一样的，模拟几次就会发现这样的一个规律了。
 注意有一点！我们一定要将D转化的二进制个数和B的长度一样，不然就不用考虑了，如果不够长我们可以加0来写二进制，因为不影响大小。

---

#include <bits/stdc++.h>
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
const int N = 1e5+5;
int a[N],b[N];
void solve ()
{string ans="99999999999999";//定义一个很大的string，用于判断int n,k;cin>>n>>k;string s;cin>>s;int cnt=0;for (int i=0;i<s.size();i++) {if (s[i]=='1') cnt++;}for (int i=0;i<=k;i++){string t;int now=cnt+i;int sss=0;while (now&&sss<k)//转化成二进制{t+=(now%2)+'0';sss++;now>>=1;}for (int i=t.size();i<k;i++)t+="0";//如果长度不够就补0reverse(t.begin(),t.end());//反转过来int pos=count(t.begin(),t.end(),'1');if (pos==i){ans=min(ans,t);}}if (ans=="99999999999999") cout<<"None"<<'\n';else cout<<ans<<'\n';
}signed main ()
{IOS;int T =1;cin>>T;while(T--) solve ();return 0;
}

---

(持续更新中)$.......................$