9月 | 2015 | 超客的水墨烟雨

uva12412

maksyuki 发表于 oj 分类，标签: 基础算法-模拟

12 9月 2015

Hi, I am an undergraduate student in institute of foreign languages. As you know, C programming is a required course in our university, even if his/her major is far from computer science. I don't like this course at all, as I am not good at computer and I don't wanna even have a try of any programming!! But I have to do the homework in order to pass 🙁 Sh... Could you help me with it? Please keep secret!! I know that you won't say NO to a poor little girl, boy. 🙂

Task

Write a Student Performance Management System (SPMS).

Concepts

In the SPMS, there will be at most 100 students, each has an SID, a CID, a name and four scores (Chinese, Mathematics, English and Programming).

SID (student ID) is a 10-digit number
CID (class ID) is a positive integer not greater than 20.
Name is a string of no more than 10 letters and digits, beginning with a capital letter. Note that a name cannot contain space characters inside.
Each score is a non-negative integer not greater than 100.

Main Menu

When you enter the SPMS, the main menu should be shown like this:

Welcome to Student Performance Management System (SPMS).

1 - Add

2 - Remove

3 - Query

4 - Show ranking

5 - Show Statistics

0 - Exit

Adding a Student

If you choose 1 from the main menu, the following message should be printed on the screen:

Please enter the SID, CID, name and four scores. Enter 0 to finish.

Then your program should wait for user input. The input lines are always valid (no invalid SID, CID, or name, exactly four scores etc), but the SID may already exist. In that case, simply ignore this line and print the following:

Duplicated SID.

On the other hand, multiple students can have the same name. You should keep printing the message above until the user inputs a single zero. After that the main menu is printed again.

Removing a Student

If you choose 2 from the main menu, the following message should be printed on the screen:

Please enter SID or name. Enter 0 to finish.

Then your program should wait for user input, and remove all the students matching the SID or name in the database, and print the following message (it's possible xx=0):

xx student(s) removed.

You should keep printing the message above until the user inputs a single zero. After that the main menu is printed again.

Querying Students

If you choose 3 from the main menu, the following message should be printed on the screen:

Please enter SID or name. Enter 0 to finish.

Then your program should wait for user input. If no student matches the SID or name, simply do nothing, otherwise print out all the matching students, in the same order they're added to the database. The format is similar to the input format for "adding a student", but 3 more columns are added: rank (1st column), total score and average score (last two columns). The student with highest total score (considering all classes) received rank-1, and if there are two rank-2 students, the next one would be rank-4. You should keep printing the message above until the user inputs a single zero. After that the main menu is printed again.

Showing the Ranklist

If you choose 4 from the main menu, the following message should be printed on the screen:

Showing the ranklist hurts students' self-esteem. Don't do that.

Then the main menu is printed again.

Showing Statistics

If you choose 5 from the main menu, show the statistics, in the following format:

Please enter class ID, 0 for the whole statistics.

When a class ID is entered, print the following statistics. Note that "passed" means to have a score of at least 60.

Chinese

Average Score: xx.xx

Number of passed students: xx

Number of failed students: xx

Mathematics

Average Score: xx.xx

Number of passed students: xx

Number of failed students: xx

English

Average Score: xx.xx

Number of passed students: xx

Number of failed students: xx

Programming

Average Score: xx.xx

Number of passed students: xx

Number of failed students: xx

Overall:

Number of students who passed all subjects: xx

Number of students who passed 3 or more subjects: xx

Number of students who passed 2 or more subjects: xx

Number of students who passed 1 or more subjects: xx

Number of students who failed all subjects: xx

Then, the main menu is printed again.

Exiting SPMS

If you choose 0 from the main menu, the program should terminate. Note that course scores and total score should be formatted as integers, but average scores should be formatted as a real number with exactly two digits after the decimal point.

Input

There will be a single test case, ending with a zero entered in the main menu screen. The entire input will be valid. The size of input does not exceed 10KB.

Output

Print out everything as stated in the problem description. You should be able to play around this little program in your machine, with a keyboard and a screen. However, both the input and output may look silly when they're not mixed, as in the keyboard-screen case.

Sample Input

0011223344 1 John 79 98 91 100

0022334455 1 Tom 59 72 60 81

0011223344 2 Alice 100 100 100 100

2423475629 2 John 60 80 30 99

0022334455

John

0011223344

Output for the Sample Input

Welcome to Student Performance Management System (SPMS).

1 - Add

2 - Remove

3 - Query

4 - Show ranking

5 - Show Statistics

0 - Exit

Please enter the SID, CID, name and four scores. Enter 0 to finish.

Duplicated SID.

Please enter the SID, CID, name and four scores. Enter 0 to finish.

Welcome to Student Performance Management System (SPMS).

1 - Add

2 - Remove

3 - Query

4 - Show ranking

5 - Show Statistics

0 - Exit

Please enter SID or name. Enter 0 to finish.

2 0022334455 1 Tom 59 72 60 81 272 68.00

Please enter SID or name. Enter 0 to finish.

1 0011223344 1 John 79 98 91 100 368 92.00

3 2423475629 2 John 60 80 30 99 269 67.25

Please enter SID or name. Enter 0 to finish.

Welcome to Student Performance Management System (SPMS).

1 - Add

2 - Remove

3 - Query

4 - Show ranking

5 - Show Statistics

0 - Exit

Please enter class ID, 0 for the whole statistics.

Chinese

Average Score: 69.00

Number of passed students: 1

Number of failed students: 1

Mathematics

Average Score: 85.00

Number of passed students: 2

Number of failed students: 0

English

Average Score: 75.50

Number of passed students: 2

Number of failed students: 0

Programming

Average Score: 90.50

Number of passed students: 2

Number of failed students: 0

Overall:

Number of students who passed all subjects: 1

Number of students who passed 3 or more subjects: 2

Number of students who passed 2 or more subjects: 2

Number of students who passed 1 or more subjects: 2

Number of students who failed all subjects: 0

Welcome to Student Performance Management System (SPMS).

1 - Add

2 - Remove

3 - Query

4 - Show ranking

5 - Show Statistics

0 - Exit

Please enter SID or name. Enter 0 to finish.

1 student(s) removed.

Please enter SID or name. Enter 0 to finish.

Welcome to Student Performance Management System (SPMS).

1 - Add

2 - Remove

3 - Query

4 - Show ranking

5 - Show Statistics

0 - Exit

Please enter class ID, 0 for the whole statistics.

Chinese

Average Score: 59.50

Number of passed students: 1

Number of failed students: 1

Mathematics

Average Score: 76.00

Number of passed students: 2

Number of failed students: 0

English

Average Score: 45.00

Number of passed students: 1

Number of failed students: 1

Programming

Average Score: 90.00

Number of passed students: 2

Number of failed students: 0

Overall:

Number of students who passed all subjects: 0

Number of students who passed 3 or more subjects: 2

Number of students who passed 2 or more subjects: 2

Number of students who passed 1 or more subjects: 2

Number of students who failed all subjects: 0

Welcome to Student Performance Management System (SPMS).

1 - Add

2 - Remove

3 - Query

4 - Show ranking

5 - Show Statistics

0 - Exit

Showing the ranklist hurts students' self-esteem. Don't do that.

Welcome to Student Performance Management System (SPMS).

1 - Add

2 - Remove

3 - Query

4 - Show ranking

5 - Show Statistics

0 - Exit

题目类型：复杂模拟题

算法分析：这是一道直叙式模拟题，但是由于要考察的要素很多，所以处理起来比较复杂。对于该问题，只有自顶至下，逐步求精，逐步测试来进行编程。注意数据中存在精度坑点，在判断浮点数关系时使用EPS，否则达不到精度会WA

#include <iostream>
#include <fstream>
#include <cstring>
#include <iomanip>
#include <algorithm>
#define EPS 1e-5
using namespace std;

const int maxn = 1000 + 66;

const char subject[6][16] = {"Chinese", "Mathematics", "English", "Programming"};
const char number[8][26] = {"passed all", "passed 3 or more", "passed 2 or more", "passed 1 or more"
, "failed all"};

struct point
{	
	char sid[36];
	char cid[36];
	char name[36];
	bool is_removed;
	int score[6];
	int all;
	int pas;
};

point stu[maxn];
int len;

void MainMenu ()
{
	cout << "Welcome to Student Performance Management System (SPMS)." << endl << endl;
	cout << "1 - Add" << endl;
	cout << "2 - Remove" << endl;
	cout << "3 - Query" << endl;
	cout << "4 - Show ranking" << endl;
	cout << "5 - Show Statistics" << endl;
	cout << "0 - Exit" << endl << endl;
}
//***********************************************
bool Search (char *val)
{
	int i;
	for (i = 0; i < len; i++)
		if (!stu[i].is_removed && !strcmp (val, stu[i].sid))
			break;

	if (i == len)
		return false;

return true;
}
//***********************************************

int RankSearch (int weizhi)
{
	int ans = 0;
	int i;
	for (i = 0; i < len; i++)
		if (!stu[i].is_removed && stu[i].all > stu[weizhi].all)
			ans++;

return ans + 1;
}

//***********************************************
void DataBaseDelete (char *val)
{
	int i;
	int sum = 0;

	for (i = 0; i < len; i++)
	{
		if (!stu[i].is_removed && (!strcmp (val, stu[i].sid) || !strcmp (val, stu[i].name)))
		{
			sum++;
			stu[i].is_removed = true;
		}
	}

	cout << sum << " student(s) removed." << endl;
}


//***********************************************
void DataBaseQuery (char *val)
{
	int i;
	
	for (i = 0; i < len; i++)
	{
		if (!stu[i].is_removed && (!strcmp (stu[i].sid, val) || !strcmp (stu[i].name, val)))
		{
			cout << RankSearch (i) << " " << stu[i].sid << " " << stu[i].cid << " " 
				 << stu[i].name << " ";
				 
			int j;
			for (j = 0; j < 4; j++)
				cout << stu[i].score[j] << " ";

			cout << stu[i].all << " " << fixed << setprecision (2)
				 << stu[i].all / 4.0 + EPS << endl;
		}
	}

}

//***********************************************
void DataBaseStatistic (char *val)
{
	int i;

	for (i = 0; i < len; i++)
	{
		if (!stu[i].is_removed)			//init!!!!!!
			stu[i].pas = 0;
	}

	char temp[6];
	
	strcpy (temp, val);

	for (i = 0; i < 4; i++)
	{
		cout << subject[i] << endl;

		int j;
		int pass = 0, fail = 0;
		double sum = 0;

		for (j = 0; j < len; j++)
		{
			if (val[0] == '0')
				strcpy (temp, stu[j].cid);

			if (!stu[j].is_removed && !strcmp (temp, stu[j].cid))
			{
				if (stu[j].score[i] >= 60)
				{
					pass++;
					stu[j].pas++;
				}

				else
					fail++;
	
				sum += stu[j].score[i];
			}
		}
		cout << "Average Score: " << fixed << setprecision (2) 
		 << sum * 10.0 / 10 / (pass + fail) + EPS << endl;
		cout << "Number of passed students: " << pass << endl;
		cout << "Number of failed students: " << fail << endl;
		cout << endl;										//important!!!!!!
	}

	int cnt[6];
	memset (cnt, 0, sizeof (cnt));
	strcpy (temp, val);

	for (i = 0; i < len; i++)
	{
		if (val[0] == '0')
			strcpy (temp, stu[i].cid);

		if (!stu[i].is_removed && !strcmp (temp, stu[i].cid))
		{
			cnt[stu[i].pas]++;	
		}
	}

	for (i = 3; i >= 1; i--)				//add the number
	{
		cnt[i] += cnt[i+1];	
	}

	cout << "Overall:" << endl;
	for (i = 0; i < 5; i++)
	{
		cout << "Number of students who " << number[i] << " subjects: " << cnt[4-i] << endl;
	}
	cout << endl;
}
//***********************************************
int main()
{
//	ifstream cin ("aaa.txt");

	MainMenu ();
	len = 0;

	int cmd;

	while (cin >> cmd)
	{
		char input[36];
		int i;

		if (cmd == 0)
			break;

		if (cmd == 1)
		{
			cout << "Please enter the SID, CID, name and four scores. Enter 0 to finish." << endl;

			while (cin >> input)
			{
			if (input[0] == '0' && strlen (input) == 1)
				break;							//important!!!!!!

			if (!Search (input))
			{
				strcpy (stu[len].sid, input);
				
				cin >> stu[len].cid >> stu[len].name;
				
				stu[len].all = 0;
				stu[len].is_removed = false;

				for (i = 0; i< 4; i++)
				{
					cin >> stu[len].score[i];
					stu[len].all += stu[len].score[i];
				}

				len++;
			}

			else
			{
				cout << "Duplicated SID." << endl;
				point temp;
				
				cin >> temp.cid >> temp.name;

				for (i = 0; i < 4; i++)
					cin >> temp.score[i];
			}

			cout << "Please enter the SID, CID, name and four scores. Enter 0 to finish." << endl;
			}
		}

		else if (cmd == 2)
		{
			cout << "Please enter SID or name. Enter 0 to finish." << endl;

			while (cin >> input)
			{
				if (input[0] == '0' && strlen (input) == 1)
					break;

				DataBaseDelete (input);

				cout << "Please enter SID or name. Enter 0 to finish." << endl;
			}
		}

		else if (cmd == 3)
		{
			cout << "Please enter SID or name. Enter 0 to finish." << endl;

			while (cin >> input)
			{
				if (input[0] == '0' && strlen (input) == 1)
					break;

				DataBaseQuery (input);
				cout << "Please enter SID or name. Enter 0 to finish." << endl;

			}
		}

		else if (cmd == 4)
		{
			cout << "Showing the ranklist hurts students' self-esteem. Don't do that." << endl;	
		}

		else if (cmd == 5)
		{
			cout << "Please enter class ID, 0 for the whole statistics." << endl;

			cin >> input;

			DataBaseStatistic (input);
		}

		MainMenu ();
	}

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

#include <iostream>

#include <fstream>

#include <cstring>

#include <iomanip>

#include <algorithm>

#define EPS 1e-5

using namespace std;

const int maxn = 1000 + 66;

const char subject[6][16] = {"Chinese", "Mathematics", "English", "Programming"};

const char number[8][26] = {"passed all", "passed 3 or more", "passed 2 or more", "passed 1 or more"

, "failed all"};

struct point

{

char sid[36];

char cid[36];

char name[36];

bool is_removed;

int score[6];

int all;

int pas;

};

point stu[maxn];

int len;

void MainMenu ()

{

cout << "Welcome to Student Performance Management System (SPMS)." << endl << endl;

cout << "1 - Add" << endl;

cout << "2 - Remove" << endl;

cout << "3 - Query" << endl;

cout << "4 - Show ranking" << endl;

cout << "5 - Show Statistics" << endl;

cout << "0 - Exit" << endl << endl;

}

//***********************************************

bool Search (char *val)

{

int i;

for (i = 0; i < len; i++)

if (!stu[i].is_removed && !strcmp (val, stu[i].sid))

break;

if (i == len)

return false;

return true;

}

//***********************************************

int RankSearch (int weizhi)

{

int ans = 0;

int i;

for (i = 0; i < len; i++)

if (!stu[i].is_removed && stu[i].all > stu[weizhi].all)

ans++;

return ans + 1;

}

//***********************************************

void DataBaseDelete (char *val)

{

int i;

int sum = 0;

for (i = 0; i < len; i++)

{

if (!stu[i].is_removed && (!strcmp (val, stu[i].sid) || !strcmp (val, stu[i].name)))

{

sum++;

stu[i].is_removed = true;

}

cout << sum << " student(s) removed." << endl;

}

//***********************************************

void DataBaseQuery (char *val)

{

int i;

for (i = 0; i < len; i++)

{

if (!stu[i].is_removed && (!strcmp (stu[i].sid, val) || !strcmp (stu[i].name, val)))

{

cout << RankSearch (i) << " " << stu[i].sid << " " << stu[i].cid << " "

<< stu[i].name << " ";

int j;

for (j = 0; j < 4; j++)

cout << stu[i].score[j] << " ";

cout << stu[i].all << " " << fixed << setprecision (2)

<< stu[i].all / 4.0 + EPS << endl;

}

//***********************************************

void DataBaseStatistic (char *val)

{

int i;

for (i = 0; i < len; i++)

{

if (!stu[i].is_removed) //init!!!!!!

stu[i].pas = 0;

}

char temp[6];

strcpy (temp, val);

for (i = 0; i < 4; i++)

{

cout << subject[i] << endl;

int j;

int pass = 0, fail = 0;

double sum = 0;

for (j = 0; j < len; j++)

{

if (val[0] == '0')

strcpy (temp, stu[j].cid);

if (!stu[j].is_removed && !strcmp (temp, stu[j].cid))

{

if (stu[j].score[i] >= 60)

{

pass++;

stu[j].pas++;

}

else

fail++;

sum += stu[j].score[i];

}

cout << "Average Score: " << fixed << setprecision (2)

<< sum * 10.0 / 10 / (pass + fail) + EPS << endl;

cout << "Number of passed students: " << pass << endl;

cout << "Number of failed students: " << fail << endl;

cout << endl; //important!!!!!!

}

int cnt[6];

memset (cnt, 0, sizeof (cnt));

strcpy (temp, val);

for (i = 0; i < len; i++)

{

if (val[0] == '0')

strcpy (temp, stu[i].cid);

if (!stu[i].is_removed && !strcmp (temp, stu[i].cid))

{

cnt[stu[i].pas]++;

}

for (i = 3; i >= 1; i--) //add the number

{

cnt[i] += cnt[i+1];

}

cout << "Overall:" << endl;

for (i = 0; i < 5; i++)

{

cout << "Number of students who " << number[i] << " subjects: " << cnt[4-i] << endl;

}

cout << endl;

}

//***********************************************

int main()

{

// ifstream cin ("aaa.txt");

MainMenu ();

len = 0;

int cmd;

while (cin >> cmd)

{

char input[36];

int i;

if (cmd == 0)

break;

if (cmd == 1)

{

cout << "Please enter the SID, CID, name and four scores. Enter 0 to finish." << endl;

while (cin >> input)

{

if (input[0] == '0' && strlen (input) == 1)

break; //important!!!!!!

if (!Search (input))

{

strcpy (stu[len].sid, input);

cin >> stu[len].cid >> stu[len].name;

stu[len].all = 0;

stu[len].is_removed = false;

for (i = 0; i< 4; i++)

{

cin >> stu[len].score[i];

stu[len].all += stu[len].score[i];

}

len++;

}

else

{

cout << "Duplicated SID." << endl;

point temp;

cin >> temp.cid >> temp.name;

for (i = 0; i < 4; i++)

cin >> temp.score[i];

}

cout << "Please enter the SID, CID, name and four scores. Enter 0 to finish." << endl;

}

else if (cmd == 2)

{

cout << "Please enter SID or name. Enter 0 to finish." << endl;

while (cin >> input)

{

if (input[0] == '0' && strlen (input) == 1)

break;

DataBaseDelete (input);

cout << "Please enter SID or name. Enter 0 to finish." << endl;

}

else if (cmd == 3)

{

cout << "Please enter SID or name. Enter 0 to finish." << endl;

while (cin >> input)

{

if (input[0] == '0' && strlen (input) == 1)

break;

DataBaseQuery (input);

cout << "Please enter SID or name. Enter 0 to finish." << endl;

}

else if (cmd == 4)

{

cout << "Showing the ranklist hurts students' self-esteem. Don't do that." << endl;

}

else if (cmd == 5)

{

cout << "Please enter class ID, 0 for the whole statistics." << endl;

cin >> input;

DataBaseStatistic (input);

}

MainMenu ();

}

return 0;

}

uva12100

maksyuki 发表于 oj 分类，标签: 数据结构-队列双端单调优先

12 9月 2015

The only printer in the computer science students’ union is experiencing an extremely heavy workload. Sometimes there are a hundred jobs in the printer queue and you may have to wait for hours to get a single page of output.

Because some jobs are more important than others, the Hacker General has invented and implemented a simple priority system for the print job queue. Now, each job is assigned a priority between 1 and 9 (with 9 being the highest priority, and 1 being the lowest), and the printer operates as follows.

• The first job J in queue is taken from the queue.

• If there is some job in the queue with a higher priority than job J, then move J to the end of the queue without printing it.

• Otherwise, print job J (and do not put it back in the queue).

In this way, all those important muffin recipes that the Hacker General is printing get printed very quickly. Of course, those annoying term papers that others are printing may have to wait for quite some time to get printed, but that’s life.

Your problem with the new policy is that it has become quite tricky to determine when your print job will actually be completed. You decide to write a program to figure this out. The program will be given the current queue (as a list of priorities) as well as the position of your job in the queue, and must then calculate how long it will take until your job is printed, assuming that no additional jobs will be added to the queue. To simplify matters, we assume that printing a job always takes exactly one minute, and that adding and removing jobs from the queue is instantaneous.

Input

One line with a positive integer: the number of test cases (at most 100). Then for each test case:

• One line with two integers n and m, where n is the number of jobs in the queue (1 ≤ n ≤ 100) and m is the position of your job (0 ≤ m ≤ n − 1). The first position in the queue is number 0, the second is number 1, and so on.

• One line with n integers in the range 1 to 9, giving the priorities of the jobs in the queue. The first integer gives the priority of the first job, the second integer the priority of the second job, and so on.

Output

For each test case, print one line with a single integer; the number of minutes until your job is completely printed, assuming that no additional print jobs will arrive.

Sample Input

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

Sample Output

题目类型：队列模拟

算法分析：用cnt[10]数组表示读入任务的优先级(1~9)出现的个数，然后按照题目的叙述模拟队列，每次通过cnt数组找到优先级最高的优先级maxval，然后出队头一个元素val，比较元素val与maxval的大小，如果val < maxval，则直接将val压入队尾。反之，则时间自加1，判断val是否是题目要求输出的任务，如果是则退出程序，返回结果。否则将cnt[maxval]--并更新maxval，下面第一份代码是更好的实现

/**************************************************
filename       :g.cpp
author         :maksyuki
created time   :2018/1/23 16:51:13
last modified  :2018/1/23 17:08:29
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

PII que[maxn];
int cnt[16], qf, qb;

void init() {
    qf = qb = 1;
    for(int i = 0; i < 16; i++)
        cnt[i] = 0;
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int t;
    scanf("%d", &t);
    while(t--) {
        init();

        int n, m;
        scanf("%d %d", &n, &m);
        m++;

        int tmp;
        for(int i = 1; i <= n; i++) {
            scanf(" %d", &tmp);
            cnt[tmp]++;
            if(i == m) que[qb++] = PII(tmp, 1);
            else que[qb++] = PII(tmp, 0);
        }
        qb--;
        
        int tim = 0;
        while(qf <= qb) {
            PII vv = que[qf++];
            cnt[vv.first]--;
            int lev = -1;
            for(int i = 9; i >= 1; i--)
                if(cnt[i]) {
                    lev = i;
                    break;
                }
            if(vv.first < lev) {
                que[++qb] = vv;
                cnt[vv.first]++; 
            }
            else {
                tim++;
                if(vv.second == 1) break;
            }
        }
        printf("%d\n", tim);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

/**************************************************

filename :g.cpp

author :maksyuki

created time :2018/1/23 16:51:13

last modified :2018/1/23 17:08:29

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

PII que[maxn];

int cnt[16], qf, qb;

void init() {

qf = qb = 1;

for(int i = 0; i < 16; i++)

cnt[i] = 0;

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int t;

scanf("%d", &t);

while(t--) {

init();

int n, m;

scanf("%d %d", &n, &m);

m++;

int tmp;

for(int i = 1; i <= n; i++) {

scanf(" %d", &tmp);

cnt[tmp]++;

if(i == m) que[qb++] = PII(tmp, 1);

else que[qb++] = PII(tmp, 0);

}

qb--;

int tim = 0;

while(qf <= qb) {

PII vv = que[qf++];

cnt[vv.first]--;

int lev = -1;

for(int i = 9; i >= 1; i--)

if(cnt[i]) {

lev = i;

break;

}

if(vv.first < lev) {

que[++qb] = vv;

cnt[vv.first]++;

}

else {

tim++;

if(vv.second == 1) break;

}

printf("%d\n", tim);

}

return 0;

}

#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;


int cnt[12];
int maxval;
int sum;

struct point
{
	int val;
	bool output;

	point (int AA, bool BB) : val (AA), output (BB) {}
};


int SearchMaxVal ()
{
	int i;
	for (i = 9; i >= 1; i--)
		if (cnt[i])
			return i;

return -1;	//error
}


int main()
{
//	ifstream cin ("aaa.txt");

	int cases;
	cin >> cases;

	while (cases--)
	{

		memset (cnt, 0, sizeof (cnt));
		queue <point> ans;

		int num, weizhi;
		cin >> num >> weizhi;

		int i, temp;
		for (i = 0; i < num; i++)
		{
			cin >> temp;
			cnt[temp]++;

			if (i == weizhi)
				ans.push (point (temp, true));

			else
				ans.push (point (temp, false));
		}

		maxval = SearchMaxVal ();
		sum = 0;

		while (1)
		{
			if (!ans.empty ())
			{
				point temp = ans.front ();

				if (temp.val < maxval)
				{
					ans.pop ();
					ans.push (point (temp.val, temp.output));
				}

				else
				{
					sum++;
					if (temp.output == true)
						break;

					else
					{
						ans.pop ();
						cnt[temp.val]--;
						maxval = SearchMaxVal ();
					}
				}
			}
		}

		cout << sum << endl;
	}

return 0;
}

#include <iostream>

#include <fstream>

#include <cstring>

#include <queue>

using namespace std;

int cnt[12];

int maxval;

int sum;

struct point

{

int val;

bool output;

point (int AA, bool BB) : val (AA), output (BB) {}

};

int SearchMaxVal ()

{

int i;

for (i = 9; i >= 1; i--)

if (cnt[i])

return i;

return -1; //error

}

int main()

{

// ifstream cin ("aaa.txt");

int cases;

cin >> cases;

while (cases--)

{

memset (cnt, 0, sizeof (cnt));

queue <point> ans;

int num, weizhi;

cin >> num >> weizhi;

int i, temp;

for (i = 0; i < num; i++)

{

cin >> temp;

cnt[temp]++;

if (i == weizhi)

ans.push (point (temp, true));

else

ans.push (point (temp, false));

}

maxval = SearchMaxVal ();

sum = 0;

while (1)

{

if (!ans.empty ())

{

point temp = ans.front ();

if (temp.val < maxval)

{

ans.pop ();

ans.push (point (temp.val, temp.output));

}

else

{

sum++;

if (temp.output == true)

break;

else

{

ans.pop ();

cnt[temp.val]--;

maxval = SearchMaxVal ();

}

cout << sum << endl;

}

return 0;

}

uva11988

maksyuki 发表于 oj 分类，标签: 数据结构-链表

12 9月 2015

You're typing a long text with a broken keyboard. Well it's not so badly broken. The only problem with the keyboard is that sometimes the "home" key or the "end" key gets automatically pressed (internally).

You're not aware of this issue, since you're focusing on the text and did not even turn on the monitor! After you finished typing, you can see a text on the screen (if you turn on the monitor).

In Chinese, we can call it Beiju. Your task is to find the Beiju text.

Input

There are several test cases. Each test case is a single line containing at least one and at most 100,000 letters, underscores and two special characters '[' and ']'. '[' means the "Home" key is pressed internally, and ']' means the "End" key is pressed internally. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.

Output

For each case, print the Beiju text on the screen.

Sample Input

This_is_a_[Beiju]_text

[[]][][]Happy_Birthday_to_Tsinghua_University

Sample Input

BeijuThis_is_a__text

Happy_Birthday_to_Tsinghua_University

题目类型：单向循环链表

算法分析：将字符串一行读入，逐个判断字符，如果字符是’[’，就将当前位置指针置为0，如果字符是’]’，就将当前位置指针置为尾指针指向的位置。如果字符是其他字符，就将该字符插入到当前指针所指向的字符位置的后一个，并更新当前指针，如果插入的位置是最后一个位置，则更新尾指针

#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

const int maxn = 100000 + 166;

char input[maxn];
int Next[maxn];


int main()
{
//	ifstream cin ("aaa.txt");

	int last, cur;
	
	while (cin >> (input + 1))
	{
		int len = strlen (input + 1);
		
		Next[0] = 0;
		cur = last = 0;

		int i;

		for (i = 1; i <= len; i++)
		{
			if (input[i] == ']')
				cur = last;

			else if (input[i] == '[')
				cur = 0;

			else
			{
				Next[i] = Next[cur];
				Next[cur] = i;
				if (cur == last)
					last = i;

				cur = i;
			}
		}

		for (i = Next[0]; i; i = Next[i])
			cout << input[i];
		cout << endl;
	}

return 0;
}

#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;

const int maxn = 100000 + 166;

char input[maxn];

int Next[maxn];

int main()

{

// ifstream cin ("aaa.txt");

int last, cur;

while (cin >> (input + 1))

{

int len = strlen (input + 1);

Next[0] = 0;

cur = last = 0;

int i;

for (i = 1; i <= len; i++)

{

if (input[i] == ']')

cur = last;

else if (input[i] == '[')

cur = 0;

else

{

Next[i] = Next[cur];

Next[cur] = i;

if (cur == last)

last = i;

cur = i;

}

for (i = Next[0]; i; i = Next[i])

cout << input[i];

cout << endl;

}

return 0;

}

uva11424

maksyuki 发表于 oj 分类，标签: 数论-欧拉函数

12 9月 2015

Given the value of N, you will have to find the value of G. The definition of G is given below:G =i<N∑i=1j∑≤Nj=i+1GCD(i, j) Here GCD(i, j) means the greatest common divisor of integer i and integer j.

For those who have trouble understanding summation notation, the meaning of G is given in the following code:

G=0;

for(i=1;i<N;i++)

for(j=i+1;j<=N;j++)

{

G+=gcd(i,j);

}

/*Here gcd() is a function that finds

the greatest common divisor of the two

input numbers*/

Input

The input file contains at most 100 lines of inputs. Each line contains an integer N (1 < N < 4000001). The meaning of N is given in the problem statement. Input is terminated by a line containing a single zero.

Output

For each line of input produce one line of output. This line contains the value of G for the corresponding N. The value of G will fit in a 64-bit signed integer.

Sample Input

100

200000

Sample Output

13015

143295493160

题目类型：欧拉函数+预打表

算法分析：简单分析可知有求解G(n)的递推公式：G(n) = G(n - 1) + F(n) 边界G(0) = 0。其中F(n) = Sigma{gcd (i, n)}, 0 < i < n。而对于gcd (a, b) = 1, a < b来说，gcd (2 * a, 2 * b) = 2，gcd (3 * a, 3 * b) = 3，… gcd (k * a, k * b) = k，则每次从小到大求出b的欧拉函数值，之后直接F(k * b) += k * euler[b]，最后维护一个前缀和即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-6;
const double PI = 2 * acos (0.0);
const int maxn = 4e6 + 66;

LL euler[maxn], aa[maxn];

LL Get ()
{
    memset (aa, 0, sizeof (aa));
    for (LL i = 0; i < maxn; i++)
        euler[i] = i;

    for (LL i = 2; i < maxn; i += 2)
        euler[i] >>= 1;

    for (LL i = 2; i < maxn; i++)
    {
        if (euler[i] == i)
        {
            for (LL j = i; j < maxn; j += i)
                euler[j] -= euler[j] / i;
        }


        for (LL j = 1; j * i < maxn; j++)
            aa[j*i] += j * euler[i];
    }

    for (LL i = 1; i < maxn; i++)
        aa[i] += aa[i-1];
}

int main()
{
    Get ();
//    CFF;
    LL n;
    while (scanf ("%lld", &n) != EOF)
    {
        if (n == 0)
            break;

        printf ("%lld\n", aa[n]);
    }
    return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-6;

const double PI = 2 * acos (0.0);

const int maxn = 4e6 + 66;

LL euler[maxn], aa[maxn];

LL Get ()

{

memset (aa, 0, sizeof (aa));

for (LL i = 0; i < maxn; i++)

euler[i] = i;

for (LL i = 2; i < maxn; i += 2)

euler[i] >>= 1;

for (LL i = 2; i < maxn; i++)

{

if (euler[i] == i)

{

for (LL j = i; j < maxn; j += i)

euler[j] -= euler[j] / i;

}

for (LL j = 1; j * i < maxn; j++)

aa[j*i] += j * euler[i];

}

for (LL i = 1; i < maxn; i++)

aa[i] += aa[i-1];

}

int main()

{

Get ();

// CFF;

LL n;

while (scanf ("%lld", &n) != EOF)

{

if (n == 0)

break;

printf ("%lld\n", aa[n]);

}

return 0;

}

uva10935

maksyuki 发表于 oj 分类，标签: 数据结构-栈/单调

12 9月 2015

Given is an ordered deck of n cards numbered 1 to n with card 1 at the top and card n at the bottom. The following operation is performed as long as there are at least two cards in the deck:

Throw away the top card and move the card that is now on the top of the deck to the bottom of the deck.

Your task is to find the sequence of discarded cards and the last, remaining card.

Input

Each line of input (except the last) contains a number n ≤ 50. The last line contains ‘0’ and this line should not be processed.

Output

For each number from the input produce two lines of output. The first line presents the sequence of discarded cards, the second line reports the last remaining card. No line will have leading or trailing spaces. See the sample for the expected format.

Sample Input

Sample Output

Discarded cards: 1, 3, 5, 7, 4, 2

Remaining card: 6

Discarded cards: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 4, 8, 12, 16, 2, 10, 18, 14

Remaining card: 6

Discarded cards: 1, 3, 5, 7, 9, 2, 6, 10, 8

Remaining card: 4

Discarded cards: 1, 3, 5, 2, 6

Remaining card: 4

题目类型：栈模拟

算法分析：按照题目所说的方式进行栈模拟，将会discard的cards数字压入输出数组output中，然后直接遍历数组输出，下面第一份代码是更好的实现

/**************************************************
filename       :c.cpp
author         :maksyuki
created time   :2018/1/22 20:09:59
last modified  :2018/1/22 20:27:01
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int sta[maxn], pt, pb;
vector<int> ans;

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int n;
    while(scanf(" %d", &n) != EOF) {
        if(!n) break;
        ans.clear();
        pt = pb = 1; 

        for(int i = 1; i <= n; i++) sta[pb++] = i;
        pb--;
        while(pt < pb) {
            ans.emplace_back(sta[pt++]);
            sta[++pb] = sta[pt];
            pt++;
        }
        
        printf("Discarded cards:");
        int len = ans.size();
        for(int i = 0; i < len; i++) {
            if(!i) printf(" %d", ans[i]);
            else printf(", %d", ans[i]);
        }
        puts("");

        printf("Remaining card: %d\n", sta[pb]);
    }
    return 0;
}

/**************************************************

filename :c.cpp

author :maksyuki

created time :2018/1/22 20:09:59

last modified :2018/1/22 20:27:01

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int sta[maxn], pt, pb;

vector<int> ans;

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int n;

while(scanf(" %d", &n) != EOF) {

if(!n) break;

ans.clear();

pt = pb = 1;

for(int i = 1; i <= n; i++) sta[pb++] = i;

pb--;

while(pt < pb) {

ans.emplace_back(sta[pt++]);

sta[++pb] = sta[pt];

pt++;

}

printf("Discarded cards:");

int len = ans.size();

for(int i = 0; i < len; i++) {

if(!i) printf(" %d", ans[i]);

else printf(", %d", ans[i]);

}

puts("");

printf("Remaining card: %d\n", sta[pb]);

}

return 0;

}

#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

const int maxn = 666;

int output[maxn];
int len;

int main()
{
//	ifstream cin ("aaa.txt");

	int num;

	while (cin >> num)
	{

		if (num == 0)
			break;

		queue <int> ans;

		int i;
		for (i = 1; i <= num; i++)
			ans.push (i);

		len = 0;

		while (ans.size () >= 2)
		{
			int temp_a = ans.front ();
			output[len++] = temp_a;
			ans.pop ();
			temp_a = ans.front ();
			ans.pop ();
			ans.push (temp_a);
		}

		output[len++] = ans.front ();
		if (num == 1)
		{
			cout << "Discarded cards:" << endl << "Remaining card: " << output[0] << endl;

		}

		else
		{
			cout << "Discarded cards:";
			for (i = 0; i < len - 2; i++)
				cout << " " << output[i] << ",";
			cout << " " << output[i] << endl;

			cout << "Remaining card: " << output[len-1] << endl;
		}
	}

return 0;
}

#include <iostream>

#include <fstream>

#include <queue>

using namespace std;

const int maxn = 666;

int output[maxn];

int len;

int main()

{

// ifstream cin ("aaa.txt");

int num;

while (cin >> num)

{

if (num == 0)

break;

queue <int> ans;

int i;

for (i = 1; i <= num; i++)

ans.push (i);

len = 0;

while (ans.size () >= 2)

{

int temp_a = ans.front ();

output[len++] = temp_a;

ans.pop ();

temp_a = ans.front ();

ans.pop ();

ans.push (temp_a);

}

output[len++] = ans.front ();

if (num == 1)

{

cout << "Discarded cards:" << endl << "Remaining card: " << output[0] << endl;

}

else

{

cout << "Discarded cards:";

for (i = 0; i < len - 2; i++)

cout << " " << output[i] << ",";

cout << " " << output[i] << endl;

cout << "Remaining card: " << output[len-1] << endl;

}

return 0;

}

uva1593

maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理

12 9月 2015

You are working in a team that writes Incredibly Customizable Programming Codewriter (ICPC) which is basically a text editor with bells and whistles. You are working on a module that takes a piece of code containing some definitions or other tabular information and aligns each column on a fixed vertical position, while keeping the resulting code as short as possible, making sure that only whitespaces that are absolutely required stay in the code. So, that the first words on each line are printed at position p1 = 1; the second words on each line are printed at the minimal possible position p2, such that all first words end at or before position p2 − 2; the third words on each line are printed at the minimal possible position p3, such that all second words end at or before position p3 − 2, etc.

For the purpose of this problem, the code consists of multiple lines. Each line consists of one or more words separated by spaces. Each word can contain uppercase and lowercase Latin letters, all ASCII punctuation marks, separators, and other non-whitespace ASCII characters (ASCII codes 33 to 126 inclusive). Whitespace consists of space characters (ASCII code 32).

Input

The input file contains one or more lines of the code up to the end of file. All lines (including the last one) are terminated by a standard end-of-line sequence in the file. Each line contains at least one word, each word is 1 to 80 characters long (inclusive). Words are separated by one or more spaces. Lines of the code can have both leading and trailing spaces. Each line in the input file is at most 180 characters long. There are at most 1000 lines in the input file.

Output

Write to the output file the reformatted, aligned code that consists of the same number of lines, with the same words in the same order, without trailing and leading spaces, separated by one or more spaces such that i-th word on each line starts at the same position pi .

Note for the Sample:

The ‘⊔’ character in the example below denotes a space character in the actual files (ASCII code 32).

Sample Input

␣␣start:␣␣integer;␣␣␣␣//␣begins␣here
stop:␣integer;␣//␣␣ends␣here
␣s:␣␣string;
c:␣␣␣char;␣//␣temp

Sample Output

start:␣integer;␣//␣begins␣here
stop:␣␣integer;␣//␣ends␣␣␣here
s:␣␣␣␣␣string;
c:␣␣␣␣␣char;␣␣␣␣//␣temp

题目类型：字符处理题

算法分析：边输入边处理，使用一个cnt数组记录每一列字符串的最大长度，使用num数组记录每行有多少字符串。输出时对于第一个字符串直接输出；对于之后的字符串要输出相应的前导空格，前导空格的数目为前一列字符串的最大长度减去前一个字符串的长度再加一：num_space = cnt[j-1] - ans[k][j-1].length () + 1;，注意每个字符串的最后不要输出多余的空格，下面第一个代码是更好的实现

/**************************************************
filename       :a.cpp
author         :maksyuki
created time   :2018/1/22 17:04:25
last modified  :2018/1/22 17:49:23
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e3 + 6666;

vector<string> dict[maxn];
int cnt[maxn], col[maxn], acol, len;

void OutSpace(int n) {
    for(int i = 1; i <= n; i++) cout << " "; 
}

int main()
{
#ifdef LOCAL
    CFF;
    CFO;
#endif
        
    string s;
    stringstream ss;
    len = acol = 0;
    while(getline(cin, s)) {
        ss.clear();
        ss << s;
        while(ss >> s) {
            dict[len].emplace_back(s);
        }
        col[len] = (int) dict[len].size();
        acol = max(acol, col[len]);
        len++;
    }
    
    for(int i = 0; i < acol; i++) {
        cnt[i] = -INF;
        for(int j = 0; j < len; j++)
            if(col[j] >= i + 1)
                cnt[i] = max(cnt[i], (int) dict[j][i].size());
    }
    
    for(int i = 0; i < len; i++) {
        for(int j = 0; j < col[i]; j++) {
            if(j) cout << " ";
            cout << dict[i][j];
            if(j < col[i] - 1)
                OutSpace(cnt[j] - (int) dict[i][j].size());
        }
        cout << endl;
    }

    return 0;
}

100

101

102

103

104

105

106

107

/**************************************************

filename :a.cpp

author :maksyuki

created time :2018/1/22 17:04:25

last modified :2018/1/22 17:49:23

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e3 + 6666;

vector<string> dict[maxn];

int cnt[maxn], col[maxn], acol, len;

void OutSpace(int n) {

for(int i = 1; i <= n; i++) cout << " ";

}

int main()

{

#ifdef LOCAL

CFF;

CFO;

#endif

string s;

stringstream ss;

len = acol = 0;

while(getline(cin, s)) {

ss.clear();

ss << s;

while(ss >> s) {

dict[len].emplace_back(s);

}

col[len] = (int) dict[len].size();

acol = max(acol, col[len]);

len++;

}

for(int i = 0; i < acol; i++) {

cnt[i] = -INF;

for(int j = 0; j < len; j++)

if(col[j] >= i + 1)

cnt[i] = max(cnt[i], (int) dict[j][i].size());

}

for(int i = 0; i < len; i++) {

for(int j = 0; j < col[i]; j++) {

if(j) cout << " ";

cout << dict[i][j];

if(j < col[i] - 1)

OutSpace(cnt[j] - (int) dict[i][j].size());

}

cout << endl;

}

return 0;

}

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iomanip>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;

#define EPS 1e-8;

string ans[1000+66][200+66];

int num[1000+66], cnt[200+66];

int main()
{
//	ifstream cin ("aaa.txt");
//	freopen ("aaa.txt", "r", stdin);
	int i = 0, j = 0;
	string input;

	while (getline (cin, input))
	{
		stringstream ss (input);
		j = 0;

		while (ss >> ans[i][j])
		{
			if (cnt[j] < ans[i][j].length ())
				cnt[j] = ans[i][j].length ();

			j++;
		}

		num[i] = j;

		i++;
	}

	int k;
	for (k = 0; k < i; k++)
	{
		for (j = 0; j < num[k]; j++)
		{
			if (j >= 1)
			{
				int q = 1, len_output = cnt[j-1] - ans[k][j-1].length () + 1;
				while (q <= len_output)
				{
					cout << " ";
					q++;
				}

				cout << ans[k][j];
			}

			else
				cout << ans[k][j];
		}
		cout << endl;
	}


return 0;
}

#include <iostream>

#include <fstream>

#include <sstream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <iomanip>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

using namespace std;

#define EPS 1e-8;

string ans[1000+66][200+66];

int num[1000+66], cnt[200+66];

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

int i = 0, j = 0;

string input;

while (getline (cin, input))

{

stringstream ss (input);

j = 0;

while (ss >> ans[i][j])

{

if (cnt[j] < ans[i][j].length ())

cnt[j] = ans[i][j].length ();

j++;

}

num[i] = j;

i++;

}

int k;

for (k = 0; k < i; k++)

{

for (j = 0; j < num[k]; j++)

{

if (j >= 1)

{

int q = 1, len_output = cnt[j-1] - ans[k][j-1].length () + 1;

while (q <= len_output)

{

cout << " ";

q++;

}

cout << ans[k][j];

}

else

cout << ans[k][j];

}

cout << endl;

}

return 0;

}

uva10533

maksyuki 发表于 oj 分类，标签: 数论-筛法

12 9月 2015

Digit Primes

A prime number is a positive number, which is divisible by exactly two different integers. A digit prime is a prime number whose sum of digits is also prime. For example the prime number 41 is a digit prime
because 4+1=5 and 5 is a prime number. 17 is not a digit prime because 1+7 = 8, and 8 is not a prime number. In this problem your job is to find out the number of digit primes
within a certain range less than 1000000.

Input

First line of the input file contains a single integer N (0<N<=500000) that indicates the total number of inputs. Each of the next N lines contains two integers t1 and t2 (0<t1<=t2<1000000).

Output

For each line of input except the first line produce one line of output containing a single integer that indicates the number of digit primes between t1 and t2 (inclusive).

Sample Input

310 2010 100100 10000

110576

题目类型：素数测试

算法分析：首先使用Euler筛将2至1000000之间的所有的素数筛出来，然后从小到大判断所有的素数val的位数字之和是否为素数，如果是则将OK[val] = 1，然后将OK构建成一个前缀表，之后对于每一个查询直接求相应数的前缀差即可

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int maxn = 1000000 + 66;

bool prime[maxn];

int primelist[maxn], num, Ok[maxn];

void Judge (int val)
{
    int sum = 0, temp = val;
    do
    {
        sum += temp % 10;
        temp /= 10;
    } while (temp);

    if (prime[sum])
        Ok[val]++;

}

void PrePare ()
{
    memset (prime, true, sizeof (prime));
    memset (Ok, 0, sizeof (Ok));
    num = 0;

    int i;
    for (i = 2; i <= maxn; i++)
    {
        if (prime[i])
            primelist[num++] = i;

        int j;
        for (j = 0; j < num; j++)
        {
            if (i * primelist[j] > maxn)
                break;

            prime[i*primelist[j]] = false;
            if (i % primelist[j] == 0)
                break;
        }
    }
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    PrePare ();
    for (int i = 0; i < num; i++)
        Judge (primelist[i]);

    for (int i = 2; i <= maxn; i++)
        Ok[i] += Ok[i-1];

    int n;
    scanf ("%d", &n);

    int i;
    for (i = 0; i < n; i++)
    {
        int val_a, val_b;
        scanf ("%d%d", &val_a, &val_b);

        printf ("%d\n", Ok[val_b] - Ok[val_a-1]);

    }

return 0;
}

#include <iostream>

#include <fstream>

#include <sstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int maxn = 1000000 + 66;

bool prime[maxn];

int primelist[maxn], num, Ok[maxn];

void Judge (int val)

{

int sum = 0, temp = val;

{

sum += temp % 10;

temp /= 10;

} while (temp);

if (prime[sum])

Ok[val]++;

}

void PrePare ()

{

memset (prime, true, sizeof (prime));

memset (Ok, 0, sizeof (Ok));

num = 0;

int i;

for (i = 2; i <= maxn; i++)

{

if (prime[i])

primelist[num++] = i;

int j;

for (j = 0; j < num; j++)

{

if (i * primelist[j] > maxn)

break;

prime[i*primelist[j]] = false;

if (i % primelist[j] == 0)

break;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

PrePare ();

for (int i = 0; i < num; i++)

Judge (primelist[i]);

for (int i = 2; i <= maxn; i++)

Ok[i] += Ok[i-1];

int n;

scanf ("%d", &n);

int i;

for (i = 0; i < n; i++)

{

int val_a, val_b;

scanf ("%d%d", &val_a, &val_b);

printf ("%d\n", Ok[val_b] - Ok[val_a-1]);

}

return 0;

}

uva10168

maksyuki 发表于 oj 分类，标签: 数论-筛法

12 9月 2015

Euler proved in one of his classic theorems that prime numbers are infinite in number. But can every number be expressed as a summation of four positive primes? I don’t know the answer. May be you can help!!! I want your solution to be very efficient as I have a 386 machine at home. But the time limit specified above is for a Pentium III 800 machine. The definition of prime number for this problem is “A prime number is a positive number which has exactly two distinct integer factors”. As for example 37 is prime as it has exactly two distinct integer factors 37 and 1.

Input

The input contains one integer number N (N ≤ 10000000) in every line. This is the number you will have to express as a summation of four primes. Input is terminated by end of file.

Output

For each line of input there is one line of output, which contains four prime numbers according to the given condition. If the number cannot be expressed as a summation of four prime numbers print the line ‘Impossible.’ in a single line. There can be multiple solutions. Any good solution will be accepted.

Sample Input

24 36 46

Sample Output

3 11 3 7 3 7 13 13 11 11 17 7

题目类型：扩展哥德巴赫猜想

算法分析：要找到4个满足条件的素数，可以考虑先将前两个素数找到，其中如果n为奇数，则将其减去奇数(2 + 3)；如果是偶数，则将其减去偶数(2 + 2)。然后再按照哥德巴赫猜想来判断n是否能够构成两个奇素数。这里构造的素数表一定要使用线性筛(Euler筛)，否则会TLE

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int maxn = 10000000 + 66;

bool prime[maxn];
int primelist[maxn], num;

void PrePare ()
{
    memset (prime, true, sizeof (prime));
    num = 0;

    int i;
    for (i = 2; i <= maxn; i++)
    {
        if (prime[i])
            primelist[num++] = i;

        int j;
        for (j = 0; j < num; j++)
        {
            if (i * primelist[j] > maxn)
                break;

            prime[i*primelist[j]] = false;
            if (i % primelist[j] == 0)
                break;
        }
    }
}


int main()
{
//    ifstream cin ("aaa.txt");

    PrePare ();

    int n;

    while (cin >> n)
    {
        if (n < 8)
            cout << "Impossible." << endl;

        else
        {
            if (n % 2)
            {
                n -= 5;
                cout << "2 3";
            }

            else
            {
                n -= 4;
                cout << "2 2";
            }

            bool is_find = false;

            int i;
            for (i = 0; i < num; i++)
            {
                if (n <= primelist[i])
                    break;

                if (prime[n-primelist[i]])
                {
                    is_find = true;
                    break;
                }
            }

            if (is_find)
                cout << " " << primelist[i] << " " << n - primelist[i] << endl;

            else
                cout << "Impossible." << endl;
        }
    }

return 0;
}

100

#include <iostream>

#include <fstream>

#include <sstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int maxn = 10000000 + 66;

bool prime[maxn];

int primelist[maxn], num;

void PrePare ()

{

memset (prime, true, sizeof (prime));

num = 0;

int i;

for (i = 2; i <= maxn; i++)

{

if (prime[i])

primelist[num++] = i;

int j;

for (j = 0; j < num; j++)

{

if (i * primelist[j] > maxn)

break;

prime[i*primelist[j]] = false;

if (i % primelist[j] == 0)

break;

}

int main()

{

// ifstream cin ("aaa.txt");

PrePare ();

int n;

while (cin >> n)

{

if (n < 8)

cout << "Impossible." << endl;

else

{

if (n % 2)

{

n -= 5;

cout << "2 3";

}

else

{

n -= 4;

cout << "2 2";

}

bool is_find = false;

int i;

for (i = 0; i < num; i++)

{

if (n <= primelist[i])

break;

if (prime[n-primelist[i]])

{

is_find = true;

break;

}

if (is_find)

cout << " " << primelist[i] << " " << n - primelist[i] << endl;

else

cout << "Impossible." << endl;

}

return 0;

}

uva1600

maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化

12 9月 2015

A robot has to patrol around a rectangular area which is in a form of m x n grid (m rows and n columns). The rows are labeled from 1 to m. The columns are labeled from 1 to n. A cell (i, j) denotes the cell in row iand column j in the grid. At each step, the robot can only move from one cell to an adjacent cell, i.e. from(x, y) to (x + 1, y), (x, y + 1), (x - 1, y) or (x, y - 1). Some of the cells in the grid contain obstacles. In order to move to a cell containing obstacle, the robot has to switch to turbo mode. Therefore, the robot cannot move continuously to more than k cells containing obstacles.

Your task is to write a program to find the shortest path (with the minimum number of cells) from cell (1, 1) to cell (m, n). It is assumed that both these cells do not contain obstacles.

Input

The input consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.

For each data set, the first line contains two positive integer numbers m and n separated by space (1m, n20). The second line contains an integer number k (0k20). The i^th line of the next m lines contains ninteger a_ij separated by space (i = 1, 2,..., m;j = 1, 2,..., n). The value of a_ij is 1 if there is an obstacle on the cell (i, j), and is 0 otherwise.

Output

For each data set, if there exists a way for the robot to reach the cell (m, n), write in one line the integer number s, which is the number of moves the robot has to make; -1 otherwise.

Sample Input

3 2 5 0 0 1 0 0 0 0 0 0 1 0 4 6 1 0 1 1 0 0 00 0 1 0 1 10 1 1 1 1 00 1 1 1 0 02 2 0 0 1 1 0

Sample Output

7 10 -1

题目类型：BFS

算法分析：使用visited[i][j][v]数组表示走到(i, j)且已经通v个墙的状态是否已经访问过。对于走到的节点值为1且还能够向下一个状态走，则将该状态的能力值减1，步数加1；如果走到的节点值为0，则将能力值恢复为k(只有这样才能最大化能力值，求得最短步数)，步数加1。一直这样扩展节点，直到有一个状态的坐标为(X, Y)，最后输出该状态的步数

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int maxn = 36;
const int INF = 66666666;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int row, col, k;

int ans[maxn][maxn];
bool visited[maxn][maxn][maxn];
int minval;

struct Node
{
    int x, y, v, s;
    Node (int xx, int yy, int vv, int ss) : x (xx), y (yy), v (vv), s (ss) {}
    Node () {}
};


inline bool Inside (int x, int y, int v)
{
    if (x >= 1 && x <= row && y >= 1 && y <= col)
    {
        if (ans[x][y])
        {
            if (!visited[x][y][v+1])
                return true;

            else
                return false;
        }

        else
        {
            if (!visited[x][y][0])
                return true;

            else
                return false;
        }
    }

return false;
}

void bfs (int x, int y, int v, int s)
{
    memset (visited, false, sizeof (visited));
    minval = INF;

    visited[x][y][v] = true;
    queue <Node> q;
    q.push (Node (x, y, v, s));

    while (!q.empty ())
    {
        Node temp = q.front ();
        q.pop ();

        if (temp.x == row && temp.y == col)
        {
            minval = temp.s;
            return ;
        }

        int i;
        for (i = 0; i < 4; i++)
        {
            if (Inside (temp.x + dx[i], temp.y + dy[i], temp.v))
            {
                int val_x = temp.x + dx[i], val_y = temp.y + dy[i];
                if (ans[val_x][val_y] && temp.v < k)
                {
                    visited[val_x][val_y][temp.v+1] = true;
                    q.push (Node (val_x, val_y, temp.v + 1, temp.s + 1));
                }

                else if (!ans[val_x][val_y])
                {
                    visited[val_x][val_y][0] = true;
                    q.push (Node (val_x, val_y, 0, temp.s + 1));
                }
            }
        }
    }
}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t;
    scanf ("%d", &t);

    while (t--)
    {
        scanf ("%d%d%d", &row, &col, &k);

        int i, j;
        for (i = 1; i <= row; i++)
        {
            for (j = 1; j <= col; j++)
                scanf ("%d", &ans[i][j]);
        }

        bfs (1, 1, 0, 0);

        if (minval == INF)
            printf ("-1\n");

        else
            printf ("%d\n", minval);
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int maxn = 36;

const int INF = 66666666;

const int dx[] = {-1, 1, 0, 0};

const int dy[] = {0, 0, -1, 1};

int row, col, k;

int ans[maxn][maxn];

bool visited[maxn][maxn][maxn];

int minval;

struct Node

{

int x, y, v, s;

Node (int xx, int yy, int vv, int ss) : x (xx), y (yy), v (vv), s (ss) {}

Node () {}

};

inline bool Inside (int x, int y, int v)

{

if (x >= 1 && x <= row && y >= 1 && y <= col)

{

if (ans[x][y])

{

if (!visited[x][y][v+1])

return true;

else

return false;

}

else

{

if (!visited[x][y][0])

return true;

else

return false;

}

return false;

}

void bfs (int x, int y, int v, int s)

{

memset (visited, false, sizeof (visited));

minval = INF;

visited[x][y][v] = true;

queue <Node> q;

q.push (Node (x, y, v, s));

while (!q.empty ())

{

Node temp = q.front ();

q.pop ();

if (temp.x == row && temp.y == col)

{

minval = temp.s;

return ;

}

int i;

for (i = 0; i < 4; i++)

{

if (Inside (temp.x + dx[i], temp.y + dy[i], temp.v))

{

int val_x = temp.x + dx[i], val_y = temp.y + dy[i];

if (ans[val_x][val_y] && temp.v < k)

{

visited[val_x][val_y][temp.v+1] = true;

q.push (Node (val_x, val_y, temp.v + 1, temp.s + 1));

}

else if (!ans[val_x][val_y])

{

visited[val_x][val_y][0] = true;

q.push (Node (val_x, val_y, 0, temp.s + 1));

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t;

scanf ("%d", &t);

while (t--)

{

scanf ("%d%d%d", &row, &col, &k);

int i, j;

for (i = 1; i <= row; i++)

{

for (j = 1; j <= col; j++)

scanf ("%d", &ans[i][j]);

}

bfs (1, 1, 0, 0);

if (minval == INF)

printf ("-1\n");

else

printf ("%d\n", minval);

}

return 0;

}

uva1588

maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理

12 9月 2015

A research laboratory of a world-leading automobile company has received an order to create a special transmission mechanism, which allows for incredibly efficient kickdown -- an operation of switching to lower gear. After several months of research engineers found that the most efficient solution requires special gears with teeth and cavities placed non-uniformly. They calculated the optimal flanks of the gears. Now they want to perform some experiments to prove their findings.

The first phase of the experiment is done with planar toothed sections, not round-shaped gears. A section of length n consists of n units. The unit is either a cavity of height h or a tooth of height 2h . Two sections are required for the experiment: one to emulate master gear (with teeth at the bottom) and one for the driven gear (with teeth at the top).

There is a long stripe of width 3h in the laboratory and its length is enough for cutting two engaged sections together. The sections are irregular but they may still be put together if shifted along each other.

The stripe is made of an expensive alloy, so the engineers want to use as little of it as possible. You need to ï¬nd the minimal length of the stripe which is enough for cutting both sections simultaneously.

Input

The input file contains several test cases, each of them as described below.

There are two lines in the input, each contains a string to describe a section. The first line describes master section (teeth at the bottom) and the second line describes driven section (teeth at the top). Each character in a string represents one section unit -- 1 for a cavity and 2 for a tooth. The sections can not be flipped or rotated.

Each string is non-empty and its length does not exceed 100.

Output

For each test case, write to the output a line containing a single integer number -- the minimal length of the stripe required to cut off given sections.

Sample Input

2112112112

2212112

12121212

21212121

2211221122

21212

Sample Output

题目类型： 字符串处理题

算法分析：写一个函数Solve，通过调用不同参数的Solve函数两次，来完成向两个方向移动的判断，Solve函数只需按照题意移动一个字符串的初始比较位置，判断是否满足高度不大于3即可，下面第一个代码是更好的实现

/**************************************************
filename       :q.cpp
author         :maksyuki
created time   :2017/12/3 15:32:28
last modified  :2017/12/3 16:15:04
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

char va[maxn], vb[maxn];
int lena, lenb;

void rev() {
    for(int i = 0; i < lena / 2; i++) swap(va[i], va[lena-1-i]);
    for(int i = 0; i < lenb / 2; i++) swap(vb[i], vb[lenb-1-i]);
}

int check(int p) {
    int i, j;
    for(i = p, j = 0; i < lena && j < lenb; i++, j++) {
        int tmpa = va[i] - '0', tmpb = vb[j] - '0';
        if(tmpa + tmpb > 3) return -1;
    }
    if(i == lena && j < lenb) return lena + lenb - j;
    if(i <= lena && j == lenb) return lena;
    return -1;
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    while(scanf(" %s", va) != EOF) {
        scanf(" %s", vb);

        lena = strlen(va), lenb = strlen(vb);
        if(lena < lenb) swap(va, vb), swap(lena, lenb);
        
        int minval = INF;
        for(int i = 0; i < lena; i++) {
            int tmp = check(i);
            if(tmp != -1) minval = min(minval, tmp);
        }

        minval = min(minval, lena + lenb);
        rev();
        for(int i = 0; i < lena; i++) {
            int tmp = check(i);
            if(tmp != -1) minval = min(minval, tmp);
        }

        printf("%d\n", minval);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

/**************************************************

filename :q.cpp

author :maksyuki

created time :2017/12/3 15:32:28

last modified :2017/12/3 16:15:04

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

char va[maxn], vb[maxn];

int lena, lenb;

void rev() {

for(int i = 0; i < lena / 2; i++) swap(va[i], va[lena-1-i]);

for(int i = 0; i < lenb / 2; i++) swap(vb[i], vb[lenb-1-i]);

}

int check(int p) {

int i, j;

for(i = p, j = 0; i < lena && j < lenb; i++, j++) {

int tmpa = va[i] - '0', tmpb = vb[j] - '0';

if(tmpa + tmpb > 3) return -1;

}

if(i == lena && j < lenb) return lena + lenb - j;

if(i <= lena && j == lenb) return lena;

return -1;

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

while(scanf(" %s", va) != EOF) {

scanf(" %s", vb);

lena = strlen(va), lenb = strlen(vb);

if(lena < lenb) swap(va, vb), swap(lena, lenb);

int minval = INF;

for(int i = 0; i < lena; i++) {

int tmp = check(i);

if(tmp != -1) minval = min(minval, tmp);

}

minval = min(minval, lena + lenb);

rev();

for(int i = 0; i < lena; i++) {

int tmp = check(i);

if(tmp != -1) minval = min(minval, tmp);

}

printf("%d\n", minval);

}

return 0;

}

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 100 + 66;

bool Test (int k, char *val_a, char *val_b)
{
int i;
for (i = 0; val_a[k+i] && val_b[i]; i++)
if ((val_a[k+i] - '0') + (val_b[i] - '0') > 3)
return false;

return true;
}


int Solve (char *val_a, char *val_b)
{
int i = 0;

while (!Test (i, val_a, val_b))
{
i++;
}

return max (strlen (val_a), strlen (val_b) + i);
}


int main()
{
//	ifstream cin ("aaa.txt");

char val_a[maxn], val_b[maxn];

while (cin >> val_a >> val_b)
{
cout << min (Solve (val_a, val_b), Solve (val_b, val_a)) << endl;
}

return 0;
}

#include <iostream>

#include <fstream>

#include <algorithm>

#include <cstring>

using namespace std;

const int maxn = 100 + 66;

bool Test (int k, char *val_a, char *val_b)

{

int i;

for (i = 0; val_a[k+i] && val_b[i]; i++)

if ((val_a[k+i] - '0') + (val_b[i] - '0') > 3)

return false;

return true;

}

int Solve (char *val_a, char *val_b)

{

int i = 0;

while (!Test (i, val_a, val_b))

{

i++;

}

return max (strlen (val_a), strlen (val_b) + i);

}

int main()

{

// ifstream cin ("aaa.txt");

char val_a[maxn], val_b[maxn];

while (cin >> val_a >> val_b)

{

cout << min (Solve (val_a, val_b), Solve (val_b, val_a)) << endl;

}

return 0;

}

uva1587

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

12 9月 2015

Ivan works at a factory that produces heavy machinery. He has a simple job -- he knocks up wooden boxes of different sizes to pack machinery for delivery to the customers. Each box is a rectangular parallelepiped. Ivan uses six rectangular wooden pallets to make a box. Each pallet is used for one side of the box.

Joe delivers pallets for Ivan. Joe is not very smart and often makes mistakes -- he brings Ivan pallets that do not fit together to make a box. But Joe does not trust Ivan. It always takes a lot of time to explain Joe that he has made a mistake. Fortunately, Joe adores everything related to computers and sincerely believes that computers never make mistakes. Ivan has decided to use this for his own advantage. Ivan asks you to write a program that given sizes of six rectangular pallets tells whether it is possible to make a box out of them.

Input

Input file contains several test cases. Each of them consists of six lines. Each line describes one pallet and contains two integer numbers w and h ( 1w, h10 000) -- width and height of the pallet in millimeters respectively.

Output

For each test case, print one output line. Write a single word POSSIBLE' to the output file if it is possible to make a box using six given pallets for its sides. Write a single word IMPOSSIBLE' if it is not possible to do so.

Sample Input

1345 2584

2584 683

2584 1345

683 1345

2584 683

1234 4567

4567 4321

4322 4567

4321 1234

Sample Output

POSSIBLE

IMPOSSIBLE

题目类型：数学题

算法分析：由平行四面体的几何关系可知组成四面体的六个长方形必须两两长宽分别相等。这里将数据输入结构体数组后，将数组先按照h递增排序，然后按照w递增排序。然后进行简单的判断即可。注意重载小于号的方法及进行递增排序的方法，下面第一个代码是更好的实现

/**************************************************
filename       :p.cpp
author         :maksyuki
created time   :2017/12/3 15:11:05
last modified  :2017/12/3 15:17:15
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

struct node {
    int a, b;
};

node v[maxn];

bool cmp(const node &a, const node &b) {
    if(a.a != b.a) return a.a < b.a;
    return a.b < b.b;
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int tmpa, tmpb;
    while(scanf(" %d", &tmpa) != EOF) {
        scanf(" %d", &tmpb);
        v[1].a = min(tmpa, tmpb);
        v[1].b = max(tmpa, tmpb);
        for(int i = 2; i <= 6; i++) {
            scanf(" %d %d", &tmpa, &tmpb);
            v[i].a = min(tmpa, tmpb);
            v[i].b = max(tmpa, tmpb);
        }

        sort(v + 1, v + 1 + 6, cmp);

        if(v[1].a == v[2].a && v[1].a == v[3].a && v[1].a == v[4].a && v[1].b == v[2].b && v[1].b == v[5].a && v[1].b == v[6].a && v[3].b == v[4].b && v[3].b == v[5].b && v[3].b == v[6].b) puts("POSSIBLE");
        else puts("IMPOSSIBLE");
    }
    return 0;
}

/**************************************************

filename :p.cpp

author :maksyuki

created time :2017/12/3 15:11:05

last modified :2017/12/3 15:17:15

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

struct node {

int a, b;

};

node v[maxn];

bool cmp(const node &a, const node &b) {

if(a.a != b.a) return a.a < b.a;

return a.b < b.b;

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int tmpa, tmpb;

while(scanf(" %d", &tmpa) != EOF) {

scanf(" %d", &tmpb);

v[1].a = min(tmpa, tmpb);

v[1].b = max(tmpa, tmpb);

for(int i = 2; i <= 6; i++) {

scanf(" %d %d", &tmpa, &tmpb);

v[i].a = min(tmpa, tmpb);

v[i].b = max(tmpa, tmpb);

}

sort(v + 1, v + 1 + 6, cmp);

if(v[1].a == v[2].a && v[1].a == v[3].a && v[1].a == v[4].a && v[1].b == v[2].b && v[1].b == v[5].a && v[1].b == v[6].a && v[3].b == v[4].b && v[3].b == v[5].b && v[3].b == v[6].b) puts("POSSIBLE");

else puts("IMPOSSIBLE");

}

return 0;

}

#include <cstdio>
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

struct point
{
    int h, w;

    bool operator < (const point &A) const {
        if (h == A.h)
			return w < A.w;

		return h < A.h;
    }
}a[16];

bool panduan ()
{
    int i;
    for (i = 0; i < 5; i += 2)
        if (a[i].h != a[i+1].h || a[i].w != a[i+1].w)
            return false;

    if (a[1].h != a[2].h)
		return false;

	if (a[1].w != a[4].h)
		return false;

	if (a[2].w != a[4].w)
		return false;

	return true;
}

int main()
{
	//ifstream cin ("aaa.txt");

    while (cin >> a[0].h >> a[0].w)
	{
        if (a[0].h > a[0].w)
			swap (a[0].h, a[0].w);

		int i;
		for (i = 1; i < 6; i++)
		{
			cin >> a[i].h >> a[i].w;

			if (a[i].h > a[i].w)
				swap (a[i].h, a[i].w);
		}

		sort (a, a + 6);

		if (panduan ())
            cout << "POSSIBLE" <<endl;

		else
			cout << "IMPOSSIBLE" << endl;
	}

	return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

#include <algorithm>

using namespace std;

struct point

{

int h, w;

bool operator < (const point &A) const {

if (h == A.h)

return w < A.w;

return h < A.h;

}

}a[16];

bool panduan ()

{

int i;

for (i = 0; i < 5; i += 2)

if (a[i].h != a[i+1].h || a[i].w != a[i+1].w)

return false;

if (a[1].h != a[2].h)

return false;

if (a[1].w != a[4].h)

return false;

if (a[2].w != a[4].w)

return false;

return true;

}

int main()

{

//ifstream cin ("aaa.txt");

while (cin >> a[0].h >> a[0].w)

{

if (a[0].h > a[0].w)

swap (a[0].h, a[0].w);

int i;

for (i = 1; i < 6; i++)

{

cin >> a[i].h >> a[i].w;

if (a[i].h > a[i].w)

swap (a[i].h, a[i].w);

}

sort (a, a + 6);

if (panduan ())

cout << "POSSIBLE" <<endl;

else

cout << "IMPOSSIBLE" << endl;

}

return 0;

}

uva1584

maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理

12 9月 2015

Some DNA sequences exist in circular forms as in the following figure, which shows a circular sequence CGAGTCAGCT", that is, the last symbol T" in CGAGTCAGCT" is connected to the first symbol C". We always read a circular sequence in the clockwise direction.

Since it is not easy to store a circular sequence in a computer as it is, we decided to store it as a linear sequence. However, there can be many linear sequences that are obtained from a circular sequence by cutting any place of the circular sequence. Hence, we also decided to store the linear sequence that is lexicographically smallest among all linear sequences that can be obtained from a circular sequence.

Your task is to find the lexicographically smallest sequence from a given circular sequence. For the example in the figure, the lexicographically smallest sequence is AGCTCGAGTC". If there are two or more linear sequences that are lexicographically smallest, you are to find any one of them (in fact, they are the same).

Input

The input consists of T test cases. The number of test cases T is given on the first line of the input file. Each test case takes one line containing a circular sequence that is written as an arbitrary linear sequence. Since the circular sequences are DNA sequences, only four symbols, A, C, G and T, are allowed. Each sequence has length at least 2 and at most 100.

Output

Print exactly one line for each test case. The line is to contain the lexicographically smallest sequence for the test case.

The following shows sample input and output for two test cases.

Sample Input

CGAGTCAGCT

CTCC

Sample Output

AGCTCGAGTC

CCCT

题目类型：字符处理题

算法分析：枚举可能出现的所有情况，用变量flag将目前为止的字典序最小的串记住，然后不断更新flag，直到最后将flag所指的字符串输出即可，下面给出两种实现，第一种通过倍增数组实现(推荐)，第二种通过循环节实现

/**************************************************
filename       :f.cpp
author         :maksyuki
created time   :2017/12/1 12:48:04
last modified  :2017/12/1 12:59:53
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

char s[maxn], v[maxn], tmp[maxn], ans[maxn];

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s);        
        strcpy(v, s);
        strcat(v, s);
        
        int len = strlen(s);
        memset(ans, 0, sizeof(ans));
        for(int i = 0; i < len; i++) {
            memcpy(tmp, v + i, len);
            tmp[len] = 0; //important
            if(!strlen(ans) || strcmp(ans, tmp) > 0) strcpy(ans, tmp);
        }
        puts(ans);
    }
    return 0;
}

/**************************************************

filename :f.cpp

author :maksyuki

created time :2017/12/1 12:48:04

last modified :2017/12/1 12:59:53

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

char s[maxn], v[maxn], tmp[maxn], ans[maxn];

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int t;

scanf("%d", &t);

while(t--) {

scanf("%s", s);

strcpy(v, s);

strcat(v, s);

int len = strlen(s);

memset(ans, 0, sizeof(ans));

for(int i = 0; i < len; i++) {

memcpy(tmp, v + i, len);

tmp[len] = 0; //important

if(!strlen(ans) || strcmp(ans, tmp) > 0) strcpy(ans, tmp);

}

puts(ans);

}

return 0;

}

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
#define maxn 106

char ans[maxn];

int least (const char *ans, int p, int q)
{
    int len = strlen (ans);
    int i;
    for (i = 0; i < len; i++)
	{
		if (ans[(p+i)%len] != ans[(q+i)%len])
			return ans[(p+i)%len] < ans[(q+i)%len];
	}
	return 0;
}

int main()
{
	int cases;
    //ifstream cin ("aaa.txt");

	cin >> cases;
	while (cases--)
	{
        cin >> ans;

        int i, flag = 0;
        int len = strlen (ans);
        for (i = 1; i < len; i++)
			if (least (ans, i, flag))
			    flag = i;

		for (i = 0; i < len; i++)
			printf ("%c", ans[(flag+i)%len]);
		printf ("\n");

	}

	return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;

#define maxn 106

char ans[maxn];

int least (const char *ans, int p, int q)

{

int len = strlen (ans);

int i;

for (i = 0; i < len; i++)

{

if (ans[(p+i)%len] != ans[(q+i)%len])

return ans[(p+i)%len] < ans[(q+i)%len];

}

return 0;

}

int main()

{

int cases;

//ifstream cin ("aaa.txt");

cin >> cases;

while (cases--)

{

cin >> ans;

int i, flag = 0;

int len = strlen (ans);

for (i = 1; i < len; i++)

if (least (ans, i, flag))

flag = i;

for (i = 0; i < len; i++)

printf ("%c", ans[(flag+i)%len]);

printf ("\n");

}

return 0;

}

uva1368

maksyuki 发表于 oj 分类，标签: 字符串-简单字符处理

12 9月 2015

DNA (Deoxyribonucleic Acid) is the molecule which contains the genetic instructions. It consists of four different nucleotides, namely Adenine, Thymine, Guanine, and Cytosine as shown in Figure 1. If we represent a nucleotide by its initial character, a DNA strand can be regarded as a long string (sequence of characters) consisting of the four characters A, T, G, and C. For example, assume we are given some part of a DNA strand which is composed of the following sequence of nucleotides:
Thymine-Adenine-Adenine-Cytosine-Thymine-Guanine-Cytosine-Cytosine-Guanine-Adenine-Thymine"
Then we can represent the above DNA strand with the string TAACTGCCGAT." The biologist Prof. Ahn found that a gene X commonly exists in the DNA strands of five different kinds of animals, namely dogs, cats, horses, cows, and monkeys. He also discovered that the DNA sequences of the gene X from each animal were very alike. See Figure 2.

	DNA sequence of gene X
Cat:	GCATATGGCTGTGCA
Dog:	GCAAATGGCTGTGCA
Horse:	GCTAATGGGTGTCCA
Cow:	GCAAATGGCTGTGCA
Monkey:	GCAAATCGGTGAGCA

Figure 2. DNA sequences of gene X in five animals.
Prof. Ahn thought that humans might also have the gene X and decided to search for the DNA sequence of X in human DNA. However, before searching, he should define a representative DNA sequence of gene X because its sequences are not exactly the same in the DNA of the five animals. He decided to use the Hamming distance to define the representative sequence. The Hamming distance is the number of different characters at each position from two strings of equal length. For example, assume we are given the two strings AGCAT" and GGAAT." The Hamming distance of these two strings is 2 because the 1st and the 3rd characters of the two strings are different. Using the Hamming distance, we can define a representative string for a set of multiple strings of equal length. Given a set of strings S = s₁,..., s_m of length n , the consensus error between a string y of length n and the set S is the sum of the Hamming distances between y and each s_i in S. If the consensus error between y and S is the minimum among all possible strings y of length n, y is called a consensus string of S . For example, given the three strings AGCAT" AGACT" and GGAAT" the consensus string of the given strings is AGAAT" because the sum of the Hamming distances between AGAAT" and the three strings is 3 which is minimal. (In this case, the consensus string is unique, but in general, there can be more than one consensus string.) We use the consensus string as a representative of the DNA sequence. For the example of Figure 2 above, a consensus string of gene X is GCAAATGGCTGTGCA" and the consensus error is 7.

Input

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing two integers m and n which are separated by a single space. The integer m (4m50)represents the number of DNA sequences and n (4n1000) represents the length of the DNA sequences, respectively. In each of the next m lines, each DNA sequence is given.

Output

Your program is to write to standard output. Print the consensus string in the first line of each case and the consensus error in the second line of each case. If there exists more than one consensus string, print the lexicographically smallest consensus string. The following shows sample input and output for three test cases.

Sample Input

5 8

TATGATAC

TAAGCTAC

AAAGATCC

TGAGATAC

TAAGATGT

4 10

ACGTACGTAC

CCGTACGTAG

GCGTACGTAT

TCGTACGTAA

6 10

ATGTTACCAT

AAGTTACGAT

AACAAAGCAA

AAGTTACCTT

AAGTTACCAA

TACTTACCAA

Sample Output

TAAGATAC

ACGTACGTAA

AAGTTACCAA

题目类型：字符处理题

算法分析：由本题的要求可知，只需对于每一个左到右，从上到下遍历已经存储在数组seq中的元素，将其与A、T、C、G顺序比较并算出每一列的Hamming距离sum，将所有列的Hamming距离都算出来后取其中的最小值并用temp记下最小值对应的A、T、C、G中的一个，累加到总Hamming距离ssum上并输出temp的值。以此类推，直到数组的最后一列之后，输出回车和ssum，下面第一个代码是更好的实现

/**************************************************
filename       :m.cpp
author         :maksyuki
created time   :2017/12/2 12:45:27
last modified  :2017/12/2 13:07:58
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1666;

const char v[] = {'*', 'A', 'C', 'G', 'T'};
int row, col;
char g[maxn][maxn];
char s[maxn];

int check(char c1, char c2) {
    if(c1 == c2) return 0;
    return 1;
}

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf(" %d %d", &row, &col);
         
        for(int i = 1; i <= row; i++)
            for(int j = 1; j <= col; j++)
                scanf(" %c", &g[i][j]);
        
        int res = 0, len = 0;
        for(int i = 1; i <= col; i++) {
            int minval = INF;
            int pos = -1;
            for(int j = 1; j <= 4; j++) {
                int tmp = 0;
                for(int k = 1; k <= row; k++) tmp += check(v[j], g[k][i]);
                
                if(minval > tmp) {
                    minval = tmp;
                    pos = j;
                }
            }
            res += minval;
            s[len++] = v[pos];
        }
        
        s[len] = 0;
        printf("%s\n%d\n", s, res);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

/**************************************************

filename :m.cpp

author :maksyuki

created time :2017/12/2 12:45:27

last modified :2017/12/2 13:07:58

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1666;

const char v[] = {'*', 'A', 'C', 'G', 'T'};

int row, col;

char g[maxn][maxn];

char s[maxn];

int check(char c1, char c2) {

if(c1 == c2) return 0;

return 1;

}

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int t;

scanf("%d", &t);

while(t--) {

scanf(" %d %d", &row, &col);

for(int i = 1; i <= row; i++)

for(int j = 1; j <= col; j++)

scanf(" %c", &g[i][j]);

int res = 0, len = 0;

for(int i = 1; i <= col; i++) {

int minval = INF;

int pos = -1;

for(int j = 1; j <= 4; j++) {

int tmp = 0;

for(int k = 1; k <= row; k++) tmp += check(v[j], g[k][i]);

if(minval > tmp) {

minval = tmp;

pos = j;

}

res += minval;

s[len++] = v[pos];

}

s[len] = 0;

printf("%s\n%d\n", s, res);

}

return 0;

}

#include <cstdio>
#include <iostream>
#include <fstream>
using namespace std;

const char flag[] = {'A', 'C', 'G', 'T'};
char seq[56][1006];

inline int absnum (int a)
{
    return a >= 0 ? a : -a;
}

int main()
{
    int cases, m, n;
    char temp;

	//ifstream cin ("aaa.txt");

    cin >> cases;
    while (cases--)
	{
        cin >> m >> n;
        int i;
        for (i = 0; i < m; i++)
			cin >> seq[i];

        int j, k, sum, ssum = 0;
        for (i = 0; i < n; i++)
		{
            int minval = 666666666;
			for (k = 0; k < 4; k++)
			{
                sum = 0;
			    for (j = 0; j < m; j++)
                    if (seq[j][i] != flag[k])
						sum++;

                if (minval > sum)
				{
					minval = sum;
					temp = flag[k];
				}

			}

			int q;
			for (q = 0; q < m; q++)
                if (seq[q][i] != temp)
                    ssum++;

            printf ("%c", temp);
		}
		printf ("\n%d\n", ssum);
	}

	return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

using namespace std;

const char flag[] = {'A', 'C', 'G', 'T'};

char seq[56][1006];

inline int absnum (int a)

{

return a >= 0 ? a : -a;

}

int main()

{

int cases, m, n;

char temp;

//ifstream cin ("aaa.txt");

cin >> cases;

while (cases--)

{

cin >> m >> n;

int i;

for (i = 0; i < m; i++)

cin >> seq[i];

int j, k, sum, ssum = 0;

for (i = 0; i < n; i++)

{

int minval = 666666666;

for (k = 0; k < 4; k++)

{

sum = 0;

for (j = 0; j < m; j++)

if (seq[j][i] != flag[k])

sum++;

if (minval > sum)

{

minval = sum;

temp = flag[k];

}

int q;

for (q = 0; q < m; q++)

if (seq[q][i] != temp)

ssum++;

printf ("%c", temp);

}

printf ("\n%d\n", ssum);

}

return 0;

}

uva1339

maksyuki 发表于 oj 分类，标签: 基础算法-排序

12 9月 2015

Ancient Roman empire had a strong government system with various departments, including a secret service department. Important documents were sent between provinces and the capital in encrypted form to prevent eavesdropping. The most popular ciphers in those times were so called substitution cipher and permutation cipher. Substitution cipher changes all occurrences of each letter to some other letter. Substitutes for all letters must be different. For some letters substitute letter may coincide with the original letter. For example, applying substitution cipher that changes all letters from A' to Y' to the next ones in the alphabet, and changes Z' to A', to the message VICTORIOUS'' one gets the message WJDUPSJPVT''. Permutation cipher applies some permutation to the letters of the message. For example, applying the permutation 2, 1, 5, 4, 3, 7, 6, 10, 9, 8 to the message VICTORIOUS'' one gets the message IVOTCIRSUO''. It was quickly noticed that being applied separately, both substitution cipher and permutation cipher were rather weak. But when being combined, they were strong enough for those times. Thus, the most important messages were first encrypted using substitution cipher, and then the result was encrypted using permutation cipher. Encrypting the message VICTORIOUS'' with the combination of the ciphers described above one gets the message JWPUDJSTVP''. Archeologists have recently found the message engraved on a stone plate. At the first glance it seemed completely meaningless, so it was suggested that the message was encrypted with some substitution and permutation ciphers. They have conjectured the possible text of the original message that was encrypted, and now they want to check their conjecture. They need a computer program to do it, so you have to write one.

Input

Input file contains several test cases. Each of them consists of two lines. The first line contains the message engraved on the plate. Before encrypting, all spaces and punctuation marks were removed, so the encrypted message contains only capital letters of the English alphabet. The second line contains the original message that is conjectured to be encrypted in the message on the first line. It also contains only capital letters of the English alphabet. The lengths of both lines of the input file are equal and do not exceed 100.

Output

For each test case, print one output line. Output YES' if the message on the first line of the input file could be the result of encrypting the message on the second line, or NO' in the other case.

Sample Input

JWPUDJSTVP

VICTORIOUS

MAMA

ROME

HAHA

HEHE

AAA

NEERCISTHEBEST

SECRETMESSAGES

Sample Output

YES

题目类型：简单排序

算法分析：本题先统计两个字符串中各个字母出现的次数，得到两个频率数组，其实原问题的等价问题是将两个频率数组按照递增排序后，如果对应相同的下标的两数组的值都相同，则原问题应回答YES，反之则回答NO

#include <cstdio>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;

char a[106], b[106];
int ditia[30], ditib[30];

int main()
{
	//ifstream cin ("aaa.txt");

    while (cin >> a >> b)
	{
        memset (ditia, 0, sizeof (ditia));
        memset (ditib, 0, sizeof (ditib));
        int i, len = strlen (a);

        for (i = 0; i < len; i++)
		{
			ditia[a[i]-'A']++;
			ditib[b[i]-'A']++;
		}

		sort (ditia, ditia + 26);
		sort (ditib, ditib + 26);

        for (i = 0; i < 26; i++)
			if (ditia[i] != ditib[i])
			    break;

		if (i == 26)
			cout << "YES" << endl;

		else
			cout << "NO" << endl;
	}

	return 0;
}

#include <cstdio>

#include <iostream>

#include <fstream>

#include <algorithm>

#include <cstring>

using namespace std;

char a[106], b[106];

int ditia[30], ditib[30];

int main()

{

//ifstream cin ("aaa.txt");

while (cin >> a >> b)

{

memset (ditia, 0, sizeof (ditia));

memset (ditib, 0, sizeof (ditib));

int i, len = strlen (a);

for (i = 0; i < len; i++)

{

ditia[a[i]-'A']++;

ditib[b[i]-'A']++;

}

sort (ditia, ditia + 26);

sort (ditib, ditib + 26);

for (i = 0; i < 26; i++)

if (ditia[i] != ditib[i])

break;

if (i == 26)

cout << "YES" << endl;

else

cout << "NO" << endl;

}

return 0;

}

uva1225

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

12 9月 2015

Trung is bored with his mathematics homeworks. He takes a piece of chalk and starts writing a sequence of consecutive integers starting with 1 to N (1 < N < 10000) . After that, he counts the number of times each digit (0 to 9) appears in the sequence. For example, with N = 13 , the sequence is:

12345678910111213

In this sequence, 0 appears once, 1 appears 6 times, 2 appears 2 times, 3 appears 3 times, and each digit from 4 to 9 appears once. After playing for a while, Trung gets bored again. He now wants to write a program to do this for him. Your task is to help him with writing this program.

Input

The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.

For each test case, there is one single line containing the number N .

Output

For each test case, write sequentially in one line the number of digit 0, 1,...9 separated by a space.

Sample Input

Sample Output

0 1 1 1 0 0 0 0 0 0

1 6 2 2 1 1 1 1 1 1

题目类型：简单数学

算法分析：枚举1到N的所有的正整数，对于每一个正整数从个位计算每一位上的数字并自加到频率数组diti相应的数字的值上。注意在判断并不断计算各位上的数字时，10的倍数需要特殊判断，下面第一个代码是更好的实现

/**************************************************
filename       :i.cpp
author         :maksyuki
created time   :2017/12/2 9:28:05
last modified  :2017/12/2 9:31:08
file location  :C:\Users\abcd\Desktop\TheEternalPoet
***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("in", "r", stdin)
#define CFO freopen ("out", "w", stdout)
#define CPPFF ifstream cin ("in")
#define CPPFO ofstream cout ("out")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define	DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int cnt[16];

int main()
{
#ifdef LOCAL
    CFF;
    //CFO;
#endif
    
    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        
        memset(cnt, 0, sizeof(cnt));
        for(int i = 1; i <= n; i++) {
            int j = i;
            while(j) {
                cnt[j%10]++;
                j /= 10;
            }
        }

        for(int i = 0; i <= 9; i++) {
            if(!i) printf("%d", cnt[i]);
            else printf(" %d", cnt[i]);
        }
        puts("");
    }
    return 0;
}

/**************************************************

filename :i.cpp

author :maksyuki

created time :2017/12/2 9:28:05

last modified :2017/12/2 9:31:08

file location :C:\Users\abcd\Desktop\TheEternalPoet

***************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("in", "r", stdin)

#define CFO freopen ("out", "w", stdout)

#define CPPFF ifstream cin ("in")

#define CPPFO ofstream cout ("out")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC)

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int cnt[16];

int main()

{

#ifdef LOCAL

CFF;

//CFO;

#endif

int t;

scanf("%d", &t);

while(t--) {

int n;

scanf("%d", &n);

memset(cnt, 0, sizeof(cnt));

for(int i = 1; i <= n; i++) {

int j = i;

while(j) {

cnt[j%10]++;

j /= 10;

}

for(int i = 0; i <= 9; i++) {

if(!i) printf("%d", cnt[i]);

else printf(" %d", cnt[i]);

}

puts("");

}

return 0;

}

#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

int main()
{
	int diti[16], cases, N;
    //ifstream cin ("aaa.txt");

    cin >> cases;
    while (cases--)
	{
        cin >> N;
        int i, j;
        memset (diti, 0, sizeof (diti));

        for (j = 1; j <= N; j++)
		{
			i = j;
            while ((i % 10) || (i % 10 == 0 && i / 10))
		    {
	    		diti[i%10]++;
	    		i /= 10;
     		}
	    }

        for (i = 0; i < 9; i++)
			printf ("%d ", diti[i]);

		printf ("%d\n", diti[i]);
	}

	return 0;
}

#include <iostream>

#include <fstream>

#include <cstring>

using namespace std;

int main()

{

int diti[16], cases, N;

//ifstream cin ("aaa.txt");

cin >> cases;

while (cases--)

{

cin >> N;

int i, j;

memset (diti, 0, sizeof (diti));

for (j = 1; j <= N; j++)

{

i = j;

while ((i % 10) || (i % 10 == 0 && i / 10))

{

diti[i%10]++;

i /= 10;

}

for (i = 0; i < 9; i++)

printf ("%d ", diti[i]);

printf ("%d\n", diti[i]);

}

return 0;

}

uva678

maksyuki 发表于 oj 分类，标签: 数据结构-二叉树

12 9月 2015

A number of K balls are dropped one by one from the root of a fully binary tree structure FBT. Each time the ball being dropped first visits a non-terminal node. It then keeps moving down, either follows the path of the left subtree, or follows the path of the right subtree, until it stops at one of the leaf nodes of FBT. To determine a ball's moving direction a flag is set up in every non-terminal node with two values, eitherfalse or true. Initially, all of the flags are false. When visiting a non-terminal node if the flag's current value at this node is false, then the ball will first switch this flag's value, i.e., from the falseto the true, and then follow the left subtree of this node to keep moving down. Otherwise, it will also switch this flag's value, i.e., from the true to the false, but will follow the right subtree of this node to keep moving down. Furthermore, all nodes of FBT are sequentially numbered, starting at 1 with nodes on depth 1, and then those on depth 2, and so on. Nodes on any depth are numbered from left to right.
For example, Fig. 1 represents a fully binary tree of maximum depth 4 with the node numbers 1, 2, 3, ..., 15. Since all of the flags are initially set to be false, the first ball being dropped will switch flag's values at node 1, node 2, and node 4 before it finally stops at position 8. The second ball being dropped will switch flag's values at node 1, node 3, and node 6, and stop at position 12. Obviously, the third ball being dropped will switch flag's values at node 1, node 2, and node 5 before it stops at position 10.
Fig. 1: An example of FBT with the maximum depth 4 and sequential node numbers.
Now consider a number of test cases where two values will be given for each test. The first value is D, the maximum depth of FBT, and the second one is I, the I^th ball being dropped. You may assume the value of Iwill not exceed the total number of leaf nodes for the given FBT.

Please write a program to determine the stop position P for each test case.
For each test cases the range of two parameters D and I is as below:

Input

Contains l+2 lines.

Line 1 I the number of test cases Line 2 test case #1, two decimal numbers that are separatedby one blank ... Line k+1 test case #k Line l+1 test case #l Line l+2 -1 a constant -1 representing the end of the input file

Output

Contains l lines.

Line 1 the stop position P for the test case #1 ... Line k the stop position P for the test case #k ... Line l the stop position P for the test case #l

Sample Input

54 23 410 12 28 128-1

Sample Output

1275123255

题目类型：完全二叉树模拟

算法分析：不能按照题目直接模拟，因为题目所给的数据过大。由于小球下落的方向与到达节点的小球序数是相关的，即对于节点i来说，第偶数个小球掉落在节点i上会往它的右子节点移动，第奇数个小球掉落在节点i上会往它的左子结点移动。所以可以直接模拟最后一个节点的移动情况，判断节点序号是奇数还是偶数，如果是奇数，就向其左子结点移动，反之，则向其右子节点移动；接着判断此时的节点是往哪走的第几个节点。对于偶数，则直接除以2，反之则加1再除以2

#include <iostream>
#include <fstream>
using namespace std;

int main()
{
//	ifstream cin ("aaa.txt");

	int cases;

	cin >> cases;

	while (cases--)
	{
		int depth, num;

		cin >> depth >> num;

		int k = 1, i;
		for (i = 0; i < depth - 1; i++)
		{
			if (num % 2)
			{
				k = 2 * k;
				num = (num + 1) / 2;
			}

			else
			{
				k = 2 * k + 1;
				num = num / 2;
			}
		}

		cout << k << endl;
	}

return 0;
}

#include <iostream>

#include <fstream>

using namespace std;

int main()

{

// ifstream cin ("aaa.txt");

int cases;

cin >> cases;

while (cases--)

{

int depth, num;

cin >> depth >> num;

int k = 1, i;

for (i = 0; i < depth - 1; i++)

{

if (num % 2)

{

k = 2 * k;

num = (num + 1) / 2;

}

else

{

k = 2 * k + 1;

num = num / 2;

}

cout << k << endl;

}

return 0;

}

返回首页上一页 12 13 14 15 16 下一页最后一页

超客的水墨烟雨

uva12412

uva12100

uva11988

uva11424

uva10935

uva1593

uva10533

uva10168

uva1600

Input

Output

Sample Input

Sample Output

uva1588

uva1587

uva1584

uva1368

uva1339

uva1225

uva678

Input

Output

Sample Input

Sample Output

分类目录

标签云

书签

近期评论

2015年9月
一	二	三	四	五	六	日
« 8月				10月 »
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30