【CSP】90%解压缩&80%化学方程式 两道大模拟

大模拟就没什么太多说的了，《解压缩》需要用一点位运算，《化学方程式》需要用字符串。

学到的主要经验就是，使用次数>2的功能拆分到不同函数内，并且对于难写的函数提前单独调试错误，不要等写完了再debug。

对于《化学方程式》，我使用模块化思想。第一步拆成不同的项，把系数缓存起来，然后对项（如Au(Ag(CN)2) ）先序列化（S = Au,"(",Ag,"(",C,N,")",2,")"），然后对其进行括号栈分析。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string.h>

#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=r;i>=l;i--)

typedef long long ll;

using namespace std;

inline int _max(const int& a,const int& b){return a>b?a:b;}
inline int _min(const int& a,const int& b){return a<b?a:b;}

const int MAXN = 3000020;
inline int normal(int& x){
    x = x&256;
    return x;
}

int p2[12] = {0,1,3,7,15,31,63,127,255,511,1023,2047};

int bts[MAXN],s;
int op[MAXN],ocnt;

int total = 0;

inline int highn(int x,int n){
    return x>>(8-n);
}

inline int lown(int x,int n){
    return x&p2[n];
}

void prbyte(int x){
    cout<<"[";
    bool tmp[8];
    dn(0,7,i){
        tmp[i] = x%2;
        x/=2;
    }
    up(0,7,i) cout<<tmp[i];
    cout<<"]";
}

int pcnt = 0;
void pbyte16(int x){
    if(pcnt >= 8 && ocnt < total-1){
        cout<<endl;
        pcnt = 0;
    }
    int a = highn(x,4);
    int b = lown(x,4);
    char c,d;
    if(a > 9) c = a-10+'a';
    else c = a+'0';
    if(b > 9) d = b-10+'a';
    else d = b+'0';
    cout<<c<<d;
    pcnt++;
}

inline int getbyte(char a,char b){
    int ret = 0;
    if(a >= '0' && a <= '9') ret += (int)(a-'0')*16;
    else ret += (int)(10+a-'a')*16;
    if(b >= '0' && b <= '9') ret += (int)(b-'0');
    else ret += (int)(10+b-'a');
    return ret;
}

void element(int &cnt){
    int l = 0;
    if(lown(bts[cnt],2) == 0){
        l = highn(bts[cnt],6);
        //printf("\ncnt=%d,进入字面值,高六位为%d\n",cnt,l);
        int del = l - 59;
        int k = 1;
        cnt++;
        if(del > 0) l = 0;
        while(del>0){
            l += k*bts[cnt];
            k *= 256;
            del--;
            cnt++;
        }
        l++;
        //printf("\ncnt=%d,字面值长度l=%d\n",cnt,l);
        while(l){
            l--;
            //printf("[l=%d]",l);
            op[ocnt++] = bts[cnt];
            pbyte16(bts[cnt]);
            cnt++;
        }
    }
    else if(lown(bts[cnt],2) == 1){
        int o;
        o = bts[cnt+1];
        o += highn(bts[cnt],3)*256;
        l = lown(bts[cnt],5)>>2;
        l += 4;
        //printf("\ncnt=%d,进入回溯引用1,l=%d,o=%d\n",cnt,l,o);
        int cnt2 = ocnt-o;//-1+1
        int tmp = ocnt-1;
        while(l){
            if(cnt2 > tmp) cnt2 = tmp-o+1;
            op[ocnt++] = op[cnt2++];
            pbyte16(op[ocnt-1]);
            l--;
        }
        cnt += 2;
    }
    else if(lown(bts[cnt],2) == 2){
        l = highn(bts[cnt],6)+1;
        int o = bts[++cnt];
        o += bts[++cnt]*256;
        int cnt2 = ocnt-o;//-1+1
        int tmp = ocnt-1;
        //printf("\ncnt=%d,进入回溯引用2,l=%d,o=%d\n",cnt,l,o);
        while(l){
            if(cnt2 > tmp) cnt2 = tmp-o+1;
            op[ocnt++] = op[cnt2++];
            pbyte16(op[ocnt-1]);
            l--;
        }
        cnt++;
    }
}

void solve(){
    int cnt = 0;
    int k = 1;
    while(highn(bts[cnt],1)){
        total += k*lown(bts[cnt],7);
        cnt++;
        k *= 128;
    }
    total += k*lown(bts[cnt],7);
    //printf("\ncnt=%d,引导区结束\n",cnt);
    cnt++;//现在cnt为数据域的第一位
    while(cnt < s-1){
        element(cnt);
    }
}

int main()
{
    //freopen("y.in","r",stdin);
    //freopen("y.out","w",stdout);

    //ios::sync_with_stdio(false);

    cin>>s;
    getchar();
    char a,b;
    up(0,s-1,i){
        a = getchar();
        if(a == '\n') {i--;continue;}
        b = getchar();
        bts[i] = getbyte(a,b);
    }

    solve();





    return 0;
}

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string.h>
#include <map>
#include <stdlib.h>
#include <vector>

#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=r;i>=l;i--)

typedef long long ll;

using namespace std;

inline int _max(const int& a,const int& b){return a>b?a:b;}
inline int _min(const int& a,const int& b){return a<b?a:b;}

int state = 0;//0 - > 等待新项
              //1 - > 正在读取项

int N;
inline bool isnum(char c){
    return (c>='0'&&c<='9');
}

map<string,int> equa;

struct Ele{
    int type;//0 == num, 1 = element, -n~n为括号级数(n>=2)
    int n;
    string ele;
};

struct Pr{
    int f,s;
};

Ele create(int t,int n,string e){
    Ele ret;
    ret.type = t;
    ret.n = n;
    ret.ele = e;
    return ret;
}

          
bool solve(string &s){
    int len = s.length();
    int k = 1;
    int ca = 0;//缓存
    up(0,len-1,i){
        if(state == 0){
            if(isnum(s[i])){
                int off = 1;
                while(i+off<len && isnum(s[i+off])){
                    off++;
                }
                string num = s.substr(i,off);
                ca = atoi(num.c_str());
                i += off;
                i--;//因为i++
                state = 1;
            }
            else{
                state = 1;
                ca = 1;
                i--;
            }
        }
        else if(state == 1){
            int off = 1;
            while(i+off<len && s[i+off]!='+' && s[i+off]!='='){
                off++;
            }
            string ele = s.substr(i,off);
            
            //TODO = 实现计算元素
            vector<Ele> seq;
            vector<int> sta;
            int cnt = 2;
            string x = "";
            up(0,ele.length()-1,j){
                if(ele[j] == '(') {
                    seq.push_back(create(cnt,0,x));
                    sta.push_back(cnt++);
                }
                else if (ele[j] == ')'){
                    int c = sta[sta.size()-1];
                    sta.pop_back();
                    seq.push_back(create(-c,0,x));
                }
                else if(isnum(ele[j])){
                    int of = 1;
                    while(j+of<len && isnum(ele[j+of])){
                        of++;
                    }
                    string num = ele.substr(j,of);
                    int numnum = atoi(num.c_str());
                    j += of;
                    j--;//因为i++
                    seq.push_back(create(0,numnum,x));
                }
                else{
                    string ee;
                    ee += ele[j];
                    if(j+1<ele.length() && ele[j+1] >= 'a' && ele[j+1] <= 'z') {ee += ele[j+1];j++;}
                    seq.push_back(create(1, 1, ee));
                }
            }

            for(auto it = seq.begin(); it != seq.end() ; it++){
                if(it->type == 1) continue;
                else if(it->type == 0){
                    auto it2 = it-1;
                    if(it2->type == 1){
                        it2->n *= it->n;
                    }
                }
                else{
                    if(it == seq.end()-1) continue;
                    if((it+1)->type == 1) continue;
                    int kk = (it+1)->n;
                    int cnt = it->type;
                    for(auto it2 = it-1; it2 != seq.begin()-1; it2--){
                        if(it2->type == -cnt) break;
                        if(it2->type == 1) it2->n *= kk;
                    }
                }

            }
            /*for(auto it = seq.begin(); it != seq.end() ; it++){
                if(it->type == 1){
                    printf("[%s,%d]",it->ele.c_str(),it->n);
                }
            }*/



            
            for(auto it = seq.begin(); it != seq.end() ; it++){
                if(it->type == 1){
                    //printf("k=%d,ca=%d\n",k,ca);
                    equa[it->ele] += k*ca*it->n;
                }
            }

            if(s[i+off] == '='){
                k = -1;
            }
            state = 0;
            i += off;
        }
    }
    for(auto it = equa.begin();it != equa.end(); it++){
        //printf("[%s,%d]",it->first.c_str(),it->second);
        if(it->second != 0) {return false;}
    }
    return true;
}

int main()
{
    //freopen("y.in","r",stdin);

    //ios::sync_with_stdio(false);

    cin>>N;
    getchar();
    
    up(1,N,i){
        string s;
        getline(cin,s);
        cout<<(solve(s)?"Y":"N")<<endl;
        equa.clear();
    }

    return 0;
}

虽说不太愿意写， 但听歌写这种玩意反而有种奇妙的快感（？

P.S.以前不重视STL，现在发现真好用。另外ios::sync_with_stdio(false)在ccf的机器上会有时会导致爆0，惨痛教训。