2015年多校联训赛第二场题目是什么？
- 内容介绍
- 文章标签
- 相关推荐
本文共计3062个文字，预计阅读时间需要13分钟。
pythondef hdu5301Buildings(n, b, m): # 定义动态规划数组 ans=[0] * (n + 1) # 初始化边界条件 for i in range(b, n + 1): ans[i]=1 # 动态规划填充 for i in range(1, n + 1): for j in range(i, n + 1): ans[j] +=ans[j - i] # 计算结果 return ans[m]
示例调用n=100b=1m=50print(hdu5301Buildings(n, b, m))
hdu 5301Buildings
机智题，卡了好久，最后小坤纸上去敲过了。。做法：假设n hdu 5302Connect the Graph 构造题。当n >= 5时肯定有解。n为奇数，假设b2 = n, w2 = n，直接可以构造出1，2，3……n一个环满足b2 = n，构造1，3，5……2，4……1这样的环满足w2 = n。n为偶数，假设b2 = n, w2 = n，可以构造出1，2，3……n满足b2 = n，构造1，3，5……2，n，n-2，n-4……4满足w2 = n。对于b2 != n, w2 != n直接拆环就好了。对于n <= 4爆搜一下就好了。（实际上b0, b1, b2, w0, w1, w2都大于等于1，小于5的情况好像只有1,2,1,1,2,1才有解，其他无解，不需要搜）
一道十分好的贪心题。最多只能绕一次环。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 11 #define inf 0x3f3f3f3f12 #define eps 1e-913 #define FOR(i,s,t) for(int i = s; i一道FFT的题目。用复数模板的FFT会因为精度误差而wa，又找了一个用快速数论变换的模板。中间有一个O(1)longlong内的乘法，我也不知道为什么这样算是对的。。
设所有的答案为 sigma(j - i +1) * X^(Sj - Si)，拓展开来就可以得到题解的式子，可以用FFT求出所有正数的答案。ans0再另外处理一下。
（c++交上去是超时的，g++才能过）
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 11 #define inf 0x3f3f3f3f 12 #define eps 1e-5 13 #define pii pair 14 #define MP make_pair 15 #define LL long long 16 #define N 100010 17 #define M 200020 18 #define mod 1000000007 19 20 int read(){ 21 int ret = 0; char ch = getchar(); 22 while(ch '9') ch = getchar(); 23 while(ch >= '0' 28 putchar(x % 10 + '0'); 29 } 30 const LL P = 50000000001507329LL, NN = 1LL<>= 1; 42 } 43 return ret; 44 } 45 LL wn[25]; 46 void getWn(){ 47 for(int i = 0; i <= 20; ++i){ 48 int t = 1 << i; 49 wn[i] = qpow(G, (P - 1) / t, P); 50 } 51 } 52 void Rader(LL *a, int len){ 53 int k; 54 for(int i = 1, j = len / 2; i算24点。傻逼了，7个7竟然没算出来。。贴纬哥的代码
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 11 #define inf 0x3f3f3f3f 12 #define eps 1e-9 13 #define FOR(i,s,t) for(int i = s; i本文共计3062个文字，预计阅读时间需要13分钟。
pythondef hdu5301Buildings(n, b, m): # 定义动态规划数组 ans=[0] * (n + 1) # 初始化边界条件 for i in range(b, n + 1): ans[i]=1 # 动态规划填充 for i in range(1, n + 1): for j in range(i, n + 1): ans[j] +=ans[j - i] # 计算结果 return ans[m]
示例调用n=100b=1m=50print(hdu5301Buildings(n, b, m))
hdu 5301Buildings
机智题，卡了好久，最后小坤纸上去敲过了。。做法：假设n hdu 5302Connect the Graph 构造题。当n >= 5时肯定有解。n为奇数，假设b2 = n, w2 = n，直接可以构造出1，2，3……n一个环满足b2 = n，构造1，3，5……2，4……1这样的环满足w2 = n。n为偶数，假设b2 = n, w2 = n，可以构造出1，2，3……n满足b2 = n，构造1，3，5……2，n，n-2，n-4……4满足w2 = n。对于b2 != n, w2 != n直接拆环就好了。对于n <= 4爆搜一下就好了。（实际上b0, b1, b2, w0, w1, w2都大于等于1，小于5的情况好像只有1,2,1,1,2,1才有解，其他无解，不需要搜）
一道十分好的贪心题。最多只能绕一次环。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 11 #define inf 0x3f3f3f3f12 #define eps 1e-913 #define FOR(i,s,t) for(int i = s; i一道FFT的题目。用复数模板的FFT会因为精度误差而wa，又找了一个用快速数论变换的模板。中间有一个O(1)longlong内的乘法，我也不知道为什么这样算是对的。。
设所有的答案为 sigma(j - i +1) * X^(Sj - Si)，拓展开来就可以得到题解的式子，可以用FFT求出所有正数的答案。ans0再另外处理一下。
（c++交上去是超时的，g++才能过）
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 11 #define inf 0x3f3f3f3f 12 #define eps 1e-5 13 #define pii pair 14 #define MP make_pair 15 #define LL long long 16 #define N 100010 17 #define M 200020 18 #define mod 1000000007 19 20 int read(){ 21 int ret = 0; char ch = getchar(); 22 while(ch '9') ch = getchar(); 23 while(ch >= '0' 28 putchar(x % 10 + '0'); 29 } 30 const LL P = 50000000001507329LL, NN = 1LL<>= 1; 42 } 43 return ret; 44 } 45 LL wn[25]; 46 void getWn(){ 47 for(int i = 0; i <= 20; ++i){ 48 int t = 1 << i; 49 wn[i] = qpow(G, (P - 1) / t, P); 50 } 51 } 52 void Rader(LL *a, int len){ 53 int k; 54 for(int i = 1, j = len / 2; i算24点。傻逼了，7个7竟然没算出来。。贴纬哥的代码
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 11 #define inf 0x3f3f3f3f 12 #define eps 1e-9 13 #define FOR(i,s,t) for(int i = s; i