2025.7.27 测试总结
前情提要:
最开始发了考过的题，最后提交的时候发现题目对不上，所有人直接爆0，重新更改，时间 3.5h--->5.5h 但我还没AK
T1
题目大意：
给定一个矩形左下角(\(X_1,Y_1\))右上角(\(X_2,Y_2\)),n辆矿车的坐标(\(x_i,y_i\)),求每辆矿车到矩形的最短距离\(\textcolor{red}{(保留小数点后9位)}\)，并输出距离最近的矿车编号
思路：
将整个区域分割成这么几块
显然，对于1 3 5 7号，最近距离就是到矩形顶点的坐标
\[\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}
\]
对于2 4 6 8号点，最近距离就是作垂线段的长度（垂线段最短不会还有人不知道吧）
而输出路程最短的点，可以用如下代码进行维护
//dis[i]表示第i辆车到矩形的距离
dis[0]=1e9;
if(dis[i]<dis[mini]) mini=i;
AC code:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
double x[N],y[N];
double n,X1,X2,Y1,Y2;
double dis[N];
int mini=0;
double f(double x1,double y1,double x2,double y2)
{return sqrt(pow(x1-x2,2)+pow(y1-y2,2));
}
int main()
{freopen("cow.in","r",stdin);freopen("cow.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>X1>>Y1>>X2>>Y2;for(int i=1;i<=n;i++) cin>>x[i]>>y[i];dis[0]=1e9;for(int i=1;i<=n;i++){if(x[i]<=X1&&y[i]>=Y2) dis[i]=f(x[i],y[i],X1,Y2);else if(x[i]<=X1&&y[i]<=Y1) dis[i]=f(x[i],y[i],X1,Y1);else if(x[i]>=X2&&y[i]>=Y2) dis[i]=f(x[i],y[i],X2,Y2);else if(x[i]>=X2&&y[i]<=Y1) dis[i]=f(x[i],y[i],X2,Y1);else if(x[i]>X1&&y[i]>Y2) dis[i]=y[i]-Y2;else if(x[i]>X1&&y[i]<Y1) dis[i]=Y1-y[i];else if(x[i]<X1&&y[i]<Y2) dis[i]=X1-x[i];else if(x[i]>X2&&y[i]<Y2) dis[i]=x[i]-X2;if(dis[i]<dis[mini]) mini=i;}for(int i=1;i<=n;i++) printf("%.9f ",dis[i]);printf("\n%d",mini);return 0;
}
T2
题目大意:
T组询问，每次给定2个数a,b,选择一个集合{1,2,3...,n}，从中选k个数，构成集合A，余下的n-k个数构成集合B，使得
\[a+\sum_{i=1}^{k}a_i=b+\sum_{i=1}^{n-k}b_i
\]
求出最小的个数n
思路：
不难发现，对于|a-b|=\(\sum_{i=1}^{n}i,n\in \mathbb N^* 时\)答案为n
所以可以先维护前缀和数组\(ans[i]=\sum_{j=1}^{i}j\)即 ans[i]=ans[i-1]+i;
假设n=4，且全放入A中，即{1,2,3,4}，若取出"1"放入B中，此时B={1}，A={2,3,4}
\(\sum_{i=1}^{3}a_i\in A-\sum_{i=1}^{1}a_i\in B\)=8,即|a-b|=8时n=4
由此，同理得当|a-b|=\(|\sum_{i=1}^{n}i-2*\sum_{j=1}^{n}j|\)时，都有合法答案为n
所以对于每一组询问，如果|a-b|=ans[i]中，直接输出i
否则用upper_bound()找出第一个大于|a-b|的数，运用上述公式枚举j，看是否合法，接着一直向后枚举直到合法
AC code(900ms):
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,cha;
const int N=1e5;
int ans[N],cnt;
void f(int cha)
{int i=upper_bound(ans,ans+cnt+1,cha)-ans;for(i;i<=cnt;i++){for(int j=1;j<=ans[i];j++){if(ans[i]-2*j<cha) break;if(ans[i]-2*j==cha){cout<<i<<"\n";return;}}}
}
signed main()
{freopen("water.in","r",stdin);freopen("water.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ans[cnt++]=0;for(int i=1;;i++){ans[cnt]=ans[cnt-1]+i;if(ans[cnt]>1e9) break;cnt++;}int T;cin>>T;while(T--){cin>>a>>b;cha=abs(a-b);if(binary_search(ans,ans+cnt+1,cha)){cout<<lower_bound(ans,ans+cnt+1,cha)-ans<<"\n";}else f(cha);}return 0;
}
T3
题目大意:
给定一颗有n个节点的树，规定任意2个距离不大于2的节点的种类不同，求出所需最少的种类数。
思路：
任意两个距离不大于2的点实质上就是一个节点及其全部子节点（父节点）所以可以枚举每一个点，找到子节点最多的那一个点，最后输出时加上本身。
AC code：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,x,y;
vector<int> g[N];
int deg[N],maxd;
int main()
{freopen("light.in","r",stdin);freopen("light.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<n;i++){cin>>x>>y;deg[x]++,deg[y]++;}for(int i=1;i<=n;i++) maxd=max(maxd,deg[i]);cout<<maxd+1;return 0;
}
T4
题目大意：
给你一段python中的代码，形如
ans=0
for A in range(a,b,c):for B in range(d,e,f):ans=ans+B
print(ans)
让你模拟整个过程
思路：
还能有啥思路，模拟就完了
第一步：处理字符串
读入： for(int i=0;i<5;i++) getline(cin,s[i]);
观察得到，对于这5串字符串，1 4 5行都是固定的，所以只需处理第2 3 行。所需的元素有A,B,a,b,c,e,d,f.其中A,B位置固定，均为'f'后第4位，直接读入即可。
对于剩下的数字，只需找到'('后遍历处理。
处理数字:num=num*10+(s[i]-'0');(记得特判'-')
对于d,e可能为A的情况，只需特判即可if(s[i]>='a'&&s[i]<='z') ch=s[i];
第二步：模拟循环过程
F1：直接模拟\(O(n^2)\)
附50pts代码:
#include<bits/stdc++.h>
using namespace std;
string s[5];
int ans=0; //初始值
char A,B; //两个循环变量
int a[3][3];
char ch[2];
void f(int i,int id)
{int cnt=0; //","数量 bool t=0; //是否为'-' for(i;i<s[id].size();i++){if(s[id][i]==')'){if(t){a[id][cnt]*=-1;
// cout<<"111"<<a[id][cnt]<<"\n";}break;}else if(s[id][i]==','){if(t){a[id][cnt]*=-1;
// cout<<"222\n";}cnt++;t=0;}else if(s[id][i]>='a'&&s[id][i]<='z') ch[cnt]=s[id][i];else if(s[id][i]=='-'){t=1;
// cout<<"!!!\n";}else a[id][cnt]=a[id][cnt]*10+(s[id][i]-'0');}
}
int main()
{freopen("for.in","r",stdin);freopen("for.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);for(int i=0;i<5;i++) getline(cin,s[i]);
// cout<<"---------\n";
// for(int i=0;i<5;i++) cout<<s[i]<<"\n";for(int i=0;i<s[1].size();i++){if(s[1][i]=='f'){A=s[1][i+4];break; }}for(int i=0;i<s[2].size();i++){if(s[2][i]=='f'){B=s[2][i+4];break; }}
// cout<<A<<" "<<B<<"\n";for(int i=1;i<=2;i++){for(int j=0;j<s[i].size();j++){if(s[i][j]=='('){f(j+1,i);break;}}}
// for(int i=1;i<=2;i++)
// {
// cout<<a[i][0]<<" "<<a[i][1]<<' '<<a[i][2]<<"\n";
// }
// for(int i=0;i<=1;i++)
// {
// if(ch[i]!=0) cout<<ch[i]<<' ';
// else cout<<"-- ";
// }
// cout<<"\n";if(a[1][2]>0){for(int i=a[1][0];i<a[1][1];i+=a[1][2]){if(ch[0]==0&&ch[1]==0){if(a[2][2]>0) for(int j=a[2][0];j<a[2][1];j+=a[2][2]) ans+=j;else for(int j=a[2][0];j>a[2][1];j+=a[2][2]) ans+=j;}else if(ch[0]==A){if(a[2][2]>0) for(int j=i;j<a[2][1];j+=a[2][2]) ans+=j;else for(int j=i;j>a[2][1];j+=a[2][2]) ans+=j;}else{if(a[2][2]>0) for(int j=a[2][0];j<i;j+=a[2][2]) ans+=j;else for(int j=a[2][0];j>i;j+=a[2][2]) ans+=j;}}}else{for(int i=a[1][0];i>a[1][1];i+=a[1][2]){
// cout<<i<<"\n";if(ch[0]==0&&ch[1]==0){if(a[2][2]>0) for(int j=a[2][0];j<a[2][1];j+=a[2][2]) ans+=j;else for(int j=a[2][0];j>a[2][1];j+=a[2][2]) ans+=j;}else if(ch[0]==A){if(a[2][2]>0) for(int j=i;j<a[2][1];j+=a[2][2]) ans+=j;else for(int j=i;j>a[2][1];j+=a[2][2]) ans+=j;}else{if(a[2][2]>0) for(int j=a[2][0];j<i;j+=a[2][2]) ans+=j;else for(int j=a[2][0];j>i;j+=a[2][2]) ans+=j;}}}cout<<ans;return 0;
}
/*
ans=0
for i in range(10,1,-2):
for j in range(i,10,3):
ans=ans+j
print(ans)
*/
F2：模拟？计算！
对于最外层的for循环，可以直接计算出循环的次数
记得提前处理b：\(\begin{cases}c>0 & b-=1\\c<0 & b+=1\end{cases}\)
总共循环次数：cnt=(b-a)/c;
第二层函数分3种情况,而且是一个等差数列\(\textcolor{red}{(若e为常数需提前处理)}\)
(1)若第二层也为常数，则能推出公式
\[ans=cnt\times(d+e)\times((e-d)\div f+1)\div 2
\]
(2)若d为A或e为A，则每次枚举d为e，\(\textcolor{red}{(需要特判d<=e)}\)可推出公式
\[ans=ans+(d+e)\times((e-d)\div f+1)\div 2;
\]
AC code:
(中午改了一部分，手懒了，要不就AK了)
#include<bits/stdc++.h>
#define int long long
using namespace std;
string s[5];
int ans=0; //初始值
char A,B; //两个循环变量
int a[3][3];//a,b,c,d,e,f
char ch[2]; //d,e是否为A
void f(int i,int id)
{int cnt=0; //","数量 bool t=0; //是否为'-' for(i;i<s[id].size();i++){if(s[id][i]==')'){if(t){a[id][cnt]*=-1;}break;}else if(s[id][i]==','){if(t){a[id][cnt]*=-1;}cnt++;t=0;}else if(s[id][i]>='a'&&s[id][i]<='z') ch[cnt]=s[id][i];else if(s[id][i]=='-'){t=1;}else a[id][cnt]=a[id][cnt]*10+(s[id][i]-'0');}
}
signed main()
{freopen("for.in","r",stdin);freopen("for.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);for(int i=0;i<5;i++) getline(cin,s[i]);//找A,B for(int i=0;i<s[1].size();i++){if(s[1][i]=='f'){A=s[1][i+4];break; }}for(int i=0;i<s[2].size();i++){if(s[2][i]=='f'){B=s[2][i+4];break; }}//处理2 3字符串 for(int i=1;i<=2;i++){for(int j=0;j<s[i].size();j++){if(s[i][j]=='('){f(j+1,i);break;}}}//处理b if(a[1][2]>0) a[1][1]--;else a[1][1]++;if(a[2][2]>0) a[2][1]--;else a[2][1]++;int cnt=(a[1][1]-a[1][0])/a[1][2];//模拟？计算！ if(ch[0]==0&&ch[1]==0) //均常数 {int l=a[2][0];int r=(a[2][1]-l)/a[2][2];r=l+r*a[2][2];ans=(l+r)*((r-l)/a[2][2]+1)/2*(cnt+1);}else if(ch[0]==A) //{for(int i=0;i<=cnt;i++){int l=a[1][0]+i*a[1][2]; //枚举d if(l>a[2][1]) continue; //d>e int r=(a[2][1]-l)/a[2][2];r=l+r*a[2][2];ans+=(l+r)*((r-l)/a[2][2]+1)/2; }}else{for(int i=0;i<=cnt;i++){int rr=a[1][0]+i*a[1][2];//枚举e//处理e if(a[2][2]>0) rr--;else rr++;int l=a[2][0];if(l>rr) continue; //e<d int r=(rr-l)/a[2][2];r=l+r*a[2][2];ans+=(l+r)*((r-l)/a[2][2]+1)/2;}}cout<<ans;return 0;
}