首页 > 代码库 > 惨不忍睹考试合集

惨不忍睹考试合集

2024-09-11 23:48:56   209人阅读

 

分别发的话实在太丑了以后就都堆这儿吧qwq

阿我到底什么时候才能强那么一点点呢qwq

太菜辣太菜辣qwq

 

 

4.1考试

愚人节快乐另外——

怀念张国荣。

 

我们讲道理 为什么我在考场上全程脑子瓦特觉得sqrt（1e10）会比log（1e10）要小？？？？

黑人问号。

1.MR板子题 不想说什么 打了一半觉得log比sqrt大就去找规律了 结果成功跪烂

 

2.背包计数问题

全场最神 暴力n^3 带上一些没有什么特别用处的优化 n^2logn 还是基本没分

fhr dalao机智地蒙点打表很牛逼的中了（%%%%%

推了一下 界线定到了n/2 然后实在头疼不想写要太多思维的题了 看到第三题网络流觉得好像还可做 于是这题放弃。

方法很神 界线定到了sqrt (n)一半在跑noip2001数的划分 另一半在滚动数组跑背包？利用推背包时候的分解可以得出一个用余数维护的数组

详见：http://blog.csdn.net/mrazer/article/details/51497933

这种优化我觉得我想出来的时候可能地崩山摧壮士死了

顺带提下还有方法 然而对目前的我而言是完全看不懂的 qwq ：http://r64.is-programmer.com/posts/200017.html (orz r_64学长

技术分享 
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<string>
 7 #include<cmath>
 8 #define ll long long
 9 #define db double
10 #define M 310
11 #define N 100100
12 #define mod 23333333
13 using namespace std;
14 int f[2][N],g[M][N],tmp[N];
15 ll gg[N],ff[N];
16 int main(){
17     //freopen ("gb.in","r",stdin);
18     //freopen ("gb.out","w",stdout);
19     int n;
20     scanf ("%d",&n);
21     f[0][0]=g[0][0]=1;
22     int now=0,pre=1;
23     int m=(int)ceil(sqrt((double)n));
24     for (int i=1;i<=m;++i){
25         for (int j=0;j<i;++j) tmp[j]=0;
26         swap(now,pre);
27         for (int j=0;j<=n;++j){
28             int q=j%i;
29             tmp[q]+=f[pre][j],tmp[q]%=mod;
30             f[now][j]=tmp[q];
31             if (j>=i*i) tmp[q]-=f[pre][j-i*i],tmp[q]+=mod,tmp[q]%=mod;
32         }
33     }
34     for (int i=0;i<=m;++i)
35         for (int j=0;j<=n;++j){
36             if (j+m+1<=n) g[i+1][j+m+1]+=g[i][j],g[i+1][j+m+1]%=mod;
37             if (i&&j+i<=n) g[i][j+i]+=g[i][j],g[i][j+i]%=mod;
38         }
39     for (int i=1;i<=n;++i)
40         for (int j=1;j<=m;++j)
41             gg[i]+=g[j][i],gg[i]%=mod;
42     for (int i=0;i<=n;++i) ff[i]=f[now][i],ff[i]%=mod;
43     gg[0]=1;
44     ll ans=0;
45     for (int i=0;i<=n;++i) ans+=(ff[i]*gg[n-i]%mod),ans%=mod;
46     printf ("%lld\n",ans);
47     return 0;
48   }
View Code

另外记得要随时%%23333 以及该开long long的地方不要吝啬。

 

3.保密 详见网络流专题

惨不忍睹考试合集


联系
我们