1、现值计算

根据题意直接倒着求价值就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>

using namespace std;

int n;
double money;
double i;//年利率 

double sum(double a,double b)//a为转换前的价值，b为年数 
{
    double li=i+1;
    return a/pow(li,b);
}

int main()
{
    scanf("%d%lf",&n,&i);
    
    scanf("%lf",&money);
    
    for(int i=1;i<=n;i++)
    {
        double temp;
        scanf("%lf",&temp);
        
        money+=sum(temp,i);
        
    }
    
    printf("%lf",money);
    return 0;
}

2、训练计划

该题可以分解为三个部分，首先是求出最早开始的时间，其次是判断是否能够在n天内完成任务，最后是求出每个科目最晚开始的时间

该题可以以依赖关系建模成一颗树，所依赖的科目为该科目的父节点

这样的话，这个题目所划分成的三个部分可以分别理解为： 求出每个科目到根节点所经过的点的权重和+1;一颗树的最大权重路是否大于n;求出每个科目往下的子树的一条
路的最大权值和sum,用n-sum+1(这里用到简单的dp)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>

using namespace std;

int n,m;

vector<int>a;
vector<int>b;

int late[110];

int main()
{
    cin>>n>>m;
    
    a.push_back(0);
    for(int i=1;i<=m;i++)
    {
        int num;
        cin>>num;
        a.push_back(num);//第i个依赖于num ,即第i个在num前完成
    }
    
    b.push_back(0);
    for(int i=1;i<=m;i++)
    {
        int num;
        cin>>num;
        b.push_back(num);//b记录完成所需天数 
    }
    
    //先计算最早开始时间
    for(int i=1;i<=m;i++)
    {
        int day=1,idx=i;
        while(a[idx]!=0)
        {
            day+=b[a[idx]];
            idx=a[idx];
        }
        cout<<day<<' ';
    }
    cout<<'\n';
    
    //再计算最晚开始时间
    //首先判断能否在n天内完成 
    int max_day=0;
    for(int i=1;i<=m;i++)
    {
        int idx=i,temp=0;//temp记录该条路的长度 
        temp+=b[i];
        while(a[idx]!=0)
        {
            temp+=b[a[idx]];
            idx=a[idx];
        }
        max_day=max(max_day,temp);
    }
    if(max_day>n)return 0;
    
    //下面来计算最晚开始时间
    //late数组记录往后的最长路径(不记本身的天数） 
    for(int i=m-1;i>=1;i--)
    {
         for(int j=i+1;j<=m;j++)
         {
         	if(a[j]==i)
         	{
         		late[i]=max(late[i],late[j]+b[j]);
            }
         }
    } 
    
    for(int i=1;i<=m;i++)cout<<n-late[i]-b[i]+1<<' ';
    return 0;
}

3、JPEG解码

大模拟题，根据近几年题目来看，应该是最简单的一个第三题，没有卡数据范围，也没有很臭很长什么的

这个题目的解决步骤已经在题干中说明了(你只需要跟着题意敲就行了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<bits/stdc++.h>

using namespace std;

double Q[8][8],M[8][8],M0[8][8],M1[8][8],M2[8][8];

int n,T;

int main()
{
    //首先读入量化矩阵Q 
    for(int i=0;i<8;i++)
        for(int j=0;j<8;j++)
            cin>>Q[i][j];
            
    cin>>n>>T;
    //然后按指定方法填入M矩阵
    int x=0,y=0;
    for(int i=1;i<=n;i++)
    {
        int num;
        cin>>num;
        if(x==0&&y%2==0)M[x][y++]=num;
        else if(x==0&&y&2==1)M[x++][y--]=num;
        else if(y==0&&x%2==1)
        {
            if(x==7)M[x][y++]=num;
            else M[x++][y]=num;
        }
        else if(y==0&&x%2==0)
        {
            if(x==0)M[x][y++]=num;
            else M[x--][y++]=num;
        }
        else if(x==7)
        {
            if(y%2==0)M[x][y++]=num;
            else M[x--][y++]=num;
        }
        else if(y==7)
        {
            if(x%2==0)M[x++][y--]=num;
            else M[x++][y]=num;
        }
        else if((x+y)%2==0)M[x--][y++]=num;
        else M[x++][y--]=num;
    }
    
//	//M0调错
//	 for(int i=0;i<8;i++)
//		{
//			for(int j=0;j<8;j++)
//			{
//				cout<<M[i][j]<<' ';
//			}
//			cout<<'\n';
//		}
    //进行乘相应元素的计算
    for(int i=0;i<8;i++)
        for(int j=0;j<8;j++)
        {
            M0[i][j]=M[i][j]*Q[i][j];
        }
        
//	//M0调错
//	 for(int i=0;i<8;i++)
//		{
//			for(int j=0;j<8;j++)
//			{
//				cout<<M0[i][j]<<' ';
//			}
//			cout<<'\n';
//		}
    //进行离散余弦逆变换
    for(int i=0;i<8;i++)
        for(int j=0;j<8;j++)
            for(int u=0;u<8;u++)
            for(int v=0;v<8;v++)
            {
                double au,av;
                if(u==0)au=sqrt(0.5);
                else au=1;
                if(v==0)av=sqrt(0.5);
                else av=1;
                M1[i][j]+=0.25*au*av*M0[u][v]*cos(0.125*(i+0.5)*u*acos(-1))*cos(0.125*acos(-1)*(j+0.5)*v);
            }
    
//	//M1调错
//	
//		for(int i=0;i<8;i++)
//		{
//			for(int j=0;j<8;j++)
//			{
//				cout<<M1[i][j]<<' ';
//			}
//			cout<<'\n';
//		}
    
    //每个元素加128后四舍五入， 大于255取255，小于0取0
    for(int i=0;i<8;i++)
        for(int j=0;j<8;j++)
        {
            M2[i][j]=M1[i][j]+128;
            M2[i][j]=(int)(M2[i][j]+0.5);
            if(M2[i][j]>255)M2[i][j]=255;
            if(M2[i][j]<0)M2[i][j]=0;
        }
    //输出结果
    if(T==0)
    {
        for(int i=0;i<8;i++)
        {
            for(int j=0;j<8;j++)
            {
                cout<<M[i][j]<<' ';
            }
            cout<<'\n';
        }
    }
    else if(T==1)
    {
        for(int i=0;i<8;i++)
        {
            for(int j=0;j<8;j++)
            {
                cout<<M0[i][j]<<' ';
            }
            cout<<'\n';
        }
    }
    else if(T==2)
    {
        for(int i=0;i<8;i++)
        {
            for(int j=0;j<8;j++)
            {
                cout<<M2[i][j]<<' ';
            }
            cout<<'\n';
        }
    }
    return 0;
}

4、聚集方差

Splay+启发式合并(正在学习中quq)

每一个子树中所有的点都是一个可重集合，并且一个节点的父亲一定包含该节点的可重集合。
每次暴力的将儿子节点的可重集合合并到父节点会超时，但可以考虑每次只将轻儿子的可重集合合并到重儿子的可重集合，时间复杂度就是 O(logn)的。
因为重儿子的子树大小一定不小于轻儿子的子树大小，也就是父节点的子树大小至少是轻儿子的子树大小的2倍，所以最多有 logn 条轻儿子。
由于每次插入一个新的节点到集合中，只会影响相邻的四个节点的方差。所以计算答案时先将之前的贡献删去，再将新产生的贡献加回来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<cstring>
using namespace std;
const int N=3e5+10;
typedef long long LL;
const LL INF=1e18;
int h[N],e[N],ne[N],root[N],_idx,n;
LL ans[N],a[N];
void add(int a,int b){
    e[_idx]=b,ne[_idx]=h[a],h[a]=_idx++;
}
struct node{
    int son[2],p;//左右儿子 父亲
    int size;//splay的大小
    LL v,min,sum;//v:员工的工作时间 sum:方差 min:splay上其他节点到该节点最短距离的平方
}tr[N];
int idx;
int get_node(int v,int p){
    idx++;
    tr[idx].v=v,tr[idx].p=p;
    tr[idx].sum=0,tr[idx].min=INF;
    tr[idx].size=1;
    return idx;
}
LL calc(int u,int v){
    return (tr[u].v-tr[v].v)*(tr[u].v-tr[v].v);
}
void pushup(int u){
    int l=tr[u].son[0],r=tr[u].son[1];
    //不是空节点才计算最小值
    if(tr[u].p)tr[u].min=min(tr[u].min,calc(u,tr[u].p));
    if(l)tr[u].min=min(tr[u].min,calc(u,l));
    if(r)tr[u].min=min(tr[u].min,calc(u,r));
    tr[u].sum=tr[u].min+tr[l].sum+tr[r].sum;
    tr[u].size=tr[l].size+tr[r].size+1;
}
void rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=(x==tr[y].son[1]);
    tr[z].son[y==tr[z].son[1]]=x,tr[x].p=z;
    tr[y].son[k]=tr[x].son[k^1],tr[tr[x].son[k^1]].p=y;
    tr[x].son[k^1]=y,tr[y].p=x;
    pushup(y),pushup(x);
}
void splay(int& root,int x,int k){
    while(tr[x].p!=k){
        int y=tr[x].p,z=tr[y].p;
        if(z!=k){
            if((tr[z].son[1]==y)^(tr[y].son[1]==x))rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if(!k)root=x;
}
void insert(int p,int& root){
    int u=root,fa=0;
    while(u){
        if(tr[u].v<=tr[p].v)fa=u,u=tr[u].son[1];
        else fa=u,u=tr[u].son[0];
    }
    if(!fa)root=p;
    else tr[fa].son[tr[fa].v<=tr[p].v]=p;
    tr[p].p=fa;
    splay(root,p,0);
}
void Tmerge(int &p, int &root)//启发式合并
{
    if(!p)return;
    Tmerge(tr[p].son[0], root);
    Tmerge(tr[p].son[1], root);
    tr[p].son[0]=tr[p].son[1]=0;
    tr[p].size=1,tr[p].p=0;
    tr[p].min=INF,tr[p].sum=0;
    insert(p,root);
}
void dfs(int u){
    int ptr=get_node(a[u],0);
    insert(ptr,root[u]);
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        dfs(j);
        if(tr[root[u]].size<tr[root[j]].size)swap(root[u],root[j]);
        Tmerge(root[j],root[u]);//启发式合并
    }
    ans[u]=tr[root[u]].sum;//splay根节点的sum就是总共的方差
}
int main(){
    int p;
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=2;i<=n;i++){
        scanf("%d",&p);
        add(p,i);
    }
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    dfs(1);//从根节点开始搜索所有下属
    for(int i=1;i<=n;i++)
        printf("%lld\n",ans[i]);
}