\(day0\)
处于广州三区，CSP 直接停掉。但是听说后续会有补测，但是无论如何，钩子应该是没有了。
晚上最后复习了快速幂，线段树，树状数组，就去睡觉了。
收到某人的祝福，挺好的（虽然远在我家隔壁一条街？）。
\(day1\)
中午 \(12\) 点开始考试，定个闹钟，到 \(3:30\)。准时结束。
开了第一题。
题意：给出 \(n\)，\(k\)，求 \(n^k\) 是否大于 \(10^9\) 是则输出 \(-1\)，否则则输出 \(n^k\)。
额，居然考了快速幂！刚刚好复习到，模板记得很清楚，打出来了。（虽然也很简单），然后开计算器算了一下 \(sqrt(10^9)\)，大于他判一下就可以。
用了不到 \(10min\) 轻松 \(AC\)。
#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10;
#define ll long long
ll ans=1;
void Slove(ll a,ll b)
{
ll base=a;
while(b>0)
{
if(b&1)
ans*=base;
base*=base;
b>>=1;
if(ans>1000000000)
cout<<"-1"<<endl,exit(0);
}
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ll a,b;
cin>>a>>b;
if(a>31622&&b>2)
cout<<"-1"<<endl,exit(0);
Slove(a,b);
cout<<ans<<endl;
return 0;
}
很快开了第二题。
题意：
求两个正整数 \(p\)，\(q\)，使 \(n=p\times q\)，\((p-1)\times (q-1)=e\times d\)。给出 \(n\)，\(d\)，\(e\)，同时有多测。
通过移项，带入，可以得到：
\[\begin{cases}p\times q=n \\p+q=n+2-e \times d\end{cases} \]一开始我还想着去枚举因数，但是发现 \(n\) 的值过大，不可做。
正在想期间，我突然回想起我们最近数学学的，完全平方公式。
\((p-q)^2=(p+q)^2-4\times p\times q\)
再连立 \(p+q\) ，\(p-q\) 即可求出 \(p\)，\(q\)。
还要考虑当前的数开平方后进行验证，即这个数是不是完全平方，还有除以 \(2\) 的部分也要判一下。因为在这两个操作会有精度损失。
最后还要记得要先输出小的。
#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10;
#define ll long long
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int t;
cin>>t;
while(t--)
{
ll n,e,d;
cin>>n>>d>>e;
ll m=n-e*d+2;
ll s=sqrt(m*m-4*n);
if(s*s!=m*m-4*n){
cout<<"NO"<<endl;continue;
}
ll p=(m+s)>>1;
if(p*2!=m+s)
{
cout<<"NO"<<endl;continue;
}
ll q=n/p;
if(p>q)
swap(p,q);
cout<<p<<" "<<q<<endl;
}
return 0;
}
考试的时候输入顺序写错了，调了 \(10min\) 才发现，我真的会谢。
看到 \(T3\) 题目很长，果断跳开，选择性躲避，开了 \(T4\)。
\(T4\) 一开始没认真读题，理解错题目以为线只可以平行于 \(x\) 或者 \(y\) 轴，对了样例看了一会，才发现他是可以斜着走的。。。
给出 \(n\) 个点坐标，以及可以添加 \(k\) 个点。从中挑选出一些点，加入一些点，是的点两两之间 即 \(x[i+1]-x[i]=1,y[i+1]=y[i]\) 或者 \(y[i+1]-y[i]=1,x[i+1]=x[i]\)。
\(30\) 分的做法显然，就是找个最长不下降子序列且公差为 \(1\) 即可。
正解还是 \(dp\)。
设 \(dp[i][j]\) 表示 第 \(i\) 个点结尾，添加 \(j\) 个点的最大值， \(dis(i,j)\) 表两点距离（也就是两个点之间至少还要添几个点）。
其中 \(l\) 枚举可以添加点的数量。
\[dp[i][l+dis(i,j)-1]=\max(dp[i][l+dis(i,j)-1],dp[j][l]+dis(i,j)) \]#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10;
int dp[1000][1000];
struct node
{
int x,y;
}a[N];
int dis(int i,int j)
{
return abs(a[i].x-a[j].x+a[i].y-a[j].y);
}
bool cmp(node a,node b)
{
return a.x==b.x?a.y<b.y:a.x<b.x;
}
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;
for(int i=1;i<=n;i++)
dp[i][0]=1;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(a[j].y<=a[i].y)
for(int l=0;(l+dis(i,j)-1)<=k;l++)
dp[i][l+dis(i,j)-1]=max(dp[i][l+dis(i,j)-1],dp[j][l]+dis(i,j));
}
}
int maxx=-INT_MAX;
for(int i=1;i<=n;i++)
for(int j=0;j<=k;j++)
maxx=max(maxx,dp[i][j]+k-j);
cout<<maxx<<endl;
}
考试的时候在判最大值的之后写了 \(j=1\) 开始，直接爆掉 \(30\) 分。
笑了，最简单的最长不下降序列的 \(30\) 分我反而没拿到。
考完还去问了学长正解，结果差点尴尬了。
\(T4\) 搞了差不多有 \(1h\) \(30min\)，留给我的时间不多了。
看回 \(T3\)，是一道大模拟。先看特殊性质的分很好搞（主要是没有优先级），括号的话通过搜索判左右区间即可。
虽然剩下还有时间，但是我还是不想搞了。（这一部分搜索不太熟练。）
最后看到了\(|s|\leq3\) 还有 \(15\) 分钟，因为不用检查文件，我开始了闲情雅致。开始枚举情况，成功的得到了 \(10\) 分。
赛时代码不堪入目，都懂的。
赛后参考了一下题解也打出来了，原来使用栈和 \(vecotr\) 维护。麻了。
结束了。。。等 \(GD\) 自主举行的考试罢。
成绩：\(100+100+60+70=330\)。
晚上和 \(npy\) 聊天，瞬间觉悟：还是 \(npy\) 好。
标签：10,int,ll,times,VP,2022,CSP,dp,dis From： https://www.cnblogs.com/JuneFailue/p/18118848