开福区网站建设中,网站制作和美工,网页版梦幻西游五色石组合,seo教程培训A题意#xff1a; N 长的数组。 一次操作#xff1a; 最开始的mx 为零。 选出一个数#xff08;使得这个数mx) ,之后将mx 更新为这个数#xff0c;将这个数置为零。 不能做这个操作的#xff0c;输。 问是否有先手赢的策略。有的话#xff0c;输出yes 否则no
当时一…A题意 N 长的数组。 一次操作 最开始的mx 为零。 选出一个数使得这个数mx) ,之后将mx 更新为这个数将这个数置为零。 不能做这个操作的输。 问是否有先手赢的策略。有的话输出yes 否则no
当时一眼就能看出来肯定是和最大值的奇偶性有关系。 当时的想法就是 最大值的奇偶性。奇数 那么就存在。偶数不存在。 但是不对。 因为先手可以决定哪个数 是可操作的最大数。 例如 3 3 3 3 2 2 2 1 1 1 这个时候如果先手选3 那么先手输。但是如果先手选2 那么先手赢。 所以我们要统计每一个数的个数。只有每个数的个数都是 偶数那么先手才输
感觉博弈论 要考虑操作会改变什么性质考虑先手的操作可以决定什么。
#include bits/stdc.h
using namespace std;void solve()
{int n;cinn;mapint,intmp;int t;for (int i0;in;i){cint;mp[t];}bool flagfalse;//反向迭代器for (auto itmp.rbegin();it!mp.rend();it){if (it-second 1){flag1;break;}}if (flag)coutYES\n;else coutNO\n;
}
int main()
{std::cin.tie(nullptr)-sync_with_stdio(false);int t; cint;while(t--){solve();}return 0;
}B题 长度为m 的数组 b 。 我们定义了 最大的前缀位置X 位置最靠前的index i 最大的后缀位置Y 位置最靠后的index i XY 其实也就是 包含的元素最少。
输出构造出m 长的数组
简单的思考一下为了确保X Y 是最大的前缀和后缀位置。从Y到 X的位置全填1. 同时Y左侧的位置 和 X 右侧的位置一定是-1. 现在来考虑两侧的位置有三种情况可以填一种是全填-1 一种是全填1一种是 1 -1 交替填 如果全填1 的话那么只要前面的1大于2Y的位置会变。 如果全填-1的话那么可能Y X之间的1比较少前缀的最大值是-1.那么X的位置就会变。 如果1 -1 交替填可以减小前面数字的影响。从而保证 XY的正确性。
#include bits/stdc.h
using namespace std;void solve()
{int n ,x,y;cinnxy;vectorintve(n1);int t-1;for (int iy-1;i1;i--){ve[i]t;t-t;}for (int iy;ix;i)ve[i]1;t-1;for (int ix1;in;i){ve[i]t;t-t;}for (int i1;in;i)coutve[i] ;cout\n;}
int main()
{std::cin.tie(nullptr)-sync_with_stdio(false);int t; cint;while(t--){solve();}return 0;
}C题 定义了mcd的行为 重新定义了最大值的定义只有出现大于等于两次的数才能被称为最大值。 n a1 a2 a3 a4 ……an 定义b 数组bi 的值 是a 数组长为i 的前缀 mcd值。 理解了定义其实就可以水到渠成的发现b 数组是单调不增的这很显然毕竟我们求的是前缀的最大值虽然这个最大值指的是出现两次及以上的数字。 之后将 a 数组 更新为 b 数组。 这样不断的迭代。直到a数组全变为0 sum 是每一个a 数组元素的和。 问sum 值。
对于这种问题一定是有一些规律在的。一般不会是很难的会比较明显的。 这个时候就要 模拟。自己去找规律。一定要去思考啊 我也感觉出来了我十分不擅长 和数学相关的思维题。找规律的一些题我都很难做出来或者做不出来。碰到这种题就不想做了qaq。希望能通过接下来的练习弥补这一块。提高一下自己签到的能力 一方面 可能和我数学素养有点关系但感觉更多的还是练的少思考的少。 我们可以自己整一个长一点的例子。 55551324666778534434 05555555566677777777 00555555556667777777 00055555555666777777 我们可以发现在操作依次之后以后的每一次都是在前面添一个零最后面的一个数出去了。 这样我们可以先做一下猜想 我们将数组处理遍之后可以根据处理后的数组。算每一个数的贡献。大概就是n-i 。可能哟个加一自己看看一下就行。 但是我们发现样例中 4 2 1 1 2 0 0 1 2变换一次之后 0 0 0 0 我们发现 根据我们之前的猜想 1 应该贡献两次但是其实只贡献了一次。之前找的规律大概没错。那么我们可以处理两次。再使用规律。又见识到了qaq
#include bits/stdc.h
using namespace std;
#define int long long
void solve()
{int n;cinn;int ans0;vectorinta(n1);for (int i1;in;i)cina[i],ansa[i];for(int k0;k2;k){int mx0;//代表在 mad 情况下的 最大值mapint,intmp;for (int i1;in;i){mp[a[i]];if (a[i]mxmp[a[i]]2)mxa[i];a[i]mx;ansa[i];}}for (int i1;in;i){if (a[i])ansa[i]*(n-i);}coutans\n;}
signed main()
{std::cin.tie(nullptr)-sync_with_stdio(false);int t; cint;while(t--){solve();}return 0;
}
