Educational Codeforces Round 137 (Rated for Div. 2)-赛后总结
Educational Codeforces Round 137 (Rated for Div. 2)-赛后总结Educational Codeforces Round 137 (Rated for Div. 2)-赛后总结Educational Codeforces Round 137 (Rated for Div. 2)-赛后总结Educational Codeforces Round 137 (Rated for Div. 2)-赛后总结Educational Codeforces Round 137 (Rated for Div. 2)-赛后总结Educational Codeforces Round 137 (Rated for Div. 2)-赛后总结
总结
一言难尽的一晚，一定要把题目读全面，否则会酿成大祸
习得小技巧是 随机生成数据且禁止HACK的题目，一般暴力就能够通过，也就是本次的D
Problem - A - Codeforces
给定·已经出现的数字，用剩下的数字来两两组合成password，样例1易知两种颜色配对有6种方案，而n种颜色配对就有 (n-1)*n/2的配对方式
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int book[10];
int main()
{
/*
两两组合 n*(n-1)/2*6
*/
int t;
cin>>t;
while(t--)
{
memset(book,0,sizeof(book));
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
book[x]=1;
}
int cnt=0;
for(int i=0;i<=9;i++)
{
if(!book[i])
cnt++;
}
cout<<max(0,(cnt)*(cnt-1)*3)<<endl;
}
return 0;
}Problem - B - Codeforces
给定n,使得构造的n的排列种，<=n的排列最少。易知排列中嵌套排列的情况仅仅出现在 1--m，m个数相邻，首先1是无论如何无法避免，1--n也是如此，剩下的，只要我们拆散1，2，那么一切便都被拆散。 1 。。。。。 2，比如我们想构成 3的排列，就必须先构成 n的排列。
还是比较巧妙的
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int ans[100];
int l=1,r=n;
int now=1;
while(now<=n)
{
ans[l]=now;
l++;
now++;
if(now>n)
break;
ans[r]=now;
r--;
now++;
}
for(int i=1;i<=n;i++)
{
cout<<ans[i]<<" ";
}
cout<<endl;
}
return 0;
}Problem - C - Codeforces
有必要吐槽一下，赛时马虎把盖子的移动方式看成了位置i能移动给全部左面的。也就导致交了一发优先队列的贪心导致白WA一发。正解应该是DP。正着推不太好搞，索性倒着。
dp[i][0] dp[i][1]分别代表本位置是否使用本位置盖子时带来的最大收益。
本位置有盖子的时候，可以自己给自己盖住，也可以依靠前一个盖子没盖住自己时的状态转移
没有盖子的时候，可以不盖，也可以被上一个盖子盖住
细节就是状态转移时注意继承关系
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll dp[200000+10][2];
ll a[200000+10];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string s;
cin>>s;
s=" "+s;
int pos=0;
for(int i=1; i<=n; i++)
{
dp[i][0]=0;
dp[i][1]=0;
cin>>a[i];
if(s[i]=='1')
pos=i;
}
for(int i=pos; i>=1; i--)
{
if(s[i]=='1')
{
if(s[i+1]=='1')
{
dp[i][1]=max(dp[i+1][0],dp[i+1][1])+a[i];
dp[i][0]=max(dp[i+1][1],dp[i+1][0]+a[i]);
}
else
{
dp[i][1]=max(dp[i+1][0],dp[i+1][1])+a[i];
dp[i][0]=max(dp[i+1][0],dp[i+1][1]);
}
}
else
{
if(s[i+1]=='1')
{
dp[i][1]=max(dp[i+1][0],dp[i+1][1]);
dp[i][0]=max(dp[i+1][0]+a[i],dp[i+1][1]);
}
else
{
dp[i][1]=max(dp[i+1][0],dp[i+1][1]);
dp[i][0]=max(dp[i+1][1],dp[i+1][0]);
}
}
}
cout<<max(dp[1][0],dp[1][1])<<endl;
}
return 0;
}Problem - D - Codeforces
D题最为坑人，或许突破点在 “禁止HACK”上面，随机数字且禁止HACK的言外之意就是HACK必定会导致程序出错，也就暗示了我们使用暴力在随机数据的前提下是能够很大概率通过的。
另外一点小思维就是，s1必定选择整个串，s2的选择应该选择第一段连续的1
贪心的想，我们必须要消灭前面的零才能使得答案最优。而如果前导零存在，那么无论如何不会被消去。反之，前导零后面那几个1，所带领的后缀是我们消去之后0的关键。那么第二段，第三段的1呢？根本不用考虑，因为只要有第二段1，就说明了第二段之前是有至少一个0，而我们依靠第二段1引领的后缀永远无法消灭这段0，因为我们是从最后一位开始与原始串进行配对的。
所以仅仅需要考虑第一段1就可以。枚举第一段1中哪个1与第一个零配对，求出来最大即可
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
struct node
{
int pos,cnt;
};
queue<node>q1,q2;
int a[1000000+10];
int main()
{
//先把全部1的位置装填，压入队列，第一个位置能够满足
//的，保留，接下来看第二个位置，保留，直到达到n
int n;
cin>>n;
string s;
cin>>s;
int len=0;
s=" "+s;
string now="";
int pos=0;
for(int i=1;s[i]!='1'&&i<=n;i++)
{
now+=s[i];
pos=i;
}
now="";
int pos2=n+1;
for(int i=pos+1;s[i]=='1'&&i<=n;i++)
{
pos2=i;
now+=s[i];
}
string ans="";
for(int i=pos+1;s[i]=='1'&&i<=n;i++)
{
string temp="";
int fuck=i;
for(int j=pos2+1;j<=n;j++)
{
if(s[fuck]=='1'||s[j]=='1')
temp+="1";
else
temp+="0";
fuck++;
}
ans=max(ans,temp);
}
if(now.size()==0)
{
cout<<0;
return 0;
}
cout<<now+ans<<endl;
return 0;
}