BUAA - SCSE 여름 알고리즘 향상 반 Final Contest 문제 풀이 보고서

http://www.bnuoj.com/bnuoj/contest_show.php?cid=1847
A
두 문자열 을 지정 합 니 다. 두 문자열 의 문자 사이 에 쌍 사 관계 가 존재 합 니 다. 이러한 맵 이 존재 하 는 지 확인 하 십시오.
두 문자열 의 각 문자 의 출현 횟수 를 통계 한 다음 정렬 하고, 출현 횟수 가 같은 지 아래 에서 크게 보면 된다.

  scanf("%s
%s",s1,s2);
  for (i = 0 ;i < strlen(s1) ;i ++)  
    a[s1[i] - 'A'] ++;
  for (i = 0 ;i < strlen(s2) ;i ++)  
    b[s2[i] - 'A'] ++;
  sort(a , a + 26);
  sort(b , b + 26);
  for (i = 0 ;i < 26 ; i ++)
    if (a[i] != b[i])
      break;
  if (i == 26)
    printf("YES");
  else printf("NO");
  return 0; 

B
하나의 용기, 요 소 를 삽입 할 수도 있 고 요 소 를 팝 업 할 수도 있 습 니 다. 팝 업 을 삽입 하 는 것 이 무엇 인지 알려 드 립 니 다. 이 용기 가 스 택 이 냐, 대기 열 이 냐, 우선 대기 열 이 냐 고 물 었 습 니 다.
직접 STL 로 시 뮬 레이 션 하 세 요. 조작 수가 매우 적 기 때문에 배열 로 시 뮬 레이 션 하 는 것 도 가능 합 니 다.

  int i , x , y;
  stack<int> s;
  queue<int> q;
  priority_queue<int> p;
  bool fs = 0, fq = 0, fp = 0;
  while (n --)
  {
    cin >> i >> x;
    if (i == 1)
    {
      if(!fs) s.push(x);
      if(!fq) q.push(x);
      if(!fp) p.push(x);
    }
    else
    {
      if (s.empty())
        fs = 1;
      else if (!fs)
      {
        y = s.top() , s.pop();
        if (y != x) fs = 1;
      }
      if (q.empty())
        fq = 1;
      else if (!fq)
      {
        y = q.front() , q.pop();
        if (y != x) fq = 1;
      }
      if (p.empty())
        fp = 1;
      else if (!fp)
      {
        y = p.top() , p.pop();
        if (y != x) fp = 1;
      }
    }
  }
  if (!fs && fp && fq) puts("stack");
  else if (fs && fp && !fq) puts("queue");
  else if (fs && !fp && fq) puts("priority queue");
  else if (fs && fp && fq) puts("impossible");
  else puts("not sure");

C
간단 한 디지털 DP, n 번 째 로 666 을 포함 하 는 숫자 를 출력 하면 2 분 이면 됩 니 다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <climits>
using namespace std;
#define N 100005
#define M 500005
int X , Y , ca;
long long dp[20][4];
int digit[20];

long long dfs(int pos , int have , bool doing)
{
    if(pos == -1)
        return have == 3;

    if(!doing && ~dp[pos][have])
        return dp[pos][have];

    long long ans = 0;
    int end = doing ? digit[pos] : 9;
    for(int i = 0 ; i <= end ; i ++)
    {
        int nhave = have;
        if (have == 0)
        {
          if (i == 6)
            nhave = 1;
          else nhave = 0;
        }
        else if (have == 1)
        {
          if (i == 6)
            nhave = 2;
          else nhave = 0;
        }
        else if (have == 2)
        {
          if (i == 6)
            nhave = 3;
          else nhave = 0;
        }
        ans += dfs(pos - 1 , nhave , doing && i == end);
    }
    if(!doing)
      dp[pos][have] = ans;
    return ans;
}

long long cal(long long x)
{
    memset(dp , -1 , sizeof(dp));
    int pos = 0;
    while(x)
    {
      digit[pos ++] = x % 10;
      x /= 10;
    }
    return dfs(pos - 1 , 0 , 1);
}

int ai(int a , int b)
{
  char s[20];int i , j , ans = 0 , x , y;
  for (i = a ; i <= b ; ++ i)
  {
    sprintf(s ,"%d" , i);
    if (strstr(s , "666")) ++ ans;
  }
  return ans;
}

void work()
{
  long long m , l , r , k;
  int q;
  scanf("%d",&q);
  while (q --)
  {
    scanf("%lld",&k);
    l = 666 , r = 10000000000LL;
    while (l < r)
    {
      m = (l + r) >> 1;
      if (cal(m) >= k)
        r = m;
      else l = m + 1;
    }
    printf("%lld
" , l);
  }
}

int main()
{
  work();
  return 0;
}

D
먼저 너비 우선 검색 으로 각 칸 에 불 이 붙 는 시간 을 계산 한 다음 출발점 에서 너비 우선 검색 을 한 번 더 합 니 다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
#define N 1005

int n , m;
char s[N][N];
int t[N][N] , d[N][N];
int dx[] = {1 , 0 , -1 , 0} , dy[] = {0 , 1 , 0 , -1};
queue< pair<int , int> > q;

bool in(int x , int y)
{
  return x > 0 && x <= n && y > 0 && y <= m;
}

void work()
{
  int i , j , x , y;
  scanf("%d%d",&n,&m);
  memset(s , 0 , sizeof(s));
  for (i = 1 ; i <= n ; ++ i)
    scanf("%s" , s[i] + 1);

  memset(t , -1 , sizeof(t));
  for (i = 1 ; i <= n ; ++ i)
    for (j = 1 ; j <= m ; ++ j)
      if (s[i][j] == 'F')
        q.push(make_pair(i , j)) , t[i][j] = 0;
  while (!q.empty())
  {
    x = q.front().first , y = q.front().second , q.pop();
    for (i = 0 ; i < 4 ; ++ i) if (in(x + dx[i] , y + dy[i]))
      if (s[x + dx[i]][y + dy[i]] != '#' && !~t[x + dx[i]][y + dy[i]])
      {
        t[x + dx[i]][y + dy[i]] = t[x][y] + 1;
        q.push(make_pair(x + dx[i] , y + dy[i]));
      }
  }

  int ans = 1 << 30;
  memset(d , -1 , sizeof(d));
  for (i = 1 ; i <= n ; ++ i)
    for (j = 1 ; j <= m ; ++ j)
      if (s[i][j] == 'J')
        q.push(make_pair(i , j)) , d[i][j] = 0;

  while (!q.empty())
  {
    x = q.front().first , y = q.front().second , q.pop();
    if (x == 1 || x == n || y == 1 || y == m) ans = min(ans , d[x][y] + 1);
    for (i = 0 ; i < 4 ; ++ i) if (in(x + dx[i] , y + dy[i]) && (!~t[x + dx[i]][y + dy[i]] || t[x + dx[i]][y + dy[i]] > d[x][y] + 1))
      if (s[x + dx[i]][y + dy[i]] != '#' && !~d[x + dx[i]][y + dy[i]])
      {
        d[x + dx[i]][y + dy[i]] = d[x][y] + 1;
        q.push(make_pair(x + dx[i] , y + dy[i]));
      }
  }
  if (ans == 1 << 30)
    puts("IMPOSSIBLE");
  else printf("%d
" , ans);

}

int main()
{
  int _; cin >> _;while (_--)
    work();
  return 0;
}

E
출력 최소 생 성 트 리 최대 변.................................................................

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <cstdio>
#include <algorithm>
#define N 10005
using namespace std;
int n , m , f[N] , ans , sum;
struct edge
{
  int x ,y ,w;     
}e[N];
bool cmp(edge x, edge y)
{
  return x.w < y.w;   
}
int getf(int x) {return f[x] == x ? x : getf(f[x]); }
int main()
{
  scanf("%d%d",&n,&m);
  int i , x , y;
  for (i = 1 ; i <= n ;i ++)
    f[i] = i;
  for (i = 1 ; i <= m ;i ++)
    scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
  sort(e + 1 , e + m + 1 , cmp);
  for (i = 1 ; i <= m ;i ++)
  {
    x = getf(e[i].x) , y = getf(e[i].y);
    if (x != y)
    {
      sum ++;
      f[x] = y;
      if (sum == n - 1)
      {
        printf("%d",e[i].w);
        return 0;
      }    
    }  
  }    
  return 0;
}

F
2 점 답 에 검증 을 더 하 는 것 도...............................................................................

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <climits>
using namespace std;
#define N 100005
#define M 500005
int n , k;
int a[N];
long long sum;
void work()
{
  int i , x; double p;
  scanf("%d%d",&n,&k);
  for (i = 1 ; i <= n ; ++ i)
    scanf("%lf" , &p) , a[i] = (int)(p * 100.0 + 1e-9) , sum += a[i];
  int l = 1 , r = 10000000 , m;
  while (r - l > 0)
  {
    m = (l + r + 1) >> 1 , x = 0;
    for (i = 1 ; i <= n ; ++ i)
      x += a[i] / m;
    if (x >= k)
      l = m;
    else r = m - 1;
  }
  if (l == 1 && sum < k) l = 0;
  printf("%.2f
" , l / 100.0);
}

int main()
{
  work();
  return 0;
}

G
고정 밀 덧셈 과 비슷 한 문제... 문 제 를 읽 는 게 관건 이에 요.

#include <iostream>
#include <string>
using namespace std;
string a,b;
int main()
{
    cin>>a;
    while (cin>>b) 
    {
       for (int i=0;i<a.length();++i)
         a[i]=(a[i]-'0'+b[i]-'0')%10+'0';
    }
    cout<<a<<endl;
} 

H
수업 시간 에 말 했 던 배열 변환 기억 나 세 요? 이것 이 바로 문자열 로 바 꾼 원제 입 니 다.
순 서 를 정 해서 넣 으 면 되 는데...

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
#define N 100005

int n , ca;
char s[N] , t[N];

void work()
{
  int i ; long long ans = 0;
  scanf("%d%s %s" , &n , s , t);
  sort(s , s + n) , sort(t , t + n);
  for (i = 0 ; i < n ; ++ i)
    ans += abs(s[i] - t[i]);
  printf("Case %d: %lld
" , ++ ca , ans);
}

int main()
{
  int _; cin >> _;while (_--)
    work();
  return 0;
}

I
변종 백 팩 문 제 는 솔직히 알 티 튜 드 에 따라 순 위 를 매 길 생각 만 하면 된다. 나머지 는 누 드 백 팩 이 니 최적화 할 필요 가 없다.

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <cstdio>
#include <algorithm>
#define N 40005
using namespace std;
bool f[N];
int n;
struct st
{
  int h , a , c;
}s[N];
bool cmp(st x , st y)
{
  return x.a < y.a;
}

int main()
{
  int i , j , k;
  cin >> n;
  for (i = 1 ; i <= n ;i ++)
    scanf("%d %d %d",&s[i].h,&s[i].a,&s[i].c);
  sort(s + 1 , s + n + 1 , cmp); 
  f[0] = 1;
  for (i = 1 ;i <= n ;i ++ ) 
    for (k = s[i].a ; k >= 0 ;k --)
      for (j = 1 ;j <= s[i].c ;j ++)
        if (k - s[i].h * j >= 0 && f[k - s[i].h * j])
          f[k] = 1;

  for (i = 40000 ; i >= 0 ;i --)
    if (f[i])
    {
      printf("%d
",i);
      break;
    }
  return 0;
}