哪个网站可以做计算机二级的题,产品报价网站建设费用,烟台做网站工资,wordpress 图片模板ICPC训练赛补题集 文章目录 ICPC训练赛补题集D - Fast and Fat (负重越野)I-路径规划G. Inscryption(邪恶铭刻)NEW Houses雪中楼(西安交通大学)L.BracketGenerationE - Checksum D - Fast and Fat (负重越野)
原题链接#xff1a;原题链接 题意#xff1a;体重大的背体重小的…ICPC训练赛补题集 文章目录 ICPC训练赛补题集D - Fast and Fat (负重越野)I-路径规划G. Inscryption(邪恶铭刻)NEW Houses雪中楼(西安交通大学)L.BracketGenerationE - Checksum D - Fast and Fat (负重越野)
原题链接原题链接 题意体重大的背体重小的速度不变体重小的背体重大的速度会变化变化 v i − ( w j − w i ) vi−(wj−wi) vi−(wj−wi)程度。有T组数据有多组测试数据。第一行输入一个整数T 表示测试数据组数对于每组测试数据 第一行输入一个整数n表示队员人数。 对于接下来n行第 i i i行输入两个整数 v i v_i vi和 w i w_i wi,表示速度和体重的大小。 The optimal strategy for the sample test case is shown as follows:
Let member 1 1 1 carry member 4 4 4. As w 1 w 4 w_1 w_4 w1w4, member 1 1 1’s speed remains unchanged, which is still 10 10 10.Let member 3 3 3 carry member 2 2 2. As w 3 w 2 w_3 w_2 w3w2, member 3 3 3’s speed will decrease by w 2 − w 3 2 w_2 - w_3 2 w2−w32 and becomes 10 − 2 8 10 - 2 8 10−28.Member 5 5 5 shall move alone. His/Her speed is 9 9 9. So the answer is 8 8 8. 思路利用二分的方法二分答案尽量往右找最后输出 l l l的值就是答案。主要思想是check函数里面的内容主要就是找出来速度低于mid的判断它们是否能被背起来达到速度最小是mid速度大于mid的都是来背或者不背其它人的。当速度小于mid的人数大于速度大于等于mid的人时这个mid一定不能用要 r e t u r n 0 return 0 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 pairint,int
using namespace std;
const int N 1e55;
//int a[N],b[N];
int n;
vectorPII a;
int check(int mid)
{priority_queue int b,c;//这里用到的优先队列会从大到小自动排序。for (int i0;in;i){if (a[i].fimid){b.push(a[i].fia[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的值cinn;for (int i1;in;i){int x,y;cinxy;a.push_back({x,y});//这里用vector加pair的方式存入两个变量也可以用结构体啥的}int l0,r1e91,mid;//标准二分答案板子while (lr){int midlr11;if (check(mid)) lmid;else rmid-1;}coutl\n;
}signed main ()
{IOS;int T 1;cinT;while(T--) solve ();return 0;
}I-路径规划
原题链接此处跳转 刚拿到这一题的时候一点思路都没有更别说能想到是二分的方法来写了。但是看完答案过后“柳暗花明又一村”豁然开朗。因为有最大的字眼所以就用二分反正这一题用二分是正解。 题意给出 n × m n×m n×m的序列 从左上角走到右下角找到最大的 M E X MEX MEX M E X MEX MEX是路径中没出现的最小非负整数例如路径中的数字为“0 2 4 5 6”那么 M E X MEX MEX的值就是1因为1没有出现过。因此我们就要找出来最大的 M E X MEX MEX的值 思路因为范围比较大 1 ≤ n , m ≤ 1 0 6 1 \le n, m \le 10^6 1≤n,m≤106, 1 ≤ n × m ≤ 1 0 6 1 \le n \times m \le 10^6 1≤n×m≤106 所以我们用一般的二维数组肯定是存不了的会爆掉我们这里用到cina[i*mj]i为行j为列这样的方式给数组存进来。输入问题解决之后就要用到很奇妙的思维了因为要求最大的mex我们这里可以用二分的思想尽量向右找然后输出l即可。那么check函数该怎么写怎么写怎么写问三遍。这里的思维很奇妙我们知道如果要让一个数符合标准例如3让3成为最小的没出现过的数我们就要找到它之前的所有数字“0 1 2 ”都要找到那么重中之重就是能不能找到这几个数字。因为只能向右和向下走那么我们可以定义一个k来存储位置判断能不能往下一个方向出发。例如:
bool check (int x)
{int k0;//定义一个kfor (int i0;in;i){for (int j0;jm;j){if (a[i*mj]x)//找小于x的数字{if (kj) return false;//如果走不到这个位置无法到达就肯定不符合条件二分return掉kj;//更改位置}}}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 pairint,int
using namespace std;
const int N 1e65;
int a[N],b[N];
int n,m;
bool check (int x)
{int k0;for (int i0;in;i){for (int j0;jm;j){if (a[i*mj]x){if (kj) return false;kj;}}}return true;
}void solve ()
{cinnm;for (int i0;in;i){for (int j0;jm;j)cina[i*mj];}int l0,rn*m,mid;while (lr){int midlr11;if (check(mid)) lmid;else rmid-1;}coutl\n;
}signed main ()
{IOS;int T 1;cinT;while(T--) solve ();return 0;
}G. Inscryption(邪恶铭刻) 原题链接点击此处 题意有T组数据每组数据有一个n接下来有n个数据 如图所示一些题目要求。分别用1 -1 0 来表示。 这道题我们写了好久没有写出来果真还是太菜了看完别人的代码感觉好简单但是这种思路我们肯定也想不到。 思路用sum来表示总共的攻击力用cnt来表示有多少人用choice来表示可以反悔多少次。这个反悔很奇妙真的太妙了。因为0可以变成1或者-1.假设我们就让0变成-1因为尽量变成-1才会让平均数最大。假设先变成-1再往后看如果后面行不通了就反悔回来sumcntchoice–。主要思想看代码
#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 pairint,int
using namespace std;
const int N 1e55;
int a[N],b[N];
void solve ()
{int n;cinn;int flag0;int sum1,cnt1,choice0;for (int i1;in;i){int x;cinx;if (x1) sum,cnt;//这种情况只能sumcntelse if (x-1){if (cnt1) cnt--;//为-1的时候cnt--sum不用减因为牺牲了但攻击力给别人了else if (choice1) sum,cnt,choice--;//如果cnt不大于1那么看看是否能反悔能反悔就可以否则输出-1else flag1;}else {if (cnt1) cnt--,choice;//假设变成-1else sum,cnt;//变成1}}int k__gcd(sum,cnt);if (flag1) cout-1\n; else coutsum/k cnt/k\n;//约分直接求出最大公约数再除以他们就ok了但是手写gcd函数会更快
}signed main ()
{IOS;int T 1;cinT;while(T--) solve ();return 0;
}感觉就是考了一个思维没想到我们却写的如此稀碎能写对的也就最大公约数的函数了。怎么办呢 还是 cai jiu duo lian吧 NEW Houses
原题链接 点击这里 题意 给出了每个人的自己住和有领居一起住的满意度问有n个人m个房间改怎么安排才能使这n个人满意度最大 这就是一个贪心的问题将满意度最大的安排起来使大家的满意度最大。 因为没有领居的话他能占两格或者三格所以我们就要注重注意一下这没有领居的人我们先给这些人的位置安排好有领居的人的位置就好安排了。那么怎么安排n个人独居的人数呢 我们可以发现当nm的时候是没有能一个人住的。我们设sum为能独居的人数我们通过计算可以得知出来sum在各个情况下的值
if(nm) sum0; else if (m2*n-1) sumn; else summ-n; 知道了各个情况下的最多能有多少个独居人数就可以进行下面的操作
这里特判一下当n1的时候直接输出独居的满意度即可 以下代码是输入的代码定义一个结构体存入数据如果独居满意度大于有领居的时候将他们存入定义的vector数组里面类型为结构体类型类似于pair。因为这样的数据可能独居可能合居所以不能单纯只存入一个数据。再将只能合居的人存入另一个vector类型为int数组里面
for (int i1;in;i){cinss[i].ass[i].b;if (ss[i].b-ss[i].a0){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 pairint,int
using namespace std;
const int N 5e55;struct node
{int a,b;
}ss[N];bool cmp (node q,node w)
{return (q.b-q.a)(w.b-w.a);
}void solve ()
{vectornode a;vectorintb;int n,m;cinnm;int sum0;if(nm) sum0;else if (m2*n-1) sumn;else summ-n;if (n1){int x,y;cinxy;couty\n;return ;}for (int i1;in;i){cinss[i].ass[i].b;if (ss[i].b-ss[i].a0){a.push_back(ss[i]);}else b.push_back(ss[i].a);}sort(a.begin(),a.end(),cmp);if (a.size()n-1sumn){sum-2;int ans10;for (auto i : a){if (sum){ans1i.b;sum--;}else {ans1i.a;}}for (auto i : b)ans1i;int ans2 0;for (int i1;in;i)ans2ss[i].b;coutmax(ans1,ans2)\n;}else {int ans0;for (auto i : a){if (sum){ansi.b;sum--;}else {ansi.a;}}for (auto i : b)ansi;coutans\n;}
}signed main ()
{IOS;int T 1;cinT;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 pairint,int
using namespace std;
const int N 2e55;
int a[N];
vectorintb[N];//开双重vector可以将序列进行转移操作
void solve ()
{int n;cinn;for (int i1;in;i){cina[i];b[i].push_back(i);//先用数组存入下标}for (int in;i0;i--){if (a[i]0)//如果为0的话证明此时已经是最小的了直接输出这一部分就可以了{for (auto j : b[i]){coutj ;}}else //如果不为零将b[i]部分都存到b[a[i]]部分{for (auto j : b[i])//遍历存入b[a[i]].push_back(j);}}
}signed main ()
{IOS;int T 1;
// cinT;while(T--) solve ();return 0;
}看完答案豁然开朗看答案之前我是生死难料模拟了好久硬是没搞出来果然还是方法不对啊 多练多找找写题的感觉我就还不行了这种题一直不会写
L.BracketGeneration 题意给出最终的序列让你从序列变到最终序列可以有多少种不同的操作序列分为2种情况 1.是向最右边加一个括号 ( ) () () 2.是选择区间[L,R]向区间外加括号 ( ) () ()。 怎么求出来一共有几种变换方案 思路先遍历一遍***字符串标记字符‘)’如果它前面有’(与它匹配就标记1否则就标记0 由此我们可以得知样例2给出的例子((()())()())(())可以标记成11211212然后从后往前将出现2的地方rescnt 再将最后结果取模即可
#includebits/stdc.h
#define int long long
#define endl \n
#define fi first
#define se second
#define PII pairint,int
using namespace std;
const int N1e65;
int a[N];
int mod998244353;
void solve(){string s;cin s;stackint st;vectorint v;//存入1和2操作的序列for(int i0;is.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 ans1;for(int i0;iv.size();i){if(v[i]2){ans*(i1);//ans乘以当前可支配的括号数量即为下标i1ans%mod;} }cout ans endl;return ;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T1;//cin T;while(T--) solve();return 0;
}E - Checksum ICPC训练赛的一道题感觉还不错难度不是很大。感觉考到了一个小小的思维。 题意给出 n n n组数据每组数据下包含两个整数 n , k n,k 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 pairint,int
using namespace std;
const int N 1e55;
int a[N],b[N];
void solve ()
{string ans99999999999999;//定义一个很大的string用于判断int n,k;cinnk;string s;cins;int cnt0;for (int i0;is.size();i) {if (s[i]1) cnt;}for (int i0;ik;i){string t;int nowcnti;int sss0;while (nowsssk)//转化成二进制{t(now%2)0;sss;now1;}for (int it.size();ik;i)t0;//如果长度不够就补0reverse(t.begin(),t.end());//反转过来int poscount(t.begin(),t.end(),1);if (posi){ansmin(ans,t);}}if (ans99999999999999) coutNone\n;else coutans\n;
}signed main ()
{IOS;int T 1;cinT;while(T--) solve ();return 0;
}(持续更新中) . . . . . . . . . . . . . . . . . . . . . . . ....................... .......................
