比赛地址

牛客OJ

Pro: 3/3/11

Rank: 55/685

[G] Game SET

题意

给出一些扑克牌,牌面上有四个属性,每种属性有三种可能的取值,还可能是通配符.问能否选出三张牌,使得它们每个属性都互不相同或者完全一样.

题解

直接暴力枚举后两张牌是什么,枚举过的牌按照所有可能的贡献加到一个集合里,之后枚举的时候就可以O(1)检测了.

代码

#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define IL inline
#define reg register
#define N 266
using namespace std;

int T,n,i;
char c[N];
int v[5][5][5][5];

struct Data{
    int f[5];
}a[N];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

IL void Work(int x){
    reg int i=0,len=strlen(c),s=0;
    for (i=0;i<len;i++){
        if (c[i]=='['){
            s++;    i++;
            if (c[i]=='*')  a[x].f[s]=0;
            else {
                if (s==1){
                    i++;
                    if (c[i]=='n')  a[x].f[s]=1;
                    if (c[i]=='w')  a[x].f[s]=2;
                    if (c[i]=='h')  a[x].f[s]=3;
                }   else if (s==2){
                    if (c[i]=='d')  a[x].f[s]=1;
                    if (c[i]=='s')  a[x].f[s]=2;
                    if (c[i]=='o')  a[x].f[s]=3;
                }   else if (s==3){
                    i++;
                    if (c[i]=='o')  a[x].f[s]=1;
                    if (c[i]=='t')  a[x].f[s]=2;
                    if (c[i]=='p')  a[x].f[s]=3;
                }   else {
                    if (c[i]=='r')  a[x].f[s]=1;
                    if (c[i]=='g')  a[x].f[s]=2;
                    if (c[i]=='p')  a[x].f[s]=3;                    
                }
            }
        }
    }
//  cout<<a[x].f[1]<<" "<<a[x].f[2]<<" "<<a[x].f[3]<<" "<<a[x].f[4]<<endl;
}

IL void Insert(int x){
    reg int i=0,j=0,k=0,g=0;
    for (i=0;i<=3;i++){
        if (i && a[x].f[1] && i!=a[x].f[1]) continue;
        for (j=0;j<=3;j++){
            if (j && a[x].f[2] && j!=a[x].f[2]) continue;
            for (k=0;k<=3;k++){
                if (k && a[x].f[3] && k!=a[x].f[3]) continue;
                for (g=0;g<=3;g++){
                    if (g && a[x].f[4] && g!=a[x].f[4]) continue;
                    v[i][j][k][g]=x;
                }
            }
        }
    }
}

IL void Cal(){
    reg int i=0,j=0,p=0,q=0,s=0,w=0;
    memset(v,0,sizeof(v));
    Insert(1);
    for (i=2;i<=n;i++){
        for (j=i+1;j<=n;j++){
            if (!a[i].f[1] || !a[j].f[1])   p=0;
            else if (a[i].f[1]==a[j].f[1])  p=a[i].f[1];
            else p=a[i].f[1]^a[j].f[1];

            if (!a[i].f[2] || !a[j].f[2])   q=0;
            else if (a[i].f[2]==a[j].f[2])  q=a[i].f[2];
            else q=a[i].f[2]^a[j].f[2];

            if (!a[i].f[3] || !a[j].f[3])   s=0;
            else if (a[i].f[3]==a[j].f[3])  s=a[i].f[3];
            else s=a[i].f[3]^a[j].f[3];

            if (!a[i].f[4] || !a[j].f[4])   w=0;
            else if (a[i].f[4]==a[j].f[4])  w=a[i].f[4];
            else w=a[i].f[4]^a[j].f[4];
            if (v[p][q][s][w]){
                //cout<<p<<" "<<q<<" "<<s<<" "<<w<<endl;
                printf("%d %d %d\n",v[p][q][s][w],i,j);
                goto END;
            }
        }
        Insert(i);
    }
    puts("-1");
    END:;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    for (int t=1;t<=T;t++){
        printf("Case #%d: ",t);
        n=read();
        for (i=1;i<=n;i++){
            scanf("%s",&c);
            Work(i);
        }
        if (n<=2){
            puts("-1");
            continue;
        }
        Cal();
    }
    return 0;
}

[I] Interesting Computer Game

题意

n轮游戏,每一轮会给出两个数字,每一次只能选择一个从没选过的数字,或者什么都不做.问最后最多选出几个数字.

题解

将同一轮出现的数字视为两个点与一条边,然后生成的图如果有环的话,环上所有的数字都能选上,否则会少选一个.DFS求一遍即可.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
int flag, a[100005], b[100005], used[200005];
int tot, fir[400005], nxt[400005], adj[400005], cnt, tab[400005];
map <int, int> M;
void add(int a, int b) {
    adj[++tot] = b;
    nxt[tot] = fir[a];
    fir[a] = tot;
    tab[tot] = cnt;
}

int dfs(int a, int from) {
    used[a] = 1;
    int ret = 1;
    for (int t = fir[a]; t; t = nxt[t]) {
        if (used[adj[t]]) {
            if (tab[t] != from) flag = 1;
            continue;
        }
        ret += dfs(adj[t], tab[t]);
    }
    return ret;
}

int main(){
    int T; cin >> T; for (int TT = 1; TT <= T; TT++) {
        int n; scanf("%d", &n);
        int id = 0; M.clear();
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &a[i], &b[i]);
            if (!M[a[i]]) M[a[i]] = ++id;
            if (!M[b[i]]) M[b[i]] = ++id;
        }
        for (int i = 1; i <= n; i++) { a[i] = M[a[i]]; b[i] = M[b[i]]; }
        tot = cnt = 0;
        for (int i = 1; i <= 200000; i++) used[i] = 0;
        for (int i = 1; i <= 400000; i++) fir[i] = nxt[i] = adj[i] = 0;
        for (int i = 1; i <= n; i++) { cnt++; add(a[i], b[i]); add(b[i], a[i]); }
        int ans = 0;
        for (int i = 1; i <= id; i++) if (used[i] == 0) {
            flag = 0;
            ans += dfs(i, 0) - 1;
            ans += flag;
        }
        printf("Case #%d: %d\n", TT, ans);
    }
    return 0;
}

[K] Kabaleo Lite

题意&题解

签到题

中间计算结果会爆long long,需要用int128来储存.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;

__int128_t a[100005], b[100005], val[100005], num[100005], ans;
long long int p;

inline void Write(__int128_t x) {
    static int sta[22];
    register int top=0;
    if (x<0)    {putchar('-');  x=-x;}
    do{
        sta[top++]=x%10,x/=10;
    }while (x);
    while (top) putchar(sta[--top]+48);
}

int main(){
    int T; cin >> T; for (int TT = 1; TT <= T; TT++) {
        int n; scanf("%d", &n);
        for (int i = 1; i <= n; i++) { scanf("%lld", &p); a[i] = p; a[i] += a[i-1]; }
        for (int i = 1; i <= n; i++) { scanf("%lld", &p); b[i] = p; if (i > 1 && b[i] > b[i-1]) b[i] = b[i-1];}
        for (int i = 0; i <= n+1; i++) val[i] = num[i] = 0;
        int tot = 1; ans = 0;
        val[1] = a[1]; num[1] = b[1];
        for (int i = 2; i <= n; i++) {
            if (a[i] > val[tot]) {
                tot++;
                val[tot] = a[i];
                num[tot] = b[i];
            }
        }
        for (int i = tot; i >= 1; i--) ans += val[i] * (num[i] - num[i+1]);
        printf("Case #%d: ", TT);
        Write(b[1]); printf(" "); Write(ans); printf("\n");
    }
    return 0;
}

总结

区分度不太友好的一场.主要暴露的问题是知识面有些狭窄.例如A题是一个离线的动态图连通性问题,可以用线段树+可撤销并查集解决,算是一个比较裸的题目,但是比赛中因为不知道这个手法一度认为不可做.之后看来要着重补一下考察频率较高的知识点.

说点什么
支持Markdown语法
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...