当前位置：首页 > news >正文

每日一题~960 div2 A+B+C(简单奇偶博弈，构造，观察性质算贡献)

news 来源：原创 2024/9/20 7:01:28

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;cin>>n;map<int,int>mp;int t;for (int i=0;i<n;i++){cin>>t;mp[t]++;}bool flag=false;//反向迭代器for (auto it=mp.rbegin();it!=mp.rend();++it){if (it->second &1){flag=1;break;}}if (flag)cout<<"YES\n";else cout<<"NO\n";
}
int  main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t; cin>>t;while(t--){solve();}return 0;
}

B题：
长度为m 的数组 b 。
我们定义了
最大的前缀位置X 位置最靠前的index i
最大的后缀位置Y 位置最靠后的index i
X>Y
其实也就是包含的元素最少。

输出构造出m 长的数组

简单的思考一下：为了确保X Y 是最大的前缀和后缀位置。从Y到 X的位置，全填1.
同时Y左侧的位置和 X 右侧的位置一定是-1.
现在来考虑两侧的位置，有三种情况可以填，一种是全填-1 ，一种是全填1，一种是 1 -1 交替填，
如果全填1 的话，那么只要前面的1大于2，Y的位置会变。
如果全填-1的话，那么可能Y X之间的1比较少，前缀的最大值是-1.那么X的位置就会变。
如果+1 -1 交替填，可以减小前面数字的影响。从而保证 XY的正确性。

#include <bits/stdc++.h>
using namespace std;void solve()
{int n ,x,y;cin>>n>>x>>y;vector<int>ve(n+1);int t=-1;for (int i=y-1;i>=1;i--){ve[i]=t;t=-t;}for (int i=y;i<=x;i++)ve[i]=1;t=-1;for (int i=x+1;i<=n;i++){ve[i]=t;t=-t;}for (int i=1;i<=n;i++)cout<<ve[i]<<" ";cout<<"\n";}
int  main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t; cin>>t;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;cin>>n;int ans=0;vector<int>a(n+1);for (int i=1;i<=n;i++)cin>>a[i],ans+=a[i];for(int k=0;k<2;k++){int mx=0;//代表在 mad 情况下的 最大值map<int,int>mp;for (int i=1;i<=n;i++){mp[a[i]]++;if (a[i]>mx&&mp[a[i]]>=2)mx=a[i];a[i]=mx;ans+=a[i];}}for (int i=1;i<=n;i++){if (a[i])ans+=a[i]*(n-i);}cout<<ans<<'\n';}
signed  main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t; cin>>t;while(t--){solve();}return 0;
}