题目描述 繁繁今天学习了二进制，繁繁觉得二进制很神奇，任何一个整数都可以由一些互不相同的2的方幂 表示，例如7的二进制是 ，所以7=4+2+1，繁繁不满足于此，繁繁在想，如果把互不相同这 个条件去掉，会有多少种方案呢？
输入 一行一个整数N(1<=N<=1000000)
输出 一个一个数，表示答案对1000000007取模的结果
输入样例1
7输入样例2
8输入样例3
9输出样例1
6输出样例2
10输出样例3
10提示 样例解释 对于样例1,7=4+2+1=4+1+1+1=2+2+2+1=2+2+1+1+1=2+1+1+1+1+1=1+1+1+1+1+1+1,6种 方案。 对于30%的数据，N<=300 对于50%的数据，N<=10000 对于100%的数据，1<=N<=1000000
简要思路：这题直接推导一个通项公式好像有点困难，不过，我们可以考虑一个数（例如上面的7），设 c n t ( 7 ) cnt(7) cnt(7)为对答案7的统计，从大到小拆除7，我们可以枚举7第一个拆出的数。 如果拆出4，可继续往后统计3拆分但不会拆出比4大的数的个数（3=2+1=1+1+1）； 如果拆出2，可继续往后统计5拆分但不会拆出比2大的数的个数（5=2+2+1=2+1+1+1=1+1+1+1+1）； 如果拆出1，可继续往后统计6拆分但不会拆出比1大的数的个数（6=1+1+1+1+1+1）。 从这可以看出，答案的统计似乎需要有限制的统计方法，头绪不够明晰，似乎只能用计搜，但是，通过仔细观察，我们不难发现拆出的数不能比 2 x 2^x 2x大这一条件好像可以用背包问题来解决，将 2 x 2^x 2x放到外层当做物品循环即可。并且会出现拆出若干同样的数的情况，这就是完全背包了。时间复杂度为 O （ n l o g n ） O（nlogn） O（nlogn）
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #define mod 1000000007 using namespace std; int er[21]; int cnt[1000005]; int n; template < typename T > inline void read( T & res ) { res = 0; T pd = 1; char aa = getchar(); while ( aa < '0' || aa > '9' ) { if ( aa == '-' ) { pd = -pd; } aa = getchar(); } while ( aa >= '0' && aa <= '9' ) { res = ( res << 1 ) + ( res << 3 ) + ( aa - '0' ); aa = getchar(); } res *= pd; return; } int main () { read(n); er[0] = 1; for ( int i = 1 ; i <= 20 ; ++i ) { er[i] = er[i - 1] * 2; } memset( cnt , 0 , sizeof(cnt) ); cnt[0] = 1; for ( int j = 0 ; j <= 20 ; ++j ) { for ( int i = er[j] ; i <= n ; ++i ) { cnt[i] = ( cnt[i] + cnt[i - er[j]] ) % mod; } } printf("%d",cnt[n]); return 0; }题目描述 繁繁想和小伙伴们打游戏，游戏在一个山庄进行，这个山庄有N座山，编号为1到N，为了方便大 家在不同的山之间移动，繁繁建了一些桥，由于技术的原因，桥连接的两座山的高度差不能超过 d，现在已知这些桥，求这个山庄最高的山和最低的山差距最大是多少？数据保证所有山之间都是 联通的。
输入 第一个一个数T，表示测试数据数量（T<=5,2<=N<=50,0<=d<=1000） 每组数据第一行两个数N和d 接下来一个N行N列的矩阵，第i行j列为Y表示i和j之间建了一座桥，否则表示没有建 保证第i行j列和第j行i列值相同，并且第i行第i列值为N
输出 T行，每行一个答案，若最大值可能为正无穷，输出-1
样例输入
3 3 10 NYN YNY NYN 2 1 NN NN 6 1000 NNYNNN NNYNNN YYNYNN NNYNYY NNNYNN NNNYNN样例输出
20 -1 3000提示 样例解释 第一个样例，1和2之间不能超过d，2和3之间不能超过d，那么最大就是1和2差恰好为d，2和3差 恰好为d 第二个样例，1和2之间没有限制，那么他们之间可能差为正无穷 对于20%的数据，T<=3,N<=40 对于50%的数据，T<=3 对于100%的数据，T<=5,2<=N<=50,0<=d<=1000
简要思路：不难看出，在没有环时，答案就是最长的两点最短路*d。 遇到环时，答案也是一样的。 如上图，当一个点经过环到达另一个点时，增加的值为环上的最短路，剩下的长路就随便了，只要符合题意就行。对于环上的两点同理。 本题就是求最大的两点之间最短路，用floyrd算法最方便，时间复杂度为 O ( n 3 ) O(n^3) O(n3)。
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #define N 55 #define M 5005 using namespace std; char s[N]; int dis[N][N]; int maxn , n , t , d; template < typename T > inline void read( T & res ) { res = 0; T pd = 1; char aa = getchar(); while ( aa < '0' || aa > '9' ) { if ( aa == '-' ) { pd = -pd; } aa = getchar(); } while ( aa >= '0' && aa <= '9' ) { res = ( res << 1 ) + ( res << 3 ) + ( aa - '0' ); aa = getchar(); } res *= pd; return; } int main () { read(t); while ( t-- ) { maxn = 0; memset( dis , 0x3f , sizeof(dis) ); read(n); read(d); for ( int i = 1 ; i <= n ; ++i ) { dis[i][i] = 0; scanf("%s",s); for ( int j = i + 1 ; j <= n ; ++j ) { if ( s[j - 1] == 'Y' ) { dis[i][j] = dis[j][i] = 1; } } } for ( int k = 1 ; k <= n ; ++k ) { for ( int i = 1 ; i <= n ; ++i ) { for ( int j = 1 ; j <= n ; ++j ) { dis[j][i] = dis[i][j] = min( dis[i][j] , dis[i][k] + dis[k][j] ); } } } for ( int i = 1 ; i <= n ; ++i ) { for ( int j = i + 1 ; j <= n ; ++j ) { maxn = max( maxn , dis[i][j] ); } } if ( maxn == 0x3f3f3f3f ) { printf("-1\n"); } else { printf("%d\n",maxn * d); } } return 0; }题目描述 繁繁有一个双向队列，队列里有数字1-N这N个数字，繁繁每次可以从队列中任意拿出一个数字， 将其放在队列的头部或者队列的尾部，不停这样操作，直到队列变成升序，求最小操作次数。
输入 第一行一个数字N(N<=50000) 接下来N行，每行一个数字
输出 一个数表示最小操作次数
输入样例1
5 2 5 3 4 1输入样例2
4 3 2 1 4输入样例3
5 4 2 1 3 5输出样例1
2输出样例2
2输出样例3
3提示 样例解释 对于样例1,5个数：2,5,3,4,1 step1:5放到队尾→2,3,4,1,5； step2:1放到队头→1,2,3,4,5； 需要两步操作。 对于30%的数据，N<=100 对于50%的数据，N<=1000 对于100%的数据，N<=50000
简要思路：这题可以换一种思维方式，将一些数按顺序放在开头，另一些数放在末尾，剩下的数就是在原来的数列中也保持1到n的顺序的数。只要找到最大的满足该性质的子序列即可。我们要找的正是“最大数值连续位置可以不连续的单调递增子序列”，方法请参考代码。
#include <iostream> #include <cstdio> #include <cstring> #define N 50005 using namespace std; int num[N] , pos[N] , flag[N]; int n , k; template < typename T > inline void read( T & res ) { res = 0; T pd = 1; char aa = getchar(); while ( aa < '0' && aa < '9' ) { if ( aa == '-' ) { pd = -pd; } aa = getchar(); } while ( aa >= '0' && aa <= '9' ) { res = ( res << 1 ) + ( res << 3 ) + ( aa - '0' ); aa = getchar(); } res *= pd; return; } int main () { read(n); for ( int i = 1 ; i <= n ; ++i ) { read(k); pos[k] = i; } for ( int i = 1 ; i <= n ; ++i ) { if ( pos[i] < pos[i + 1] ) { flag[i] = 1; } } k = 0; int tot = 1; for ( int i = 1 ; i <= n ; ++i ) { if ( flag[i] ) { tot++; } else { tot = 1; } if ( tot > k ) { k = tot; } } printf("%d",n - k); return 0; }这次连简单题都翻车了，以后还是要多注意啊，切忌把简单题复杂化 。
