2016百度の星資格試合

怠け者になって、最近やった多くの問題は貼りたくない.ただでさえ怠けていたのに、助からなかった.Aはあまり考えていないので,逆元を設けて過ぎた.
Bフィボナッチ数列高精度.n==0で改行を出力します...
C辞書ツリーでは、ノードの単語数と現在のノードが単語の末尾であるかどうかを記録し、deleteの場合、接頭辞に対応するシリアル数を先に見つける必要があります.では、DFSで末尾ノードの総数を統計し、接頭辞で減らせばいいです.最初はDFSが走っていた時にdeleteの結点を外していませんでした(SBでしょう)が、951 msを強引に通り過ぎてしまい、その後用事がなくて265 msを改めて走りました...

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define CLR(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int MAXN = 3 * 1e6 + 10;
const int MOD = 9973;
const int INF = 0x3f3f3f3f;
int sum;
struct Trie {
    int L, next[MAXN][30], root, word[MAXN], End[MAXN];
    int newnode() {
        for(int i = 0; i <= 25; i++) next[L][i] = -1;
        word[L] = 0; End[L] = 0; L++;
        return L-1;
    }
    void init() { L = 0; root = newnode(); }
    void Insert(char *s) {
        int u = root;
        for(int i = 0; s[i]; i++) {
            int v = s[i] - 'a';
            if(next[u][v] == -1)
                next[u][v] = newnode();
            u = next[u][v];
            word[u]++;
        }
        End[u]++;
    }
    void DFS(int u) {
        sum += End[u]; word[u] = 0; End[u] = 0;
        for(int i = 0; i <= 25; i++) {
            if(next[u][i] != -1) {
                DFS(next[u][i]);
                next[u][i] = -1;
            }
        }
    }
    void Delete(char *s) {
        int u = root; sum = 0;
        for(int i = 0; s[i]; i++) {
            int v = s[i] - 'a';
            if(next[u][v] == -1) return ;
            u = next[u][v];
        }
        DFS(u); u = root;
        for(int i = 0; s[i]; i++) {
            int v = s[i] - 'a';
            u = next[u][v];
            //cout << word[u] << endl;
            word[u] -= sum;
        }
        word[u] += sum;
    }
    bool Query(char *s) {
        int u = root;
        for(int i = 0; s[i]; i++) {
            int v = s[i] - 'a';
            u = next[u][v];
            //cout << word[u] << endl;
            if(word[u] == 0 || u == -1) return false;
        }
        return true;
    }
};
Trie T;
int main()
{
    int n;
    while(scanf("%d", &n) != EOF) {
        char op[10], str[100];
        T.init();
        while(n--) {
            scanf("%s%s", op, str);
            if(op[0] == 'i') {
                T.Insert(str);
            }
            else if(op[0] == 'd') {
                T.Delete(str);
            }
            else {
                printf(T.Query(str) ? "Yes
" : "No
");
            }
        }
    }
    return 0;
}

D mapちょっとでいい
E各条件のサブ条件間が和であるため、各条件が合法であるか否か(2つのサブ条件が矛盾する可能性がある場合)を先に判断することができる.条件i,jの判定については、iの1つのサブ条件とjの1つのサブ条件が矛盾しているか、またはi(j)が1つ自体が不法である限り、iとjは交差しない.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define CLR(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int MAXN = 3 * 1e6 + 10;
const int MOD = 9973;
const int INF = 0x3f3f3f3f;
struct Node {
    char var[20];
    int digit, op;
};
Node num[1010][40];
int cnt[1010];
void Solve(char *s, int id) {
    int top = 0; cnt[id] = 0; num[id][cnt[id]].op = 0;
    int len = strlen(s), mark = 0, sum = 0, sign = 1;
    s[len] = ',';
    for(int i = 0; i <= len; i++) {
        if(s[i] == ',') {
            num[id][cnt[id]].digit = sum * sign;
            cnt[id]++; top = mark = 0;
            num[id][cnt[id]].op = 0;
            sum = 0; sign = 1;
        }
        else if(s[i] == ' ') {
            if(s[i+1] != ' ') {
                if(mark == 1) {
                    num[id][cnt[id]].var[top] = 0;
                }
            }
        }
        else if(s[i] == '>') {
            mark = 2;
            num[id][cnt[id]].op = 1;
        }
        else if(s[i] == ') {
            mark = 2;
            num[id][cnt[id]].op = 2;
        }
        else if(s[i] == '=') {
            mark = 2;
            num[id][cnt[id]].op += 3;
        }
        else if(s[i] == '-' || (s[i] >= '0' && s[i] <= '9')) {
            mark = 3;
            if(s[i] == '-') {
                sign = -1;
                continue;
            }
            sum = sum * 10 + (s[i] - '0');
        }
        else {
            mark = 1;
            num[id][cnt[id]].var[top++] = s[i];
        }
    }
}
// > 1 < 2 = 3 >= 4 <= 5 == 6
bool Check(int op1, int v1, int op2, int v2) {
    if(op1 == 1) {
        if(op2 == 2 && v2 <= v1 + 1) {
            return false;
        }
        if(op2 == 5 || op2 == 6) {
            if(v2 <= v1) {
                return false;
            }
        }
    }
    if(op1 == 2) {
        if(op2 == 1 && v2 >= v1 + 1) {
            return false;
        }
        if(op2 == 4 || op2 == 6) {
            if(v2 >= v1) return false;
        }
    }
    if(op1 == 4) {
        if(op2 == 2 && v2 <= v1) {
            return false;
        }
        if(op2 == 5 || op2 == 6) {
            if(v2 < v1) {
                return false;
            }
        }
    }
    if(op1 == 5) {
        if(op2 == 1 && v2 >= v1) {
            return false;
        }
        if(op2 == 4 || op2 == 6) {
            if(v2 > v1) return false;
        }
    }
    if(op1 == 6) {
        if(op2 == 1 && v2 >= v1) {
            return false;
        }
        if(op2 == 2 && v2 <= v1) {
            return false;
        }
        if(op2 == 4 && v2 > v1) {
            return false;
        }
        if(op2 == 5 && v2 < v1) {
            return false;
        }
        if(op2 == 6 && v2 != v1) {
            return false;
        }
    }
    return true;
}
bool judge(int x, int y) {
    for(int i = 0; i < cnt[x]; i++) {
        for(int j = 0; j < cnt[y]; j++) {
            if(strcmp(num[x][i].var, num[y][j].var) == 0) {
                if(!Check(num[x][i].op, num[x][i].digit, num[y][j].op, num[y][j].digit)) {
                    return false;
                }
            }
        }
    }
    return true;
}
char str[101000];
int rec[1010];
bool vis[1010];
int main()
{
    int n;
    while(scanf("%d", &n) != EOF) {
        getchar();
        for(int i = 1; i <= n; i++) {
            gets(str); Solve(str, i);
//            for(int j = 0; j < cnt[i]; j++) {
//                printf("%s %d %d
", num[i][j].var, num[i][j].op, num[i][j].digit);
//            }
            vis[i] = judge(i, i);
            if(vis[i] == false) {
                printf("unique
");
                continue;
            }
            int m = 0; bool flag = false;
            for(int j = 1; j < i; j++) {
                if(vis[j] == false) continue;
                if(judge(i, j)) {
                    rec[++m] = j;
                    flag = true;
                }
            }
            if(!flag) {
                printf("unique
");
            }
            else {
                for(int j = 1; j <= m; j++) {
                    if(j > 1) printf(" ");
                    printf("%d", rec[j]);
                }
                printf("
");
            }
        }
    }
    return 0;
}