手机版电子商务网站开发,网站系统管理计划,湘潭网站建设工作室,做网站文字字号大小A. Submission Bait#xff08;博弈#xff09;
题意#xff1a;爱丽丝和鲍勃在大小为n的数组a中进行游戏#xff0c;他们轮流进行运算#xff0c;爱丽丝先开始#xff0c;不能运算的一方输#xff0c;一开始mx0#xff0c;每次操作#xff0c;玩家可以选择一个牵引i…A. Submission Bait博弈
题意爱丽丝和鲍勃在大小为n的数组a中进行游戏他们轮流进行运算爱丽丝先开始不能运算的一方输一开始mx0每次操作玩家可以选择一个牵引iaimxmx设置为aiai设为0.判断爱丽丝是否有一个获胜策略。
分析只要一个数出现奇数个那么爱丽丝就可以先手拿走那出现奇数个的数的最大值从这个数到数组最大值都是剩下偶数个无论鲍勃怎么拿爱丽丝都能取走最后一个并获得胜利。
代码
#includebits/stdc.h
using namespace std;
int main(){int t; cint;while(t--){int n; cinn;mapint,intmp;for(int i1;in;i){int x;cinx;mp[x];}int cnt1;for(auto x:mp){if(x.second%21){cnt0;break;}}if(!cnt)coutYESendl;else coutNOendl;}return 0;
}
B. Array Craft构造贪心
题意对于长度为m的数组b可以定义(j为数组任意下标)
b的最大前缀位置是b1...bimax(b1...bj)的最小牵引i
b的最大后缀位置是bi....bmmax(bj...bm)的最大牵引i
现在给三个整数nxy构造一个数组满足
对于所有1inai要么是1要么是-1
a的最大前缀位置是xa的最大后缀位置是y。
分析因为yx,可以分成三部分,[1,y-1],[y,x],[x1,n]可以让第一部分等于-1这样不会对后缀和最大值有影响第三部分等于-1这样不会对前缀和产生影响让中间部分都等于1.
代码
#includebits/stdc.h
using namespace std;
void sol(){int n,x,y;cinnxy;for(int i1;in;i){int a;if(iy)a(y-i)%20?1:-1;else if(ix)a1;else a(i-x1)%20?-1:1;couta ;}coutendl;
}
int main(){int t;cint;while(t--)sol();return 0;
}
C. Mad MAD Sum贪心
题意定义MAD为数组中至少出现两次的最大数字如果没有就是0.给定一个长度为n的数组asum0下面的过程将依次循环执行直到a中的所有数字都变成0
设置sum∑ai设biMADa1,a2..ai),aibi
求过程结束后sum的值。
分析经历操作一次后的数组是非递减的以后每次都是将数组向右移动为了防止数组从左往右不含0的第一个数字在数组里只出现1此我们可以再执行一次操作所以只要执行两次操作就能知道剩下的操作次数。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N2e510;
bool c[N];
ll n,a[N];
void g(){for(ll i1;in;i)c[i]false;ll ma0;for(ll i1;in;i){if(c[a[i]])mamax(ma,a[i]);c[a[i]]true;a[i]ma;}
}
void sol(){cinn;ll ans0;for(int i1;in;i){cina[i];ansa[i];}g();for(ll i1;in;i)ansa[i];g();for(ll i1;in;i){ans(n-i1)*a[i];}coutansendl;
}
int main(){int t;cint;while(t--)sol();return 0;
}
D. Grid Puzzle
题意给定一个数组有一个nn的网格。在第i行从第一个到第ai个都是黑格子剩下的是白格子。可以进行以下操作将2×2子网格染白将整行染白。找出将所有单元格染白的最少操作次数。 分析如果ai5我们会想使用操作2因为至少需要三个2×2的子网覆盖它第i-1和i1行不一定是黑格子所以有可能浪费了。先考虑ai4的情况。
只右三种情况不受上一行影响涂前两格涂后两格。
代码贪心
#includebits/stdc.h
using namespace std;
typedef long long ll;
void sol(){int n;cinn;int a[n10];for(int i1;in;i)cina[i];bool b10,b20;ll ans0;for(int i1;in;i){if((!b1)(!b2)){if(a[i]0)continue;ans;if(a[i]2)b11;}else if(b1){b10;if(a[i]2)continue;ans;if(a[i]4)b21;}else{b20;if(a[i]0)continue;ans;if(a[i]4)b11;}}coutansendl;
}
int main(){int t;cint;while(t--)sol();return 0;
}
dp
#includebits/stdc.h
using namespace std;
const int N2e510;
int a[N],dp[N];
void sol(){int n;cinn;int b[2]{N,N};for(int i1;in;i)cina[i];//b0Nb1N就是对下一行无影响for(int i1;in;i){dp[i]dp[i-1]1;if(a[i]0)dp[i]min(dp[i],dp[i-1]);if(a[i]2)dp[i]min(dp[i],ib[1-i%2]);//上一个位置在奇数现在在偶数就可以减去1.反之一偶一奇也可以if(a[i]2)b[i%2]min(b[i%2],dp[i-1]-i);else if(a[i]4)b[0]b[1]N;}coutdp[n]endl;
}
int main(){int t;cint;while(t--)sol();return 0;
}
