丽江市网站建设,海南网站建设基本流程,做设计挣钱的网站,撩人的网站怎么做目录
D.The Game of Eating
E.Square
F.Link with Chess Game
H.0 and 1 in BIT
I.Link with Gomoku
K.Box D.The Game of Eating
思路#xff1a;倒着贪心。因为正着贪会导致一种局面#xff1a;我选了当前喜爱值最大的菜#xff0c;但是就算我不选这个菜#xff0…目录
D.The Game of Eating
E.Square
F.Link with Chess Game
H.0 and 1 in BIT
I.Link with Gomoku
K.Box D.The Game of Eating
思路倒着贪心。因为正着贪会导致一种局面我选了当前喜爱值最大的菜但是就算我不选这个菜后面的人也可能选这一道菜我依然能吃上这道菜那么我为什么不选其它的菜而两者兼得呢所以我们考虑倒着贪心。贪心到第i个人时根据喜爱值从大到小遍历一遍菜如果这个菜被后面的人选过了那就不选了直到有一个菜是没被选过的。
bool cmp(PII a,PII b) {return a.firstb.first;
}
void solve() {mapint,intmp;int n,m,k;cinnmk;for(int i1; in; i)v[i].clear();for(int i1; in; i) {for(int j1; jm; j) {int x;cinx;v[i].push_back({x,j});}sort(v[i].begin(),v[i].end(),cmp);}for(int ik; i1; i--) {int nowi%n,j0;if(!now)nown;while(mp[v[now][j].second])j;mp[v[now][j].second]true;}for(auto x:mp) {coutx.first ;}coutendl;
} E.Square
思路题目的公式可以表示为求Y使得 Y^2-(Y^2)%(10^K) X*(10^K) 可见只需枚举K的大小然后判断即可。
代码
string cmp;
bool pd(int y) {string nowto_string(y*y);while(now.size()cmp.size())now0;//防止runtime errorfor(int i0; icmp.size(); i) {if(cmp[i]!now[i])return false;//有一位不相同就不合法答案}return true;
}
void solve() {int x;cinx;cmpto_string(x);for(int k0; k9; k) {//枚举k的大小int nowpow(10,k)*x;int ysqrt(now);if(pd(y)) {//判断这个y是否合法coutyendl;return;}if(pd(y1)) {//因为y*y会减掉一部分余数所以要判一下y1couty1endl;return;}}cout-1endl;
}
F.Link with Chess Game
思路若只有一个棋子当棋子有距离边界为奇数长度的局面为先手必胜态因为两个人必须在这个奇数区间里一直走而先手可以一直选到所有位置选完。该情况可推广至三个棋子三个棋子的距离端点距离可以抽象为所有棋子距离端点的距离之和棋子可以在端点之和为奇数的区间内反复横跳来保持自己的最终的奇偶性从而导致先手必胜反之先手必败。
代码
void solve() {int n,a,b,c;cinnabc;int sum1(a-1)(b-1)(c-1);int sum2(n-a)(n-b)(n-c);if(sum1%2||sum2%2)coutAliceendl;else coutBob\n;
}
H.0 and 1 in BIT
思路操作A相当于将x变成反码也就是在取模意义下操作A会令x-x-1而操作B会xx1所以我们先开两个前缀和数组一个记录前缀A的个数一个记录前缀的贡献然后在每次操作中若l~r的区间内的A的个数为奇数则原本的贡献要乘上-1如此模拟即可。
代码
int sum1[maxn],sum2[maxn];
//sum1记录前缀A的个数sum2记录前缀的贡献
void solve() {int n,q,l,r,L,R,ans0;string s,x;cinnqs;for(int i1; in; i) {sum1[i]sum1[i-1](s[i-1]A);if(s[i-1]A)sum2[i]-sum2[i-1]-1;else sum2[i]sum2[i-1]1;}while(q--) {int sum0;cinlrx;Lmin((ans^l)%n1,(ans^r)%n1),Rmax((ans^l)%n1,(ans^r)%n1);int now1(sum1[R]-sum1[L-1])%2,now2;for(int i0; ix.size(); i) {sumsum*2(x[i]-0);}//将x转换为10进制方便与贡献进行运算if(now1) {//若区间A的个数为奇数则贡献*-1now2sum2[R]sum2[L-1];sum-sum;} else now2sum2[R]-sum2[L-1];int mod(1(int)x.size());ans(now2summod)%mod;for(int i(int)x.size()-1; i0; i--) {cout((ansi)1);}coutendl;}
}
I.Link with Gomoku
思路在前面的n-n%2行中摆放方式和题目样例一样 xxxxoxxxxoxxxxo...... ooooxooooxoooox...... 最后一行若为奇数行则这样摆放即可 xoxoxoxoxo...... 代码
void solve() {int n,m;cinnm;for(int i1; in-n%2; i) {int cnt0;for(int j1; jm; j) {if(cnt%54) {//前4个放相同的 if(i%2)couto;//行与行之间连续4个xo交替放 else coutx;} else {//最后一个放不同的 if(i%2)coutx;else couto;}cnt;}coutendl;}if(n%2) {//若最后一行为奇数行则xoxox......交替放 for(int i1; im; i) {if(i%2)coutx;else couto;}coutendl;}
}
K.Box
思路我们设
dp[i][0]表示第i位移动到i-1位的情况
dp[i][1]表示第i位不移动的情况
dp[i][2]表示第i位移动到i1位的情况
具体实现见代码注释。
代码
void solve() {int n;cinn;for(int i1; in; i)cina[i];for(int i1; in; i)cinb[i];for(int i1; in; i) {if(b[i]) {//只有1有主动权0是被迫的QAQdp[i][0]dp[i-1][0]a[i-1];//当前1左移只能由上一个1左移转移过来dp[i][1]max(dp[i-1][0],dp[i-1][1])a[i];//当前位置不动上一个位置1不动或者左移都可以dp[i][2]max({dp[i-1][0],dp[i-1][1],dp[i-1][2]})a[i1];//当前位置右移上一个位置1不动、左移、右移都可以} else {dp[i][0]max({dp[i-1][0],dp[i-1][1]});// 当前位左移可以由上一个位置左移或者上一个位置1还没动的过转移过来dp[i][1]dp[i-1][2];//这个0可以被上个右移的1挤到左边}}coutmax(dp[n][0],dp[n][1])endl;//最终答案在左移和不动的情况下取max(因为最后一个位置无法右移)
}
