CodeForces747 解题报告

写在最前

因为本人太菜,所以F题目前尚不会,有空补上解题报告23333

思路

A

暴力枚举一下n的每个因数就好辣

B

显然ACGT每个字母出现的次数都是n/4次,然后算一算依次填就好了

C

考虑到只有100个机器,我们每次循环暴力模拟一下就好了23333

D

这题写了我一会会=。=

首先所有温度为负数的天一定要用冬天专用轮胎,先扣除掉,也是有无解的唯一判据。

然后剩下的冬天轮胎使用天数我们就可以开始浪了。

我们先假设一旦发生温度的负数和非负两个状态的切换时我们同样换轮胎,得到了一个换胎次数。

下面我们考虑怎么去节约。

将连续的温度非负的天数放在一组,输出每组有几天。

这样的组分为三种,我们分别考虑(不一定都存在)

两边都是温度为负的,被覆盖时贡献为2

左边为负数,右边直接到头的,贡献为1

右边为负数,左边是开始的,贡献为0

显然我们贪心地先覆盖两边温度都为负的情况,然后第二种情况能覆盖就覆盖就好了。

没覆盖掉一段,在原来的换胎次数上减去区间的贡献,就做完辣

E

这题就比较简单了,字符串处理的模拟题

我们先将每一段评论和其后面的数字分离,然后组对保存下来

然后采取类似DFS,或者手动栈的实现,去保存一下每一段评论属于第几层,最后分层输出就好了。

详见代码

代码

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n,i,j;
int ans,x,y;

int main()
{
int ans=1000000;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
if(n%i!=0)continue;
if(i>n/i)break;
if(n/i-i<ans){x=i;y=n/i;ans=y-x;}
}
printf("%d %d",x,y);
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
char s[300];
map<char,int> m;
int i,n;

int main()
{
scanf("%d\n",&n);
gets(s+1);
for(i=1;i<=n;i++)m[s[i]]++;
if(n%4!=0){printf("===");return 0;}
if(m['A']>n/4 || m['C']>n/4 || m['G']>n/4 || m['T']>n/4){printf("===");return 0;}
for(i=1;i<=n;i++)
{
if(s[i]!='?')continue;
if(m['A']<n/4){s[i]='A';m['A']++;continue;}
if(m['C']<n/4){s[i]='C';m['C']++;continue;}
if(m['G']<n/4){s[i]='G';m['G']++;continue;}
if(m['T']<n/4){s[i]='T';m['T']++;continue;}
}
printf("%s",s+1);
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
int a[105];
int i,j,k,t,d,n,m;
int sum;

int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)a[i]=1;
while(m--)
{
scanf("%d%d%d",&t,&k,&d);
j=0;sum=0;
for(i=1;i<=n;i++)if(a[i]<=t)j++;
if(j<k){printf("-1\n");continue;}
for(i=1;i<=n;i++)
{
if(a[i]>t)continue;
a[i]=t+d;sum+=i;k--;
if(k<=0)break;
}
printf("%d\n",sum);
}
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
42
43
int i,j,k,l,r,m,n,ans,tot;
int a[200005],b[200005];

int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]<0)j++;
}
if(j>m){printf("-1");return 0;}
m-=j;
l=r=0;
for(i=1;i<=n;i++)
if(a[i]>=0)l++;else break;
for(i=n;i>=max(l,1);i--)
if(a[i]>=0)r++;else break;
if(l+r>=n){printf("0");return 0;}
for(i=l+1,j=k=0;i<=n-r;i++)
{
if(a[i]>=0 && j<=0){j=i;continue;}
if(a[i]<0 && j>0)
{
b[++k]=i-j;
j=0;
}
}
for(j=0,i=1;i<=n;i++)
{
if(j==0 && a[i]<0){ans++;j=1;}
if(j==1 && a[i]>=0){ans++;j=0;}
}
sort(b+1,b+k+1);
for(i=1;i<=k;i++)
{
if(m<b[i])break;
m-=b[i];ans-=2;
}
if(m>=r && r>0){m-=r;ans--;}
printf("%d",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
39
40
41
42
43
char is[1000005];
string s;
vector<string> g[500005];
int a[500005],t[500005];
string st[500005];
int i,j,k,l,m,n,ans;

int main()
{
gets(is);n=strlen(is);l=1;s="";m=0;
is[n]=',';k=0;
for(i=0;i<=n;i++)
{
if((is[i]>='A' && is[i]<='Z') || (is[i]>='a' && is[i]<='z')){s+=is[i];continue;}
if(is[i]>='0' && is[i]<='9'){m=m*10+is[i]-48;continue;}
if(l<=1){l++;continue;}
if(l>=2)
{
st[++k]=s;s="";
a[k]=m;m=0;
l=1;
}
}
l=1;ans=1;t[1]=5000000;
for(i=1;i<=k;i++)
{
g[l].push_back(st[i]);
ans=max(ans,l);t[l]--;
if(a[i]>0)t[++l]=a[i];
while(t[l]==0)l--;
}
printf("%d\n",ans);
for(i=1;i<=ans;i++)
{
for(j=0;j<g[i].size();j++)
{
if(j>0)cout<<' ';
cout<<g[i][j];
}
cout<<endl;
}
return 0;
}