T1 图像旋转

本题是水题，只需要仔细看看旋转后的坐标和旋转前的坐标规律即可！

T2 定价

本题是一个贪心

思路1

正常是要选定一个价格，然后找出所有的小于等于它的价格，然后++ai，这样子需要n^2

思路2

那么我们sort一下，这样子我们选定的ai，那么就可以定下来，i个物品是小于等于ai的，然后就可以出来了！

有序化在考虑有些问题的时候，还是很方便的，希望大家以后能尝试一下！

    sort(a+1,a+1+n);    
    for(ll i=1;i<=n;i++)
        ans=max(ans,(n-i+1)*a[i]); 
    cout<<ans;

T3 先修课程

本题是一个拓扑排序，本质就是通过入度为0的课程起手，塞入队列中，然后bfs跑一遍即可！如果不是很了解的建议先看看拓扑排序

	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		in[v]++;
	}
	for(int i=1;i<=n;i++)
		if(!in[i]) q.push(i);
	while(!q.empty()){
		int u=q.front();
		cnt++;
		q.pop();
		for(int i=0;i<G[u].size();i++){
			int x=G[u][i];
			in[x]--;
			if(in[x]==0) q.push(x);
		}
	}
	if(cnt==n) cout<<"Valid";
	else cout<<"Invalid";

T4保持距离

本题是一个二分答案，二分答案并没有多高级，其实就是通过二分快速尝试答案是否在可行性范围里面，所以往往用在寻找最优解上，所以我们利用二分不停的逼近答案！

这里给大家一个比较好的模板！

	int l=0,r=1e10,mid,ans=-1;//这个l和r还是需要自己去估算的，还有就是l和r很大的话注意开long long，防止mid爆int
	while(l<=r){
		mid=l+r>>1;
		if(check(mid))ans=mid,l=mid+1;//这里为什么要用ans=mid呢，就是我们为了保留一个可行性的解，如果ans最终还是等于-1，就表示一个都不可行
		else r=mid-1;
	}

然后其实二分答案最难的就是check部分的代码，这里还是简单的，就是模拟这个距离，然后去保留即可

bool check(long long x){
	int now=1,pos=1,cnt=1;
	while(pos<=n){
		if(a[pos]-a[now]<x) pos++;
		else{
			now=pos;
			cnt++;
		}
	}
	if(cnt>=k) return true;
	else return false;
}

T5 作品展示

本题是一个数学思维题，

首先求出总数，我们给他设置一个平均数ave

其次，如果我们最多的社团人数大于这个平均数，显然这个社团的人是多余作品的数量的，所以我们把问题所见，去除这个社团人数，并认为只要剩下的社团去拼凑队伍即可！

具体还是看代码把！

这里用sort来实现，不过效率没有priority_queue快，能做的同学可以去想想看用priority_queue实现的

    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum+=a[i];//求和
    }
    sort(a+1,a+1+n);//排序
    for (int i=n;i>=1;i--){//从人数最多的社团开始
        long long ave=sum/m;//求平均数
        if (a[i]<=ave){//当前最多的社团人数小于平均数，则平均数是解
            cout<<ave;
            return 0;
        }else{//否则去掉最大的社团，继续
            sum-=a[i];
            m--;
        }
    }

这个代码还有点问题，同学们自己可以去思考一下正解！

T6 树的连通子图

本题对初一同学来说有点超纲了，树形DP的板子题

其实就是树形DP结合组合数学中的初步，加法和乘法原理

long long mod=1000000007;
void dfs(int x){
    dp[x][0]=1;
    for(int i=0;i<v[x].size();i++){//递归所有子树
    	int t=v[x][i];
    	if(dp[t][1]==0) dfs(t);
    	dp[x][1]+=dp[t][1]+dp[t][0];//不含根的加法原理，先加不含根的,再加含根的
        dp[x][1]%=mod;
        dp[x][0]*=(dp[t][0]+1);//含根的乘法原理
        dp[x][0]%=mod;
    }
}
int main() {
    scanf("%d",&n);
    for (int i=2;i<=n;i++){
        int x;
        scanf("%d",&x);
        v[x].push_back(i);
    }
    dfs(1);//从根开始递归
    cout<<(dp[1][0]+dp[1][1])%mod;
    return 0;
}

反思如何写：

反思大纲如下：

P1你没学过的是那几个题目

P2没学过什么知识点

P3这个知识点是如何应用的

P4这几个知识点转换成代码是怎么写的

P5洛谷上有什么相似题推荐（我们可以根据大家的推荐，作为下周的题单）