注：本系列題目全是按照通過率降序來排列的，基本保證題目難度遞增。
?
1、
題目名稱：游戲任務標記
來源：騰訊
題目描述
游戲里面有很多各式各樣的任務，其中有一種任務玩家只能做一次，這類任務一共有1024個，任務ID范圍[1,1024]。請用32個unsigned int類型來記錄著1024個任務是否已經完成。初始狀態都是未完成。 輸入兩個參數，都是任務ID，需要設置第一個ID的任務為已經完成；并檢查第二個ID的任務是否已經完成。 輸出一個參數，如果第二個ID的任務已經完成輸出1，如果未完成輸出0。如果第一或第二個ID不在[1,1024]范圍，則輸出-1。
輸入描述:
輸入包括一行,兩個整數表示人物ID.輸出描述:
輸出是否完成示例1
輸入
1024 1024輸出
1分析：經過（艱難的）讀題，分析出只有兩個數相等，才輸出1，否則第二個ID一定未完成，輸出0，不在范圍輸出-1即可。
p=(input().split())
f,s=int(p[0]),int(p[1])
if f not in range(1,1025) or s not in range(1,1025):print(-1)
elif s==f:print(1)
else:print(0)當然，這可能不是題目的本意，真的這么寫可能會被打。
1024=32*32,因此可用32個整數表示1024位(因為每個整數32位)
因為任務ID范圍是1~1024,所以減1轉化為0~1023
然后任務ID除以32，商為存到哪個整數，余數為該整數對應位（置1即可）
注：除以32相當于直接右移5位，對32取余相當于"與31"（這個技巧只對2的次方數有效）．
#include <iostream>
using namespace std;unsigned int arr[32];int main()
{int id1, id2;while(cin>>id1>>id2){if(!(id2>=1 && id2<=1024)){cout<<-1<<endl;continue;}arr[(id1-1)>>5] |= (1<<(id1&31));cout<<( (arr[(id2-1)>>5] & (1<<(id2&31))) != 0)<<endl;}return 0;
}?
2、
題目名稱：網絡走法數目
來源：美團
題目描述
有一個X*Y的網格，小團要在此網格上從左上角到右下角，只能走格點且只能向右或向下走。請設計一個算法，計算小團有多少種走法。給定兩個正整數int x,int y，請返回小團的走法數目。
輸入描述:
輸入包括一行，逗號隔開的兩個正整數x和y，取值范圍[1,10]。輸出描述:
輸出包括一行，為走法的數目。示例1
輸入
3 2
輸出
10分析：
函數f(a,b)代表走到坐標（a,b)的走法數目
#include<iostream>
using namespace std;
int step(int m,int n){if(m == 0 || n == 0)return 1;return step(m - 1,n) + step(m,n -1);
}
int main(){int x,y;cin >> x >> y;cout << step(x,y) <<endl;
}最笨寫法，太多的重復子問題計算
簡單動態規劃
用二維表記錄下來結果，并加以利用。
壓縮：我們發現，除了這個位置上本身的數，DP[i,j]只和DP表中左邊和上邊的值有關，所以可以生成長度為矩陣較小邊長一維表，用兩層循環。注意順序，從左向右打表，只有這樣，左邊的那個元素才是被更新過的，才是本行的左邊那個元素。
l=(input().split())
x,y=int(l[0])+1,int(l[1])+1
l=[0]*x
l[0]=1
for p in range(y):for i in range(1,x):l[i]+=l[i-1]
print(l[-1])3、
題目名稱：幸運數
來源：京東
題目描述
小明同學學習了不同的進制之后，拿起了一些數字做起了游戲。小明同學知道，在日常生活中我們最常用的是十進制數，而在計算機中，二進制數也很常用。現在對于一個數字x，小明同學定義出了兩個函數f(x)和g(x)。 f(x)表示把x這個數用十進制寫出后各個數位上的數字之和。如f(123)=1+2+3=6。 g(x)表示把x這個數用二進制寫出后各個數位上的數字之和。如123的二進制表示為1111011，那么，g(123)=1+1+1+1+0+1+1=6。 小明同學發現對于一些正整數x滿足f(x)=g(x)，他把這種數稱為幸運數，現在他想知道，大于0且小于等于n的幸運數有多少個？
輸入描述:
每組數據輸入一個數n(n<=100000)輸出描述:
每組數據輸出一行，小于等于n的幸運數個數。示例1
輸入
21
輸出
3分析：思想確實不難，按照題目意思走就可以了。實現稍微考察了coding能力吧，就要多練。
給出各種語言的實現：
python：
def f1(n):ret,t=0,nwhile 1:ret+= t%2t=t//2if t==0:breakreturn ret
def f2(n):q=0for i in str(n):q+=int(i)return q
r=int(input())
k=0
for i in range(1,r+1):if f1(i)==f2(i):k+=1
print(k)java：
package 幸運數;
import java.util.*;
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNext()) {int n = in.nextInt();int count = 0;for (int i = 1; i <= n; i++) {if (f(i) == g(i)) {count++;}}System.out.println(count);}}/** 二進制 */private static int g(int n) {int sum = 0;while (n != 0) {sum += n % 2;n /= 2;}return sum;}/** 十進制 */private static int f(int n) {int sum = 0;while (n != 0) {sum += n % 10;n /= 10;}return sum;}
}c++：
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<stdlib.h>
#define N 30;
using namespace std;
int f(int i)
{int sum = 0;while(i){sum+=i%10;i/=10;}return sum;
}
int g(int i)
{int sum = 0;for(int j = 1;j<100000;j*=2){if((j&i)==j) sum++;}return sum;
}
int main()
{//cout<<f(123)<<endl;cout<<g(123)<<endl;int n;while(cin>>n){int sum = 0;for(int i = 1;i<=n;i++){if(f(i)==g(i)) {sum++;}}cout<<sum<<endl;}return 0;
}4、
題目名稱：解救小易
來源：網易
題目描述
有一片1000*1000的草地，小易初始站在(1,1)(最左上角的位置)。小易在每一秒會橫向或者縱向移動到相鄰的草地上吃草(小易不會走出邊界)。大反派超超想去捕捉可愛的小易，他手里有n個陷阱。第i個陷阱被安置在橫坐標為xi?，縱坐標為yi?的位置上，小易一旦走入一個陷阱，將會被超超捕捉。你為了去解救小易，需要知道小易最少多少秒可能會走入一個陷阱，從而提前解救小易。
輸入描述:
第一行為一個整數n(n ≤ 1000)，表示超超一共擁有n個陷阱。
第二行有n個整數xi，表示第i個陷阱的橫坐標
第三行有n個整數yi，表示第i個陷阱的縱坐標
保證坐標都在草地范圍內。輸出描述:
輸出一個整數,表示小易最少可能多少秒就落入超超的陷阱示例1
輸入
3
4 6 8
1 2 1輸出
3分析：從[1,1]走到[X，Y]需要（X-1）+（Y-1）步這樣對每個陷阱計算一下從[1,1]到陷阱所用的步數，求最小值即可。
n=int(input())
//保存橫縱坐標
x=[int(x) for x in input().split()]
y=[int(x) for x in input().split()]
s=x[0]-y[0]-2//保存值
for i in range(n):s=min(x[i]+y[i]-2,s)
print(s)5、
題目名稱：身份證分組
來源：去哪網
題目描述
18位身份證的編碼規則是：
前1、2位數字表示：所在省（直轄市、自治區）的代碼
第3、4位數字表示：所在地級市（自治州）的代碼
第5、6位數字表示：所在區（縣、自治縣、縣級市）的代碼；
第7—14位數字表示：出生年、月、日；
第15、16位數字表示：所在地的派出所的代碼；
第17位數字表示性別：奇數表示男性，偶數表示女性；
第18位數字是校檢碼，用來檢驗身份證的正確性。
用戶在輸入身份證的過程中經常會輸入錯誤，為了方便用戶正確輸入需要在輸入過程中對用戶的輸入按照 6+8+4 的格式進行分組，實現一個方法接收輸入過程中的身份證號，返回分組后的字符
輸入描述:
輸入數據有多行，每一行是一個輸入過程中的身份證號輸出描述:
分組后的字符串示例1
輸入
5021
502104 198803
5021041988033084
502104198803308324
輸出
5021
502104 198803
502104 19880330 84
502104 19880330 8324?
分析：就是判斷一下字符串長度的情況
s=input().replace(' ','')
if len(s)<=6:print(s)
elif len(s)<=14:print(s[0:6]+' '+s[6:])
else:print(s[0:6]+' '+s[6:14]+' '+s[14:])有些同學沒學python，找了個別人的c++，自己看吧
#include <iostream>
#include <string>
using namespace std;//按順序輸出字符串，跳過空格
//重新確定空格的位置，輸出時對非空格字符計數，6及18時輸出一個空格
//注意一種特殊清空，字符串就6個，那么計數為6時不加空格
int main(){string s;while(getline(cin,s)){int cnt=0;for(int i=0;i<s.size();++i){if(s[i]!=' '){++cnt;cout<<s[i];if(i==s.size()-1) break;if(cnt==6||cnt==14) cout<<" ";}}cout<<endl;}
}?
)
