Writing your first blog (official)
Before more or less wrote a little thing, but mostly write disorderly things, and did not stick to it. Now it is different, (I am a working person), I should write something for those students who love learning, for their better study and review materials, I will keep updating my blog in the future.
The title list
POJ 3278 POJ 2442 HDU 1870 HDU 1022 HDU 1237 UVA 673 HDU 1509
The title is located at Vjudge, the alternate address
Get into the business
The first question
Super class titleI haven’t told you about BFS yet, but don’t stop the guys from writing it out, manual membrane. Because we haven’t learned that yet, so I’ll post the code first and then make up the solution.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
struct node {
int x; / / position
int step; // Number of walks
}now,nex; // The current position is the next position
int n,m;
int vis[200005]; // mark to prevent trespassing
int bfs(int n) {
queue<node>q; // Queues are omnipotent
now.x=n;
now.step=0;
vis[now.x]=1;
q.push(now); // The initial location information presses the queue
while(! q.empty()) {
now =q.front(a); q.pop(a);if(now.x==m) // Determine if you can finish
return now.step;
for(int i=1; i<=3; i++) { // Three ways of walking
if(i==1)
nex.x=now.x+1;
if(i==2)
nex.x=now.x- 1;
if(i==3)
nex.x=now.x*2;
if(nex.x<0||nex.x>200005||vis[nex.x])continue; // Do not conform to the situation
vis[nex.x]=1;
nex.step=now.step+1;
q.push(nex); }}return - 1;
}
int main(a) {
scanf("%d %d",&n,&m);
memset(vis,0.sizeof(vis));
int ans=bfs(n);
printf("%d\n",ans);
return 0;
}
Copy the codeThe second question
Priority queues, hereinafter referred to as queues). First, the sequence of m rows is sorted from smallest to largest. Queue the elements in the first row of the sequence, then fetch, dynamically compare one of the elements in each row with the sum of the values of the elements in the following row.
#include<iostream>
#include<cstdio>
#include<map>
#include<queue>
#include<algorithm>
#define ll long long
//#include<bits/stdc++.h>
using namespace std;
inline int in(a) {
char ch;
int a=0;
while(! (((ch=getchar> = ())'0')&&(ch<='9'))); // Use getchar to read.
a*=10;
a+=ch-'0';
while(((ch=getchar> = ())'0')&&(ch<='9'))a*=10,a+=ch-'0'; // Then use ASCII to int
return a;
}
inline void out(int a) {
if(a>=10)out(a/10);
putchar(a%10+'0');
}
int num[105] [2005],cun[2005];
void change(priority_queue<int>&p,int m) {
for(int i = 0 ; i < m ; i++) {
cun[i] = p.top(a); p.pop();
}
}
int main(a) {
int t;
t=in(a);while(t--) {
priority_queue<int>p;
int n,m;
n=in(),m=in(a);for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
num[i][j]=in(a); }sort(num[i],num[i]+m);
}
for(int i=0; i<m; i++)
p.push(num[0][i]);
for(int i = 1 ; i < n ; i++) {
change(p,m); // The queue is empty
for(int j = 0 ; j < m ; j++) {
for(int k = m- 1 ; k >= 0 ; k--) {
if(j == 0)
p.push( num[i][j]+cun[k] );
// j == 0, this judgment executes a complete loop, m elements are stored in the queue
// the smallest element in the first column and all the sums in the second column
else {
// There are already m elements in the queue
if( num[i][j] + cun[k] < p.top() ) {
p.pop(a); p.push(num[i][j]+cun[k]);
} else break; // If there is a greater than, pass it over, because the array is ordered.}}}}change(p,m);
out(cun[m- 1]);
for(int j = m2 - ; j >= 0 ; j--) {
printf("");out(cun[j]);
}
puts("");
}
return 0;
}
Copy the codeThe third question
#include <iostream>
#include <stack>
using namespace std;
stack<int> a;
int main(a){
char b;
int sum=0;
while(cin>>b){
a.push(b);
if(a.top() = ='(') sum++;
else if(a.top() = =') ') sum--;
else{ cout<<sum<<endl; }}return 0;
}
Copy the codeThe fourth question
#include<bits/stdc++.h>
using namespace std;
char a[110],b[110];
int main(a) {
int n;
while(~scanf("%d %s %s",&n,a,b)) {
stack<char> st;
int i,j,kai;// I controls the stack entry sequence, J controls the stack exit sequence, kai controls the VIS state sequence
i=j=kai=0;
int vis[110] = {0};
while(n--) {
st.push(a[i++]); / / into the stack
vis[kai++]=1; // mark the stack
while(! st.empty()) {
if(st.top()==b[j]) { // The characters on the stack are equal to the characters off the stack
st.pop(a); j++;// Move the stack sequence to the right
vis[kai++]=2; // mark the stack
} else break; // Will not meet the stack condition}}if(st.empty()) { // The match is successful
printf("Yes.\n");
for(i=0; i<kai; i++) {
if(vis[i]==1) printf("in\n");
else if(vis[i]==2) printf("out\n");
}
printf("FINISH\n");
} else {// Failed to match
printf("No.\n");
printf("FINISH\n"); }}return 0;
}
Copy the codeThe fifth problem
The sixth question
#include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>
#include<stack>
#include<string>
#include<cstring>
using namespace std;
char trans(char a)
{
if(a==') ') return '(';
if(a=='] ') return '[';
return ' ';
}
int main(a)
{
int n;
cin>>n;
getchar(a);while(n--)
{
stack<char> s;
string str;
getline(cin,str); // Use getLine to avoid empty strings
int len=str.size(a);for(int i=0; i<len; ++i) {if(s.empty()||s.top()! =trans(str[i])) s.push(str[i]);
else s.pop(a); }if(s.empty()) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
Copy the codeNumber 7
#include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>
#include<stack>
#include<string>
#include<cstring>
using namespace std;
struct node{
string name;
int num,data,rank;
friend bool operator < (const node &a,const node b){ // Overload the operator
return a.rank==b.rank?a.num>b.num:a.rank>b.rank;
}
};
priority_queue<node> pq;
int main(a)
{
string str;int i=0;
while(cin>>str)
{
if(str[0] = ='G')
{
if(pq.empty()) cout<<"EMPTY QUEUE!"<<endl;
else{
cout<<pq.top().name<<""<<pq.top().data<<endl;
pq.pop();
}
}
else{
node t;
cin>>t.name>>t.data>>t.rank;
t.num=++i;
pq.push(t); }}return 0;
}
Copy the code