noip2024游记

tang2hao4zhe2 · 2024-11-28 21:30:17 · 生活·游记

Day -?

csp成绩出了，我们大湖州唯一的省一是lqr的普及组省一，然而他提高组初赛没过.

Day -4

开始停课，爽!!!!!!
写noip2017，删掉两道签到题

Day1t2:
大模拟，水，一遍过

Day1t3:
30pts是最短边路计数
70pts是不考虑0环的DP 100pts是在记忆化搜索中判断调用栈
然而这个蒟蒻70pts没调出来，写了30pts跑路

Day2t2:
n<=12，看上去是状压dp，但这个蒟蒻不会
n<=8：70pts？
直接O(n!),但只拿到65pts

Day2t3:
由于这个蒟蒻没时间了，写了个30pts的模拟

省流:100+30+65+30 (以前的分是真好骗啊!!!)

晚自修切了this,差点没笑死

Day-3

csps2019

Day1t1:
水，
我绝不会告诉你我unsigned long long忘打long long

Day1t2:
树形dp，水中之水

Day2t2:
亲测搜索剪枝32pts

Day2t3:
只打了链性质，还挂了，蒟蒻

省流：100+100+32+0

Day-2

noip2017,老师让我们做Day1&&Day2t1

Day1t1:
水

做完下一题后，观察出一个重要性质，对于节点u，经过它的赛道要么是两条子树里的链，要么是一条子树里的链再连到父亲上(当然不连也是可以的)
于是就不难了，二分答案，判断最大建造赛道数量ans>=m是否成立，二分长度k
我们设计函数dfs(u)表示u传到父节点的链的长度，考虑v\in sonu，w_i=dfs(v)+l_i，若w_i>=k，ans=ans+1，反之放进一个可重集里，将小边与第一个与之和大于k拼成一条链，最后把剩下的传上去
code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e4+5;
struct edge{
    int to,val;
};
vector<edge> G[N];
void addedge(int u,int v,int w){
    G[u].push_back((edge){v,w});
}
int n,m,ans;
multiset<int> s[N];
int dfs(int u,int fath,int k){
    s[u].clear();
    for(edge e:G[u]){
        int v=e.to;
        if(v==fath) continue;
        int val=dfs(v,u,k)+e.val;
        if(val>=k) ans++;
        else s[u].insert(val);

    }
    int maxn=0;
    while(!s[u].empty()){
        if(s[u].size()==1) return max(maxn,*s[u].begin());
        auto it=s[u].lower_bound(k-*s[u].begin());
        if(it==s[u].begin()&&s[u].count(*it)==1) it++;
        if(it==s[u].end()){
            maxn=max(maxn,*s[u].begin());
            s[u].erase(s[u].find(*s[u].begin()));
        }
        else {
            ans++;
            s[u].erase(s[u].find(*it));
            s[u].erase(s[u].find(*s[u].begin()));
        }
    }
    return maxn;
}

bool check(int mid){
    ans=0;
    dfs(1,0,mid);
    return ans>=m;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n-1;i++){
        int u,v,w;cin>>u>>v>>w;
        addedge(u,v,w);
        addedge(v,u,w);
    }
    int h=0,t=1e9;
    while(h<t){
        int mid=(h+t+1)/2;
        if(check(mid)) h=mid;
        else t=mid-1;
    }
    cout<<h<<endl;
    return 0;
}

我绝对不会告诉你我最开始用set拿了70pts

Day2t1:
水中之水

56pts:你发现字符集大小为1很好写，分奇偶简单讨论然后乘法原理计数即可
然后写一半被拉去考数学和物理了，考到一半，直接脑子里切掉了
大概就是，每次重复计算F(A)很浪费，可以把它放到一个权值树状数组里，在O(1)算出F(C)后，就可以O(log_226) \approx O(1)计算贡献了
回机房一交，被卡常了，大概有23.5的常数，对n=10^6来说还是有点难跑的
附上卡常代码:

#include<bits/stdc++.h>
using namespace std;
const int base=1e5+7;
const int N=(1<<20)+5;
unsigned long long h[N],m[N];
inline unsigned long long gethash(int l,int r){
    return h[r]-h[l-1]*m[r-l+1];
}
int pre[N][26],suf[N][26];
int p[N],s[N];
int tree[30];
inline int lowbit(int x){
    return x&-x;
}
inline void add(int x,int pos){
    while(pos<=27){
        tree[pos]+=x;
        pos+=lowbit(pos);
    }
}
inline long long getsum(int pos){
    long long ans=0;
    while(pos>0){
        ans+=tree[pos];
        pos-=lowbit(pos);
    }
    return ans;
}
void solve(){
    long long ans=0;
    string s;cin>>s;
    int n=s.size();
    s=' '+s;

    m[0]=1;
    for(int i=1;i<=n;i++){
        h[i]=h[i-1]*base+s[i]-'a'+1;
        m[i]=m[i-1]*base;
    }

    for(int i=1;i<=n;i++){
        for(int c=0;c<26;c++) pre[i][c]=pre[i-1][c];
        pre[i][s[i]-'a']++;
        if(pre[i][s[i]-'a']%2) p[i]=p[i-1]+1;
        else p[i]=p[i-1]-1;
    }

    for(int i=n;i>=1;i--){
        for(int c=0;c<26;c++) suf[i][c]=suf[i+1][c]; 
        suf[i][s[i]-'a']++;
        if(suf[i][s[i]-'a']%2) s[i]=s[i+1]+1;
        else s[i]=s[i+1]-1;
    } 
    //枚举AB长度 
    for(int i=2;i<n;i++){
        int r=i;
        unsigned long long hval=h[i];
        add(1,p[i-1]+1);
        for(;;){
            ans+=getsum(s[r+1]+1);
            if(r+i>=n||gethash(r+1,r+i)!=hval) break;
            r+=i;
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++) for(int c=0;c<26;c++) pre[i][c]=suf[i][c]=0;
    memset(tree,0,sizeof(tree));
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;cin>>t;
    while(t--) solve();
    return 0;
}

再附上被卡常代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int base=1e9+7;
const int N=(1<<20)+5;
unsigned int h[N],m[N];
unsigned int gethash(int l,int r){
    return h[r]-h[l-1]*m[r-l+1];
}
int pre[N][26],suf[N][26];
int p[N],s[N];
int cnt1(int r){
    int ans=0;
    for(int c=0;c<26;c++) if(pre[r][c]%2) ans++;
    return ans;
}
int cnt2(int l){
    int ans=0;
    for(int c=0;c<26;c++) if(suf[l][c]%2) ans++;
    return ans;
}
int tree[30];
int lowbit(int x){
    return x&-x;
}
void add(int x,int pos){
    while(pos<=27){
        tree[pos]+=x;
        pos+=lowbit(pos);
    }
}
int getsum(int pos){
    int ans=0;
    while(pos>0){
        ans+=tree[pos];
        pos-=lowbit(pos);
    }
    return ans;
}
void solve(){
    int ans=0;
    string s;cin>>s;
    int n=s.size();
    s=' '+s;

    m[0]=1;
    for(int i=1;i<=n;i++){
        h[i]=h[i-1]*base+s[i]-'a'+1;
        m[i]=m[i-1]*base;
    }

    for(int i=1;i<=n;i++){
        for(int c=0;c<26;c++) pre[i][c]=pre[i-1][c];
        pre[i][s[i]-'a']++;
    }
    for(int i=1;i<=n;i++) p[i]=cnt1(i);
    for(int i=n;i>=1;i--){
        for(int c=0;c<26;c++) suf[i][c]=suf[i+1][c]; 
        suf[i][s[i]-'a']++;
    } 
    for(int i=1;i<=n;i++) s[i]=cnt2(i);
    //枚举AB长度 
    for(int i=2;i<n;i++){
        int r=i;
        unsigned int hval=h[i];
        add(1,p[i-1]+1);
        for(;;){
            ans+=getsum(s[r+1]+1);
            if(r+i>=n||gethash(r+1,r+i)!=hval) break;
            r+=i;
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++) for(int c=0;c<26;c++) pre[i][c]=suf[i][c]=0;
    memset(tree,0,sizeof(tree));
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;cin>>t;
    while(t--) solve();
    return 0;
}

t3:
懒得写

t4:
cout<<-1 and you will get 10 pts

省流:100+100+0+10

Day0

在写游记，颓废

Day1

唐完了
按照csps2023，noip2023，csps2024的经验，t1是签到题，然而20min过去，我对正解没有一点想法，果断写性质跑路，我尝试把性质B扩展成正解，但是假了
t2感觉像是一个O(m)的dp，推了会式子，但不会，于是先把m=1写了，回去想了一会t1，还是不会
我意识到这场比赛必须得拿暴力和性质分了，开了t3，两个性质是送的，画张图出来了，然后暴力是一个类似于枚举生成树的东西，但我不会
开了t4，暴力快速打好，两个性质没有什么思路
这时，我开始思考t1的C性质，感觉能扩展出正解，但是失败了
然后我又想到，考虑s_{1,i}在s_2中的可匹配区间，手玩了三个样例都是对的，果断开写，这是只剩1h了，然后我发现我性质B写错了，还好调出来了，然后我正解的树状数组跟个唐人一样无限循环
于是赶紧写t3暴力，然后我还是不会
最后20min，对t4的A性质有点想法，然后假了
最后检查了一下文件相关，遗憾离场
省流:60+40+20+12=132

赛后

唐唐唐
t3的菊花图性质我把点数想成n了，链性质忘考虑链头的情况了，（我相信西西弗的随机数据不会把我hack掉）
省流:60+40+[0,4]+12
感觉今年才找到一点比赛感觉，2024还是带着很多遗憾的