【Codeforces】Round #485 Div2

전송문CodeforcesRound#485Div2

A Infinity Gauntlet

B High School: Become Human

C Three displays

D Fair

E Petr and Permutations

F AND Graph

A Infinity Gauntlet
뭐라고 말하고 싶지 않은데... emmm 문법문제??

#include
using namespace std;
int n,m;
int exi[10];
char s[33];
int main(){
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%s",s);
        if(s[0]=='p'){
            exi[1]=1;
        }else if(s[0]=='g'){
            exi[2]=1;
        }else if(s[0]=='b'){
            exi[3]=1;
        }else if(s[0]=='o'){
            exi[4]=1;
        }else if(s[0]=='r'){
            exi[5]=1;
        }else if(s[0]=='y'){
            exi[6]=1;
        }
    }
    printf("%d
",6-n);
    if(!exi[1]) printf("Power
");
    if(!exi[2]) printf("Time
");
    if(!exi[3]) printf("Space
");
    if(!exi[4]) printf("Soul
");
    if(!exi[5]) printf("Reality
");
    if(!exi[6]) printf("Mind
");
}

B High School: Become Human
로그를 하나 취하면 n차멱은 n을 곱하는 것이 된다.우리가 xyxy와 yxyx를 비교하면 y∗ log(x) y∗ l o g(x)와 x∗ log(y) x󕅉 l o g(y)를 비교한 것이다.그동안 WA는 본연의 x=y만 있을 때 =가 있는 줄 알았던 QWQ인데 24는 똑같아요. 혈액WA... 더블변수로 이 값을 저장하지 않는 게 좋을 것 같아요. 카드 정밀도가 높대요.

#include
#define db double 
using namespace std;
int x,y,t;

int main(){
    scanf("%d%d",&x,&y);
    if(log(x)*y==log(y)*x){printf("=
");}
    else if(log(x)*y<log(y)*x) printf(");
    else printf(">
");
}

C Three displays
욕심

#include
const int inf=2e9; 
using namespace std;
int f[3010][3],n,c[3010],s[3010];
int ans=inf;

int main(){
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;++i){f[i][1]=f[i][2]=inf;scanf("%d",&s[i]);}
    for(i=1;i<=n;++i) scanf("%d",&c[i]);
    for(i=1;i<=n;++i){
        f[i][0]=c[i];
        for(j=1;jif(s[j]1]=min(f[i][1],f[j][0]+c[i]);
                if(f[j][1]2]=min(f[i][2],f[j][1]+c[i]);
                }
            }
        }
    }
    for(i=3;i<=n;++i) ans=min(ans,f[i][2]);
    if(ans>=inf) printf("-1
");
    else printf("%d
",ans); 
}

D Fair
k<=100k<=100... 우리는 직접 k회 bfs로 각 점에서 각 색깔과 가장 가까운 거리를 찾습니다.모든 답안을 구할 때sort는 앞의 s개를 합치면 된다.본체는 처음에 피T... bfs때 디스=0의 점만 넣고 뛰었기 때문에 (당연히 피T) 모든 것을 넣으면 지나간다.

#include
using namespace std;
const int inf=2e9,N=1e5+5;
int d[N][102],a[N],n,k,cur,m,s,vis[N];
int head[N],to[N<<1],nxt[N<<1],tot,dir[102];
queue<int>Q;
vector<int>in[102];
inline int rd()
{
    char ch=getchar();int x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

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

inline void bfs(int col)
{
    int i,j,x;
    for(i=in[col].size()-1;i>=0;i--){
        j=in[col][i];Q.push(j);d[j][col]=0;vis[j]=1;
    }
    while(!Q.empty()){
        x=Q.front();Q.pop();vis[x]=0;
        for(i=head[x];i;i=nxt[i]){
            j=to[i];
            if(d[j][col]>d[x][col]+1){
                d[j][col]=d[x][col]+1;
                if(!vis[j]){
                    Q.push(j);
                    vis[j]=1;
                }
            }
        }
    }
}

int main(){
    int i,j,x,y;
    n=rd();m=rd();k=rd();s=rd();
    for(i=1;i<=n;++i) 
      for(j=1;j<=k;++j)
       d[i][j]=inf;
    for(i=1;i<=n;++i) {a[i]=rd();in[a[i]].push_back(i);}
    while(m--){x=rd();y=rd();lk(x,y);lk(y,x);}
    for(i=1;i<=k;++i) bfs(i);
    for(i=1;i<=n;++i){
        cur=0;
        sort(d[i]+1,d[i]+k+1);
        for(j=1;j<=s;++j) cur+=d[i][j];
        printf("%d ",cur);
    }
} 

E Petr and Permutations
이것은 물문제다.근데 본고시 때는 아직 피투성이였어.직접 욕심을 내서 최소 몇 번을 교환하면 현재 서열을 얻을 수 있습니다.남은 조작 횟수가 짝일 경우 반드시 성립된다는 것을 알 수 있다.3n에서 현재 횟수를 빼면 짝인지 아닌지를 판정하면 된다.

#include
using namespace std;
const int N=1e6+10;
int cnt,n,a[N],in[N];

int main(){
    int i,j,t;
    scanf("%d",&n);
    for(i=1;i<=n;++i){scanf("%d",&a[i]);in[a[i]]=i;}
    for(i=1;i<=n;++i){
        if(a[i]!=i){
           j=in[i];
           a[j]=a[i];in[a[i]]=j;a[i]=i; 
           cnt++;
        }
    }
    if((3*n-cnt)%2==0) printf("Petr
");
    else printf("Um_nik
");
}

F AND Graph
전집은 당연히 2^n-1이다.처음의 사고방식은 1-n 매거, 매거 각수 이상 또는 전집의 자집(바로 연결할 수 있는 수)을 같은 자신의 용도와 조사집을 연결하는 것이다.마지막으로 몇 개인지 알아봤으면 좋겠어요.아니나 다를까 TLE 는 이렇게 번거로울 필요가 없다는 것을 알게 되었다. 우리는 앞의 수를 처리할 때 뒤의 수로 연결되고, 뒤의 수를 처리할 때 다시 되돌아와 여러 번 반복해서 처리한다.사실 저희는 O(n)dfs 한 번만 하면 돼요.

#include
using namespace std;
const int N=(1<<22)+10;
int n,m,exi[N],a[N],v[N],ans,al;

inline void dfs(int x)
{
    if(v[x]) return;
    v[x]=1;
    if(exi[x]) dfs(al^x);
    for(int i=0;iif(x&(1<1<int main(){
    int i,j,cur,now,q,p;
   scanf("%d%d",&n,&m);al=(1<1;
   for(i=1;i<=m;++i){scanf("%d",&a[i]);exi[a[i]]=1;}
   for(i=1;i<=m;++i){
        if(!v[a[i]]){ans++;v[a[i]]=1;dfs(al^a[i]);}
    }   
   printf("%d
",ans);
}

이거 진짜 물놀이 방송... 여러분, 빨리 AK 전체로 오세요.