winter 2024 day2

bible- / 2024-01-25 / 原文

2023 中国大学生程序设计竞赛（CCPC）新疆赛区（重现赛

H数学

思路：有四平方和定理知道，任意正整数可表示为不超过四个整数的平方和。

并且n的范围为1e5，可以枚举出f（x）值为1、2、3、4的平方数组合情况。

也可以dp，f[i]=min(f[i]，f[i-k*k]+1)

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int MAXN=1e8+5;
const double eps=1e-6;


void solve() {
    int n;
    cin >> n;
    vector<int> f(n + 5, INF);
    vector<int> g;
    for (int i = 1; i * i <= n; ++i)g.push_back(i * i);
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < g.size(); ++j) {
            if (g[j] > i)break;
            f[i] = min(f[i], f[i - g[j]] + 1);
        }
    }
    int ans = 1;
    for (int i = 1; i <= n; ++i)ans = (ans * f[i]) % mod;
    cout << ans;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
//    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

View Code

D在此同步

思路：想的相邻的两个数交换会让逆序对数改变一，那就找一个加一和一个减一的相邻对交换一下总逆序对数就不变，暴力找一遍就可以。后面抗体姐被自己整笑了，直接找个山峰或山谷（三个连续数），然后将其内部后移一位就行

...

BSang的奇妙冒险

F任务安排

思路：首先没有序列a的话就是求拓扑排序，首先判断是否为拓扑序；其次，给每个点设置权值，求拓扑序时用优先队列即可。对于设置权值，把序列a按顺序递增给权值1、2、3....。还有一个问题，当序列a中的点，指向不在序列a中的点时可能会导致最后的拓扑序中序列a中的点不连续，那么在序列a中的点里，若其后缀为非序列a中的点，将其后缀的权值设为无穷大，这样就可以在当前拓扑序里已有序列a的点的情况下，优先选择权值小的，也就是在序列a中的点

E外接圆

思路：首先要知道的是三点确定圆，那么就来个n³的枚举确定圆，再来来个n的枚举判断剩余点是否在圆上，噢记得先去重了，记录每个点出现次数。还要注意所有点共线的情况，那就是两点确定一圆，找到出现次数最多的两点即可

...抄板子

G动态二叉树

思路：考虑离线求，由于整个二叉树不会改变，可以先求出最终的二叉树。操作二问的是x右边的节点，其实就是bfs序中x的后继，可以先求出最终二叉树的所有节点对应的bfs序号。再重新依次操作，若是操作一，先找到该节点所在层数，在该层插入该节点的bfs序号，由于bfs序号是有序的，这里可以用set存储，二分找到该节点的后继。

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int MAXN=1e8+5;
const double eps=1e-12;
struct E{
    int op,p;
    char c;
};

void solve() {
    int n;
    cin>>n;
    vector<E>ve(n);
    vector<int>L(n+5),R(n+5),id(n+5),to(n+5);
    for(int i=0,idx=2;i<n;++i){
        cin>>ve[i].op;
        if(ve[i].op==1){
            cin>>ve[i].p>>ve[i].c;
            if(ve[i].c=='L')L[ve[i].p]=idx++;
            else R[ve[i].p]=idx++;
        }else{
            cin>>ve[i].p;
        }
    }
    queue<int>q;
    int idx=1;
    q.push(1);
    while(q.size()){
        int c=q.size();
        while(c--){
            int t=q.front();q.pop();
            to[idx]=t,id[t]=idx++;
            if(L[t])q.push(L[t]);
            if(R[t])q.push(R[t]);
        }
    }
    set<int>g[N+5];
    vector<int>d(n+5);
    g[0].insert(1);
    for(int i=0,now=2;i<n;++i){
        if(ve[i].op==1){
            int fd=d[ve[i].p];
            d[now]=fd+1;
            g[d[now]].insert(id[now++]);
        }else{
            auto t=g[d[ve[i].p]].lower_bound(id[ve[i].p]+1);
            int ans=-1;
            if(t!=g[d[ve[i].p]].end())ans=to[*t];
            cout<<ans<<'\n';
        }
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
//    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}