1、二进制中的"101"
输入一个整数,求其二进制序列中用多少个'101',以及第一个'101'出现的位置,二进制序列右端为起始位置。
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;
string Base2Bin(string n){
char a[32];
int len_n = n.size()*4;
int m;
stringstream ss;
ss<<n;
ss>>m;
for (int i=0; i<32; i++){
a[i] = '0';
}
int j = 0;
while(m){
a[j] = m%2 + '0';
m /= 2;
j = j+1;
}
//cout<<endl;
string str = "";
for (int i=len_n-1; i>=0; i--){
str += a[i];
}
return str;
}
int main(){
string n;
int num = 0;
int begin = -1;
int last_begin = 0;
cin>>n;
string str = Base2Bin(n);
string p = "101";
while((begin = str.find(p, begin+1)) != string::npos){
if (begin != -1){
last_begin = begin;
num++;
begin = begin+1;
}
}
if (num == 0){
cout<<num<<" "<<-1<<endl;
}else{
cout<<num<<" "<<str.size()-3-last_begin<<endl;
}
return 0;
}
2、 自定义数据存储格式
题目太长,待补充。。。
/*
测试用例:
,"abc",1,"b,","a,""","6""",bk,,op,"fa","cd
*/
#include <iostream>
#include <string>
using namespace std;
int main(){
string s;
string cnt[100];
freopen("in.txt", "r", stdin);
getline(cin, s);
int count = 0, flag = 0, len = s.size(), error = 0;
for (int i=0; i<len; i++){
if (s[i] == '"'){
if (flag == 0) {
if (cnt[count].size() > 0) error = 1; //如果"出现在字段中间 ,字段头却没有
else flag = 1;
}
else if (flag == 1){
if (i < len-1 && s[i+1] != ','){
if (s[i+1] == '"') {//如果下一个还是"
cnt[count] += '"';
i += 1;
}else{//如果不是", error
error = 1;
}
}
else {
flag = 0;
if (i != len-1){//如果没结束
count++;
i++;
}
}
}
}
else if (s[i] == ','){
if (flag == 0) count++;
else{
cnt[count] += s[i];
}
}
else {
cnt[count] += s[i];
}
}
if (flag || error){
cout<<"ERROR"<<endl;
}else{
cout<<count + 1<<endl;
for (int i=0; i<=count; i++){
if (cnt[i] == "") cout<<"--"<<endl;
else cout<<cnt[i]<<endl;
}
}
return 0;
}
//个人理解,题目中的不明确信息太多,很难全A
3、 好友推荐
有一款社交软件APP,假设注册用户m人(0<m<50), 用户编号为0~m-1,
用r[i][j]表示用户i和用户j之间的好友关系
(r[i][j]=0代表i和j不是好友,r[i][j]=1~9代表是好友且数值代表熟悉程度,其中r[i][j] = r[j][i]),
编制程序,输出特定用户i的n度好友(1<=n<=10, 1表示直接好友,2表示好友的好友),
并按推荐值降序输出好友列表(若推荐值相同,则按好友编号升序, 推荐值是指关系熟悉度之和),
若此用户没有n度好友输出-1.
输入:
输入一个整数T,表示有T组数据(0<T<100)
对于每组数据,输入两行:
第一行, 输入3个整数m, i, n, m表示用户数, 某个特定的用户编号i, n度好友,
即表示本组数据需要输出用户i的n度好友
第二行, 输入一个整型k, 接下来输入3*k个整数, 每三个组成一个关系对,
每个关系有3个整数i, j, w, 表示i和j的好友熟悉程度, 没有输入的关系默认为非好友
输出:
输出T行, 每行对应每组测试数据的用户i的n度好友, 按推荐值降序输出,
若推荐值相同, 则按好友编号升序, 没有n度好友输出-1
测试用例:
输入:
2
10 5 2
13 0 3 5 0 4 9 0 6 8 0 7 5 1 2 6 1 6 3 2 9 7 3 4 3 3 5 3 3 8 3 3 9 3 5 8 9 7 8 9
10 0 2
13 0 3 5 0 4 9 0 6 8 0 7 5 1 2 6 1 6 3 2 9 7 3 4 3 3 5 3 3 8 3 3 9 3 5 8 9 7 8 9
输出:
7 0 4 9
1 5 8 9
/*
思路:
BFS至第n层, 中间可达的需标记
*/
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
int r[55][55];
int vis[55];
typedef struct ND_Friend{
int x, sum, degree;
}NDF;
bool compare (NDF left, NDF right)
{
if (left.sum != right.sum) {
return left.sum > right.sum;
}
else return left.x < right.x;
}
queue<NDF> cq;
void BFS(int m, NDF index){
vis[index.x] = 1;
for (int i=0; i < m; i++){
if (r[index.x][i] != 0 && vis[i] != 1){
//cout<<i<<" "<<index.degree<<"degree"<<endl;
NDF nd;
nd.x = i;
nd.sum = index.sum + r[index.x][i];
nd.degree = index.degree - 1;
cq.push(nd);
vis[i] = 1;
}
}
}
int main(){
int T;
freopen("in.txt", "r", stdin);
cin>>T;
while(T--){
int m, index, n;
cin>>m>>index>>n;
memset(r, 0, sizeof(r));
memset(vis, 0, sizeof(vis));
int k, i, j, w;
cin>>k;
for (int p=0; p<k; p++){
cin>>i>>j>>w;
r[i][j] = w;
r[j][i] = w;
}
NDF root;
root.x = index;
root.sum = 0;
root.degree = n;
cq.push(root);
while(!cq.empty()){
NDF ndf = cq.front();
if (ndf.degree == 0){
break;
}
cq.pop();
BFS(m, ndf);
}
if (cq.empty()){
cout<<"-1"<<endl;
break;
}
int p = 0;
NDF nd_friend[55];
while(!cq.empty()){
NDF ndf = cq.front();
cq.pop();
nd_friend[p++] = ndf;
//cout<<ndf.x<<" "<<ndf.sum<<endl;
}
sort(nd_friend, nd_friend+p, compare);
for (int pp=0; pp<p; pp++){
cout<<nd_friend[pp].x<<" ";
}
cout<<endl;
}
return 0;
}
/*
//遗留问题:
第二个测试用例:
0->3->8 推荐值8
0->7->8 推荐值14
都可达,推荐值不同,测试用例取了第一种,没有给出解释
*/