欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

day17

程序员文章站 2022-12-21 11:41:34
wdnmd什么垃圾网站,把我两道题分搞没了,实际得分50/300,应该得分150/300; 无话可说; T1暴力枚举; T2数论+DP; T3几何等; T1先枚举行的情况,再枚举列的情况; #include #include #include ......

wdnmd什么垃圾网站,把我两道题分搞没了,实际得分50/300,应该得分150/300;

无话可说;

t1暴力枚举;

t2数论+dp;

t3几何等;

t1先枚举行的情况,再枚举列的情况;

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring> 
using namespace std;
int xx[20],yy[20],ans=2147483647;
char a[20][20],d;
int n,m,r,c;
void dfs(int x,int tot)
{
    if(x>n)
    {
        memset(yy,0,sizeof(yy));
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(!xx[i]&&a[i][j]=='x')yy[j]=1;
        }
        for(int j=1;j<=m;j++)
        {
            if(yy[j])
            {
                for(int k=0;k<c;k++)
                yy[min(j+k,m)]=0;
                tot++;
            }
        }
        ans=ans<tot?ans:tot;
        return;
    }
    else
    {
        for(int i=x;i<=min(x+r,n);i++)xx[i]=1;
        dfs(x+r,tot+1);
        for(int i=x;i<=min(x+r,n);i++)xx[i]=0;
    }
    dfs(x+1,tot);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
    {
        d=getchar();
        while(d!='.'&&d!='x')
        d=getchar();
        a[i][j]=d;
    }
    cin>>r>>c;
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}

t2

 

day17

#include<iostream>
#include<cstdio>
using namespace std;
unsigned long long h[1200],num[1000],f[1000],ans=1;
int n,k;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        h[i]=1;
    }
    for(int i=1;i<k;i++)
    {
        for(int j=1;j<=n;j++)
        {
            h[j]=(h[j]+h[j-1])%1000000009;
        }
    }
    int i=1,p=n;
    while(n)
    {
        int x=n;
        while(x%2==0)
        {
            x/=2;
            f[2]++;
        }
        for(int j=3;j<=x;j+=2)
        {
            while(x%j==0)
            {
                f[j]++;
                x/=j;
            }
        }
        if(x>1)f[x]++;
        for(int j=1;j<=n;j++)
        {
            num[j]=(num[j]+f[j]*h[i]%1000000009)%1000000009;
            f[j]=0;
        }
        i++;n--;
    }
    for(int i=2;i<=p;i++)
    {
        ans=ans*(num[i]+1)%1000000009;
    }
    cout<<ans<<endl;
    return 0;
}

 t3

day17

day17

 

截距只是为了缩小枚举范围,按纵截距排序后答案只在相邻两个点连成的线里;

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct node{
    double x,y,b;
}a[210000];
double p,q,temp,stand,minn=0x7fff;
int x,y;
int n,ans1,ans2;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
inline int gcd(int p,int q){return q==0?p:gcd(q,p%q);}
inline double xl(int i){return (a[i].y-a[i+1].y)/(a[i].x-a[i+1].x);}
inline double cmp(node p,node q){return p.b<q.b;}
int main()
{
    freopen("slope.in","r",stdin);freopen("slope.out","w",stdout);
    n=read();p=read();q=read();
    stand=p/q;
    for(int i=1;i<=n;i++){
    a[i].x=read();a[i].y=read();a[i].b=a[i].y-a[i].x*stand;}
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<n;i++)
    {
        temp=xl(i);
        if(abs(temp-stand)<abs(minn-stand)){
            minn=temp;x=int(a[i].x)-int(a[i+1].x);y=a[i].y-a[i+1].y;
        }
    }
    x=abs(x);y=abs(y);
    int gcdd=gcd(max(x,y),min(x,y));
    x/=gcdd;y/=gcdd;
    cout<<y<<'/'<<x<<endl;
    return 0;
}

好了,day17全部改完了。

300/300