NOIP 2023 游记

ZJGpyc · 2023-11-18 17:12:55 · 个人记录

NOIP 2023 游记

备注：笔者高二，竞赛已一年，比完退役。

早上

起床发现6:40 匆忙下床 7:00机房集合

早饭是两块面包喝了一罐牛奶然而是冷的来不及喝完就走人了

入场

T1

开题即做

鉴定为：字符串内部排序再将各个串的最小排列与最大排列比较

代码如下： ```cpp #include <iostream> #include <string> #include <set> #include <algorithm> using namespace std; int n, m; char minest[3030][3030]; char maxest[3030][3030]; string minstr[3030]; string maxstr[3030]; multiset<string> workingspace; int main(){ freopen("dict.in", "r", stdin); freopen("dict.out", "w", stdout); cin>>n>>m; for (int i=0; i<n; i++){ cin>>minest[i]; sort(minest[i], minest[i]+m); for (int j=0;j<m;j++){ maxest[i][j]=minest[i][m-j-1]; } minstr[i] = string(minest[i]); maxstr[i] = string(maxest[i]); workingspace.insert(maxstr[i]); } for (int i=0;i<n;i++){ workingspace.erase(maxstr[i]); workingspace.insert(minstr[i]); if (*(workingspace.begin())==minstr[i]) cout<<'1'; else cout<<'0'; workingspace.erase(minstr[i]); workingspace.insert(maxstr[i]); } fclose(stdin); fclose(stdout); return 0; } ``` 写着写着肚子疼没去厕所自己好了对拍程序计时大样例1.2s 没管先写T2去了 #### T2 烦内先看T3 #### T3 一番思考认为 $ dp_{i,j} \rightarrow dp_{i+1,j}, dp_{i,j+1}

然而真的开DP数组空间指定爆炸于是使用BFS

但是BFS依然不能去重直接用DFS

bool inrule(int idX, int idY, bool cmprule){
    if (seqX[idX]==seqY[idY]) return false;
    return ((seqX[idX]<seqY[idY])==cmprule);
}
bool answer;
void dfs(int xi, int yi, bool crule){
    if (xi>n or yi>m) return;
    if (xi==n and yi==m) {
        answer = true; return;
    }
    if (inrule(xi, yi+1, crule) && (!answer)) dfs(xi, yi+1, crule);
    if (inrule(xi+1, yi, crule) && (!answer)) dfs(xi+1, yi, crule);
}

基本写完后测试发现样例1、2正常过，样例3直接栈溢出

没管去看T2

T2

先打case 3、4

cin>>Cas>>T;
char opt; int u, v;
if (Cas == 3 || Cas == 4) {
    while (T--){
        cin>>n>>m;
        for (int i=1;i<=n;i++) reftab[i].sign='/';

        for (int i=0;i<m;i++){
            cin>>opt>>u;
            reftab[u].sign = opt;
        }
        int answer = 0;
        for (int i=1;i<=n;i++) answer += (reftab[i].sign=='U'?1:0);
        cout<<answer<<endl;
    }
}

草稿纸上一通比划决定使用

const int maxn = (int)1e5 + 114;
struct valref{
    int bindwith;
    char sign;
};
valref reftab[maxn];

来模拟，其中 bindwith=i 表示赋值为 x_i ， sign 表示 '+'或'-' 常量使用 bindwith=0 sign='U'/'T'/'F'

多次费劲的调试后：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int Cas, T;
int n, m;
const int maxn = (int)1e5 + 114;
struct valref{
    int bindwith;
    char sign;
};
valref reftab[maxn];
char reverse(char cc) {
    if (cc=='U') return 'U';
    if (cc=='T') return 'F';
    if (cc=='F') return 'T';
    if (cc=='+') return '-';
    if (cc=='-') return '+';
    return '?';
}
int main(){
    freopen("tribool.in", "r", stdin);
    freopen("tribool.out", "w", stdout);
    cin>>Cas>>T;
    char opt; int u, v;
    if (Cas == 3 || Cas == 4) {
        while (T--){
            cin>>n>>m;
            for (int i=1;i<=n;i++) reftab[i].sign='/';

            for (int i=0;i<m;i++){
                cin>>opt>>u;
                reftab[u].sign = opt;
            }
            int answer = 0;
            for (int i=1;i<=n;i++) answer += (reftab[i].sign=='U'?1:0);
            cout<<answer<<endl;
        }
    } else {
        while (T--){
            cin>>n>>m;
            for (int i=0;i<=n;i++){
                reftab[i].bindwith=i;
                reftab[i].sign = '+';
            }
            for (int i=0;i<m;i++){
                cin>>opt;
                switch (opt) {
                    case 'T':
                    case 'F':
                    case 'U':{
                        cin>>u;
                        reftab[u].bindwith=0;
                        reftab[u].sign = opt;
                        break;
                    }
                    case '+':
                    case '-':{
                        cin>>u>>v;
                        while (reftab[v].bindwith!=v and reftab[v].bindwith!=0) {
                            if (opt == reftab[v].sign) opt='+';
                            else opt='-';
                            v=reftab[v].bindwith;
                        }
                        if (reftab[v].bindwith != 0){
                            reftab[u].bindwith=v;
                            reftab[u].sign=opt;
                        } else {
                            reftab[u].bindwith=0;
                            if (reftab[u].sign == '-') reftab[u].sign=reverse(reftab[v].sign);
                            else reftab[u].sign=reftab[v].sign;
                        }
                        break;
                    }
                }
            }
            int answer = 0;
            for (int i=1;i<=n;i++) {
                if (reftab[i].bindwith==i && reftab[i].sign=='-') {
                    reftab[i].bindwith=0; reftab[i].sign='U';
                }
            }
            for (int ti=1;ti<=n;ti++){
                for (int i=1;i<=n;i++){
                    if (reftab[i].bindwith==i) continue;
                    if (reftab[i].bindwith==0) continue;
                    if (reftab[reftab[i].bindwith].bindwith != 0)
                        reftab[i].sign = (reftab[i].sign==reftab[reftab[i].bindwith].sign?'+':'-');
                    else reftab[i].sign =
                        (reftab[i].sign=='+'?reftab[reftab[i].bindwith].sign:reverse(reftab[reftab[i].bindwith].sign));
                    reftab[i].bindwith = reftab[reftab[i].bindwith].bindwith;
                }
            }
            for (int i=1;i<=n;i++) answer+=(reftab[i].sign=='U'?1:0);
            cout<<answer<<endl;
        }
    }
    return 0;
}

样例只过了1和2

中途还灵机一动去改T1

#include <iostream>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
int n, m;
char minest[3030][3030];
char maxest[3030][3030];
string minstr[3030];
string maxstr[3030];
multiset<string> workingspace;
int main(){
    freopen("dict.in", "r", stdin);
    freopen("dict.out", "w", stdout);
    cin>>n>>m;
    if (n==1) {
        cout<<'1'<<endl; return 0;
    }
    int minix1, minix2;
    bool find1=false, find2=false;
    for (int i=0; i<n; i++){
        cin>>minest[i];
        sort(minest[i], minest[i]+m);
        for (int j=0;j<m;j++){
            maxest[i][j]=minest[i][m-j-1];
        }
        minstr[i] = string(minest[i]);
        maxstr[i] = string(maxest[i]);
        if (not find1) {
            minix1 = i; find1 = true;
        } else if (not find2) {
            minix2 = i; find2 = true;
            if (maxstr[minix1] > maxstr[minix2]) {
                swap(minix1, minix2);
            }
        } else {
            if (maxstr[i] < maxstr[minix1]) {
                minix2 = minix1; minix1 = i;
            } else if (maxstr[i] < maxstr[minix2]) {
                minix2 = i;
            }
        }
    }
    for (int i=0;i<n;i++){
        if (i==minix1) {
            if (minstr[i] < maxstr[minix2]) cout<<'1';
            else cout<<'0';
        }
        else if (minstr[i] < maxstr[minix1]) cout<<'1';
        else cout<<'0';
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}

然后给T3加部分记忆化

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int maxsize = 500010;
int n, m;
int c, q;
int backupX[maxsize], backupY[maxsize];
int seqX[maxsize], seqY[maxsize];
vector<char> anss;
bool inrule(int idX, int idY, bool cmprule){
    if (seqX[idX]==seqY[idY]) return false;
    return ((seqX[idX]<seqY[idY])==cmprule);
}
bool answer;
bool vis[20020][20020];
void dfs(int xi, int yi, bool crule){
    if (xi>n or yi>m) return;
    if (xi==n and yi==m) {
        answer = true; return;
    }
    if (xi<20000 and yi<20000){
        if (vis[xi][yi]) return;
        vis[xi][yi]=true;
    }
    if (inrule(xi, yi+1, crule) && (!answer)) dfs(xi, yi+1, crule);
    if (inrule(xi+1, yi, crule) && (!answer)) dfs(xi+1, yi, crule);
}
int main(){
    freopen("expand.in", "r", stdin);
    freopen("expand.out", "w", stdout);
    cin>>c>>n>>m>>q;
    for (int i=1;i<=n;i++) cin>>seqX[i];
    for (int i=1;i<=n;i++) backupX[i]=seqX[i];
    for (int i=1;i<=m;i++) cin>>seqY[i];
    for (int i=1;i<=m;i++) backupY[i]=seqY[i];
    answer = false;
    if (seqX[1]!=seqY[1] and (seqX[1]<seqY[1])==(seqX[n]<seqY[m])) dfs(1, 1, (seqX[1]<seqY[1]));
    if (answer) anss.push_back('1');
    else anss.push_back('0');

    for (int j=0;j<=min(n, 20010);j++){
        for (int k=0;k<=min(m,20010);k++){
            vis[j][k]=false;
        }
    }

    for (int i=1, kx, ky;i<=q;i++) {
        cin>>kx>>ky;
        for (int j=0, px, vx;j<kx;j++){
            cin>>px>>vx;
            seqX[px]=vx;
        }
        for (int j=0, py, vy;j<ky;j++){
            cin>>py>>vy;
            seqY[py]=vy;
        }
        answer = false;
        if (seqX[1]!=seqY[1] and seqX[n]!=seqY[m]) {
            if ((seqX[1]<seqY[1]) == (seqX[n]<seqY[m]))
                dfs(1, 1, (seqX[1]<seqY[1]));
        }
        if (answer) anss.push_back('1');
        else anss.push_back('0');
        if (i!=q) {
            for (int j=1;j<=n;j++) seqX[j]=backupX[j];
            for (int j=1;j<=m;j++) seqY[j]=backupY[j];
            for (int j=0;j<=min(n, 20010);j++){
                for (int k=0;k<=min(m,20010);k++){
                    vis[j][k]=false;
                }
            }
        }
    }
    for (char cc:anss) cout<<cc;
    cout<<endl;
    fclose(stdin); fclose(stdout);
    return 0;
}

T4

最后五分钟乱写一通

#include <iostream>
#include <cstdio>
using namespace std;
int c, t;
int n, m, k, d;
int main(){
    freopen("run.in", "r", stdin);
    freopen("run.out", "w", stdout);
    cin>>c>>t;
    int x, y, v;
    int ans = 0;
    while (t--){
        cin>>n>>m>>k>>d;
        for (int i=0;i<m;i++){
            cin>>x>>y>>v;
            ans += v;
            ans -= y*d;
        }
        cout<<ans<<endl;
    }
    return 0;
}
// Have no time.
// I love you.
// AFO.

出场

回校喝早上的牛奶

回家