SMU Winter 2025 div1 2nd
文章目录
- The Second Week
- 一、前言
- 二、算法
- 1.深度优先搜索
- <1>（2025寒假训练3 L2-3）
- 2.异或
- <1>（牛客训练营4 L）
- 3.二分
- <1>（Xenia and Colorful Gems）
- <2>（牛客训练营3 E）
- 4.构造
- <1>（牛客训练营5 L）
- 三、总结
The Second Week
雄关漫道真如铁，而今迈步从头越。 ————毛泽东
一、前言
2.4 PTA 3h 169/175
2.5 CF 2h 3/4
2.6 牛客4 5h 6/8
2.8 牛客5 5h 8/8
rating：牛客：1257-1543 codefoces：1339-1339
二、算法
1.深度优先搜索
<1>（2025寒假训练3 L2-3）
龙龙送外卖 19/25
基本的解题思路想到了，但是算法思路没跟上，代码写的太乱了，加上主观上没有使用dfs的方向，有几分没拿到
题解：
当每新加入一个点时，考虑最近公共祖先，需要往这绕一圈并回去，也就是v*2，由于题目说完成送餐后无需返回外卖站，记录最远的点的距离，减去即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int N = 1e5+10;
int ans = 0,res = 0;
int fa[N];
int st[N];//记录节点深度
vector<int>a[N];
int dfs(int u,int v) {
if(st[u] || fa[u] == -1) {
res = max(res,st[u]+v);//最远的点不返回
return 2*v;
}
int ls = dfs(fa[u],v+1);//找到并返回为止，传递
st[u] = st[fa[u]]+1;
return ls;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> fa[i],st[i] = 0;
for (int i = 1; i <= m; i++) {
int x; cin >> x;
ans += dfs(x,0);
cout << ans-res << endl;
}
}
// 7 4
// -1 1 2 3 4 5 6
// 5
// 6
// 2
// 6 一组样例
2.异或
<1>（牛客训练营4 L）
题解：
异或的题目首先考虑逐位计算，这道题画图可以发现一个小正方形内的所有数字的和，也就是每个数位上的01，10个数相乘求和。代码实现上并不复杂，主要是有关异或计算的思想。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5+10;
const int mod = 1e9+7;
int n,q;
int a[N],b[N];
int x[N];
int fa[N][35];
int fb[N][35];//到b[i]时第j位有几个1
void solve() {
cin >> n >> q;
// memset(fa,0,sizeof fa);
// memset(fb,0,sizeof fb);
// memset(x,0,sizeof x);
for (int i = 1; i <= n; i++) {
cin >> a[i];
for (int j = 0; j <= 30; j++) {
fa[i][j] = fa[i-1][j];
if(a[i] >> j & 1) fa[i][j]++;
}
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
for (int j = 0; j <= 30; j++) {
fb[i][j] = fb[i-1][j];
if(b[i] >> j & 1) fb[i][j]++;
}//cout << b[i] << ' ';
}
for (int i = n; i >= 1; i--) {
x[i] = x[i+1];
for (int j = 0; j <= 30; j++) {
int b1 = fb[n][j]-fb[i-1][j];
int b0 = n-i+1-b1;
if(a[i] >> j & 1) x[i] = x[i] + (1<<j)*b0;
else x[i] = x[i] + (1<<j)*b1;
x[i] %= mod;
}//从下到上的小三角形的和
// cout << x[i] << ' ';
}
while(q--) {
int l,r;
cin >> l >> r;
int res = x[l]-x[r+1];
res = (res+mod)%mod;
//需要减去r列到n列的一块方形
// cout << res << endl;
for (int i = 0; i <= 30; i++) {
int a1 = fa[r][i]-fa[l-1][i];
int a0 = r-l+1-a1;
int b1 = fb[n][i]-fb[r][i];
int b0 = n-r-b1;
int y = (1<<i)*a1*b0+(1<<i)*a0*b1;
y %= mod;
res -= y;
res = (res+mod)%mod;
// res = (res+10*mod)%mod;
// cout << res << '/';
}
cout << res << endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t--) solve();
}
3.二分
<1>（Xenia and Colorful Gems）
接连俩场碰到二分题，需要有意识学一下二分函数（lower_bound）的用法，不然每次都手写。
题解：
分别对a，b，c进行遍历，每次找到小于它的最大值和大于它的最小值，也就是符合条件的最接近答案，判断特殊条件，比较即可。
代码：
#include<bits/stdc++.h>
#define endl '\n'
#define null NULL
#define ls p<<1
#define rs p<<1|1
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll long long
#define int long long
#define vi vector<int>
#define mii map<int,int>
#define pii pair<int,int>
#define ull unsigned long long
#define all(x) x.begin(),x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
char *fs,*ft,buf[1<<20];
#define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++;
inline int read(){
int x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();}
return x*f;}
using namespace std;
const int N=2e5+5;
const int inf=0x7fffffff;
const int mod=998244353;
const double eps=1e-6;
int a[N],b[N],c[N];
int check(int i,int j,int k)
{
// cout<<i<<' '<<j<<' '<<k<<endl;
return (a[i]-b[j])*(a[i]-b[j])+(a[i]-c[k])*(a[i]-c[k])+(c[k]-b[j])*(c[k]-b[j]);
}
signed main()
{
int t;
cin>>t;
while(t--)
{
int na,nb,nc;
cin>>na>>nb>>nc;
for(int i=1;i<=na;i++)
cin>>a[i];
for(int i=1;i<=nb;i++)
cin>>b[i];
for(int i=1;i<=nc;i++)
cin>>c[i];
sort(a+1,a+na+1);sort(b+1,b+nb+1);sort(c+1,c+nc+1);
int res=2e18;
for(int i=1;i<=na;i++)
{
int pb=lower_bound(b+1,b+nb+1,a[i])-b;
int pc=lower_bound(c+1,c+nc+1,a[i])-c;
if(pb==nb+1)
pb--;
if(pc==nc+1)
pc--;
res=min(res,check(i,pb,pc));
if(pb!=1)
res=min(res,check(i,pb-1,pc));
if(pc!=1)
res=min(res,check(i,pb,pc-1));
if(pb!=1&&pc!=1)
res=min(res,check(i,pb-1,pc-1));
}
for(int i=1;i<=nb;i++)
{
int pa=lower_bound(a+1,a+na+1,b[i])-a;
int pc=lower_bound(c+1,c+nc+1,b[i])-c;
if(pa==na+1)
pa--;
if(pc==nc+1)
pc--;
res=min(res,check(pa,i,pc));
if(pa!=1)
res=min(res,check(pa-1,i,pc));
if(pc!=1)
res=min(res,check(pa,i,pc-1));
if(pa!=1&&pc!=1)
res=min(res,check(pa-1,i,pc-1));
}
for(int i=1;i<=nc;i++)
{
int pb=lower_bound(b+1,b+nb+1,c[i])-b;
int pa=lower_bound(a+1,a+na+1,c[i])-a;
if(pb==nb+1)
pb--;
if(pa==na+1)
pa--;
res=min(res,check(pa,pb,i));
if(pb!=1)
res=min(res,check(pa,pb-1,i));
if(pa!=1)
res=min(res,check(pa-1,pb,i));
if(pb!=1&&pa!=1)
res=min(res,check(pa-1,pb-1,i));
}
cout<<res<<endl;
}
}
<2>（牛客训练营3 E）
wa了9发…浪费了非常多的罚时，最后才想到二分，算法敏捷度不太够
题解：
题目比较简单，不放题解了，具体看被注释部分，血淋淋的教训
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,k;
int p[N];
vector<int>a,b;
vector<int>sj;
bool check(int x) {
int res = 0;
for (auto bb:b) {
int ll = 0,rr = a.size()-1;
while(ll < rr) {
int mid = (ll+rr)/2;
if(a[mid] > bb) rr = mid;
else ll = mid+1;
}int ls = rr;//第一个大于bb的值
ll = 0,rr = a.size()-1;
while(ll < rr) {
int mid = (ll+rr)/2;
if(a[mid] >= bb-x) rr = mid;
else ll = mid+1;
}//第一个大于等于bb-x的值
int ks = ls-rr;if(ks < 0) ks = 0;
res += ks;
// for (int j = rr-1; j >= 0; j--) {
// if(bb-a[j] <= x) res++;
// else break;
// }
// cout << ' ' << bb << ' ' << ks << endl;
}//cout << x << ' ' << res << endl;
return res >= k;
}
signed main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> p[i]; int vv; cin >> vv;
if(vv == 1) a.push_back(p[i]); //you
else b.push_back(p[i]); //zuo
}sort(a.begin(),a.end());
sort(b.begin(),b.end());
a.push_back(1e9+10);
int l = 0,r = 1e9+10;
//int l = 0,r = 10;
while(l < r) {
// cout << l << '/' << r << endl;
int mid = (l+r)/2;
if(check(mid)) r = mid;
else l = mid+1;
}
if(r == 1e9+10) cout << "No" << endl;
else {cout << "Yes" << endl;
float ans = (float) r/2;
printf("%0.6f",ans);
}
return 0;
}
4.构造
<1>（牛客训练营5 L）
题解：
一道比较复杂的构造题，我的做题思路是确定2个非互质数，在抓取一个别的数字，正解最好是6个为一组，还没重新补题，赛时已ac
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+10;
int n;
int a[N][5];
void solve() {
cin >> n;
int ls = (n-1)/3;
// if(n % 3 == 0 && n != 3 && ls%2 == 0) {
// cout << ls+1 << endl;
// }else
if(n % 3 == 0) {
if(n == 3) cout << 0 << endl;
else {
cout << n/3 << endl;
if(n%6 == 0) {
for (int i = 1; i <= ls; i++) {
cout << a[i][1] << ' ' << a[i][2] << ' ' << a[i][3] << endl;
}cout << 1 << ' ' << a[ls+1][1] << ' ' << a[ls+1][2] << endl;
}
else {
int lt = (n/3)-2;
for (int i = 1; i <= (n/3)-2;i++) {
cout << a[i][1] << ' ' << a[i][2] << ' ' << a[i][3] << endl;
}cout << a[lt+1][2] << ' ' << a[lt+1][3] << ' ' << a[lt+2][1] << endl;
cout << 1 << ' ' << a[lt+1][1] << ' ' << n << endl;
}
}
return;
}
cout << ls << endl;
if(ls % 2 == 0) {
for (int i = 1; i <= ls; i++) {
cout << a[i][1] << ' ' << a[i][2] << ' ' << a[i][3] << endl;
}//cout << 1 << ' ' << a[ls+1][1] << ' ' << a[ls+1][2] << endl;
}//3 9 15
else {
for (int i = 1; i < ls; i++) {
cout << a[i][1] << ' ' << a[i][2] << ' ' << a[i][3] << endl;
}cout << a[ls][1] << ' ' << a[ls][3]-2 << ' ' << a[ls][2] << endl;
// cout << 1 << ' ' << n-1 << ' ' << n << endl;
}//6 12 18
}
signed main() {
int t = 1;
int er = 2; int san = 3;
for (int i = 1; i <= 1000000; i++) {
a[i][1] = er;a[i][2] = er+2;a[i][3] = er+3;
er = er+6;
if((a[i][3]+1)%6 == 0) {
a[i+1][1] = san;
a[i+1][2] = san+3;
a[i+1][3] = san+4;
san = san+6;
i++;
}
}
// cout << a[999999][1] << ' ' << a[999999][2] << ' ' << a[999999][3] << endl;
for (int i = 1; i <= 20; i++) {
cout << a[i][1] << ' ' << a[i][2] << ' ' << a[i][3] << endl;
}
cin >> t;
while(t--) solve();
}
// 4 7 10 13 1 3 6 9 12
// 4
// 2 4 3
// 3 6 7
// 8 10 9
// 9 12 13
// 1 2 3 4 7 10 13
// 2 3 4
// 2 4 5 6
// 3 6 1
// 8 10 11
// 9 12 13
三、总结
这周比赛状态相对比较好，基本该做出来的都能做出来，但是做题速度太慢，尤其体现在CF和PTA这种只有2，3个小时的比赛中，在比赛结束后二三十分钟才ac，得有意识调整做题模式，不要在做不出来的题目上浪费了时间。
没有进行系统算法学习，立体几何掌握的不是很好，学了些比较偏的，下周继续