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的奇妙冒险
思路：首先分析式子，因为是要从1到n，对于|i-j|整体看来就是n-1。对于|ai-aj|，这里题目求的是代价最小的方案数，那么很明显最小的代价是|a1-an|，直接一步到终点，因为在1到n的路途中出现山峰或山谷的话，只会增加代价，那么选择的ai应该是不递减或不递增的。问题就转化为求最长不下降子序列（a1<an）或最长不上升子序列（a1>an），翻转下后的求法就是一样的。
F任务安排
思路：首先没有序列a的话就是求拓扑排序，首先判断是否为拓扑序；其次，给每个点设置权值，求拓扑序时用优先队列即可。对于设置权值，把序列a按顺序递增给权值1、2、3....。还有一个问题，当序列a中的点，指向不在序列a中的点时可能会导致最后的拓扑序中序列a中的点不连续，那么在序列a中的点里，若其后缀为非序列a中的点，将其后缀的权值设为无穷大，这样就可以在当前拓扑序里已有序列a的点的情况下，优先选择权值小的，也就是在序列a中的点
E外接圆
思路：首先要知道的是三点确定圆，那么就来个n3的枚举确定圆，再来来个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;
}
View Code
J子段和二象性
思路：搞成图来想，（但是还是不懂T^T），，那就要有点和关系，看原数组的前缀和数组，在满足条件的情况下，Si<Si+n，Si<Si-m（因为每n个数和为正，每m个数和为负），那么点就看成是Si，根据大小关系，Si指向Si+n，Si指向Si-m，找到非环的最长的链。
对于n=2、m=3，可以这样构造，从0开始，S0→S2→S4→S1→S3→S0，直到构成了环为止，这时候的最大长度为最大编号减一(不懂)
打表可以发现答案为n+m-gcd（n，m）-1
证明
标签：typedef,const,winter,idx,int,day2,2024,序列,ve From： https://www.cnblogs.com/bible-/p/17983616