10.26周赛补题

http://101.76.200.10/cache/4/03/maratona.ime.usp.br/7e08452c5de83ec599229759a9466aca/maratona_en.pdf

A.问能否从左上角走到右下角，那么就转化为能否从左下角走到右上角，如果能走到，则原来的路线不通，类似于狼抓兔子

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#define maxn 100010
using namespace std;
int m,n,k,a[maxn],b[maxn],c[maxn],head[maxn],num,nn;
bool vis[maxn];
struct node{
    int to,pre;
}e[maxn*50];
int Abs(int x){
    if(x>0)return x;
    else return -x;
}
void Insert(int from,int to){
    e[++num].to=to;
    e[num].pre=head[from];
    head[from]=num;
}
queue<int>q;
bool bfs(){
    vis[0]=1;
    q.push(0);
    while(!q.empty()){
        int now=q.front();q.pop();
        for(int i=head[now];i;i=e[i].pre){
            int to=e[i].to;
            if(vis[to])continue;
            vis[to]=1;
            q.push(to);
            if(to==nn)return 1;
        }
    }
    if(vis[nn])return 1;
    return 0;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    m++,n++;
    for(int i=1;i<=k;i++){
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
        a[i]=a[i]+1;
        b[i]=b[i]+1;
    }
    for(int i=1;i<=k;i++)
        for(int j=i+1;j<=k;j++)
            if(sqrt(1.0*(a[i]-a[j])*(a[i]-a[j])+1.0*(b[i]-b[j])*(b[i]-b[j]))<=c[i]*1.0+c[j]*1.0){
                Insert(i,j);
                Insert(j,i);
//                cout<<i<<' '<<j<<endl;
            }
    for(int i=1;i<=k;i++){
        if(b[i]-1<=c[i]){//left 
            Insert(i,k+a[i]);
            Insert(k+a[i],i);
//            cout<<i<<' '<<k+a[i]<<endl;
        }
        if(n-a[i]<=c[i]){//under
            Insert(i,k+n+b[i]);
            Insert(k+n+b[i],i);
//            cout<<i<<' '<<k+n+b[i]<<endl;
        }
        if(m-b[i]<=c[i]){//right
            Insert(i,k+m+n+a[i]);
            Insert(k+m+n+a[i],i);
//            cout<<i<<' '<<k+m+n+a[i]<<endl;
        }
        if(a[i]-1<=c[i]){//on
            Insert(i,k+m+n+n+b[i]);
            Insert(k+m+n+n+b[i],i);
//            cout<<i<<' '<<k+m+n+n+b[i]<<endl;
        }
    }
    nn=(n+m)*2+k+1;
    for(int i=k+2;i<k+m+n;i++){
        Insert(0,i);
        Insert(i,0);
    }
    for(int i=k+m+n+1+1;i<k+m+n+m+n;i++){
        Insert(i,nn);
        Insert(nn,i);
    }
    bool flag=bfs();
    if(flag)puts("N");
    else puts("S");
    return 0;
}

View Code

I.二分答案

#include<iostream>
#include<cstdio>
#define maxn 100010
using namespace std;
int a[maxn],n,c,k,ans;
bool Judge(int x,int limit){//ÅжÏÄÜ·ñÔÚlimitÃëÄÚ³ÔÍêx¸öÓñÃ× 
    int flag=0;
    if(x%k)flag=1;
    return x/k+flag<=limit;
}
bool check(int x){//Åжϲ»³¬¹ý¸ÃÃëÊýÄÜ·ñ³ÔÍê 
    int sum=0,cnt=0;
    for(int i=1;i<=n;i++){
        if(Judge(sum+a[i],x)){
            sum+=a[i];
        }
        else {
            cnt++;
            sum=a[i];
        }
        if(cnt>c)return 0;
    }
    if(cnt+1>c)return 0;
    return 1;
}
int main(){
    scanf("%d%d%d",&n,&c,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int l=0,r=1000000000;
    for(int i=1;i<=n;i++){
        int flag=0;
        if(a[i]%k)flag=1;
        l=max(l,flag+a[i]/k);
    }
    while(l<=r){//¶þ·ÖÃëÊý 
        int mid=(l+r)>>1;
        if(check(mid))r=mid-1,ans=mid;
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

View Code