2018 '바 이 두 의 별' 프로 그래 밍 대회 - 퀄 리 파 잉 게임

BB
됐어 요. 제 가 이렇게 오래 살 면서 문 제 를 안 쓰 면 요리 가 바 뀌 잖 아 요. 이런 문 제 를 이렇게 오래 썼 는데.
T1
이 문 제 는 처음 보 았 을 때 mb 얼굴 을 하고 데이터 범 위 를 보고 마음 이 놓 였 습 니 다. 부분 집합 을 써 서 매 거 진 제출 했 습 니 다. 하지만 주의해 야 할 것 은 마지막 으로 답 을 통계 할 때 모든 숫자 가 나타 나 는 횟수 를 두 번 곱 하고 다시 구 하 는 것 입 니 다.

#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 10000 + 5;
int n,m,k;
int all[MAXN];
bool solve(int jh) {
    //TODO: init
    int tmp[MAXN] = {0};
    for(int i = 0;i < n;i ++) {
        tmp[i] = all[i];
    }
    //TODO: make tmp by jh
    for(int t = 0;t < m;t ++) {
        if((jh >> t) & 1)
            continue;
        for(int i = 0;i < n;i ++)
            tmp[i] |= (1 << t);
    }
    //TODO: unique
    sort(tmp, tmp + n);
    int l = 0,r = 0;
    int tot = 0;
    while(true) {
        while(tmp[l] == tmp[r])
            r ++;
        if(r > n)
            break;
        tmp[tot ++] = r - l;
        l = r;
    }
    //TODO: get ans
    int ans = 0;
    for(int i = 0;i < tot;i ++)
        for(int j = i + 1;j < tot;j ++)
            ans += tmp[i] * tmp[j];
    return ans >= k;
}

int solve() {
    int ans = 0;
    for(int i = 0;i < (1 << m);i ++) {
        ans += solve(i);
    }
    return ans;
}

int T;
int main() {
    scanf("%d", &T);
    for(int t = 1;t <= T;t ++) {
        memset(all, 0, sizeof(all));
        scanf("%d %d %d",&n, &m, &k);
        for(int i = 0;i < n;i ++) {
            for(int j = 0;j < m;j ++) {
                char t = getchar();
                while(!isalpha(t))
                    t = getchar();
                if(t == 'A')
                    all[i] |= (1 << j);
            }
        }
        printf("Case #%d: %d
", t,solve());
    }
}

T2
emmmm T2 는 약간 구덩이 가 있 죠? 사전 순서 가 가장 작은 것 은 당연히 알파벳 입 니 다!그리고 접두사 26 개 랑... 잘 써 요.

#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 100000 + 5;
int T;
int sum[26][MAXN];
int n,q;
char c[MAXN];
int main()
{
    scanf("%d",&T);
    for(int t = 1;t <= T; t ++)
    {
        printf("Case #%d:
",t);
        scanf("%d %d",&n,&q);
        memset(sum,0,sizeof(sum));
        for(int i = 1;i <= n;i ++)
        {
            c[i] = getchar();
            while(!isalpha(c[i]))
                c[i] = getchar();
        }
        for(int i = 1;i <= n;i ++)
            sum[c[i] - 'A'][i] ++;
        for(int j = 0;j < 26;j ++)
            for(int i = 1;i <= n;i ++)
                sum[j][i] += sum[j][i - 1];
        int a,b;
        while(q --)
        {
            scanf("%d %d",&a,&b);
            for(int i = 0;i < 26;i ++)
                if(sum[i][b] - sum[i][a - 1])
                {
                    printf("%d
", sum[i][b] - sum[i][a - 1]);
                    break;
                }
        }
    }
    return 0;
}

T3
이것 은 이분 도 일치 합 니까?아니면 네트워크 흐름?모 르 겠 어 요. 문제 풀이 기다 리 는 거 아니 죠?
T4
치 료 를 포기 하고 문 제 를 해결 할 수 있 습 니까?
T5
T6
출석 체크 해 주세요......................................................................................

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 100000 + 5;
int n,m;
struct edge
{
    int f,t,v;
    char c;
    bool operator < (const edge &b)const
    {
        return v < b.v;
    }
}e[MAXN];
struct bcj
{
    int fa[MAXN];
    void init()
    {
        for(int i = 1;i <= n;i ++)
            fa[i] = i;
        return;
    }
    int find(int x)
    {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    bool same(int x,int y)
    {
        return find(x) == find(y);
    }
    void merge(int x,int y)
    {
        x = find(x);
        y = find(y);
        fa[x] = y;
        return;
    }
}b;
int ans[MAXN],tmp[MAXN];
queue <int> q;
int kru()
{
    int tot = 0,count = 0;
    sort(e + 1, e + m + 1);
    b.init();
    while(!q.empty())
        q.pop();
    for(int i = 1;i <= m;i ++)
    {
        if(e[i].c != 'B' && !b.same(e[i].f, e[i].t))
        {
            tot += e[i].v;
            count ++;
            b.merge(e[i].f, e[i].t);
        }
        else
            q.push(e[i].v);
    }
    return count == n - 1 ? tot : -1;
}
void tj()
{
    int t = kru();
    if(t == -1)
    {
        for(int i = 1;i <= m;i ++)
            ans[i] = -1;
        return;
    }
    for(int i = 1;i < n - 1;i ++)
        ans[i] = -1;
    ans[n - 1] = t;
    for(int i = n;i <= m;i ++)
    {
        ans[i] = ans[i - 1] + q.front();
        q.pop();
    }
    return;
}
void change(int x)
{
    switch (e[x].c)
    {
        case 'B':e[x].c = 'R';break;
        case 'R':e[x].c = 'B';break;
        default:break;
    }
    return;
}
int really(int i)
{
    if(ans[i] == -1)
        return tmp[i];
    if(tmp[i] == -1)
        return ans[i];
    return min(ans[i],tmp[i]);
}
int T;
int main()
{
    scanf("%d",&T);
    for(int t = 1;t <= T;t ++)
    {
        printf("Case #%d:
",t);
        scanf("%d %d",&n,&m);
        memset(tmp,0,sizeof(tmp));
        memset(ans,0,sizeof(ans));
        for(int i = 1;i <= m;i ++)
            scanf("%d %d %d %c",&e[i].f, &e[i].t, &e[i].v, &e[i].c);
        tj();

        for(int i = 1;i <= m;i ++)
            change(i);
        for(int i = 1;i <= m;i ++)
            tmp[i] = ans[i];
        tj();

        for(int i = 1;i <= m;i ++)
            ans[i] = really(i);
        for(int i = 1;i <= m;i ++)
            printf("%d
",ans[i]);
    }
    return 0;
}