比赛链接：Dashboard - Codeforces Round 939 (Div. 2) - Codeforces
A
签到题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int k,q;
cin>>k>>q;
int x;
cin>>x;
for(int i=1;i<k;i++)
{
int y;
cin>>y;
}
for(int i=1;i<=q;i++)
{
int p;
cin>>p;
if(p<x)cout<<p<<" ";
else cout<<x-1<<" ";
}
cout<<endl;
}
return 0;
}
|
B
签到题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[n+1]={0};
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a[x]++;
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(a[i]==2)ans++;
}
cout<<ans<<endl;
}
}
|
C
题意：有一个 $n\times n$ 的方格，每次执行以下操作中的一种：
- 选择一行，并将 $1-n$ 的一个排列填入。
- 选择一列，并将 $1-n$ 的一个排列填入。
最多操作 $2n$ 次，求方格所有数的和的最大值。
构造出最大的方案是如下：
4 4 4 4
3 3 3 4
2 2 3 4
1 2 3 4
可以通过如下方式构造：第一行填1 2 3 4，第四列填4 3 2 1；第二行填1 2 3 4，第三列填4 3 2 1……
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<bits/stdc++.h>
using namespace std;
#define LL long long
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
LL ans=0;
for(int i=1;i<=n;i++)ans+=1LL*i*(2*i-1);
cout<<ans<<" "<<2*n<<endl;
for(int i=1;i<=n;i++)
{
cout<<"1 "<<i<<" ";
for(int j=1;j<=n;j++)cout<<j<<" ";
cout<<endl;
cout<<"2 "<<n-i+1<<" ";
for(int j=n;j>=1;j--)cout<<j<<" ";
cout<<endl;
}
}
return 0;
}
|
D
题意：给定一个长为 $n$ 的数组 $a$ ，现可以执行以下操作不超过 $5e5$ 次：选择 $l,r$ ，并将 $a_l,…,a_r$ 替换为 $MEX{a_l,a_{l+1},…,a_r}$ 。给出操作序列并求 $a$ 所有元素和的最大值。$m\leq 18$
注意到对于一个长为 $len$ 的数组，可以将其每个元素都变成 $len$ ，因此得到的最大的和为 $len^2$ 。首先求出最大值，即求出分界点，那些元素全部变成 $len$ 。注意到 $n$ 非常小，直接暴力枚举 $2^{18}$ 个分界点即可。
接下来求操作方案：要将长为 $len$ 的数组全变成 $len$ ，首先要将其变零，然后分别将 $a[len-1]$ 变成 $len-1$ ，将 $a[len-2]$ 变成 $len-2$，……整个是个递归的过程，通过递归实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int mask=1<<18+5;
int n;
int a[200];
int pos[300],tot;
int rpos[200],rtot;
pair<int,int>t[500010];
int cnt;
int cal(int msk)
{
int ans=0;
tot=0;
for(int i=0;i<n;i++)
{
if(msk & (1<<i))pos[++tot]=i+1;
}
for(int i=1;i<=tot;i++)ans+=(pos[i]-pos[i-1]-1)*(pos[i]-pos[i-1]-1)+a[pos[i]];
ans+=(n-pos[tot])*(n-pos[tot]);
return ans;
}
void print(int l,int r,bool is0)
{
if(!is0)
{
cnt++;
t[cnt].first=l;
t[cnt].second=r;
}
if(l==r)
{
cnt++;
t[cnt].first=l;
t[cnt].second=r;
return;
}
for(int i=r-1;i>=l;i--)print(l,i,i==r-1);
cnt++;
t[cnt].first=l;
t[cnt].second=r;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int maxx=0;
for(int msk=0;msk<mask;msk++)
{
int t=cal(msk);
if(maxx<t)
{
maxx=max(maxx,t);
rtot=tot;
for(int i=1;i<=tot;i++)rpos[i]=pos[i];
}
}
cout<<maxx<<" ";
for(int i=1;i<=rtot;i++)
{
int l=rpos[i-1]+1,r=rpos[i]-1;
if(l>r)continue;
for(int i=l;i<=r;i++)
{
if(a[i]!=0)
{
cnt++;
t[cnt].first=i;
t[cnt].second=i;
}
}
print(l,r,1);
}
for(int i=rpos[rtot]+1;i<=n;i++)
{
if(a[i]!=0)
{
cnt++;
t[cnt].first=i;
t[cnt].second=i;
}
}
int l=rpos[rtot]+1,r=n;
if(l<=r)
{
print(rpos[rtot]+1,n,1);
}
cout<<cnt<<endl;
for(int i=1;i<=cnt;i++)
{
cout<<t[i].first<<" "<<t[i].second<<endl;
}
return 0;
}
|
E
题意：有 $n$ 个怪兽围成一圈，每个怪兽的攻击力 $a_i$ 与其初始生命值相等，从第一个怪物开始依次攻击下一个怪兽。求无限次后剩下的怪兽的下标。$a_i\leq 2e5$
当某一个怪兽死之后，这个怪兽将相当于分界线了。考虑分界线后的第一个怪兽，这个怪兽不会被攻击，可以无限次攻击以后的怪兽，因此这个怪兽的下一个怪兽必死，因此若在某一时刻分界线之间只有2个怪兽，那么就可以直接确定哪些怪兽能存活。设三个相邻怪兽分别是 $a_1,a_2,a_3$ ，且 $a_1=1,a_3=200000$ ，可得要使 $a_3$ 死亡的最大次数是 $\sqrt{200000}$ 。因此直接暴力枚举 $\sqrt{200000}$ 次，然后统计还活着的第一个的下标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int T,n,a[maxn];
int main()
{
cin>>T;
while(T--)
{
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
for(int rd=1;rd<=700;rd++)
{
for(int i=0;i<n;i++)
{
a[(i+1)%n]=max(0,a[(i+1)%n]-a[i]);
}
}
for(int i=0;i<n;i++)
{
if(a[i]>0 && a[(i+1)%n]>0)a[(i+1)%n]=0;
}
vector<int> ans;
for(int i=0;i<n;i++)
{
if(a[i]>0)ans.push_back(i+1);
}
cout<<ans.size()<<endl;
for(auto x:ans)cout<<x<<" ";
cout<<endl;
}
return 0;
}
|
微信
支付宝
