Codeforces Round #765 (Div. 2)A，B，C
昨天晚上打了个牛客小白月赛，今天来补昨天的vp
真是丢大脸了，竟然爆零了，我真是太菜了，o(╥﹏╥)o
A
这个A题老长了，说了半天的废话，看了半天都没看懂，后来看懂了，想用bitset，发现我自己根本不会用
以后如果需要问一个数的第几位是1还是0（变成二进制的）,我觉得可以这样用
for (int i=0;i<32;i++)
{
if ((tmp<<i)&1)//这代表着tmp的二进制第i位是1，否则是0
}
对于bitset,我觉得好用的是它可以修改任意位的值，还有可以通过字符串来赋值
bitset<4> foo (string("1001"));//通过字符串直接赋值
bitset<n> b(unsigned long u);//b有n位,并用u赋值;如果u超过n位,则顶端被截除,如:bitset<5>b0(5);则"b0"为"00101";
bitset<11> b2(bitval2);
cout<<b2<<"is "<<b2.to_ulong()<<endl;//变成整型（十进制）输出，而不是以二进制的形式
而这一道题就是需要我们给我们的数字的二进制的0到l位0的数量多，ans的那一位就是0，否则就是1，最后求出答案
#include <iostream>
using namespace std;
int t,n,l;
void solve()
{
cin>>n>>l;
int cnt[32]={0};
for (int i=1;i<=n;i++)
{
int tmp;
cin>>tmp;
for (int j=0;j<=l-1;j++)
{
if ((tmp>>j)&1)
{
cnt[j]++;
}
}
}
int ans=0;
for (int i=0;i<=l+1;i++)
{
if (cnt[i]>(n-cnt[i]))
{
ans+=(1<<i);
}
}
cout<<ans<<'\n';
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
B
这一道题大意是在一个数组里找到一个类似下面的的两个子串
1 3 4 5
2 3 5 7
这两个子串只要存在一个位置存在一个数是一样的即可，问我们可以获得的子串最长长度是多少
对于一个数组
1 3 4 6 3 7 8//这一个数组，最长的可能是3前面有1位，那么这个位置就是第二位，第二个3后面有2位，那么3也是倒数第三位，那么此时最长的长度为1+2+1（前面的数量+后面的数量+本身），可以发现规律是
ans=(l-1)+(n-r)+1=n-(r-l)//l是左边的那一个位置，r是右边的位置，r-l越小，则答案越大，那么这两个一样的一定是相邻的
#include <iostream>
#include <stdlib.h>
#include <map>
using namespace std;
const int maxn=3e5+10;
int n,t,a[maxn];
void solve()
{
cin>>n;
map<int,int>l;
int ans=-1;
for (int i=1;i<=n;i++)
{
cin>>a[i];
if (l[a[i]])
{
//cout<<l[a[i]]<<" "<<i<<'\n';
ans=max(ans,n-(i-l[a[i]]));
}
l[a[i]]=i;
}
cout<<ans<<'\n';
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
C
题大意是有一段路，每个位置都会有一个速度，输入n个位置，n的速度，第一个位置是0，需要走到l
如
位置 0 2 5 7 10
速度1 3 2 3
需要时间是 1X2+3X2+2X2+3X3
我们可以拆除最多k个牌子，问我们最后可以最快到达l的时间是多少
我先前以为是一个贪心问题，后来发现不对劲，后面才知道正解是dp
详见代码
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=500+10;
int n,l,k;
int dp[maxn][maxn];//dp[i][j]是第0块牌子到i-1块牌子，有j块牌子被拆除了，第i 块牌子被留下来，方便进行更新，那么后面的一定是b[i]的速度
int a[maxn],b[maxn];
int main ()
{
cin>>n>>l>>k;
for (int i=1;i<=n;i++)
{
cin>>a[i];
}
a[n+1]=l;
for (int i=1;i<=n;i++)
{
cin>>b[i];
}
for (int i=0;i<=n+1;i++)
{
for (int j=0;j<=k+1;j++)
{
dp[i][j]=1e9;
}
}
dp[1][0]=0;//dp[i][j]代表着0到i个牌子里，i个牌子不拆除，0到i-1有j个牌子拆除时到达i的最快时间,因为在到达i位置的一路，第i个牌子没有起到作用
for (int i=2;i<=n+1;i++)//第i个牌子没有拆
{
dp[i][0]=dp[i-1][0]+(a[i]-a[i-1])*b[i-1];
for (int j=1;j<=k;j++)//列举拆除的牌子数量
{
for (int h=1;h<i;h++)//
//0到i有j个，h到i总共有（i-h+1)个，而0到i的j个不包括i,0到h也不包括h，那么只有h+1到i-1都是拆除的状态了，(i-1)-(h+1)+1=i-j-1个了，
//故0到h有这么多个，是0到i有j个拆除的的上一级
{
if (j-(i-h-1)<0||j-(i-h-1)>=h) continue;//数量需要满足条件
dp[i][j]=min(dp[i][j],dp[h][j-(i-h-1)]+(a[i]-a[h])*b[h]);
}
}
}
int ans=dp[n+1][0];//一个牌子都不拆的情况
for (int i=1;i<=k;i++)
{
ans=min(ans,dp[n+1][i]);
}
cout<<ans<<'\n';
system ("pause");
return 0;
}