Codeforces Round #558 (Div. 2)

佚名 6年前 (2019-05-10) 随笔 501人围观抢沙发百度已收录

签到，然而手残WA了一发，不过加上50分名次不变。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    m=n-m;
    if(m==n)printf("1");
    else if(m<=n/2)printf("%d",m);
    else printf("%d",n-m);
}

View Code

设前i个位置存在m种颜色，显然只有以下几种情况：1、所有颜色出现1次。2、出现最多的颜色有1种，出现次多的颜色出现次数为出现最多颜色出现次数-1，且有(m-1)种。3、出现最多的颜色种类有(m-1)种，且剩余一种颜色仅出现1次。然后维护mx的值，即为出现最多颜色出现次数，随便判一下就好了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int n,m,ans,mx,a[N],b[N],c[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        int col=a[i];
        if(b[col])c[b[col]]--;else m++;
        c[++b[col]]++;
        if(b[col]>mx)mx=b[col];
        if(m==1||mx==1||c[mx]==m-1&&c[1]==1||c[mx-1]==m-1&&c[mx]==1)ans=i;
    }
    printf("%d",ans);
}

View Code

可以O(n^2)枚举两两点对间的直线，记录k和b，即y=kx+b，对于不存在斜率的线，记录x坐标的位置即可。eps设为1e-10即可。然后去重，统计相同斜率的直线个数直接计算。因为答案就是斜率不同的直线对数目÷2。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1010;
struct line{double k,b;}l[N*N];
int n,num,n1,n2,m,x[N],y[N],h1[N*N],h2[N*N],b[N];
ll ans;
bool cmp(line a,line b){return fabs(a.k-b.k)<1e-10?a.b<b.b:a.k<b.k;}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    for(int i=1;i<n;i++)
    for(int j=i+1;j<=n;j++)
    if(x[i]==x[j])
    {
        if(!h1[x[i]+10000])n1++;
        h1[x[i]+10000]=1;
    }
    else l[++m].k=1.0*(y[i]-y[j])/(x[i]-x[j]),l[m].b=y[i]-l[m].k*x[i];
    sort(l+1,l+m+1,cmp);
    l[0].k=-1e18;
    for(int i=1;i<=m;i++)
    if(fabs(l[i].k-l[i-1].k)>1e-10)n2++,h2[++num]++;
    else if(fabs(l[i].b-l[i-1].b)>1e-10)n2++,h2[num]++;
    ans=1ll*n1*n2;
    for(int i=1;i<=num;i++)ans+=1ll*(n1+n2-h2[i])*h2[i];
    cout<<ans/2;
}

View Code

看到|c|<=1000,|s|,|t|<=50，不妨想到dp，f[i][j][k]表示c串走i步，到达|s|串j位置，|t|串k位置最大值为多少，若遇到字母直接转移，遇到*枚举26个字母。预处理s和t在每一个位置使用26个字母转移后的j/k最大值，这个暴力计算即可。复杂度O(|s|^3+|t|^3+26|c||s||t|)

#include<bits/stdc++.h>
using namespace std;
const int N=1002;
int n,ns,nt,ans=-1e9,gs[52][26],gt[52][26],f[N][52][52];
char c[N],s[N],t[N];
bool Qs(int x,int y)
{
    int p=x-y;for(int i=1;i<=y;i++)if(s[i]!=s[p+i])return 0;
    return 1;
}
bool Qt(int x,int y)
{
    int p=x-y;for(int i=1;i<=y;i++)if(t[i]!=t[p+i])return 0;
    return 1;
}
void upd(int&x,int y){x=x>y?x:y;}
int main()
{
    scanf("%s",c+1),n=strlen(c+1);
    scanf("%s",s+1),ns=strlen(s+1);
    scanf("%s",t+1),nt=strlen(t+1);
    for(int i=0;i<=ns;i++)
    for(int j=i;j>=0;j--)
    if((i!=ns||j!=ns)&&Qs(i,j))gs[i][s[j+1]-'a']=max(gs[i][s[j+1]-'a'],j+1);
    for(int i=0;i<=nt;i++)
    for(int j=i;j>=0;j--)
    if((i!=nt||j!=nt)&&Qt(i,j))gt[i][t[j+1]-'a']=max(gt[i][t[j+1]-'a'],j+1);
    for(int i=0;i<=n;i++)
    for(int j=0;j<=ns;j++)
    for(int k=0;k<=nt;k++)
    f[i][j][k]=-1e9;
    f[0][0][0]=0;
    for(int i=1;i<=n;i++)
    for(int j=0;j<=ns;j++)
    for(int k=0;k<=nt;k++)
    if(f[i-1][j][k]>-1e9)
    {
        if(c[i]!='*')
        {
            int x=c[i]-'a';
            upd(f[i][gs[j][x]][gt[k][x]],f[i-1][j][k]+(gs[j][x]==ns)-(gt[k][x]==nt));
        }
        else for(int x=0;x<26;x++)
        upd(f[i][gs[j][x]][gt[k][x]],f[i-1][j][k]+(gs[j][x]==ns)-(gt[k][x]==nt));
    }
    for(int j=0;j<=ns;j++)
    for(int k=0;k<=nt;k++)
    upd(ans,f[n][j][k]);
    printf("%d",ans);
}