- 2014
- 武功秘籍 （小学题...）
- 猜字母 （约瑟夫环）
- 大衍数列 （小学题...）
- 打印图形 （代码填空题）
- 神奇算式 (模拟 - 字符串转换 - 分解)
- 绳圈 (难 - dp) 但可以猜
- 分糖果 （模拟）
- 地宫寻宝 (dfs)
- 小朋友排身高 （树状数组 - 区间和数组 - 模板）
- 2014年总结
2000多页的武功秘籍 （注意有1000页 ， 常识！！！：然后1001-1002页与1 - 2 是连在一起的）
书的10与11在同一张纸张上，第11和12页不在同一张纸张上
要想取走书的81到92页的武功，至少要撕下多少张纸带走
答案为7
*/
/*等额本金 （小学题…）
贷款3万块 ，约定24个月，以等额本金方式还款
每个月除了1/24的本金之外，还要还固定的利息
利息公式： 剩余还款本金 * 0.005
问小明在第十五个月需要还款多少（本金和利息的总和）：
答案为浮点数（保留两位小数 如32.5要写成32.50）
1312.50
#include 把abcd…s共19个字母组成的序列重复拼接106次，得到长度为2014的字符串
接下来删除第1个字母（即a），以及第3个字母，第5个字母等所有奇数位置的字母
得到的新串再进行删除奇数位置字母的动作，最后只剩下一个字母，请写出该字母
for()pop if(i%2)continue,else{q.push()}
“abcdefghijklmnopqrs” 赋值： for arr[i] = ‘a’ + i;
可以先用19个试验算法正确性
#include前几项 0 2 4 8 12 18 24 32 40 50
其规律是：对偶数项，是序列平方再除2，奇数项 ，是序号平方减1再除2
填空代码：
test_03(
/*小明在X星球的城堡中发现了如下图形和文字：
rank=3
*
* *
* *
* * * *
rank=5
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
ran=6
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
小明开动脑筋，编写了如下的程序，实现该图形的打印。
*/
70void f (
char [][ a],intN,int , rankint ) rowif ( col==
{
1)rank[][{
a]row='*'col; return ;}
int=
1
; w int ;for
( i=
0;i<-1 i;rank++)*= i2; w ; f(
____________________________________________,
-1a, rank+/2 row,w);f col(,
-1a, rank+/2 row,w+); col}wintmain
(
) char[]
{
[ a]N;intN,;
for i(j=
0;i<;++i)Nfori(=
0;j<;++j)N[j][ a]i=' 'j; f (,
6,a0,0);for(=
0;i<;++ i)Nfor i(={
0;j<;++ j)Nprintf j("%c" ,[][a]i);jprintf("\n"
);}return0
;
} int=
0
/*
请仔细分析程序逻辑，填写缺失代码部分。
答案：
*/
由4个不同数字组成一个乘法算式，它们的乘积仍然由这4个数字组成
如：
210 * 6 = 1260
8 * 473 = 3784
27 * 81 = 2187
如果满足乘法交换律算作同一种情况，那么包含共有多少种 （坑点）
填写该数字
; ans # include
#include#
includebool
#include
using namespace std;
char a[10],b[10],c[10];
int l,sum,ans;
int main(){
for(int i=1;i<=999;i++){
for(int j=1;j<=999;j++){
sum=i*j;
if(sum>1000&&sum<9999&&i
分糖果 （模拟）今天有 100 根绳子 ，当然会有 200 个绳头
如果任意取绳头两两配对 ，把所有的绳头打结连接起来，最后会形成若干个绳圈
我们的问题是：请计算最后将形成多少个绳圈的概率最高
结果为一个整数：
绳 头 圈 （分析）
1 2 1
2 4 圈2 1/3 圈1 2/3
i-1 2(i -1) ci-1
p(x圈) = 形成x圈的组合方式 /所有方式
分析：概率 – >dp
答案： 3
n个小朋友做成一圈，随机发糖果，然后进行下面游戏：
每个小朋友都把自己的糖果分一半给左边的孩子
一轮分糖后，拥有奇数个糖果的孩子由老师补发1个糖果，从而变成偶数
反复进行这个游戏，直到每个小朋友的糖果数都相同为止
问老师要补发多少个糖果
输入：
3
2 2 4
输出：
4
include
int
main(
,&);[n0]//输入N，小朋友的个数。
a=0;for(=//把a[0]定义为一个类似于缓冲区的东西，用于暂时的存放数据。
1;i<=;++i)nscanfi("%d"
,&[])a;iwhile(!//为方便起见，把a[i]直接就看成第i个小朋友 。
)[0flag]//flag初始为0，即现在每人糖数不相等，需要进行以下 *** 作进行重新分配。
（即使现在糖数相同时 以下的 *** 作也不影响目前的每个人的糖数，因为在每人都相等的情况下，无论进行多少次分配都不会改变数据。
）
{
a=[1]a/2;//缓冲区存放第一个小朋友的for(=
1;i<;++i)n[i]=
a[i]/a2i+[+1a]i/2;//用循环语句，依次将前n-1个小朋友的糖果传一半给前一个人[]=
a[n]/a2n+[0]a;//由于大家坐成一个圈，所以第n个小朋友把自己的一半去掉之后同时又得到第一个小朋友糖数的一半（即缓冲区的数目）for(=
1;i<=;++i)nifi([
{
]%a2i!=0)[]={a[i]+a1i;++;}count}for
(
= //用一个循环一次检查是否是奇数，并同时统计老师补发糖的数量。
1;i<=;++i)nifi([
{
]==a[i1]a)=1;
flagelse=0
;{flagbreak;}}}
printf
( //判断是否每个人糖数是否相等，如果糖数都相等，flag=1，此时while(!flag）跳出循环，游戏结束。
如果糖数不相等，继续游戏。
"%d"
,);returncount0;
} //****************递归一定要想清楚上一步 到当前的所有情况//此题还要改进 时间复杂度 -- 四维数组
int
【题目描述】
X 国王有一个地宫宝库。
是 n x m 个格子的矩阵。
每个格子放一件宝贝。
每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。
输入
输入一行3个整数，用空格分开：n m k (1< =n,m< =50, 1< =k< =12)
接下来有 n 行数据，每行有 m 个整数 Ci (0< =Ci< =12)代表这个格子上的宝物的价值
输出
要求输出一个整数，表示正好取k个宝贝的行动方案数。
该数字可能很大，输出它对 1000000007 取模的结果。
输入：
2 2 2
1 2
2 1
输出：
2
输入2：
2 3 2
1 2 3
2 1 5
输出2：
14
/* my~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int d[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}
int map[55][55];
int n,m,k;
int ans = 0;
int mod = 1000000007;
int value[55 * 55]; // ---------优化，每次记录最大的值就好了，与最大的比较就好了，不需要数组
bool check(int v){ //当前宝物值
for(int i = 0;i < k;i++){
if(value[i] < v){
return false;
}
}
return true;
}
void dfs(int x,int y){
if(x >= 0 && x < n &&y >=0 && y < m){
if(check(map[x][y])){ //选或者不选 ...
}
else{ //不能拿
for(int i = 0;i < 4;i++){
dfs(x + d[i][0],y + d[i][1]);
}
}
}
}
int test_06(){
scanf("%d%d%d",&n,&m,&k);
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
scanf("%d",&map[i][j]);
}
}
value[0] = map[0][0];
dfs(0,0);
return 0;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*/
[
55
] data[55];int,,
; n_06constm_06intk_06=
1000000007 ; mod_06 long long;
//题目已经提示数值很大 void ans_06dfs_06 (
int ,int, xint, yint) max//max记录当前最大值， cnt统计当前拿了多少件int cnt= { [
] cur [ data]x;//cur取值比较yif(==
||==x || n_06 ) y //越界 + 看看哪些变量可以剪枝 ，x，y，cnt可以剪枝 m_06 return cnt > k_06; { }
if (
==
-1x && n_06 == - 1 y ) m_06 //出口 if( { ==
||(cnt ( k_06 ==-1cnt ) k_06 && )) // 上一个格子已经k_06件 或者 加上这个格子k_06件 ！！！！ cur > max++ ; { if
ans_06()
%=;ans_06 > mod_06} {
ans_06 } mod_06}
if
(
)
//可以取这个物品 ,更新max = curdfs_06cur > max( { ,
+1x , y , + 1 cur ) cnt ; //只能往右走或往下走 dfs_06(+
1,x , , + y 1 cur ) cnt ; } //对于价值小的，或者价值大但不取dfs_06
(
,
+1x , y , ) ; max dfs_06 cnt (+
1,x , , ) y ; max } cnt inttest_06
(
) scanf("%d%d%d" {
,&,&,n_06&)m_06;fork_06(int
=0; i < ;++ i ) n_06for i(int {
=0; j < ;++ j ) m_06scanf j("%d" {
,&[][data]i);j}}dfs_06
(
0
,0,-1,0);//第一个点的价值可能是0 ， 用-1保证可以选择拿<<<< ;
cout return ans_06 0 endl;
} n3
//树状数组模板
n 个小朋友站成一排。
现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。
开始的时候，所有小朋友的不高兴程度都是0。
如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。
当要求某个小朋友第k次交换时，他的不高兴程度增加k。
请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。
如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。
输入格式
输入的第一行包含一个整数n，表示小朋友的个数。
第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。
输出格式
输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。
样例输入
3
3 2 1
样例输出
9
样例说明
首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。
数据规模和约定
对于10%的数据， 1<=n<=10；
对于30%的数据， 1<=n<=1000；
对于50%的数据， 1<=n<=10000；
对于100%的数据，1<=n<=100000，0<=Hi<=1000000。
预处理 模板
①前缀和数组，存放前缀和累加
如 a[3] = a1 + a2 + a3
但是一个改了，后面的全部都要改
②树状数组
某个区间的和 [k - lowbit(k), k] //lowbit(k)是k的二进制中最后一个1代表的整数
C6 – > 110 --> lowbit(6) = 2
C6 为Sum∑[4,6]
getSum()
①2#包含前面全部项的和
②奇数项只包括自己
③其余的按照 减去二进制的最后1代表的整数的规则 代表包括项
如查前10项 == C10 [8,10] + C8 (2include包含前8项)
int
lowbit(
) int[] {
= arr1, 2 {,3,4,5,6,7,8,9};int[9
] c;memset(,
0,csizeof());cfor(int
=0; i < 8; i ++ )updata i(9 {
,+1,i[],arr)i;}c<<getSum
(
cout , 5)c<<;<< getSum endl(
cout , 6)c<<;<< getSum endl(
cout , 7)c-getSum( , 4)c<<;// Sum[4,7] 第4个元素到第7个元素 return endl0 ;
} //有规律的数列求和 -- 数学公式！！！ 等差 & 等比//只能相邻位， -- 暴力会超时 -- 树状数组的思维转换 （此处代码略）
//每一个数要交换的次数 == 这个数前面比它大的数+后面比它小的数，即逆序对数 ！！
//合并为一步
//解题 ： 不高兴次数 = 1 + 2 + ... + i = i(1+i)/2 (交换次数i) -->转换为记录所有的交换次数，再累加求和
[
]
/*
int test_08() { // ............logic bug ·················
int n;
long long ans = 0;
scanf("%d",&n);
int h[n];
int cnt[n];//记录每个孩子交换的次数
memset(cnt,0,sizeof(cnt));
int maxH = -1;
for(int i = 0; i < n; i++) {
scanf("%d",&h[i]);
if(h[i] > maxH)maxH = h[i];
}
int c[maxH+1];
for(int i = 0; i < n; i++) {
updata(maxH+1,h[i] + 1,1,c); //真正的身高对应成下标 ，在相应位置计数变为1，其实就是用树状数组维护数据出现的个数
//
int sum = getSum(c,h[i] + 1); //小于等于 h[i]+1的数据的个数 h[i]只代表下标，而树状数组中不允许出现0
cnt[i] += (i + 1) - sum; //得到的就是当前数据左侧比数据大的数的个数
}
memset(c,0,sizeof(c));
for(int i = n-1; i >= 0; i--) {
updata(maxH+1,h[i]+1,1,c); //在响应位置的计数变为1，其实就是用树状数组维护数据出现的个数
/*
int sum = getSum(c,h[i]+1); //小于等于 h[i]+1的数据的个数
int self = getSum(c,h[i]+1) - getSum(c,h[i]);
cnt[i] += sum ; //上一步求出的等于h的个数，扣掉自己的个数，得到的就是当前数据右侧比数据小的个数
*/ +=
cntgetSumi( , []c)h;i//求出小于h[i]+1的数据的个数}for (
int
=0; i < ;++ i ) n+= i[] {
ans * cnt(i([]-cnt1i)/2) ; //先除2减小数值}printf (
"%lli\n"
,);returnans0;
} intmain
(
01 武功秘籍 不用运算 ，考验思维（小学题）
02 等额本金 （小学题）
03 猜字母 数组的 *** 作 （挪动数列） – （约瑟夫环）
04 大衍数列 奇偶数
05 打印图形 递归 上下文推测 - 参数的含义（图形规律）
06 神奇算式 枚举 -（字符串排序 比较）
07 神圈 数学归纳 dp推导 （难***）
08 分糖果 模拟
09 地宫取宝 深搜dfs （模板**） 子问题重复求解
10 小朋友排队 （最难****） 树状数组妙用
) test_08() {
;return0;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）