1.珂朵莉与数字
描述：
众所周知，珂朵莉是世界上最幸福的女孩子；
但这道题目和幸福没有任何关系。
珂朵莉发现，对于任何一个正整数都有一个珂学值，那就是该正整数的n次方的正根。
因为珂学崇尚简洁，所以你只需要告诉珂朵莉该珂学值向下取整的结果
输入：
第1行一个整数t，表示一共有t个整数
接下来t行每行有两个整数x，n，表示询问正整数x的n次方的正根
输出：
共t行，每行一个整数，分别为每次询问的结果
思路：
目标是求 x 的 n次方正根，调用 pow函数 即可
核心代码：
pow(x,(double)1/n)
2.珂朵莉与序列(前缀和)
描述：
众所周知，珂朵莉是世界上最幸福的女孩子；
但这道题目与幸福没有任何关系；
珂朵莉发现，对于任何一个序列a都有唯一一个珂学序列，即每个数与其他所有数的差的绝对值之和
由于珂学崇尚伟大，所以这串序列的数量可能非常大
但由于珂学又崇尚专一，所以并没有要求对序列进行修改
输入：
第1行一个整数n，表示序列a一共有n个整数
第2行n个整数，表示序列a
输出：
共1行，n个整数，分别为a[i]与其他所有数的差的绝对值之和
提示：
对于30%的数据，n<=100
对于60%的数据，n<=1000
对于另外20%的数据，a[i]<=10
对于100%的数据，n<=105,每个整数的值小于等于109,1<=l<=r<=n
思路：对于每一个点值去搜索一遍复杂度是O(n2)，而我们可以用前缀和优化这个复杂度到O(nlogn)
就是先标记好序列中元素的位置，根据值的大小对序列中的元素排序，排好序的序列每个数的查询值就是
查询值=(本点前面数的个数*本点的值-本点前面的值的和)+(本点后面值的和-本点后面值的个数*本点值的和)；
此时把查询值储存起来再根据之前标记的位置排回来即可；
复杂度即为排序的复杂度：O(nlogn)
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx = 1e18; const int N = 1e5+100; const int p = 1e4; const double eps = 1e-8; ll n; struct node{ ll num;//存数 int key;//标记位置 ll sum1;//存查询值 }a[N]; ll sum2[N];//前缀和数组 bool cmp1(node a,node b) { return a.num<b.num; }//根据值排序 bool cmp2(node a,node b) { return a.key<b.key; }//根据位置排序 int main() { cin>>n; for(int i=1;i<=n;i++) { scanf("%lld",&a[i].num); a[i].key=i; } sort(a+1,a+1+n,cmp1); for(int i=1;i<=n;i++) { sum2[i]=sum2[i-1]+a[i].num; }//预处理前缀和 for(int i=1;i<=n;i++) { a[i].sum1=(i-1)*a[i].num-sum2[i-1]+(sum2[n]-sum2[i])-(n-i)*a[i].num; }//求出查询值 sort(a+1,a+1+n,cmp2);//排会原位 for(int i=1;i<=n;i++) { printf("%lld ",a[i].sum1); }//输出 }
3.珂朵莉与字符串(线性dp+高精)
描述：
众所周知，珂朵莉是世界上最幸福的女孩子；
但这道题目与幸福没有任何关系；
珂朵莉发现，对于任何一个字符串s都有一个珂学值，即其中含有子序列“chtholly”的个数
由于珂学崇尚壮阔，珂学值的结果可能很大
输入：
第1行一个字符串S。
输出：
共1行，一个整数，表示珂学值
提示：
对于10%的数据，|S|<=8
对于30%的数据，|S|<=20
对于60%的数据，|S|<=1000
对于100%的数据，|S|<=100000
答案保证在可输出的范围内
之前见过这类线性dp的题，与之前的“有几个ACM”思路相同
不懂思路的可以先去看看我之前的博客
有几个ACM
这个题的要注意的地方有两点
1.s最大长度为十万，ull存不下，要用高精；
2.串中存在重复元素，注意加到顺序
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx = 1e18; const int N = 1e5+100; const int p = 1e4; const double eps = 1e-8; string s; int len; int cntc[p],cnth1[p],cntt[p],cnth2[p],cnto[p],cntl1[p],cntl2[p],cnty[p]; int lenc=1,lenh1=1,lent=1,lenh2=1,leno=1,lenl1=1,lenl2=1,leny=1; void check() { int carry=0; for(int i=1;i<=lenc;i++) { cntc[i]+=carry; carry=cntc[i]/10; cntc[i]%=10; } while(carry) { cntc[++lenc]=carry%10; carry/=10; } }//处理第一个元素'c' 的个数 void add(int a[],int b[],int &lena,int &lenb) { int i=1,j=1,carry=0; int k=1,c[N]; memset(c,0,sizeof(c)); while(i<=lena||j<=lenb) { c[k]=a[i]+b[j]+carry; carry=c[k]/10; c[k]%=10; i++;j++;k++; } while(carry) { c[k]=carry%10; carry/=10; k++; } for(int i=1;i<k;i++) { a[i]=c[i]; } lena=k-1; }//高精加 int main() { cin>>s; len=s.size(); for(int i=0;i<len;i++) { if(s[i]=='c') cntc[1]++; check(); if(s[i]=='h') add(cnth1,cntc,lenh1,lenc); if(s[i]=='t') add(cntt,cnth1,lent,lenh1); if(s[i]=='h') add(cnth2,cntt,lenh2,lent); if(s[i]=='o') add(cnto,cnth2,leno,lenh2); if(s[i]=='l') add(cntl2,cntl1,lenl2,lenl1); if(s[i]=='l') add(cntl1,cnto,lenl1,leno);//注意这两个l加的顺序，这两个l是相邻的，一个l不能先做左边的l，再做右边的l，所以有要先加右边的l if(s[i]=='y') add(cnty,cntl2,leny,lenl2); } for(int i=leny;i>=1;i--) cout<<cnty[i]; }
4.珂朵莉与面积：
描述：
众所周知，珂朵莉是世界上最幸福的女孩子；
但这道题目与幸福终于有了一点关系；
珂朵莉在平面上发现了一个圆，其圆心位于点（0,0），半径为1，她还发现有两条直线x=L,x=R（保证 L,R为实数且-1<=L<=R<=1），对于这个圆而言，这两条直线之间的区域和这个圆相交的面积是“幸福区域”。
由于珂学崇尚精确，珂朵莉要求该幸福区域的面积并请你保留3位小数
输入：
第1行两个实数L，R，表示两直线。
输出：
共1行，每行一个实数，表示答案。要求保留3位小数
思路：一道数学题，肯定要分为两种情况，一种是两个线异侧，另一种是是两个线同侧，异侧两边面积相加，同侧做差取绝对值；
两侧面积我们可以分解：
分解为扇形面积+三角形面积
扇形面积为：asin(x)(一条直线围成的两个)
三角形面积为：x*sqrt(1-x * x)(一条线围成的大三角形面积)
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx = 1e18; const int N = 1e5+100; const int p = 1e4; const double eps = 1e-8; double l,r; const double pi = 3.141592653589793; int main() { cin>>l>>r; if(l>0&&r>0||l<0&&r<0) { l=abs(l); r=abs(r); printf("%.3lf",fabs(asin(r)+r*sqrt(1-r*r)-asin(l)-l*sqrt(1-l*l)));//同侧相减取绝对值 } else { l=abs(l); printf("%.3lf",asin(r)+r*sqrt(1-r*r)+asin(l)+l*sqrt(1-l*l)); }//异侧相加 }
注意反三角求出的就是弧度，不用再次转换成弧度！
