CCF-CSP认证考试准备第十一天
### Day11: 1.202303-2 2.202305-2 3.202309-2 4.202312-2(结束第二题)
#### 1.202303-2:垦田计划(模拟，10分->85分->100分)
(1)85分代码:
```
#include <bits/stdc++.h>
using namespace std;
struct Farm{
int time;
int cnt;
};
bool cmp(const Farm& fa,const Farm& fb){
return fa.time<fb.time;
}
int main(){
ios::sync_with_stdio(false);
int n,m,k;
cin>>n>>m>>k;
vector<Farm> vfarms(n+1);
vector<long long> vCnts(n+1,0);//前缀和记录天数
for(int i=1;i<=n;i++){
cin>>vfarms[i].time>>vfarms[i].cnt;
}
sort(vfarms.begin()+1,vfarms.end(),cmp);
for(int i=1;i<=n;i++){
vCnts[i]=vCnts[i-1]+vfarms[i].cnt;
}
int i=n;
int j=i;;
while(m>=0 && i>0){
static int backSumCnt=0;//上一次循环的总资源消耗量
if(vfarms[i].time<=k){
break;
}
while(j>0 && vfarms[i].time==vfarms[j].time){
j--;
}
if(j<=0){
break;
}
int sumCnt=vCnts[i]-vCnts[j]+backSumCnt;//相同开垦耗时的总消耗资源数量+上一次循环的总资源消耗量
backSumCnt=sumCnt;
long long sum=sumCnt*(vfarms[i].time-vfarms[j].time);
if(sum<=m){
m-=sum;
i=j;
j=i-1;
}
else{
break;
}
}
int res=vfarms[i].time;
if(j==0){
int tmp=m/vCnts[n];
res=max(k,vfarms[i].time-tmp);
}
cout<<res;
return 0;
}
```
**10分原因:构建前缀和数组要在对数组排序之后进行，而不是在输入遍历的时候就构建**
目前还未找到85分原因
（2）学习：
上面85分代码繁琐的地方就是
```
int sumCnt=vCnts[i]-vCnts[j]+backSumCnt;//相同开垦耗时的总消耗资源数量+上一次循环的总资源消耗量
backSumCnt=sumCnt;
long long sum=sumCnt*(vfarms[i].time-vfarms[j].time);
```
计算消耗资源数量部分，既要用static变量记录前一循环的消耗量，还要用双指针加上前缀和计算当前资源消耗量，太过麻烦，所以直接可以考虑用一个
```
map<int,int> flag;//flag记录开垦耗时相同的所有区域降低一天的总耗资源量
```
map记录（不用vector是因为开垦耗时是不连续的，稀疏的），然后类似于后缀和开垦耗时要降低一天就要`flag[i-1]+=flag[i];`(**抽象**：同一元素的某个值累加放到map中记录，前一元素的某个值继承后一个元素的某个值)
除此之外要考虑用struct存储是为了什么，是方便用sort排序吗？两个元素不一定struct是最好的选择，要获取最大值或者最小值可以间接获取
**代码**：
```
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int n,m,k;
cin>>n>>m>>k;
vector<int> vTimes(n),vRes(n);
int maxTime=-1;
for(int i=0;i<n;i++){
cin>>vTimes[i]>>vRes[i];
maxTime=max(maxTime,vTimes[i]);
}
map<int,int> flag;
for(int i=0;i<n;i++){
flag[vTimes[i]]+=vRes[i];//flag记录开垦耗时相同的所有区域降低一天的总耗资源量
}
int res=maxTime;
for(int i=maxTime;i>=k;i--){
if(m>=flag[i]){
m-=flag[i];
res--;
flag[i-1]+=flag[i];
}
else{
break;
}
}
cout<<res;
return 0;
}
```
结构体存储(更好一点）：
```
vector<Farm> vfarms(n);
for(int i=0;i<n;i++){
cin>>vfarms[i].time>>vfarms[i].cnt;
}
sort(vfarms.begin(),vfarms.end(),cmp);
map<int,int> flag;
for(int i=0;i<n;i++){
flag[vfarms[i].time]+=vfarms[i].cnt;//flag记录开垦耗时相同的所有区域降低一天的总耗资源量
}
int res=vfarms[n-1].time;
for(int i=vfarms[n-1].time;i>=k;i--){
```
更极端一点，其实根本不需要存储输入的时间和资源量，因为都放到flag里面了(但这里节省的空间其实没必要，最好存储起来)
```
int maxTime=-1;
int time,cnt;
map<int,int> flag;
for(int i=0;i<n;i++){
cin>>time>>cnt;
maxTime=max(maxTime,time);
flag[time]+=cnt;//flag记录开垦耗时相同的所有区域降低一天的总耗资源量
}
```
#### 2.202305-2:矩阵运算(模拟,70分->100分)
(1)基础知识（矩阵的叉乘和点乘运算法则）：
1.点乘：
2.叉乘：
(2)70分原因：内存超限（从左往右算）
（3）**优化**(计算顺序的改变）：
(W⋅(Q×KT))×V
从左往右算，因为d<<n,而矩阵运算可以交换，为( (1xn) · ( (nxd)x(dxn) ) )x(nxd),从左往右算(nxd)x(dxn)=(nxn)，然后计算(nxn)x(nxd),非常麻烦,而从右往左算(dxn) x(nxd)=(dxd)，然后计算(nxd)x(dxd),大大简化
```
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int n,d;
cin>>n>>d;
vector<vector<int>> vQ(n,vector<int>(d,0));
vector<vector<int>> vK(n,vector<int>(d,0));
vector<vector<int>> vKT(d,vector<int>(n,0));
vector<vector<int>> vV(n,vector<int>(d,0));
vector<vector<long long>> vKTxV(d,vector<long long>(d,0));
vector<int> vW(n,0);
for(int i=0;i<n;i++){
for(int j=0;j<d;j++){
cin>>vQ[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<d;j++){
cin>>vK[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<d;j++){
cin>>vV[i][j];
}
}
for(int i=0;i<n;i++){
cin>>vW[i];
}
for(int i=0;i<d;i++){
for(int j=0;j<n;j++){
vKT[i][j]=vK[j][i];
}
}
//矩阵叉乘
for(int i=0;i<d;i++){
for(int j=0;j<d;j++){
long long tmp=0;
for(int k=0;k<n;k++){//单独一个k就行
tmp+=vKT[i][k]*vV[k][j];
}
vKTxV[i][j]=tmp;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<d;j++){
long long tmp=0;
for(int k=0;k<d;k++){
tmp+=vQ[i][k]*vKTxV[k][j];
}
cout<<tmp*vW[i]<<" ";
}
cout<<endl;
}
return 0;
}
```
优化原因:
70分:
```
vector<vector<long long>> vQxKT(n,vector<long long>(n,0));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
long long tmp=0;
for(int Qj=0,KTi=0;Qj<d;Qj++,KTi++){
tmp+=vQ[i][Qj]*vKT[KTi][j];
}
vQxKT[i][j]=tmp;
}
}
```
需要n* n的矩阵，而且运算要n* n * d
100分:
```
vector<vector<long long>> vKTxV(d,vector<long long>(d,0));
for(int i=0;i<d;i++){
for(int j=0;j<d;j++){
long long tmp=0;
for(int k=0;k<n;k++){
tmp+=vKT[i][k]*vV[k][j];
}
vKTxV[i][j]=tmp;
}
}
```
只需要d* * d的矩阵，而且运算只要d* d * n
#### 3.202309-2:坐标变换（其二）(前缀和,前缀积)
(1)操作和查询以及题目的描述就是使用前缀和和前缀积简化，其中拉伸k倍使用前缀积（初始化为1），角度累加用前缀和（初始化为0），且数学公式推导得出两种操作的先后顺序没有影响。
还是最好用scanf和printf
(2)代码（100）：
```
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
scanf("%d%d",&n,&m);
vector<double> vk(n+1,1);
vector<double> vkS(n+1,1);
vector<double> vtheta(n+1,0);
vector<double> vthetaS(n+1,0);
int op;
double t;
for(int i=1;i<=n;i++){
scanf("%d%lf",&op,&t);
if(op==1){
vk[i]=t;
}
else{
vtheta[i]=t;
}
}
for(int i=1;i<=n;i++){
vkS[i]=vkS[i-1]*vk[i];
vthetaS[i]=vthetaS[i-1]+vtheta[i];
}
int i,j;
int x,y;
while(m--){
double resx=0,resy=0;
scanf("%d%d%d%d",&i,&j,&x,&y);
resx=x*(vkS[j]/vkS[i-1]);
resy=y*(vkS[j]/vkS[i-1]);
double tmp=resx;
double theta=vthetaS[j]-vthetaS[i-1];
resx=resx*cos(theta)-resy*sin(theta);
resy=tmp*sin(theta)+resy*cos(theta);
printf("%.3f %.3f\n",resx,resy);
}
return 0;
}
```
#### 4.202312-2：因子化简(模拟，质因数)
(1)思想：题目每次查询就是要获取数的素因子，而每次查询再求会超时，所以就提前把200以内的素数放到一个数组里面以便后边查询（数量很少，遍历数组很快）
**注意**：输入的n和结果res都要开成long long，一开始n写的int不对
(2)代码(100):
```
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int q;
cin>>q;
vector<int> vPrimes;
vPrimes.push_back(2);
for(int n=3;n<200;n+=2){
bool isPrime=true;
for(int i=3;i<=sqrt(n);i+=2){
if(n%i==0){
isPrime=false;
break;
}
}
if(isPrime){
vPrimes.push_back(n);
}
}
while(q--){
long long n,k;
cin>>n>>k;
map<int,int> mp;//<底数,指数>
long long res=1;
long long t=n;
for(auto it=vPrimes.begin();it!=vPrimes.end();){
if(t==1) break;
int x=*it;
if(t%x==0){
mp[x]++;
it=vPrimes.begin();
t/=x;
}
else{
it++;
}
}
for(auto x:mp){
if(x.second>=k){
res*=(int)pow(x.first,x.second);
}
}
cout<<res<<endl;
}
return 0;
}
```