好不容易参个赛才做几个小时
http://www.luogu.org/contest/show?tid=624
只做了前4题，后面5题直接空着其实只是刷刷水题
工厂，模拟题
一开始zz想了半天怎么贪心，差点去写搜索，最后突然发现只能按序放……
秒之（一开始没注意规模wa了，改了long long就a了）
——不知道为什么有人T掉，无法理解
1 #include <cstdio> 2 int main() 3 { 4 int n,h,k; 5 long long x=0,ans=0; 6 scanf("%d%d%d",&n,&h,&k); 7 for(int i=1;i<=n;i++) 8 { 9 int a; 10 scanf("%d",&a); 11 x+=a; 12 if(x>h) 13 { 14 x=a; 15 ans++; 16 } 17 ans+=x/k; 18 x%=k; 19 } 20 ans+=x!=0; 21 printf("%lld",ans); 22 return 0; 23 }
一看长度就是水题
T2更神奇，你要解方程倒是出道不是裸的啊
高斯消元不解释——保证唯一解，所以很多东西都不用判
1 #include <cstdio> 2 double a[201][202]; 3 int n; 4 double ans[201]; 5 int main() 6 { 7 scanf("%d",&n); 8 for(int i=1;i<=n;i++) 9 for(int j=1;j<=n+1;j++) 10 scanf("%lf",&a[i][j]); 11 for(int i=1;i<n;i++) 12 for(int j=i+1;j<=n;j++) 13 for(int k=i+1;k<=n+1;k++) 14 if(a[j][i]) 15 a[j][k]=a[i][k]-a[j][k]/a[j][i]*a[i][i]; 16 for(int i=n;i>=1;i--) 17 { 18 ans[i]=a[i][n+1]/a[i][i]; 19 for(int j=1;j<i;j++) 20 a[j][n+1]-=ans[i]*a[j][i]; 21 } 22 for(int i=1;i<=n;i++) 23 printf("%.2f ",ans[i]); 24 return 0; 25 }
这代码长度也是水……醉了
T3一眼就是数学题：
给定n个二次函数，求1~m中整点的最小值
而且还保证了a＞0，可以少讨论几种情况
数学课就该会的题，没a的无颜见初中数学老师
又没看到数据规模，wa了好几遍——无颜见信息老师啊
1 #include <cstdio> 2 int main() 3 { 4 unsigned long long n,m; 5 long long min; 6 bool flag=true; 7 scanf("%llu%llu",&n,&m); 8 for(int i=1;i<=n;i++) 9 { 10 int a,b,c; 11 scanf("%d%d%d",&a,&b,&c); 12 double o=(-1.0*b)/2/a; 13 if(o<1) 14 { 15 if(flag || min>a+b+c) 16 { 17 min=a+b+c; 18 flag=false; 19 } 20 } 21 else 22 if(o>m) 23 { 24 if(flag || min>a*m*m+b*m+c) 25 { 26 min=a*m*m+b*m+c; 27 flag=false; 28 } 29 } 30 else 31 { 32 long long p=(long long)(o+0.5); 33 if(flag || min>a*p*p+b*p+c) 34 { 35 min=a*p*p+b*p+c; 36 flag=false; 37 } 38 } 39 } 40 printf("%lld",min%1000000007); 41 return 0; 42 }
T4终于来了一道非一眼题
但是题目描述跟鬼畜一样（顺便一提，前面3道的描述也是深井冰，实数整数傻傻分不清）
其实就是找一棵树上的连通块个数
显然树形dp
1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 int first[100001],next[100001]; 5 int a[200001],b[200001]; 6 unsigned long long ans=0; 7 unsigned long long dfs(int k,int fa) 8 { 9 unsigned long long s=1; 10 for(int i=first[k];i!=0;i=next[i]) 11 if(b[i]!=fa) 12 { 13 s*=dfs(b[i],k)+1; 14 s%=1000000007; 15 } 16 ans+=s; 17 ans%=1000000007; 18 return s; 19 } 20 int main() 21 { 22 int n; 23 scanf("%d",&n); 24 for(int i=1;i<n;i++) 25 { 26 scanf("%d%d",&a[i],&b[i]); 27 a[i+n]=b[i];b[i+n]=a[i]; 28 next[i]=first[a[i]]; 29 first[a[i]]=i; 30 next[i+n]=first[b[i]]; 31 first[b[i]]=i+n; 32 } 33 dfs(1,0); 34 printf("%llu",ans); 35 return 0; 36 }
dfs真乃缩代码神奇，而且跑一跑树还是挺快的
后面没做过，先口胡一下，在心理上A掉它
T5
在确定一个数为中位数后，肯定从最后面和它前面的最后面开始取数对（两边各取一个，称为一对）
随着数对一对一对取进来，平均数肯定先增大后减小，三分之
复杂度是 枚举中位数*三分，应该能过
T6
= =
题目说了模板题
T7
蜜汁斐波那契（应该是快速面）
一串链上的总和的递推公式的开始两项显然是链上各点开始两项的总和——用树形dp就可以预处理出来，调用O（1）
然后就是求一个特殊的斐波那契（明明就是典型的递推）
推一推就好了吧，，，最后写个快速面
T8
听说dp，听说四次
一听就毫无兴趣
T9
= =
要我再说一遍吗
蜜汁斐波那契（应该是快速面）
一串链上的总和的递推公式的开始两项显然是链上各点开始两项的总和——用树形dp就可以预处理出来，调用O（1）
然后就是求一个特殊的斐波那契（明明就是典型的递推）
推一推就好了吧，，，最后写个快速面
心理上做完了，心情好难受