首页 > 代码库 > [3.3校内训练赛]

[3.3校内训练赛]

2024-09-06 20:14:48   219人阅读

我好菜啊都不会

---------------

A.[百练2812] 恼人的青蛙

给丁一张r*c的图，上面有最多n个青蛙脚印，一个青蛙行走的路线是一条直线，且间隔距离相同，最少行走3个点。

求可能的青蛙走过的踩过最多脚印的路线的脚印数量。

技术分享

r,c,n<=5000

做法：枚举两个点，check一下。

加一些剪枝，比如如果目前这条直线即使可行也不会比答案优秀，我们就可以退出了。

还可以把点按照横坐标排序，每次如果因为横坐标相差过大导致出现剪枝1的情况，就可以不搜前面这个点了，因为后面的点相差显然更大。

然后加了跑的飞快 165ms 就过了 复杂度O(能过）

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();}
    return x*f;
}

inline int abs(int x){return x<0?-x:x;}

bool yes;
bool b[5005][5005];
int r,c;
int n,u,v,ans=0,num,xx,yy;
struct node{
    int x,y;
}s[5005];

bool cmp(node x,node y){return x.x<y.x;}

int main()
{
    r=read();c=read();n=read();
    for(register int i=1;i<=n;i++)
    {
        s[i].x=read();s[i].y=read();
        b[s[i].x][s[i].y]=1;
    }
    sort(s+1,s+n+1,cmp);
    for(register int i=1;i<=n;i++)
        for(register int j=i+1;j<=n;j++)
            if(abs(s[i].x-s[j].x)*ans<=r)
            {
                if(abs(s[i].y-s[j].y)*ans>c)continue;
                num=0;yes=true;
                for(xx=s[i].x,yy=s[i].y;xx>0&&yy>0&&xx<=r&&yy<=c;xx+=s[i].x-s[j].x,yy+=s[i].y-s[j].y)
                    if(!b[xx][yy]){yes=false;break;}else ++num;
                if(yes)for(xx=s[j].x,yy=s[j].y;xx>0&&yy>0&&xx<=r&&yy<=c;xx+=s[j].x-s[i].x,yy+=s[j].y-s[i].y)
                    if(!b[xx][yy]){yes=false;break;}else ++num;
                if(yes) ans=max(ans,num);
            }
            else break;
    printf("%d\n",ans>2?ans:0);
    return 0;
}

C.[hdu2197]本原串

求长度为n的没有循环节的二进制串的个数。n<=10^8

题解：筛出所有因数，然后容斥原理

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define mod 2008
using namespace std;

int s[10005],num[10005],n,cnt;
int ans=0;

int pow(int x,int p)
{
    int sum=1;
    for(int i=x;p;p>>=1,i=(i*i)%mod)if(p&1)
          sum=(sum*i)%mod;
    return sum;
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        cnt=0;ans=pow(2,n);
        for(int i=1;i<=sqrt(n);i++)
            if(n%i==0)
            {
                s[++cnt]=i;num[cnt]=-1;
                if(i*i!=n)s[++cnt]=n/i,num[cnt]=-1;    
            }
        sort(s+1,s+cnt+1);
        for(int i=cnt-1;i;i--)
            for(int j=1;j<i;j++)
                if(s[i]%s[j]==0) num[j]-=num[i];
        for(int i=1;i<cnt;i++)ans=(ans+1000*mod+num[i]*pow(2,s[i]))%mod;
        cout<<ans<<endl;
    }
    return 0;
}

D.Poj2112

有c个奶牛，n个点，每个点最多m头牛，每头牛要去一个点，给丁所有牛和点的距离，求所有牛都有点去的时候最大距离的最小值  

c<=200,n<=30,m<=15

二分答案，然后网络流check一下

因为是临时换题了，所以不知道还有这道大水题...没去切.....但是看看就会做（原来的D题貌似是dancing link)

E.有n个人,m个限制条件，每个限制条件要求ai比bi更前。n<=200000,m<=400000

你要在限制的基础上，安排一个顺序，让1的位置尽量小，然后2的位置尽量小........

题解：倒着建图，堆+括扑排序，倒着输出

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();}
    return x*f;
}

priority_queue<int> q;

int n,m,cnt=0;
struct edge{
    int to,next;
}e[400005];
int head[200005];
int to[200005];
int ans[200005];

void ins(int f,int t)
{
    e[++cnt].next=head[f];head[f]=cnt;
    e[cnt].to=t;
}

int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        ins(v,u);to[u]++;
    }
    for(int i=1;i<=n;i++)if(!to[i])q.push(i);
    for(int i=1;i<=n;i++)
    {
        int x=q.top();q.pop();
        ans[i]=x;
        for(int i=head[x];i;i=e[i].next){--to[e[i].to];if(!to[e[i].to])q.push(e[i].to);}
    }
    for(int i=n;i;i--)printf("%d ",ans[i]);
    return 0;
}

 

[3.3校内训练赛]


联系
我们