1.Problem - C - Codeforces
看似是求期望,实际上是推式子,容易发现每天都会由一种可能分裂成两种相差为1的可能,那么在第k天所有的可能可以组成一个由x * 2^k为首项公差为1且一共有2^k项的等差数列,并且在最后一天只会翻倍不会减少因此我们的首项实际上是x*2^(k+1),公差为2,一共2^k项的等差数列,因为我们要求的是期望所以我们算出前n项和之后还要除去2^k,化简完之后答案的式子是x * 2^(k+1) - 2^k + 1,有几点细节问题需要注意
1.过程与结果都要取模,并且发现最后的答案中有减号因此要多加一个mod
2.特判x = 0的情况
3.需要注意x == mod的情况,这种情况下先不要对x取mod
#define yyy cout<<"Yes"<<"\n"
#define nnn cout<<"No"<<"\n"
#define x first
#define y second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<ll , ll> pii;
const int N = 5e5 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;ll x,k;ll qmi(ll a,ll b)
{ll res = 1;a %= mod;while(b){if(b & 1){res = (res * a) % mod;}a = (a * a) % mod;b /= 2;}return res;
}int main()
{IOS;cin>>x>>k;if(x == 0){cout<<0;return 0;}if(x > 1e9 + 7){x %= mod;}ll a = qmi(2 , k + 1) * x % mod,m = qmi(2 , k);cout<<(a - m + 1 + mod) % mod;
}
2.Problem - A - Codeforces
一道计算几何的基础题目,实际上就是要我们求多边形和p点的最短距离和最大距离作为半径形成的圆的面积差,最大距离只需要找距离p最远的顶点即可,但是最短距有可能是某一个顶点也可能是p点向多边形某一条边做的垂线,我们主要讨论如何求出p点到多边形每一条边的垂线长度,假设我们此时三个点分别是p,a,b首先我们需要判定p在ab上的垂足是不是在ab上还是在ab外,这其实就是要求我们的∠pab和∠pba都是<= 90的,那么通过余弦定理可以转换成b * b + p * p - a * a >= 0 && a * a + p * p - b * b >= 0的时候满足条件,接下来我们已知的是三角形三个顶点的坐标,那么我们就可以利用坐标求出三角形三边的长,然后通过海伦公式可以得到三角形的面积,所以p到ab的垂线的长度也很容易就得到了,之后的答案就是大圈面积-小圈面积即可
#define yyy cout<<"Yes"<<"\n"
#define nnn cout<<"No"<<"\n"
#define x first
#define y second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<ll , ll> pii;
const int N = 5e5 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;
const double pi = 3.14159265358979323846265433832795028841971;
int n;
pii a[N];
ll px,py;double f(double x,double y,double xx,double yy)
{return (x - xx) * (x - xx) + (y - yy) * (y - yy);
}double hl(double p,double a,double b,double c)
{return p * (p - a) * (p - b) * (p - c);
}int main()
{IOS;cin>>n>>px>>py;for(int i = 1 ; i <= n ; i++){cin>>a[i].x>>a[i].y;} vector <int> b;double R2 = 0,r2 = 1e16;for(int i = 1 ; i <= n ; i++){double x = f(px , py , a[i].x , a[i].y);R2 = max(R2 , x);r2 = min(r2 , x);int t = i + 1;if(i == n){t = 1;}double x1 = a[i].x,y1 = a[i].y,x2 = a[t].x,y2 = a[t].y;double a = f(px , py , x1 , y1);double b = f(px , py , x2 , y2);double c = f(x1 , y1 , x2 , y2);if(b + c - a < 0 || a + c - b < 0){continue;}a = sqrt(a),b = sqrt(b),c = sqrt(c);double p = (a + b + c) / 2.0;double s = sqrt(hl(p , a , b , c));double h = 2 * s * 1.0 / c;r2 = min(r2 , h * h);}double ans = (R2 - r2) * pi;printf("%.18lf",ans);
}
3.Problem - C - Codeforces
今天div2上的c题,首先我们需要对数组进行排序,那么什么时候这个数组一定合法呢,那就是当a[1] + a[2] > a[n]的时候数组一定合法,那么现在有两条思路,一条是我们从1开始遍历将不合法的小数变成大数,还有一条思路是从n往1遍历将大数变为小数,然后分别在两个数组上进行两种操作取一个最小值,但这是错误的,这就有点类似于之前做过的一道每次可以删去左端点或右端点的一个元素,问删除k个元素后留下的元素之和最大是多少,遇到类似这样的问题单纯的只考虑数组的左端和右端是不严谨的,比如这题如果我们只考虑左端和右端那么遇到
1 1 1 1 2 2 2 2 2 10
这样的样例的时候删左端答案是9，右端是6,但其实最少的操作次数是4,我们只需要将该数组变为
1 2 2 2 2 2 2 2 2 2即可,我们发现这样是在左右两端同时进行了操作,那么就说明这一类问题并不是单纯的选一边进行操作就是正确的,我们可以换一条思路,我们发现每一次删除操作只会改变左右两端也就是说最后剩下来的一定是中间一段完整的子数组,因此我们可以考虑留下最长的子数组不修改,那么问题就转变成了找到一段最长的合法的子数组,那么我们就可以用双指针线性的解决这个问题，以后遇到题目还是不能急着去敲代码,应该多思考一下,在自己目前的思路上纠错。
#define yyy cout<<"Yes"<<"\n"
#define nnn cout<<"No"<<"\n"
#define x first
#define y second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<ll , ll> pii;
const int N = 3e5 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;int n;
ll a[N];void work()
{cin>>n;for(int i = 1 ; i <= n ; i++){cin>>a[i];}sort(a + 1 , a + n + 1);if(a[1] + a[2] > a[n]){cout<<0<<"\n";}else{int maxn = 0;int j = 3;for(int i = 1 ; i <= n ; i++){while(a[i] + a[i + 1] > a[j] && j < n){j++;if(a[i] + a[i + 1] <= a[j]){j--;break;}}if(j - i + 1 >= 3 && a[i] + a[i + 1] > a[j]){maxn = max(maxn , j - i + 1);}}cout<<min(n - maxn , n - 2)<<"\n";}
}int main()
{IOS;int t;cin>>t;while(t--){work();}
}
本来还在思考接下来是否要学习计算几何的知识,感觉还有很多知识没有学,比如计算几何,今天做了这一道题后才发现自己很多高中的基础数学知识都完全忘光了,还有平衡树,主席树等高级数据结构,之前字符串有关的算法像是ac自动机和后缀自动机长时间不使用也会遗忘生疏,还有图论的算法以及dp等等都掌握的不扎实没有办法灵活的利用去解决难题,现在就属于已经学过的不够精通但还有很多甚至都没有学过,明天早上有一场组队vp成都区域赛,晚上十abc,后天晚上是牛客周赛,明天还要推进一下背诵英语单词,估计不一定有精力再学新的算法,目前初步定下来之后的计划就是把每天的两道羊蹄写了之后的时间学习新的算法,就从平衡树开始吧.
