2019中山大学程序设计竞赛

solved 5

rank 2

5道签到比谁签的快？

unsolved

题意：给出n条木棍，问是否能组成至少一个三角形。

按长度排序后只需要检查A(i)+A(i+1)>A(i+2)是否成立，这样O(nlogn)理论上可以通过，但实际时限卡的比较紧会TLE。考虑不能构成三角形时，木棍的长度至少按斐波那契数列的速度增长，很快就会超出int范围，那么可以肯定n较大一定可以形成三角形，这样时间复杂度为O(n)(读入数据)，但是可以通过。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define st first
#define nd second 
#define mp make_pair
#define pb push_back


const int N=1e3+7;

int n,x;

ll a[N];

int main(){
    ios::sync_with_stdio(false);
    while(cin>>n){
        
        if(n>100){
            rep(i,n){
                cin>>x;
            }
            cout<<"YES"<<'
';
            continue;
        }
        rep(i,n)cin>>a[i];
        sort(a+1,a+1+n);
        int f=0;
        rep(i,n-2){
            if(a[i+2]<a[i+1]+a[i]){
                cout<<"YES"<<'
';
                f=1;             
                break;
            }
        }
        if(!f)cout<<"NO"<<'
';
    }    
}

View Code

00：21（4A）

unsolved

题意：n*m的矩阵，已知有p个矩形，q次询问一个矩形区域是否被之前p个矩形完全覆盖。

前半部分通过二维差分预处理出每个点被覆盖的次数，覆盖次数大于1的变成1，然后再对01矩阵做二维前缀和，即可O(1)回答询问。卡内存，需要映射一下。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define st first
#define nd second 
#define mp make_pair
#define pb push_back


const int N=1e7+7;
int n,m; 
int index(int x,int y){
    if(x>n||y>m||!x||!y)return 0;
    return m*(x-1)+y;
}

int a[N];



int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>m){
        rep(i,n)
        rep(j,m)a[index(i,j)]=0;
        int x1,y1,x2,y2;
        
        int p;
        cin>>p;
        rep(i,p){
            cin>>x1>>y1>>x2>>y2;
            a[index(x1,y1)]++;
            a[index(x2+1,y2+1)]++;
            a[index(x1,y2+1)]--;
            a[index(x2+1,y1)]--;
        }
        
        rep(i,n)
            rep(j,m){
                a[index(i,j)]=a[index(i-1,j)]+a[index(i,j-1)]-a[index(i-1,j-1)]+a[index(i,j)];
            }
        rep(i,n)
            rep(j,m)if(a[index(i,j)])a[index(i,j)]=1;
            
        rep(i,n)
            rep(j,m){
                a[index(i,j)]=a[index(i-1,j)]+a[index(i,j-1)]-a[index(i-1,j-1)]+a[index(i,j)];
            }
        
        int q;
        cin>>q;
        rep(i,q){
            cin>>x1>>y1>>x2>>y2;
            if(a[index(x2,y2)]-a[index(x1-1,y2)]-a[index(x2,y1-1)]+a[index(x1-1,y1-1)]==(x2-x1+1)*(y2-y1+1))cout<<"YES"<<'
';
            else cout<<"NO"<<'
';
        } 
        
        
    }
}

View Code

01：51（3A）

题意：模拟

（行末要有空格，输出末不能有空行，见过的最恶心的PE）

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define st first
#define nd second 
#define mp make_pair
#define pb push_back


const int N=1e5+7;

string s;

int a[N*24];

int main(){
    ios::sync_with_stdio(false);
    cin>>s;
    int l=s.size(),now=1;
    for(int i=0;i<l;i++){
        int res=s[i];
        for(int j=now;j<=now+7;j++){
            if(res&1)a[j]=1;
            res>>=1;
            if(!res)break;
        }
        now+=8;
    }
    now=1;
    rep(i,l/3*4){
        int res=0;
        for(int j=now;j<=now+5;j++){
            res<<=1;
            res+=a[j]; 
            //cout<<res<<endl; 
        }
        now+=6; 
        cout<<res<<" ";
    }
}

View Code

00：42（3A）

unsolved

题意：给出0/1三视图，1表示有东西，0表示没东西，求物体的最大体积。

三重循环枚举每个点，这个点在三视图上都为1就计入答案。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define st first
#define nd second 
#define mp make_pair
#define pb push_back


const int N=1e2+7;

int a[3][N][N];

int main(){
    ios::sync_with_stdio(false);
    int x,y,z;
    while(cin>>x>>y>>z){
        rep(i,x)
            rep(j,y)cin>>a[0][i][j];
        rep(i,y)
            rep(j,z)cin>>a[1][i][j];
        rep(i,z)
            rep(j,x)cin>>a[2][i][j];
        
        
        int ans=0;
        rep(i,x)
        rep(j,y)
        rep(k,z){
            if(a[0][i][j]&&a[1][j][k]&&a[2][k][i])ans++;
        }        
        cout<<ans<<'
';
    }
}

View Code

00：54（1A）

题意：模拟

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long
#define st first
#define nd second 
#define mp make_pair
#define pb push_back


const int N=1e2+7;

char a[N][N];

int main(){
    int n,m,k;
    while(cin>>n>>m>>k){
        rep(i,n)scanf("%s",a[i]);
        
        rep(i,k*n){
            rep(j,m){
                rep(w,k)cout<<a[i/k][j];
            }
            cout<<endl;
        }
    }
}

View Code

00：09（2A）

unsolved