Codeforces Round #488 Div. 1-白红宇

Codeforces Round #488 Div. 1

阅读量：4583 次

发布时间：2019-06-09

本文共 6656 字，大约阅读时间需要 22 分钟。

　　A：枚举每个点判断是否同时在两个正方形中即可。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long longchar getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}struct data{ int x,y; void get(){x=read();y=read();}}a[4],b[4];bool isin1(int x,int y){ int LEFT=1000,RIGHT=-1000,UP=-1000,DOWN=1000; for (int i=0;i<4;i++) LEFT=min(LEFT,a[i].x), RIGHT=max(RIGHT,a[i].x), UP=max(UP,a[i].y), DOWN=min(DOWN,a[i].y); if (LEFT<=x&&RIGHT>=x&&UP>=y&&DOWN<=y) return 1; else return 0;}bool isin2(int x,int y){ int LEFT=1000,RIGHT=-1000,UP=-1000,DOWN=1000; for (int i=0;i<4;i++) LEFT=min(LEFT,b[i].x), RIGHT=max(RIGHT,b[i].x), UP=max(UP,b[i].y), DOWN=min(DOWN,b[i].y); int mid1=(LEFT+RIGHT)/2,mid2=(UP+DOWN)/2; if (abs(x-mid1)+abs(y-mid2)<=mid1-LEFT) return 1; else return 0;}void win(){cout<<"Yes";exit(0);}signed main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif for (int i=0;i<4;i++) a[i].get(); for (int i=0;i<4;i++) b[i].get(); for (int i=-100;i<=100;i++) for (int j=-100;j<=100;j++) if (isin1(i,j)&&isin2(i,j)) win(); cout<<"No"; return 0; //NOTICE LONG LONG!!!!!}

　　B：莫名其妙的题。首先要知道这俩人只想知道他们的共同数字是什么，而不是对方的数字对是什么。先判断啥都不知道能否确定该数字，只要考虑每一对仅有一个数字相同的数对，如果其共同数字都相同，即可确定该数为答案。否则仍考虑每一对可能的数对，如果某一种情况下有一方无法确定共同数字，即输出-1。最后输出0即可。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 100char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,m;struct data{int x,y;}a[N],b[N];int calc(data a,data b){ return (a.x==b.x)+(a.x==b.y)+(a.y==b.x)+(a.y==b.y);}int same(data a,data b){ if (a.x==b.x||a.x==b.y) return a.x; else return a.y;}signed main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif n=read(),m=read(); for (int i=1;i<=n;i++) { a[i].x=read(),a[i].y=read(); if (a[i].x>a[i].y) swap(a[i].x,a[i].y); } for (int i=1;i<=m;i++) { b[i].x=read(),b[i].y=read(); if (b[i].x>b[i].y) swap(b[i].x,b[i].y); } int ans=0,uuu; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (calc(a[i],b[j])==1) ans++,uuu=same(a[i],b[j]); bool flag=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (calc(a[i],b[j])==1&&same(a[i],b[j])!=uuu) flag=1; if (!flag) {cout<

　　C：显然答案位置至少在一对飞船的交点上，这个数量级是O(nm)的。预处理每个位置能消灭哪些飞船，bitset存储，然后暴力枚举每一对位置，bitset上or一下count一下就完了。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 122char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,m,a[N],b[N],ans;bitset
            
              f[N>>1][N>>1];signed main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif n=read(),m=read(); for (int i=1;i<=n;i++) a[i]=read(); for (int i=1;i<=m;i++) b[i]=read(); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { for (int x=1;x<=n;x++) for (int y=1;y<=m;y++) if (a[i]-a[x]==b[y]-b[j]) f[i][j][x]=1,f[i][j][y+n]=1; } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int x=1;x<=n;x++) for (int y=1;y<=m;y++) ans=max(ans,(int)(f[i][j]|f[x][y]).count()); cout<

　　D：显然二分答案。相当于每将一个功率=x的任务放在第一批，就为功率<x的任务提供了一个垃圾桶。于是按功率从大到小排序，设f[i][j]为前i个任务剩余j个垃圾桶的最小值。唯一的问题是功率相同的任务间不能提供垃圾桶，状态再加一维处理即可。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 55char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n;ll f[N][N][N];struct data{ ll x,y; bool operator <(const data&a) const { return x>a.x||x==a.x&&y
           
            =0;j--) for (int x=0;x<=j;x++) f[i][j][0]=min(f[i][j][0],f[i][j-x][x]); } for (int i=0;i<=n;i++) if (f[n][i][0]<=0) return 1; return 0;}signed main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif n=read(); for (int i=1;i<=n;i++) a[i].x=1000ll*read(); for (int i=1;i<=n;i++) a[i].y=read(); sort(a+1,a+n+1); ll l=0,r=10000000000000000ll,ans; while (l<=r) { ll mid=l+r>>1; if (check(mid)) ans=mid,r=mid-1; else l=mid+1; } cout<

　　E：显然每个数有用的信息仅仅是其和x的大小，根据这个设为01后，即相当于求和为k的区间个数。又可以转换为前缀和之差为k的区间个数。裸的FFT。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 1100010#define double long doublechar getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,m,f[N],r[N];ll ans[N];const double PI=3.14159265358979324;struct complex{ double x,y; complex operator +(const complex&a) const { return (complex){x+a.x,y+a.y}; } complex operator -(const complex&a) const { return (complex){x-a.x,y-a.y}; } complex operator *(const complex&a) const { return (complex){x*a.x-y*a.y,x*a.y+y*a.x}; }}a[N],b[N];void DFT(int n,complex *a,int p){ for (int i=0;i
           
            >1]>>1)|(i&1)*(n>>1); for (int i=0;i
            
             >1);k++,w=w*wn) { complex x=a[k],y=w*a[k+(i>>1)]; a[k]=x+y,a[k+(i>>1)]=x-y; } } }}void mul(int n,complex *a,complex *b){ DFT(n,a,1),DFT(n,b,1); for (int i=0;i

　　居然还有我能在场上做五题的div1

转载于:https://www.cnblogs.com/Gloid/p/10427398.html

你可能感兴趣的文章