比赛链接：Dashboard - Educational Codeforces Round 164 (Rated for Div. 2) - Codeforces
A
签到题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m,k;
cin>>n>>m>>k;
if(n/m*(m-1)+max(n%m-1,0)>k)cout<<"YES\n";
else cout<<"NO\n";
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
int a[n+5];
for(int i=1;i<=n;i++)cin>>a[i];
if(a[1]!=a[n])
{
cout<<"0\n";
return;
}
int st=a[1];
int ans=3e5+5;
int cnt=0;
for(int i=1;i<=n;i++)
{
if(a[i]==st)cnt++;
else
{
if(cnt==0)
{
cout<<"0\n";
return;
}
ans=min(ans,cnt);
cnt=0;
}
}
ans=min(ans,cnt);
if(ans>=n)cout<<"-1\n";
else cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)solve();
return 0;
}
|
C
题意：给出两个长度相等的数 ，可以交换相同数位上的数，最后要使得 最大。
注意到 是一个定值，要使 最大，那么就要使 尽可能接近。假设 ，那么从高位枚举，使 某一位上的数比 相同位小即可。
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
| #include<bits/stdc++.h>
using namespace std;
void solve()
{
string x,y;
cin>>x>>y;
int s;
int len=x.length();
int pos=-1;
for(int i=0;i<len;i++)
{
if(x[i]==y[i])continue;
s=x[i]>y[i];
pos=i;
break;
}
if(pos==-1)
{
cout<<x<<endl<<y<<endl;
return ;
}
for(int i=pos+1;i<len;i++)
{
if(s==1)
{
if(x[i]>y[i])swap(x[i],y[i]);
}
else
{
if(x[i]<y[i])swap(x[i],y[i]);
}
}
cout<<x<<endl<<y<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)solve();
return 0;
}
|
D
题意：有 种不同的颜色，每种颜色的球有 个。现在选某几种颜色的所有球视为一类，那么共有 类，并将其分组，分组规则如下：每一组不超过两个球，且不能有相同颜色的球，且要使分的组数尽可能少。求所有类的分组的个数的总和。
考虑对于某一类，如何分组最优。假设数量最多的球的个数是 ，总和是 。
- 若 ，那么组数就是就是 。具体方法为每一个 配一个其他颜色的球。
- 若 ，那么组数就是 。
因此可以采用如下方法进行统计：利用背包现将所有组合按照 进行统计，然后再补偿 的情况。
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int a[5005];
int dp[5005];
signed main()
{
int n;
cin>>n;
int sum=0;
int ans=0;
for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=sum;j>=a[i];j--)
{
dp[j]=(dp[j]+dp[j-a[i]])%mod;
}
}
for(int i=1;i<=sum;i++)
{
ans=(ans+(i+1)/2*dp[i]%mod)%mod;
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<a[i];j++)
{
ans=(ans+(a[i]-(j+a[i]+1)/2)*dp[j]%mod)%mod;
}
}
cout<<ans;
return 0;
}
|
E
题意：有 个怪兽，每个怪兽的生命值是 。通过连锁反应进行攻击：每次选择一个没死的怪兽作为攻击起点，对其进行 点攻击，然后攻击朝左边和右边扩散，都造成 点攻击，直到遇到一个已经死亡的怪兽才停下来。对于 ，分别求出最少杀死所有怪物的施法次数。
考虑 的情况，可以发现攻击的次数即为 。可以考虑将其转换成一个至于本身有关的多项式，即转化为 。关于系数 ，可以有如下方式确定：初始 ，若 ， ，若 ， 。
对于 的情况，只需将 变成 即可。
关于统计答案对于某一个 ，可以观察到 是根据 分段的，即按照以下方式统计：
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
| #include<bits/stdc++.h>
using namespace std;
#define LL long long
int main()
{
int n;
cin>>n;
int a[n+2];
int mx=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
mx=max(mx,a[i]);
}
int ad[mx+1]={0};
for(int i=1;i<=n;i++)
{
int c=0;
if(i==1 || a[i]>a[i-1])c++;
if(i<n && a[i]<a[i+1])c--;
ad[a[i]]+=c;
}
for(int i=1;i<mx;i++)ad[i+1]+=ad[i];
for(int k=1;k<=mx;k++)
{
LL ans=0;
for(int val=1,l=1;l<=mx;l+=k,val++)
{
ans+=1LL*val*(ad[min(l+k-1,mx)]-ad[l-1]);
}
cout<<ans<<" ";
}
return 0;
}
|
微信
支付宝
