Codeforces Round 960 (Div. 2) A B C
A. Submission Bait
题目
Alice和Bob正在一个大小为 n n n 的数组 a a a 中玩一个游戏。
他们轮流做操作，爱丽丝先开始。不会操作的玩家会输。首先，将变量 m x mx mx 设置为 0 0 0 。
在一个操作中，玩家可以做:
—选择索引 i i i ( 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n )为 a i ≥ m x a_{i} \geq mx ai≥mx ，将 m x mx mx 设置为 a i a_{i} ai 。然后将 a i a_{i} ai 设置为 0 0 0 。
判断Alice是否有制胜策略。
输入* * * *
第一行包含一个整数 t t t ( 1 ≤ t ≤ 1 0 3 1 \leq t \leq 10^3 1≤t≤103 )—测试用例的数量。
对于每个测试用例:
—第一行为整数
n
n
n (
2
≤
n
≤
50
2 \leq n \leq 50
2≤n≤50 )，表示数组的大小。
—第二行包含
n
n
n 个整数
a
1
,
a
2
,
…
,
a
n
a_1, a_2, \ldots, a_n
a1,a2,…,an (
1
≤
a
i
≤
n
1 \leq a_i \leq n
1≤ai≤n )—数组的元素。
-
-
- *输出
-
对于每个测试用例，如果Alice有一个获胜的策略，输出“YES”。否则输出“NO”。
您可以在任何情况下输出答案(上或下)。例如，字符串“yEs”、“yEs”、“yEs”和“yEs”将被识别为积极响应。
AC代码
// 从较大的数开始选择，如果存在较大值为奇数则一定存在制胜策略
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N];
int v[N];
void solve()
{
memset(v,0,sizeof(v));
memset(a,0,sizeof(a));
int n;cin>>n;
vector<int> num;
int sum=0,ma=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
v[a[i]]++; // 统计出现数的次数
if(v[a[i]]==1)
{
num.push_back(a[i]);// 统计出现的数
}
}
sort(num.begin(),num.end());
int t=v[num[num.size()-1]],tt=0;
int f=0;
for(int i=num.size()-1;i>=0;i--)
{
if(v[num[i]]%2==0)f=0;
else
{
f=1;
break;
}
}
if(f==1)cout<<"Yes";
elsecout<<"No";
cout<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);c out.tie(0);
int t;cin>>t;
while(t--)solve();
return 0;
}
B. Array Craft
题目
对于大小为 m m m 的数组 b b b ，定义:
-
b
b
b 的最大前缀位置是满足
b
1
+
…
+
b
i
=
max
j
=
1
m
(
b
1
+
…
+
b
j
)
b_1+\ldots+b_i=\max_{j=1}^{m}(b_1+\ldots+b_j)
b1+…+bi=maxj=1m(b1+…+bj) 的最小索引
i
i
i ;
— b b b 的最大后缀位置是满足 b i + … + b m = max j = 1 m ( b j + … + b m ) b_i+\ldots+b_m=\max_{j=1}^{m}(b_j+\ldots+b_m) bi+…+bm=maxj=1m(bj+…+bm) 的最大索引 i i i 。
给定三个整数 n n n ， x x x 和 y y y ( KaTeX parse error: Expected 'EOF', got '&' at position 3: x &̲gt; y )。构造一个大小为 n n n 的数组 a a a ，满足:
- a i a_i ai 是 1 1 1 或 − 1 -1 −1 对于所有 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n ;
- a a a 的最大前缀位置为 x x x ;
- a a a 的最大后缀位置为 y y y 。
如果有多个符合条件的数组，输出any。可以证明，在给定条件下，这样的数组总是存在的。
输入* * * *
第一行包含一个整数 t t t ( 1 ≤ t ≤ 1 0 4 1 \leq t \leq 10^4 1≤t≤104 )—测试用例的数量。
对于每个测试用例:
—唯一一行包含三个整数 n n n 、 x x x 和 y y y ( 2 ≤ n ≤ 1 0 5 , 1 ≤ y < x ≤ n ) 2 \leq n \leq 10^5, 1 \le y \lt x \le n) 2≤n≤105,1≤y<x≤n) )。
保证所有测试用例的 n n n 之和不超过 1 0 5 10^5 105 。
-
-
- *输出
-
对于每个测试用例，在新行中输出 n n n 空格分隔的整数 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an 。
AC代码
// 令x~y 之间的数为1 ，再从x-1 和 y+1 的位置开始-1,1 交替出现
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N];
int v[N];
void solve()
{
memset(v,0,sizeof(v));
memset(a,0,sizeof(a));
int n,x,y;cin>>n>>x>>y;
for(int i=y;i<=x;i++)a[i]=1;
int f=0;
for(int i=y-1;i>=1;i--)
{
if(f==0)
{
a[i]=-1;
f=1;
}
else
{
a[i]=1;
f=0;
}
}
f=0;
for(int i=x+1;i<=n;i++)
{
if(f==0)
{
a[i]=-1;
f=1;
}
else
{
a[i]=1;
f=0;
}
}
for(int i=1;i<=n;i++)
{
cout<<a[i]<<' ';
}
cout<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--)solve();
return 0;
}
C. Mad MAD Sum
题目
我们将数组中的 MAD \operatorname{MAD} MAD (Maximum appear Duplicate)定义为在数组中至少出现两次的最大数字。具体来说，如果没有数字至少出现两次，则 MAD \operatorname{MAD} MAD 值为 0 0 0 。
例如， MAD ( [ 1 , 2 , 1 ] ) = 1 \operatorname{MAD}([1, 2, 1]) = 1 MAD([1,2,1])=1 ， MAD ( [ 2 , 2 , 3 , 3 ] ) = 3 \operatorname{MAD}([2, 2, 3, 3]) = 3 MAD([2,2,3,3])=3 ， MAD ( [ 1 , 2 , 3 , 4 ] ) = 0 \operatorname{MAD}([1, 2, 3, 4]) = 0 MAD([1,2,3,4])=0 。
给定一个大小为 n n n 的数组 a a a 。最初，变量 s u m sum sum 被设置为 0 0 0 。
下面的过程将在一个顺序循环中执行，直到 a a a 中的所有数字都变成 0 0 0 :
- s u m : = s u m + ∑ i = 1 n a i sum := sum + \sum_{i=1}^{n} a_i sum:=sum+∑i=1nai ;
- 设 b b b 为大小为 n n n 的数组。为所有 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n 设置 b i : = MAD ( [ a 1 , a 2 , … , a i ] ) b_i :=\ \operatorname{MAD}([a_1, a_2, \ldots, a_i]) bi:= MAD([a1,a2,…,ai]) ，然后为所有 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n 设置 a i : = b i a_i := b_i ai:=bi 。
处理结束后，查找 s u m sum sum 的值。
输入* * * *
第一行包含一个整数 t t t ( 1 ≤ t ≤ 2 ⋅ 1 0 4 1 \leq t \leq 2 \cdot 10^4 1≤t≤2⋅104 )—测试用例的数量。
对于每个测试用例:
—第一行包含一个整数
n
n
n (
1
≤
n
≤
2
⋅
1
0
5
1 \leq n \leq 2 \cdot 10^5
1≤n≤2⋅105 )—数组的大小
a
a
a ;
—第二行包含
n
n
n 个整数
a
1
,
a
2
,
…
,
a
n
a_1, a_2, \ldots, a_n
a1,a2,…,an (
1
≤
a
i
≤
n
1 \leq a_i \leq n
1≤ai≤n )——数组的元素。
保证所有测试用例的 n n n 之和不超过 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105 。
-
-
- *输出
-
对于每个测试用例，在新的一行中输出 s u m sum sum 的值。
AC代码
// 操作两次后必然出现 数列 前 2 位为 0；此后为 数组的后移
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int a[N];
int v[N];
void solve()
{
int n;cin>>n;
vector<int> a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
int ans=0;
for(int j=1;j<=2;j++)
{
map<int,int>mp;
int ma=0;
for(int i=1;i<=n;i++)
{
ans+=a[i];
mp[a[i]]++;
if(mp[a[i]]>1)ma=max(a[i],ma);
a[i]=ma;
}
}
for(int i=1;i<=n;i++)
{
ans+=a[i]*(n-i+1);
}
cout<<ans;
cout<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--)solve();
return 0;
}
原文地址：https://blog.csdn.net/2302_80423900/article/details/140583366
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！