2023 NOIP 游寄

Expert_Dream · 2023-11-18 14:38:12 · 个人记录

我看看有多少人吊打我

Day -1：

复习了ST表，线段树，KMP，LCA，~~结果，一个都没考！！~~

Day 0：

再次复习，好像都会了，又好像都不会，思考了考场策略，然后就躺倒床上了。

Day 1：

六点半才起来，再复习了一下。

吃完早餐直奔yh。

7：30 来到了yh，一个人也没有，过了一会，z老师来咯，祝福了我然后就送我进考（xing）场。
8：00 跟 @hzlqwq 大佬一个考场，膜拜了一通，他却虚心地说只能做T1。

【T1】

8：30 终于开始了。。。
8：31 哇，T1 好水，直接开切。
9：30 为什么阳历都过不了？什么奇怪的东西？~~我甚至手玩了大样例~~
10：00 不对啊，我的程序对的啊，为啥阳历过不了？
10：10 重新看题：w'_i 看成了 w_i。。啊啊，难受啊。没事，只需要再维护最大值就好了。

10：15好吧，大样例过了，呃？大样例4s？不行，得卡常，卡卡卡卡，到了3s，卡不下去了。没事，这是i3-8，CCF 老爷机好歹是 i7-8 + O2。希望能过。。。

#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
int n,m;
pair<string,int> s[N];
int tt[35];
string s2[N];
bool check(int x){
if(s2[s[x].second] < s[1].first || (x==1 && s2[s[x].second] < s[2].first)) return true;
else return false;
}
bool cmp(pair<string,int> x,pair<string,int> y){
return x.first<y.first;
}
int vis[N];
char ch[N];
string ru[N];
int main(){
freopen("dict.in","r",stdin);
freopen("dict.out","w",stdout); 
scanf("%d%d",&n,&m);
for(int i =1;i <= n;i++) {
    scanf("%s",ch);
    ru[i]=ch;
}if(n==1){
    cout<<1;
    exit(0);
}
for(int x = 1;x <= n;++x){
    memset(tt,0,sizeof tt);
    for(int i = 0 ;i < m;++i) tt[ru[x][i]-'a'] ++;
    string ans,ans2;
    for(int i=25;i >= 0;--i){
        int y=tt[i];
        while(tt[i]--) ans=ans+char(i+'a');
        tt[i]=y;
    }s[x].first = ans;
    for(int i=0;i <= 25;++i){
        while(tt[i]--) ans2=ans2+char(i+'a');
    }s2[x]=ans2;
}
for(int i = 1;i <= n;i++) s[i].second=i;
sort(s+1,s+1+n,cmp);
for(int i = 1;i <= n;i++){
    if(check(i))vis[s[i].second]=1;
}for(int i = 1;i <= n;i++) printf("%d",vis[i]);
return 0;
}

【T2】

10：40 试图思考正解，我在草稿纸上写了三个大字——并查集（~~结果没写出来，赛后dalao们说这是正解，警钟长鸣）。。~~ 但是发现不会了。。。。于是思考线性解法，发现不会啊，贪心？不会，DP？不会。不行啊，启动暴力吧。
10：50 DFS面向数据写完，20pts 到手
11：15 特殊数据点，20pts 到手
11：20 开始进军接下来的 20pts。发现我的结论假了。
11：40 实在想不出来，过//开后两题。

#include <bits/stdc++.h>
using namespace std;
int c,t;
int n,m;
const int N = 1e5+5;
struct node{
    char op;
    int x,y;
}a[N];
int z[15],b[15];
int ans=1e9;
void dfs(int x){
    if(x==n+1){
        for(int i = 1;i <= n;i++)b[i]=z[i];
        for(int i = 1;i <= m;i++){
            if(a[i].op=='T'){
                b[a[i].x]=1;
            }else if(a[i].op=='F'){
                b[a[i].x]=2;
            }else if(a[i].op=='U'){
                b[a[i].x]=3;
            }else if(a[i].op=='-'){
                if(b[a[i].y]==3){
                    b[a[i].x]=3;
                }else if(b[a[i].y]==2){
                    b[a[i].x]=1;
                }else if(b[a[i].y]==1){
                    b[a[i].x]=2;
                }
            }else if(a[i].op=='+'){
                if(b[a[i].y]==3){
                    b[a[i].x]=3;
                }else if(b[a[i].y]==2){
                    b[a[i].x]=2;
                }else if(b[a[i].y]==1){
                    b[a[i].x]=1;
                }
            }
        }
        int flag=1;
        for(int i = 1;i <= n;i++){
            if(b[i] != z[i]){
                flag=0;
                break;
            }
        }
        int res=0;
        for(int i = 1;i <= n;i++){
            if(b[i]==3){
                res++;
            }
        }
        if(flag){
//          cout<<res<<endl;
            ans=min(ans,res);
        }

        return ;
    }
    for(int i = 1;i <= 3;i++){
        z[x]=i;
        dfs(x+1);
    }
}
char sub2[N];
int sub3[N];
int main(){
    freopen("tribool.in","r",stdin);
    freopen("tribool.out","w",stdout);
    scanf("%d%d",&c,&t);
    while(t--){
        ans=1e9;
        scanf("%d%d",&n,&m);    
        for(int i = 1;i <= m;i++) {
            cin>>a[i].op;
            scanf("%d",&a[i].x);
            if(a[i].op=='-'||a[i].op=='+'){
                scanf("%d",&a[i].y);
            }else{
                a[i].y=-1;      
            }
        }
        if(c<=2){
            dfs(1);
            printf("%d\n",ans);
        }else if(c >= 3 && c <= 4){
            int res2=0;
            for(int i = 1;i <= n;i++)sub2[i] = ' ';
            for(int i = 1;i <= m;i++){
                sub2[a[i].x] = a[i].op;
            }for(int i=1;i<=n;i++){
                if(sub2[i]=='U'){
                    res2++;
                }
            }printf("%d\n",res2);
        }
//      else if(c >= 5 && c <= 6){
//          memset(sub3,0,sizeof sub3);
//          for(int i = 1;i <= n;i++){
//              for(int j = m;j >= 1;j--){
//                  if(a[i].x == i){
//                      if(a[i].op=='U'){
//                          sub3[a[i].x]=1;
//                      }else break;
//                  }
//              }
//          }
//          for(int  i = 1;i <= n;i++){
//              int x = 
//          }
//      }
        else dfs(1);

    }
    return 0;
} 
/*

*/

【T3】

12：00 终于读完题目啦。不会咋办。
12：01 奥，n,m = 1。瞎写一通，走人。

#include <bits/stdc++.h>
using namespace std;
int c,n,m,q,x,y;
int main(){
    freopen("expand.in","r",stdin);
    freopen("expand.out","w",stdout);
    scanf("%d%d%d%d",&c,&n,&m,&q);
    if(n==1&&m==1){
        scanf("%d%d",&x,&y);
        while(q--){
            int kx,ky;
            scanf("%d%d",&kx,&ky);
            for(int i = 1;i <= kx;i++){
                int a,b;
                scanf("%d%d",&a,&b);
                if(a==1) x=b;
            }for(int i = 1;i <= ky;i++){
                int a,b;
                scanf("%d%d",&a,&b);
                if(a==1) y=b;
            }if(x!=y)cout<<'1';
            else cout<<'0';
        } 
    } 
    return 0;
}

【T4】

12：15 题面舒服多了，看起来不那么难受，启动状态枚举，8分到手咯。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int M = 1E5+5;
int c,t;
int n,m,k,d;
struct node{
    int x,y,z;
}a[M];
int vis[30];
int q[30];
int main(){
    freopen("run.in","r",stdin);
    freopen("run.out","w",stdout);
    scanf("%d%d",&c,&t);
    while(t--){
        scanf("%d%d%d%d",&n,&m,&k,&d);
        for(int i = 1;i <= m;i++){
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
            int x=a[i].x-a[i].y+1,y=a[i].x;
            a[i].x=x,a[i].y=y;
        } 
        if(c <= 2){
            ll ans=0;
            for(int z=0;z <= (1 << (n+1));z++){
                memset(vis,0,sizeof vis);
                memset(q,0,sizeof q);
                for(int i = 1;i <= n;i++){
                    if((1<<i) & z) vis[i]=1;
                }
                int cnt=0;
                int maxx=0;
                for(int i =1;i <= n;i++){
                    if(!vis[i]){
                        maxx = max(maxx,cnt);
                        cnt=0;
                    }else{
                        cnt++;
                    }
                }maxx = max(maxx,cnt);
                if(maxx > k) continue;
                for(int i = 1;i <= n;i++) {
                    q[i] = q[i-1] + vis[i];
                }
                ll res=-1 * q[n] * d;
                for(int i = 1;i <= m;i++){
                    if(q[a[i].y] - q[a[i].x - 1] == a[i].y - a[i].x + 1) res+=a[i].z;
                }ans = max(ans,res);
            }printf("%lld\n",ans);
        }
    }
    return 0;
}

总结：

不够细心，时间分配不好，下次要审题仔细，然后抓紧时间。

【估分】

【预估分数】：100+40+0+0 ~ 100+40+5+8 之间。

【小图灵】：90+40+0+0 = 130

【洛谷】：90+40+0+0 = 130

【云斗】：90+40+0+0 = 130

【信友队】：90+40+0+0 = 130

好好好，都是130是吧！！

我瞬间傻了，T1我的做法是要取最大和次大，我也不知道我写一个sort干啥用的！！！！成功将 O(2\times nm) 的算法提高到 O(nm\log n)，你看我多厉害！！！！赛时还在卡常的我！！！！！！！！！！！！

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

祭

顺便给个关注呗

~~点个赞呗~~