首页 > 代码库 > 2016.8.27一套简单的题解题报告
2016.8.27一套简单的题解题报告
一套不错的题，需要相关资料的联系我咯
考试分析：
1． 由于题目的名字加上第一道题没读完时我以为是我最不擅长的treeDP(其实不得不说，树和图上的题我真的是不想写，一般都写不对，上课太不认真，这个弱点要加强训练)，我直接跳到了最后一道题，明知考3h还用了30min去分析，不过还是感谢，这30min救了我两道题出来；
这套题的确还是比较简单，后两道题只要认真分析数据都不会有问题，也许是因为暑假切了贪心和递推，我对分析数据比较在行，第三题切完之后还有2h，不过没写高精的我有点慌，打算最后留一点时间来补，然后第一次写矩阵快速幂速度还不错，很快就搞定了，然而卡死在了快速幂上——对快速幂调试了30Min,没什么好怨天尤人的，至少这不是NOIP2016，知道了不会就好好补；然后最后终于过了，时间估算错误以为能过50分，结果log1e9可以看成比较大的常数，ll又慢，就只拿了30分；后来5分钟想了一下优化，没有静下来而且一昧否定，总觉得优化就不能快速幂了没注意自己可以改写法，也算是上了一课吧；
然后分给第一题的时间只有30min了，没有分析只想着能写多少是多少，然而感谢暑假训练来的代码实现能力，几乎10min一次过，不知道多一点时间我能不能分析出来，不过我也满意了，希望以后不要花那么多时间来调试以免耽误时间；
回过头来给第三题完结了一下，不然的话和普通算法没有任何区别——嗯就是相等跳出那里；
2．第二题分析过程：
首先，这反常地是一道很容易看出递推的提题，然后我们要开始抽象化，撇开数值的关系后我们发现，这道题对于某个点来说，它自身数值的系数，周围不同距离的点的系数都是有关系的，于是决定直接算系数，这里就可以用到我刚刚学的矩阵快速幂；
矩阵快速幂的用处其实就是优化这种算很多次而系数又不好算的递推；但是，由于配数据的失误？只过了30分；
正解比矩阵快速幂还要高端一点，是我在考试时没捣鼓出来的序列乘法，利用的是这个矩阵的对称性，其实 递推中应该很多这种多项式本来系数就相同的多次递推，都可以用序列乘法优化到n^2；
3． 手算大法好；拿到以后，迫于题目名字的压力，不敢不全过，然而1e12肯定是不能白过的，于是开始手算找解法顺便放松心情（什么！），算了11 11没有规律，然后21 21开始发现规律了：怎么是等差呢？好奇怪；然后抱着半确定的心算了50 50，果然是这样，正确性也能得到证明，只是这道“最简单的题”算下来应该是要用高精度的，结果配数据的神牛也才发现这件事，默默地配成了ll,由于这套题只考3小时，分析了30min担心没时间的我没有写高精，居然歪打正着地A了，看到cena一片绿简直开心；
4． 手算大法好，还可以用来自己防止出错，对分析数据也很有利；
5． 学过的东西一定要好好掌握，手算一次也是不错的方法，这样才能在考到时马上想出来，实现就不困难了；努力，终于有回报啦！
解题报告：
一. 一道简单题：
题意：选定一个根节点，使得所以子节点的奶牛数乘以它们到根节点的距离的和最小；
分析：-这道题采用的是我原来一直用错的方法，即把子节点的牛加到父节点，让父节点来背这一段距离的锅，这样先走一次dfs就可以枚举边，得到某条边换向之后对结果的影响，即先减去原来这个节点及子节点在这一条路上加过的数，再加上其余节点在转向后要走的路（其余节点的算法就是size[1]-size[x]，这就是先把所有节点的牛加到dfs根节点的好处），所以其实这道题是贪心；
亮点：根据对结果的影响贪心；
程序：
#include<iostream>
#include<cstdio>
#include<vector>
const int maxn=100005;
using namespace std;
int size[maxn],c[maxn],n,dis[maxn],sta,fin,len;
long long ans;
vector<int>e[maxn],w[maxn];
void dfs(int x,int f)
{
int len=e[x].size();size[x]=c[x];//第一次访问；
for(int i=0;i<len;i++){
int y=e[x][i],v=w[x][i];
if(y==f)continue;
dis[y]=dis[x]+v;//唯一父亲；//变量
ans+=dis[y]*c[y];//dis已得到，不能用size;
dfs(y,x);
size[x]+=size[y];
}
}
void move(int x,int f)
{
int len=e[x].size();
for(int i=0;i<len;i++){
int y=e[x][i],v=w[x][i];
if(y==f)continue;
if(size[1]-2*size[y]<0)ans+=size[1]*v-2*size[y]*v;//对儿子节点的操作；
move(y,x);
}
}
int main()
{
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
for(int i=1;i<n;i++){
scanf("%d %d %d",&sta,&fin,&len);
e[sta].push_back(fin);e[fin].push_back(sta);
w[sta].push_back(len);w[fin].push_back(len);//复制要注意变量
}
dfs(1,0);
move(1,0);
printf("%I64d",ans);
return 0;
}
我看了很久的标程：
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 998244353
#define pi acos(-1)
#define inf 0x7fffffff
#define ll long long
using namespace std;
ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
return x*f;
}//读入优化；
int n;
ll ans;
ll c[100005],dis[100005],size[100005];
vector<int> e[100005],w[100005];//动态存链表不容易超内存；
ll dfs(int x,int fa)
{
ll ans=dis[x]*c[x];
size[x]=c[x];
for(int i=0;i<e[x].size();i++)//最好直接保存；
{
int y=e[x][i],v=w[x][i];
if(y==fa)continue;
dis[y]=dis[x]+v;
ans+=dfs(y,x);
size[x]+=size[y];//直接帮背子树距离的锅；
}
return ans;
}
void move(int x,int fa)
{
for(int i=0;i<e[x].size();i++)
{
int y=e[x][i],v=w[x][i];
if(y==fa)continue;//多叉树；
if(size[1]-2*size[y]<0)
{
ans=ans+(size[1]-2*size[y])*v;//这个改变会使ans变小，转一次边；
move(y,x);//一个size是求本来自己的牛数;//1处存总数；
}
}
}//树上求距离
int main()
{
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
c[i]=read();//ll赋给int不会有问题；
for(int i=1;i<n;i++)
{
int u=read(),v=read(),x=read();
e[u].push_back(v);//双向边
e[v].push_back(u);
w[u].push_back(x);//一一对应
w[v].push_back(x);
}
ans=dfs(1,0);
move(1,0);
cout<<ans<<endl;
return 0;
}
二. 一道更简单题：
题意：每个点等于周围d距离的点的值相加，求最后每个点的值；
分析：根据矩阵的对称性用序列乘法，一个固定不动一个循环一下就ok,注意优化时间复杂度；还是可以结合而且甚至可以交换！
注意：dfs时在等于一就不拓展，不然会多出整整一层，至少3~4的常数，而且本身dfs比较慢里面还有步骤，很可怕，这道题2s测试点也就增加了常数倍，本来3e7的算法常数大了就boom;标程常数还要优一点，多学习；矩阵是不能交换的哦所以总是写在最后，只有序列可以
程序：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000000007;
int n,d,k,a[1005];
long long res[1005],ovo[1005],tmp[1005];
void cf(int pd)
{
tmp[1]=0;
if(pd){
for(int i=1;i<=n;i++,tmp[i]=0){
for(int j=1;j<=n;j++){
int qwq=(i-j+1+n)%n;if(!qwq)qwq=n;
tmp[i]+=res[qwq]*ovo[j]%maxn;
}//原理同正方形矩阵，故可“交换”
tmp[i]%=maxn;}
}
else{
for(int i=1;i<=n;i++,tmp[i]=0){
for(int j=1;j<=n;j++){
int qwq=(i-j+1+n)%n;if(!qwq)qwq=n;
tmp[i]+=res[qwq]*res[j]%maxn;//循环；
}
tmp[i]%=maxn;
}
}
for(int i=1;i<=n;i++)res[i]=(long long)tmp[i];
}
void ef(int u)
{
if(u>>1){//
if(u>>1!=1)ef(u>>1);cf(0);
}
if(u&1&&u!=1)cf(1);
}
int main()
{
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
scanf("%d %d %d",&n,&d,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
res[1]=ovo[1]=1;//省去“第一排”；
for(int i=1;i<=d;i++)res[1+i]=res[1-i+n]=ovo[1+i]=ovo[1-i+n]=1;
//向下溢出补一个循环；
ef(k);
for(int i=1;i<=n;i++){
long long ans=0;
for(int j=1;j<=n;j++){
int qwq=(i-j+1+n)%n;if(!qwq)qwq=n;
ans+=res[qwq]*a[j]%maxn;//过程；//顺序
}
printf("%I64d ",ans%maxn);
}
return 0;
}
常数小的标程：语法各种酷炫简洁，只能膜拜；
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdlib.h>
#include <time.h>
#include<cstring>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include <limits.h>
#include<cmath>
#include<map>
#include<queue>
#include<set>
using namespace std;
long long n,d,k;
long long m=1000000007;
void mul(long long a[],long long b[])
{
int i,j;
long long c[1501];
for(i=0;i<n;++i)for(c[i]=j=0;j<n;++j)c[i]+=a[j]*b[i>=j?(i-j):(n+i-j)]%m;
//三目运算简化好帅qwq; //for和运算写一行调试直接跳好厉害 for(i=0;i<n;b[i]=c[i++]%m);
}
long long init[1501],tmp[1501];
int main()
{
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
long long i,j;
scanf("%lld%lld%lld",&n,&d,&k);
//k=1;d=1;
for(i=0;i<n;++i)scanf("%lld",&init[i]);
for(tmp[0]=i=1;i<=d;++i)tmp[i]=tmp[n-i]=1;//边for边简化；//对对称的简化；
while(k)//快速幂的方法一定要掌握！
{
if(k&1)mul(tmp,init);//b存结果；//先把现在的乘一次就是init啦；
mul(tmp,tmp);//mul是算幂的意思可以规范化啦，//等于1的时候反正也不会乘啦；
k>>=1;//这样最后的2变1就不用担心了，反正就顺便乘上去，然后直接输出，
//怎么都不会出问题； //从外到里乘；tmp有的，init同步
//2 2^2 2^3，2*2^2,2^4,2,2*2^2*2^4;
}
for(i=0;i<n;++i)if(i)printf(" %lld",init[i]);else printf("%lld",init[i]);
printf("\n");
return 0;
}
三. 最简单的题：
题意：求k mod 1+到k mod n的值；
分析：找规律，很容易发现在商相同的序列里是商为公差的等差数列；
程序：
#include<iostream>
#include<cstdio>
using namespace std;
long long ans,r,k,n,l,cnt,sta;
int main()
{
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
scanf("%I64d %I64d",&n,&k);
if(n>k)ans+=(n-k)*k;
r=k-1;l=k/2+1;cnt=1;sta=1;
while(1){
ans+=(2*sta+cnt*(r-l))*(r-l+1)/2;
r=l-1;l=k/(++cnt+1)+1;
if(r>0&&l>=0)
sta=k%r;
else break;
if(r==l)break;
}
for(int i=1;i<=l;i++)ans+=k%i;
printf("%I64d",ans);
return 0;
}
不得不说，标程不仅不巧妙还转了很！多！个！弯！
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long LL;
LL n,m;
LL sum;
int main(void)
{
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
scanf("%lld%lld",&n,&m);
sum+=(LL)n*m;//剩下的要减；//容易爆ll;
// printf("%I64d\n",sum);
if (n>m) n=m;
//先把数本身加上去，然后把差的减回来，差的就是结合了顺序
//和商的等差数列； 公式去掉相同的以后，可以看出
//2*n-j(l+r)其实就是首项加末项；
LL l,r,j;
for (LL i=1;i<=n;i=r+1)//i:上次处理的数右边的数；
{
j=m/i,l=m/(j+1)+1,r=m/j;//从前向后移动区间，i加了优化没有那么慢
if (r>=n) r=n;//j:商；l:左区间；r:右区间；区间也是数本身
sum-=(LL)(l+r)*(r-l+1)*j/2;
}
printf("%I64d\n",sum);
return 0;
}//只能告诉我们，有的时候可以根据公式再简化出一个很神奇的东西；尤其是mod这种我们可以自己写公式的东西！
2016.8.27一套简单的题解题报告