【Codeforces】#Round495 Div2

傳送門:CodeforcesRound495Div2

• A. Sonya and Hotels
• B. Sonya and Exhibition
• C. Sonya and Robots
• D. Sonya and Matrix
• E. Sonya and Ice Cream
• F. Sonya and Bitwise OR

A. Sonya and Hotels

這題沒啥說的，就是int爆了要用long long

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans;
ll n,a[],d;

int main(){
    ll i,j,q;
    scanf("%I64d%I64d",&n,&d);
    for(i=;i<=n;++i)scanf("%I64d",&a[i]);
    sort(a+,a+n+);
    ans=;
    for(i=;i<n;++i){
        j=a[i]+d;
        if(a[i+]>=j+d) ans++; 
        q=a[i+]-d;
        if(q>a[i]+d) ans++;
    }
    printf("%d",ans);
}
           

B. Sonya and Exhibition

看題一臉懵逼？？這是個B？？？

切完C才反應過來：

不管怎樣增加區間要求，我們隻要01間隔輪流擺總是沒錯的…

跪在b題，還是我太菜

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,i;
int main(){
    scanf("%d%d",&n,&m);
    for(i=;i<=m;++i) scanf("%d%d",&x,&y);
    for(i=;i<=n;++i) printf("%c",'0'+(i&));
}
           

C. Sonya and Robots

離散化一下，标記一下每個值第一次和最後一次出現的位置，指針掃一遍即可。

同樣注意用long long

include<bits/stdc++.h>
using namespace std;
const int N=+;
typedef long long ll;
int n,v[N],z[N],f[N],a[N],b[N],cnt;
ll ans;

inline bool cmp(const int &x,const int &y){return z[v[x]]<z[v[y]];}
inline bool cmq(const int &x,const int &y){return f[v[x]]<f[v[y]];}

int main(){
    int i,j;
    scanf("%d",&n);
    for(i=;i<=n;++i){
        scanf("%d",&a[i]);
        if(!z[a[i]]) z[a[i]]=i;
        f[a[i]]=i;
    }
    sort(a+,a+n+);v[++cnt]=a[];
    for(i=;i<=n;++i){
        if(a[i]!=a[i-]){
            v[++cnt]=a[i];
        }
    } 
    for(i=;i<=cnt;++i) a[i]=b[i]=i;
    sort(a+,a+cnt+,cmp);sort(b+,b+cnt+,cmq);
    for(j=,i=;i<=cnt;++i){
        while(f[v[b[j]]]<=z[v[a[i]]] && j<=cnt) 
        ++j;
        ans+=(cnt-j+);
    }
    printf("%I64d",ans);
}
           

D. Sonya and Matrix

這題挺有意思的.

感覺把圖旋轉一下也沒有什麼差別。是以随便找一個x最小的答案就好啦。

可以發現，找到值最小的數 i(i>0) i ( i > 0 ) 且i的出現次數小于4*i次，這個i就等于0的x坐标。

同樣假設可以把整個矩形分成左上左下右上右下四塊，強行讓0在右下這塊，那麼離它最遠的必然是左上角的點，也就是數組裡的最大值，設為 b=m+n−x−y b = m + n − x − y 。

設 (x,y) ( x , y ) 離右下角的距離 a=x+y−2 a = x + y − 2

然後就枚舉t的因數即枚舉n,m的值，此時知道了 n,m,b,x n , m , b , x ， y y 由上面等式自然就推出來了，于是暴力O(t)O(t)算一遍這個數組，和原數組比較。

這個複雜度… n−−√ n 的枚舉還套上 nlogn n log ⁡ n 的排序和有常數的枚舉。

總之cf評測機能過

#include<bits/stdc++.h>
using namespace std;
const int N=e6+;
int t,q[N],b,a,m,n,x,y,res[N],cnt;

inline void check()
{
    if((a>b) || (a<) || (y<)) return;\
    if((!(n&) && n<x*2) || ((n&) && n+<x*2)) return;
    if((!(m&) && m<y*2) || ((m&) && m+<x*2)) return;
    int i,j;cnt=;
    for(i=;i<=n;++i)
      for(j=;j<=m;++j)
      {res[++cnt]=abs(i-x)+abs(j-y);}
    sort(res+,res+t+);
    for(i=;i<=t;++i) if(res[i]!=q[i]) return;
    printf("%d %d\n%d %d",n,m,x,y);exit();
}

int main(){
    int i,j;
    scanf("%d",&t);
    for(i=;i<=t;++i) scanf("%d",&q[i]);
    if(t==){
       if(q[1]==) printf("1 1\n1 1\n");
       else printf("-1\n");
       return ;
    }
    sort(q+,q+t+);
    for(i=;i<=t;i=j+){
        for(j=i;q[j+1]==q[i] && j<t;++j);
        if((j-i+)!=*q[i]){x=q[i];break;}
    }
    b=q[t];
    for(i=;i*i<=t;++i) if(t%i==){
        n=i;m=t/i;y=m+n-b-x;
        a=m+n-b-;check();
        if(i*i!=t){swap(m,n);check();}
    }
    printf("-1\n");
}
           

E. Sonya and Ice Cream

這題的貪心也很有意思。

可以肯定這樣一條長度不超過k-1的鍊必然是直徑上的一段子序列。

不詳說，很好證明。

那麼就先找出最長鍊建兩個指針分别指向鍊的兩個端點，不斷向内跳直到長度不超過k-1。而且可以肯定，當長度不超過k-1時， len=min(diameter,k−1) l e n = m i n ( d i a m e t e r , k − 1 ) 一定能使答案最優。

#include<bits/stdc++.h>
using namespace std;
const int N=+;
int mx[N],f[N],dis[N];
int n,k,rt,dt,hd,tl,d[N],in[N];
int head[N],to[N<<],nxt[N<<],w[N<<],tot;
int son[N];

inline void lk(int u,int v,int c)
{to[++tot]=v;nxt[tot]=head[u];head[u]=tot;w[tot]=c;}

inline void dfs(int x)
{
    int i,j,mx1=x,mx2=x;mx[x]=x;
    for(i=head[x];i;i=nxt[i]){
        j=to[i];if(j==f[x]) continue;
        f[j]=x;d[j]=d[x]+;dis[j]=dis[x]+w[i];dfs(j);
        if(dis[mx[j]]>dis[mx1]){
            mx2=mx1;mx1=mx[j];
        }else if(dis[mx[j]]>dis[mx2]){
            mx2=mx[j];
        }
    }
    mx[x]=mx1;if(dis[mx1]+dis[mx2]-*dis[x]>dt){
        dt=dis[mx1]+dis[mx2]-*dis[x];
        hd=mx1;tl=mx2;rt=x;
    }
}

inline void df(int x)
{
    int i,j;
    for(i=head[x];i;i=nxt[i]){
        j=to[i];if(j==f[x]) continue;
        if(in[x] && in[j]) son[x]=j;
        f[j]=x;d[j]=d[x]+;dis[j]=dis[x]+w[i];
        df(j);  
    }
}

inline void dfss(int x)
{
    int i,j;mx[x]= in[x]? :x;
    for(i=head[x];i;i=nxt[i]){
        j=to[i];if(j==f[x]) continue;
        dis[j]=dis[x]+w[i];f[j]=x;dfss(j);
        if(dis[mx[j]]>dis[mx[x]]) mx[x]=mx[j];
    }
    if(in[x]) {dt=max(dt,dis[mx[x]]-dis[x]);mx[x]=;}
}

int main(){
    int i,j,ix,iy,iz,upl,upr,l=,r=,sonl,sonr;
    scanf("%d%d",&n,&k);
    for(i=;i<n;++i){
      scanf("%d%d%d",&ix,&iy,&iz);
      lk(ix,iy,iz);lk(iy,ix,iz);
    }
    dfs();
    for(i=hd;i!=rt && f[i]!=rt;i=f[i]) in[i]=;
    if(f[i]==rt) sonl=i,in[i]=;
    for(i=tl;i!=rt && f[i]!=rt;i=f[i]) in[i]=;
    if(f[i]==rt) sonr=i,in[i]=;
    in[rt]=;
    ix=d[hd]+d[tl]-*d[rt]-k+;
    f[rt]=;d[rt]=,dis[rt]=;df(rt);
    upl= (d[hd]>d[rt]);upr=(d[tl]>d[rt]);
    for(;ix>;ix--){
        if(upl) i=-(dis[f[hd]]-dis[hd]);
        else i= hd==rt?-(dis[rt]-dis[sonr]):-(dis[hd]-dis[son[hd]]);
        if(upr) j=-(dis[f[tl]]-dis[tl]);
        else j= tl==rt?-(dis[rt]-dis[sonl]):-(dis[tl]-dis[son[tl]]);
        if(l+i<=j+r){
          l+=i;in[hd]=;if(upl) hd=f[hd];else hd= rt==hd? sonr:son[hd];
          if(hd==rt) upl=;
        }else{
          r+=j;in[tl]=;if(upr) tl=f[tl];else tl= rt==tl? sonl:son[tl];
          if(tl==rt) upr=;
        }
    }
    dt=;dis[hd]=;f[hd]=;dfss(hd);
    printf("%d\n",dt);
}
           

F. Sonya and Bitwise OR

先留個坑。