2020 CCPC Wannafly Winter Camp Day1 A,B,E~I题解
程序员文章站
2022-07-15 16:13:55
...
A. 期望逆序对
题意：
给定n个随机变量的区间[l, r]，每个随机变量的值为区间内随机取一个整数。假设你给出一个1~n的排列，可以使得这n个随机变量按照排列摆放后逆序对的期望值最小，求其该排列下逆序对的期望值。
解题思路：
要使逆序对较小，排在前面的数应该尽量小于后面的数，不妨大力猜测按照每个随机变量期望值排序后得到的序列就是最优序列。
关于这个猜测证明，因为相邻位置前者期望肯定不大于后者，否则调换后整个序列期望逆序对会更少（因为调换相邻位置对与其它位置产生的逆序对不影响），这个关系又具有可传递性，及每个相邻位置前者期望都小于等于后者。
将n个随机变量按照区间中点排序后题目便转化成求这个随机变量序列的逆序对期望值。
直接枚举两个变量i， j（序列中i在j前面)。因为i的期望小于等于j，所以i的区间总体来说是在j的左侧的。故分四类讨论计算答案：
（图片里第二类分子中的+1不小心写成-1了）
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define Inf 223372036854775807
#define maxn 201000
using namespace std;
typedef long long ll;
const ll mod=998244353;
const double eps=1e-9;
const double PI=acos(-1.0);
struct item
{
ll l, r, z, inv;
}p[maxn];
ll n, ans, inv[maxn];
ll ksm(ll a, ll b)
{
ll ans=1;
while (b)
{
if (b&1) ans=ans*a%mod;
b=b>>1, a=a*a%mod;
}
return ans;
}
int main()
{
cin>>n;
for (int i=1; i<=n; i++)
{
cin>>p[i].l>>p[i].r;
p[i].z=p[i].l+p[i].r;
p[i].inv=ksm(p[i].r-p[i].l+1, mod-2);
}
sort(p+1, p+1+n, [](item a, item b){return a.z<b.z;});
for (int i=1; i<=n; i++)
{
for (int j=i+1; j<=n; j++)
{
ll temp;
if (p[i].r<=p[j].l) temp=0;
else if (p[i].r<=p[j].r && p[i].l<=p[j].l)
{
temp=(p[i].r-p[j].l+1)*(p[i].r-p[j].l)/2%mod;
}
else if (p[i].l>=p[j].l && p[j].r>=p[i].r)
{
temp=(p[i].r-p[i].l+1)*(p[i].r-p[i].l)/2%mod;
temp=(temp+(p[i].l-p[j].l)*(p[i].r-p[i].l+1)%mod)%mod;
}
else if (p[i].l<=p[j].l && p[i].r>=p[j].r)
{
temp=(p[j].r-p[j].l+1)*(p[j].r-p[j].l)/2%mod;
temp=(temp+(p[j].r-p[j].l+1)*(p[i].r-p[j].r)%mod)%mod;
}
temp=temp*p[i].inv%mod*p[j].inv%mod;
ans=(ans+temp)%mod;
}
}
cout<<ans;
return 0;
}
B. 密码学
题意：
签到题，题意又长，不写了
解题思路：
根据题意，倒着模拟加密操作（加法变减法）就行了
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
#define inf 1e9+1
#define Inf 223372036854775807
#define maxn 1010
#define eps 1e-8
const ll mod=998244353;
string s[maxn];
int num[maxn][maxn], len[maxn], n, m;
int op[maxn][2];
void jm(int l, int r)
{
for (int i=0; i<len[r]; i++)
num[r][i]=(num[r][i]-num[l][i%len[l]]+52)%52;
}
string fun(int x)
{
string s="";
for (int i=0; i<len[x]; i++)
{
if (num[x][i]<=25) s+='a'+num[x][i];
else s+='A'+num[x][i]-26;
}
return s;
}
int main()
{
cin>>n>>m;
for (int i=1; i<=m; i++)
cin>>op[i][0]>>op[i][1];
for (int i=1; i<=n; i++)
{
cin>>s[i];
len[i]=s[i].size();
for (int j=0; j<len[i]; j++)
{
if (s[i][j]>='a' && s[i][j]<='z')
num[i][j]=s[i][j]-'a';
else num[i][j]=s[i][j]-'A'+26;
}
}
for (int i=m; i; i--)
jm(op[i][0], op[i][1]);
for (int i=1; i<=n; i++)
cout<<fun(i)<<"\n";
return 0;
}
E. 树与路径
题意：
给定一颗无根树，有m条指定的路径。假设某点为根的情况下每条路径的权值为两端到其最小公共祖先的长度的乘积。求每个点为根时所有路径的权值之和。
解题思路：
对每个点考虑其为根情况下每条路径的贡献显然会大大的超时，因此需要转换思路，想办法对某一点的答案进行转移。
先设1号点为根，O（m*log（n））的求出1号点的答案。单取一条路径来考虑，取一个点 i 和其父亲 fi 。如果 i 和 fi 之间的边不在这条路径上，显然以这两点为根时这条路径的权值不会变化。如果 i 和 fi 间的边在这条路径上，路径的权值在以这两点为根的情况下的差值便可以求出来，而且这个差值是有迹可循的。
自下往上维护差分，注意增量中的“2x”需要用到二阶差分维护，且在每条路径的最小公共祖先位置需要消除该条路径的差分和二阶差分，细节可以参考代码。
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define Inf 223372036854775807
#define maxn 301000
using namespace std;
typedef long long ll;
const ll mod=998244353;
const double eps=1e-9;
const double PI=acos(-1.0);
ll n, m;
vector<ll> edge[maxn];
ll deep[maxn], fa[maxn][30], ans[maxn];
ll anspp[maxn], ansp[maxn];
void dfs1(ll now, ll f)
{
deep[now]=deep[f]+1;
fa[now][0]=f;
for (ll i=1; (1<<i)<=deep[now]; i++)
fa[now][i]=fa[fa[now][i-1]][i-1];
for (auto &to: edge[now])
if (to!=f) dfs1(to, now);
}
ll lca(ll x, ll y)
{
if (deep[x]<deep[y]) swap(x, y);
while (deep[x]!=deep[y]) x=fa[x][(int)(log2(deep[x]-deep[y])+eps)];
if (x==y) return x;
for (ll i=(log2(deep[x])+eps)+1; i>=0; i--)
if (fa[x][i]!=fa[y][i])
x=fa[x][i], y=fa[y][i];
return fa[x][0];
}
void dfs2(ll now, ll f)
{
for (auto &to: edge[now])
{
if (to==f) continue;
dfs2(to, now);
ansp[now]+=ansp[to];
anspp[now]+=anspp[to];
}
ansp[now]+=anspp[now];
}
void dfs3(ll now, ll f)
{
for (auto &to: edge[now])
{
if (to==f) continue;
ans[to]=ans[now]-ansp[to];
dfs3(to, now);
}
}
int main()
{
cin>>n>>m;
for (ll i=1, u, v; i<n; i++)
{
cin>>u>>v;
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs1(1, 0);
for (ll i=1, u, v; i<=m; i++)
{
cin>>u>>v;
ll LCA=lca(u, v), len=deep[u]+deep[v]-2*deep[LCA];
ans[1]+=(deep[u]-deep[LCA])*(deep[v]-deep[LCA]);
ansp[u]+=len-1, ansp[LCA]-=len-1;
ansp[v]+=len-1, ansp[LCA]-=len-1;
if (deep[u]-deep[LCA]>1)
{
anspp[u]-=2, ansp[u]+=2;
anspp[LCA]+=2, ansp[LCA]+=2*(deep[u]-deep[LCA]-1);
}
if (deep[v]-deep[LCA]>1)
{
anspp[v]-=2, ansp[v]+=2;
anspp[LCA]+=2, ansp[LCA]+=2*(deep[v]-deep[LCA]-1);
}
}
dfs2(1, 0);
dfs3(1, 0);
for (ll i=1; i<=n; i++)
cout<<ans[i]<<"\n";
return 0;
}
F. 乘法
题意：
给定长度为n的数列A和长度为m的数列B，两者中的数字相乘有n*m个结果，求结果中其中第k大的数字
解题思路：
用桶记录B数列的数字，再维护桶的前缀和，这样就可以O（1）查询B数列在某个范围内的数字的个数。二分答案，check时枚举A中的数字，由二分的当前值和A中的值可以得到B中数字符合要求的区间。
较繁琐的地方是数字有正有负，而且还有0的情况，需要分开讨论。
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define Inf 223372036854775807
#define maxn 2010000
using namespace std;
typedef long long ll;
const ll mod=998244353;
const double eps=1e-9;
const double PI=acos(-1.0);
ll num[maxn], cot[maxn], tot[maxn];
ll n, m, k;
ll check(ll x)
{
ll res=0;
for (int i=1; i<=n; i++)
{
if (num[i]==0)
{
if (x>=0) res+=m;
continue;
}
double temp=1.0*x/num[i];
if (temp<-1000000) temp=-1000000;
if (temp>1000000) temp=1000000;
if (num[i]>0) res+=tot[(int)floor(temp)+1000005];
if (num[i]<0) res+=m-tot[(int)ceil(temp-1.0)+1000005];
}
return res>=k;
}
int main()
{
cin>>n>>m>>k;
k=n*m-k+1;
for (int i=1; i<=n; i++)
cin>>num[i];
for (int i=1, x; i<=m; i++)
{
cin>>x;
cot[x+1000005]++;
}
for (int i=0; i<maxn; i++)
tot[i]=cot[i]+tot[i-1];
ll l=-1ll*1e6*1e6, r=1ll*1e6*1e6, mid;
while (r>l+100)
{
mid=(l+r)/2;
if (check(mid)) r=mid;
else l=mid;
}
for (; l<=r; l++)
if (check(l)) break;
cout<<l;
return 0;
}
G. 圆凸包
题意：
给定n个圆，求这些圆形成的凸包周长
解题思路：
易知最后凸包一定是由一些直线和圆弧所组成，且直线一定来自圆与圆的外切线。
考虑寻找到所有外切线的端点后，先筛去其中不可能为边界的点（即被某些圆覆盖了的点），然后对这些端点求凸包。凸包上相邻的点若来自同一个圆，则这段应该是来自该圆的圆弧。
这题困难的地方在于细节较多（其实计算几何都是这个样子 ），包括最后只剩一个圆无外切线的情况，圆弧要取劣弧还是优弧等等。
这题我wa了挺久，最后实在没办法，多了一步操作，把每个圆上下左右四个方向的点都添加到要求凸包的点集里（在从点集里筛除被覆盖的点操作之前完成），然后求圆弧的时候就默认为劣弧才ac这题。大概是我之前的代码还有漏洞没处理好吧，不过wa了十几发已经不想纠结这个了。
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define Inf 223372036854775807
#define maxn 100010
using namespace std;
typedef long long ll;
const ll mod=998244353;
const double eps=1e-9;
const double PI=acos(-1.0);
int dcmp(double x)
{//避免浮点误差
if (fabs(x)<eps) return 0;
return x<0? -1: 1;
}
struct Point//点&向量
{
double x, y;
int id;
Point(double x=0, double y=0): x(x),y(y) {}
}p[maxn], o, tb[maxn];
int tbtot, ptot;
Point operator + (Point a, Point b) {return Point(a.x+b.x, a.y+b.y);}
Point operator - (Point a, Point b) {return Point(a.x-b.x, a.y-b.y);}
Point operator * (Point a, double b) {return Point (a.x*b, a.y*b);}
Point operator / (Point a, double b) {return Point (a.x/b, a.y/b);}
double Dot(Point a, Point b) {return a.x*b.x+a.y*b.y;}
double Cross(Point a, Point b) {return a.x*b.y-a.y*b.x;}
double PPdis(Point a, Point b)//两点距离
{
return sqrt(Dot(b-a, b-a));
}
bool cmp_jj(Point a, Point b)//对o点极角排序
{//需先设o点
if (atan2(a.y-o.y, a.x-o.x)!=atan2(b.y-o.y, b.x-o.x))
return atan2(a.y-o.y, a.x-o.x)<atan2(b.y-o.y, b.x-o.x);
return a.x<b.x;
}
struct Circle
{
Point o;
double r;
int id;
Circle(Point o=0, double r=1): o(o),r(r) {}
Point get_point(double rad)//由圆心角求点坐标
{
Point temp=Point(o.x+cos(rad)*r, o.y+sin(rad)*r);
temp.id=id;
return temp;
}
}cir[maxn];
int Get_CCtange(Circle a, Circle b, vector<Point> &pa)
{//寻找两圆切线，切线端点储存在pa，pb中，返回切线个数（根据题目修改，只求了外切线）
if (a.r<b.r)
swap(a, b);
int cnt=2;
double d2=PPdis(a.o, b.o), rdif=a.r-b.r, rsum=a.r+b.r;
if (d2<rdif) return 0;//内含，无切线
double base=atan2(b.o.y-a.o.y, b.o.x-a.o.x);
if (dcmp(d2)==0 && dcmp(a.r-b.r)==0) return -1;//无限切线
if (dcmp(d2-rdif)==0)//圆内切
return 1;
double ang=acos((a.r-b.r)/d2);//外切线
pa.push_back(a.get_point(base-ang));
pa.push_back(a.get_point(base+ang));
pa.push_back(b.get_point(base-ang));
pa.push_back(b.get_point(base+ang));
return cnt;
}
void Get_convex_hull(int n, Point point[])//求点集凸包
{//需先设Point tb[maxn]; int tbtot;
for (int i=1; i<=n; i++)
if (point[i].y<point[1].y || (point[i].y==point[1].y && point[i].x<point[1].x))
swap(point[i], point[1]);
o=point[1];
sort(point+2, point+1+n, cmp_jj);
tb[1]=point[1], tb[2]=point[2], tbtot=2;
if (n<3) {tbtot=n; return ;}
for (int i=3; i<=n; i++)
{
while (tbtot>1 && dcmp(Cross(point[i]-tb[tbtot-1],tb[tbtot]-tb[tbtot-1]))!=-1)
tbtot--;
tb[++tbtot]=point[i];
}return ;
}
double cal(Point a, Point b)
{
Circle c=cir[a.id];
double sita=asin(fabs(Cross(b-c.o, a-c.o))/c.r/c.r);
if (dcmp(sita)==0 && dcmp(PPdis(a, b))!=0) sita=PI;
if (sita>PI) sita=2*PI-sita;
return c.r*sita;
}
int T, n;
int main()
{
cin>>T;
while (T--)
{
tbtot=ptot=0;
cin>>n;
for (int i=1; i<=n; i++)
{
cir[i].id=i;
cin>>cir[i].o.x>>cir[i].o.y>>cir[i].r;
}
for (int i=1; i<=n; i++)
for (int j=i+1; j<=n; j++)
{
if (cir[j].id==0) continue;
if (dcmp(PPdis(cir[i].o, cir[j].o)+cir[j].r-cir[i].r)<=0) cir[j].id=0;
}
int cnt=0, cirid;
for (int i=1; i<=n; i++)
if (cir[i].id) cnt++, cirid=i;
if (cnt==1)
{
cout<<cir[cirid].r*2*PI<<endl;
continue;
}
vector<Point> tangeP;
for (int i=1; i<=n; i++)
{
if (cir[i].id==0) continue;
tangeP.push_back(cir[i].get_point(0));
tangeP.push_back(cir[i].get_point(PI/2));
tangeP.push_back(cir[i].get_point(PI));
tangeP.push_back(cir[i].get_point(PI*3/2));
}
for (int i=1; i<=n; i++)
{
if (cir[i].id==0) continue;
for (int j=i+1; j<=n; j++)
{
if (cir[j].id==0) continue;
Get_CCtange(cir[i], cir[j], tangeP);
}
}
for (auto &po: tangeP)
{
for (int i=1; i<=n; i++)
if (dcmp(cir[i].r-PPdis(cir[i].o, po))>0)
po.id=0;
}
for (auto &po: tangeP)
if(po.id!=0) p[++ptot]=po;
Get_convex_hull(ptot, p);
double ans=0;
for (int i=1; i<=tbtot; i++)
{
if (tb[i].id!=tb[i%tbtot+1].id)
ans+=PPdis(tb[i], tb[i%tbtot+1]);
else ans+=cal(tb[i], tb[i%tbtot+1]);
}
cout<<fixed<<setprecision(11)<<ans<<endl;
}
return 0;
}
H. 最大公约数
题意：
给整数n，k，求整数x使得x与1到n的所有数字求gcd，gcd(k, x)的值在这些结果里是唯一的。若x有多解，输出最小解。
解题思路：
若x不为k的倍数（即若gcd(k,x)不为k），则gcd(k, x)的值一定和gcd(x, gcd(k, x))相同x，故x一定为k的倍数。
此外还要保证其它k的倍数与x求gcd后不为k，故x应包含 1到n中所有k的倍数 除以k后出现过的所有质因数。
因为1到500中素数相乘远远超过了long long的范围，所以需要用到大数。
ps：我直接套了大数板子所以代码较长，这个板子还是很好用的
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
#define inf 1e9+1
#define Inf 223372036854775807
#define maxn 1010
#define eps 1e-8
const ll mod=998244353;
struct BigInteger
{
static const int BASE = 100000000; //和WIDTH保持一致
static const int WIDTH = 8; //八位一存储,如修改记得修改输出中的%08d
bool sign; //符号, 0表示负数
size_t length; //位数
vector<int> num; //反序存
//构造函数
BigInteger(long long x = 0) { *this = x; }
BigInteger(const string &x) { *this = x; }
BigInteger(const BigInteger &x) { *this = x; }
//剪掉前导0，并且求一下数的位数
void cutLeadingZero()
{
while (num.back() == 0 && num.size() != 1)
num.pop_back();
int tmp = num.back();
if (tmp == 0)
length = 1;
else
{
length = (num.size() - 1) * WIDTH;
while (tmp > 0)
{
length++;
tmp /= 10;
}
}
}
//赋值运算符
BigInteger &operator=(long long x)
{
num.clear();
if (x >= 0)
sign = true;
else
sign = false, x = -x;
do
{
num.push_back(x % BASE), x /= BASE;
} while (x > 0);
cutLeadingZero();
return *this;
}
BigInteger &operator=(const string &str)
{
num.clear();
sign = (str[0] != '-'); //设置符号
int x, len = (str.size() - 1 - (!sign)) / WIDTH + 1;
for (int i = 0; i < len; i++)
{
int End = str.size() - i * WIDTH;
int start = max((int)(!sign), End - WIDTH); //防止越界
sscanf(str.substr(start, End - start).c_str(), "%d", &x);
num.push_back(x);
}
cutLeadingZero();
return *this;
}
BigInteger &operator=(const BigInteger &tmp)
{
num = tmp.num;
sign = tmp.sign;
length = tmp.length;
return *this;
}
//绝对值
BigInteger abs() const
{
BigInteger ans(*this);
ans.sign = true;
return ans;
}
//正号
const BigInteger &operator+() const { return *this; }
//负号
BigInteger operator-() const
{
BigInteger ans(*this);
if (ans != 0)
ans.sign = !ans.sign;
return ans;
}
// + 运算符
BigInteger operator+(const BigInteger &b) const
{
if (!b.sign)
return *this - (-b);
if (!sign)
return b - (-*this);
BigInteger ans;
ans.num.clear();
for (int i = 0, g = 0;; i++)
{
if (g == 0 && i >= num.size() && i >= b.num.size())
break;
int x = g;
if (i < num.size())
x += num[i];
if (i < b.num.size())
x += b.num[i];
ans.num.push_back(x % BASE);
g = x / BASE;
}
ans.cutLeadingZero();
return ans;
}
// - 运算符
BigInteger operator-(const BigInteger &b) const
{
if (!b.sign)
return *this + (-b);
if (!sign)
return -((-*this) + b);
if (*this < b)
return -(b - *this);
BigInteger ans;
ans.num.clear();
for (int i = 0, g = 0;; i++)
{
if (g == 0 && i >= num.size() && i >= b.num.size())
break;
int x = g;
g = 0;
if (i < num.size())
x += num[i];
if (i < b.num.size())
x -= b.num[i];
if (x < 0)
x += BASE, g = -1;
ans.num.push_back(x);
}
ans.cutLeadingZero();
return ans;
}
// * 运算符
BigInteger operator*(const BigInteger &b) const
{
int lena = num.size(), lenb = b.num.size();
BigInteger ans;
for (int i = 0; i < lena + lenb; i++)
ans.num.push_back(0);
for (int i = 0, g = 0; i < lena; i++)
{
g = 0;
for (int j = 0; j < lenb; j++)
{
long long x = ans.num[i + j];
x += (long long)num[i] * (long long)b.num[j];
ans.num[i + j] = x % BASE;
g = x / BASE;
ans.num[i + j + 1] += g;
}
}
ans.cutLeadingZero();
ans.sign = (ans.length == 1 && ans.num[0] == 0) || (sign == b.sign);
return ans;
}
//*10^n 大数除大数中用到
BigInteger e(size_t n) const
{
int tmp = n % WIDTH;
BigInteger ans;
ans.length = n + 1;
n /= WIDTH;
while (ans.num.size() <= n)
ans.num.push_back(0);
ans.num[n] = 1;
while (tmp--)
ans.num[n] *= 10;
return ans * (*this);
}
// /运算符 (大数除大数)
BigInteger operator/(const BigInteger &b) const
{
BigInteger aa((*this).abs());
BigInteger bb(b.abs());
if (aa < bb)
return 0;
char *str = new char[aa.length + 1];
memset(str, 0, sizeof(char) * (aa.length + 1));
BigInteger tmp;
int lena = aa.length, lenb = bb.length;
for (int i = 0; i <= lena - lenb; i++)
{
tmp = bb.e(lena - lenb - i);
while (aa >= tmp)
{
str[i]++;
aa = aa - tmp;
}
str[i] += '0';
}
BigInteger ans(str);
delete[] str;
ans.sign = (ans == 0 || sign == b.sign);
return ans;
}
// %运算符
BigInteger operator%(const BigInteger &b) const
{
return *this - *this / b * b;
}
// < 运算符
bool operator<(const BigInteger &b) const
{
if (sign != b.sign) //正负，负正
return !sign;
else if (!sign && !b.sign) //负负
return -b < -*this;
//正正
if (num.size() != b.num.size())
return num.size() < b.num.size();
for (int i = num.size() - 1; i >= 0; i--)
if (num[i] != b.num[i])
return num[i] < b.num[i];
return false;
}
bool operator>(const BigInteger &b) const { return b < *this; } // > 运算符
bool operator<=(const BigInteger &b) const { return !(b < *this); } // <= 运算符
bool operator>=(const BigInteger &b) const { return !(*this < b); } // >= 运算符
bool operator!=(const BigInteger &b) const { return b < *this || *this < b; } // != 运算符
bool operator==(const BigInteger &b) const { return !(b < *this) && !(*this < b); } //==运算符
// 逻辑运算符
bool operator||(const BigInteger &b) const { return *this != 0 || b != 0; } // || 运算符
bool operator&&(const BigInteger &b) const { return *this != 0 && b != 0; } // && 运算符
bool operator!() { return (bool)(*this == 0); } // ！ 运算符
//重载<<使得可以直接输出大数
friend ostream &operator<<(ostream &out, const BigInteger &x)
{
if (!x.sign)
out << '-';
out << x.num.back();
for (int i = x.num.size() - 2; i >= 0; i--)
{
char buf[10];
sprintf(buf, "%08d", x.num[i]);
for (int j = 0; j < strlen(buf); j++)
out << buf[j];
}
return out;
}
//重载>>使得可以直接输入大数
friend istream &operator>>(istream &in, BigInteger &x)
{
string str;
in >> str;
size_t len = str.size();
int start = 0;
if (str[0] == '-')
start = 1;
if (str[start] == '\0')
return in;
for (int i = start; i < len; i++)
if (str[i] < '0' || str[i] > '9')
return in;
x.sign = !start;
x = str.c_str();
return in;
}
};
int T;
int n, k;
int mark[510];
void fun(int x)
{
for (int i=2; i*i<=x; i++)
{
if (x%i==0)
{
mark[i]=1;
while (x%i==0) x/=i;
}
}
if (x!=1) mark[x]=1;
}
int main()
{
cin>>T;
while (T--)
{
memset(mark, 0, sizeof(mark));
cin>>n>>k;
BigInteger res=k;
for (int i=2*k; i<=n; i++)
fun(i/k);
for (int i=1; i<=n; i++)
if (mark[i]) res=res*i;
cout<<res<<"\n";
}
}
I. K小数查询
题意：
给n个数，进行m次操作，一种操作是将指定区间内数字里超过x（操作里给出的值）的数字改为x，另一种是询问指定区间内第k（操作里给出的值）小的数字。
解题思路：
官方题解树套树，然而不会，看别人说可以分块搞，于是就做了下。
首先对n个数分块，大小设为 sqrt(n) 不懂最优大小怎么求 ，然后每块记录块中最大值（即块内数字的上限），数字要记录其原本的位置（随便用pair或啥都行），然后按照数字大小排序。
对于修改操作，区间内的整块直接修改这个块的上限就行了，包含区间两端的块则暴力遍历一遍，只修改原本位置处于区间内的数字，然后更新块的上限，并且块内重新按照大小排序。修改操作复杂度O(sqrt(n))。
对于查询操作，二分答案，check的时候对于区间内的整块直接二分得到个数，包含端点的块则暴力查找。复杂度O(log(n)*sqrt(n)*log(sqrt(n)) )。
细节可以参考代码
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define Inf 223372036854775807
#define maxn 201000
using namespace std;
typedef long long ll;
const ll mod=998244353;
const double eps=1e-9;
const double PI=acos(-1.0);
int n, m, num[maxn], upli[maxn], knum, ksize;
vector<pair<int, int> > vec[maxn];
int getid(int x)
{
return (x+ksize-1)/ksize;
}
int fd(int k, int x)
{
if (x<vec[k][0].second) return 0;
int l=0, r=vec[k].size()-1, mid;
while (r>l+1)
{
mid=(l+r)/2;
if (vec[k][mid].second<=x) l=mid;
else r=mid;
}
if (l!=r && l+1<vec[k].size() && vec[k][l+1].second<=x) l++;
return l+1;
}
int check(int x, int l, int r, int k)
{
int res=0;
for (int j=getid(l)+1; j<=getid(r)-1; j++)
{
if (upli[j]<=x)
{
res+=vec[j].size();
continue;
}
else res+=fd(j, x);
}
if (1)
{
int id=getid(l);
for (auto &j: vec[id])
{
if (j.second>upli[id])
j.second=upli[id];
if (j.first<l || j.first>r)
continue;
if (j.second<=x) res++;
}
}
if (getid(l)!=getid(r))
{
int id=getid(r);
for (auto &j: vec[id])
{
if (j.second>upli[id])
j.second=upli[id];
if (j.first<l || j.first>r)
continue;
if (j.second<=x) res++;
}
}
return res>=k;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>m;
for (int i=1; i<=n; i++)
cin>>num[i];
ksize=sqrt(n);
knum=(n+ksize-1)/ksize;
for (int i=1; i<=n; i++)
{
vec[getid(i)].push_back(make_pair(i, num[i]));
upli[getid(i)]=max(upli[getid(i)], num[i]);
}
for (int i=1; i<=knum; i++) sort(vec[i].begin(), vec[i].end(), [](pair<int, int> a, pair<int, int> b){return a.second<b.second;});
for (int i=1, op, l, r, x; i<=m; i++)
{
cin>>op>>l>>r>>x;
if (op==1)
{
for (int j=getid(l)+1; j<=getid(r)-1; j++)
upli[j]=min(upli[j], x);
if (1)
{
int id=getid(l);
for (auto &j: vec[id])
{
if (j.second>upli[id]) j.second=upli[id];
if (j.first<l || j.first>r) continue;
j.second=min(j.second, x);
}
sort(vec[id].begin(), vec[id].end(), [](pair<int, int> a, pair<int, int> b){return a.second<b.second;});
upli[id]=0;
for (auto &j: vec[id]) upli[id]=max(upli[id], j.second);
}
if (getid(l)!=getid(r))
{
int id=getid(r);
for (auto &j: vec[id])
{
if (j.second>upli[id]) j.second=upli[id];
if (j.first<l || j.first>r) continue;
j.second=min(j.second, x);
}
sort(vec[id].begin(), vec[id].end(), [](pair<int, int> a, pair<int, int> b){return a.second<b.second;});
upli[id]=0;
for (auto &j: vec[id]) upli[id]=max(upli[id], j.second);
}
}
if (op==2)
{
int L=1, R=1e9+1, mid;
while (L<R)
{
mid=(L+R)/2;
if (check(mid, l, r, x)) R=mid;
else L=mid+1;
}
cout<<L<<"\n";
}
}
return 0;
}
推荐阅读
-
2020 CCPC Wannafly Winter Camp Day1 A,B,E~I题解
-
2020 CCPC Wannafly Winter Camp Day1 F 乘法 （二分）
-
2020 CCPC Wannafly Winter Camp Day1 H 最大公约数（唯一分解定理）
-
2020 CCPC Wannafly Winter Camp Day1 F 乘法（二分）
-
2020 CCPC Wannafly Winter Camp Day1 B 密码学（ 模拟）
-
2020 CCPC Wannafly Winter Camp Day1 Div.1&2（A题 期望逆序对）（找规律）
-
2020 CCPC Wannafly Winter Camp Day1 （部分题解）
-
2020 CCPC Wannafly Winter Camp Day1 E- 树与路径
-
2020 CCPC Wannafly Winter Camp Day1 Div.1&2F题解
-
2020 CCPC Wannafly Winter Camp Day1 Div1&2（重现赛）B题解