0%

简单的栈应用。一开始忽略了判断栈是否为空。

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
31
#include<iostream>
#include<string>
#include<stack>
#include<map>
using namespace std;
int n;
string s;
map<char,char>a;
int main(){
a[')']='(';
a[']']='[';
cin>>n;
cin.get();
while(n--){
stack<char>c;
getline(cin,s);
int i;
for(i=0;i<s.length();i++){
if(s[i]=='('||s[i]=='[') c.push(s[i]);
else if(s[i]==')'||s[i]==']'){
if(c.empty()) break;
if(c.top()==a[s[i]]) c.pop();
else break;
}
else continue;
}
if(i==(int)s.length()&&c.empty()) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

是道例题,没错就是道例题。书上有代码,就是有代码。有代码的题应该不写博客的,可是代码不对,不对!!!!

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
31
32
33
34
35
36
#include<iostream>
#include<stack>
using namespace std;
const int maxn=1000+10;
int n,target[maxn];
int main(){
while(cin>>n&&n){
while(cin>>target[1]&&target[1]){
stack<int>s;
int A=1,B=1;
for(int i=2;i<=n;i++)
cin>>target[i];
int ok=1;
while(B<=n){
if(A==target[B]){
A++;
B++;
}
else if(!s.empty()&&s.top()==target[B]){
s.pop();
B++;
}
else if(A<=n) s.push(A++);
else{
ok=0;
break;
}
}
if(ok) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}

cout<<endl;
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

昨天ACM培训时开始写的,一看就有思路,建了两个结构体表示topics和员工。循环中间多加了个else一直没检查出来,错了好多次。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct topic{
int tid,num,t0,t,dt,q_num,finished;
};
struct member{
int pid,k,work_left,last;
vector<int>pidk;
bool operator <(const member&a) const{
if(a.last==last) return a.pid>pid;
else return a.last>last;
}
};
vector<topic>topics;
vector<member>staff;
int main(){
int m,n,kase=0;
while(cin>>m&&m){
int time=0,need=0;
while(m--){
topic a;
cin>>a.tid>>a.num>>a.t0>>a.t>>a.dt;
a.q_num=a.finished=0;
topics.push_back(a);
}
cin>>n;
int z=0;
while(n--){
z++;
member a;
int x;
a.work_left=a.last=0;
cin>>a.pid>>a.k;
a.pid=z;
for(int i=0;i<a.k;i++){
cin>>x;
a.pidk.push_back(x);
}
staff.push_back(a);
}
while(1){
for(int i=0;i<topics.size();i++)
if(time>=topics[i].t0&&topics[i].finished+topics[i].q_num<topics[i].num){
topics[i].t0+=topics[i].dt;
topics[i].q_num=min(++topics[i].q_num,topics[i].num-topics[i].finished);
}
sort(staff.begin(),staff.end());
for(int i=0;i<staff.size();i++){
if(!staff[i].work_left)
for(int j=0;j<staff[i].pidk.size();j++)
for(int k=0;k<topics.size();k++)
if(staff[i].pidk[j]==topics[k].tid&&topics[k].q_num){
staff[i].last=time;
staff[i].work_left=topics[k].t;
topics[k].q_num--;
need=max(need,topics[k].t);

if(++topics[k].finished==topics[k].num){
topics.erase(topics.begin()+k);
if(!topics.size()){
time+=need;
goto END;
}
}
goto NEXT_P;
}
NEXT_P:
continue;
}
time++;
need=max(--need,0);
for(int i=0;i<staff.size();i++)
staff[i].work_left=max(--staff[i].work_left,0);
}
END:
kase++;
cout<<"Scenario "<<kase<<": All requests are serviced within "<<time<<" minutes."<<endl;
staff.clear();
topics.clear();
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

本来想Ac掉UVa-12333的但后来发现目前的知识做有些困难,准备以后再做了,又Ac了个第五章的例题,有效题数50了。

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

给出一个表格,问有没有r1、r2、c1、c2满足着两行与两列相交的单元格内部分别相同。

首先进行预处理,给每一种数据分配ID,将string转化为int。

然后使用pair,把两个int组成二元组,存在另一个map里,之后单次遍历储存查找。

PS:这是UVa上Ac的第50道题。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstring>
#include<string>
#include<map>
using namespace std;
int a[10010][15];
typedef pair<int,int>two_data;
map<string,int>data_id;
map<two_data,int>data_r;//二元组映射。
string s0;
int main(){
int m,n;
while(cin>>m>>n){
int t=1;
getchar();
string s;
for(int i=0;i<m;i++){
int k=0;
getline(cin,s);
string x;
for(int j=0;j<s.length();j++){//预处理分配ID。
if(s[j]!=',') x+=s[j];
if(s[j]==','||j==s.length()-1){
if(!data_id.count(x)){
data_id[x]=t;
t++;
}
a[i][k]=data_id[x];
x=s0;
k++;
}
}
}
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
for(int k=0;k<m;k++){
int x=a[k][i],y=a[k][j];
if(data_r.count(make_pair(x,y))){//遍历数据库查找相同组。
cout<<"NO"<<endl;
cout<<data_r[make_pair(x,y)]+1<<" "<<k+1<<endl;
cout<<i+1<<" "<<j+1<<endl;
goto END;
}
data_r[make_pair(x,y)]=k;
}
data_r.clear();
}
}
cout<<"YES"<<endl;
END:
data_id.clear();
data_r.clear();
memset(a,0,sizeof(a));
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

给出旧字典和新字典,输出字典的变化增加+、减少-、更改*。

保存字典之后对比就好,但是注意在没有那项变动时不要多输出符号。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
using namespace std;
struct key_value{
string key,value;
};
set<string>key;
vector<string>change[3];
map<string,string>dict[2];
int main(){
int t,flag=1;
key_value x,y;
cin>>t;
getchar();
while(t--){
dict[0].clear();
dict[1].clear();
for(int i=0;i<3;i++) change[i].clear();
change[0].push_back("+");
change[1].push_back("-");
change[2].push_back("*");
key.clear();
char c;
for(int i=0;i<2;){
c=getchar();
if(c=='{'){
flag=1;
x=y;
continue;
}
if(c=='}'){
if(x.key!=""&&x.value!=""){
dict[i][x.key]=x.value;
key.insert(x.key);
}
i++;
getchar();
continue;
}
if(c==','||c==':'){
flag=!flag;
if(c==','){
dict[i][x.key]=x.value;
key.insert(x.key);
x=y;
}
continue;
}
if(flag) x.key+=c;
else x.value+=c;
}
for(set<string>::iterator it=key.begin();it!=key.end();it++){
if(!dict[0].count(*it)) change[0].push_back(*it);
else if(!dict[1].count(*it)) change[1].push_back(*it);
else if(dict[0][*it]!=dict[1][*it]) change[2].push_back(*it);
}
int k=0;
for(int i=0;i<3;i++){
int first=2;
if(change[i].size()-1){
for(int j=0;j<change[i].size();j++){
if(first) first--;
else cout<<",";
cout<<change[i][j];
}
cout<<endl;
k++;
}
}
if(!k) cout<<"No changes"<<endl;
cout<<endl;
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

给出平面上的n个点,求一条竖直直线使平面上所有点对称,注意是竖直直线。

给所有的点排序,排序后取第一个点作为标准,找其他的点进行匹配,确定一条轴,判断其他点是否关于这个轴对称。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct point{
double x,y;
bool operator < (const point &a)const{
if(a.y==y) return a.x>x;
else return a.y>y;
}
};
vector<point>a;
vector<point>b;
int main(){
int t;
double mid=0;
cin>>t;
while(t--){
int n,k=1;
point p;
cin>>n;
while(n--){
cin>>p.x>>p.y;
a.push_back(p);
b.push_back(p);
}
if(n==1){
cout<<"YES"<<endl;
a.clear();
b.clear();
continue;
}
sort(a.begin(),a.end());
for(int i=1;i<a.size();i++){
if(a[0].y!=a[i].y){
mid=(a[0].x+a[i-1].x)/2;
break;
}
}
for(int i=0;i<b.size();i++) b[i].x=2*mid-b[i].x;
sort(b.begin(),b.end());
for(int i=0;i<a.size();i++){
if(a[i].x!=b[i].x||a[i].y!=a[i].y){
k=0;
break;
}
}
if(k) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
a.clear();
b.clear();
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

输入一段程序代码,要你找出bug,有两种bug,一是引用未赋值变量,二是下标越界。

主要考察的就是细节,思路并不难,找程序的bug,首先自己写的程序细节上不能出bug。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<string>
#include<sstream>
#include<map>
using namespace std;
string s0,s,s1,s2,left_value,right_value;
int bug;
map<string,unsigned int>a;
map<string,string>value;
string get_value(string x,string arr){
unsigned int t=0;
string y,z;
if(x.find("[")==string::npos){
stringstream ss(x);
ss>>t;
if(arr!=s0&&t>=a[arr]) bug=1;
return x;
}
y=x.substr(0,x.find("["));
z=x.substr(x.find("[")+1,x.find_last_of("]")-2);
z=get_value(z,y);
if(bug) return s0;
x=y+"["+z+"]";
if(!value.count(x)) bug=1;
return value[x];
}
void get_arr(){
string x,y;
unsigned int z;
x=s.substr(0,s.find("["));
y=s.substr(s.find("[")+1,s.find_last_of("]")-2);
y=get_value(y,s0);
stringstream ss(y);
ss>>z;
a[x]=z;
return;
}
int main(){
int flag=0,cnt=1;
a[s0]=0;
string arr,indx;
while(cin>>s){
if(s!=".") flag=1;
else if(!flag) break;
else{
if(!bug) cout<<"0"<<endl;
a.clear();
value.clear();
left_value=right_value=s0;
cnt=1;
bug=flag=0;
continue;
}
if(bug) continue;
if(s.find("=")==string::npos) get_arr();
else{
s1=s.substr(0,s.find("="));
s2=s.substr(s.find("=")+1);
arr=s1.substr(0,s1.find("["));
indx=s1.substr(s1.find("[")+1,s1.find_last_of("]")-2);
indx=get_value(indx,arr);
stringstream ss(indx);
unsigned int t;
ss>>t;
if(t>=a[arr]) bug=1;
left_value=arr+"["+indx+"]";
right_value=get_value(s2,s0);
if(bug){
cout<<cnt<<endl;
continue;
}
value[left_value]=right_value;
left_value=right_value=s0;
}
cnt++;
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

做UVa的第三十天。。本来准备明天Ac道题再写总结的,但是,昨天晚上9点半,出现了很好玩的东西。

昨完题之后十一点多,目测十二点之前也睡不着了,所以就直接写总结了。。

这十天刷的题挺多的,学到的也很多。感觉第五章前面好多水题。

从7号到现在一直没刷题。。周六做了协会题,周日比赛,昨天写了道没写完。。

这十天主要学了STL,感觉没想象中的那么难,之前的UVa-101现在看也很简单了。

比赛时发现,其实主要还是要学后面几章,尽快结束第五章。

以后继续努力吧。

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

和学长一起参加了青理工的比赛,从开始到断电,做了3h40min,Ac了5道题,感觉现场做题确实是容易有点小激动。。很多低级的错误都出现了。。

5道题中,我参与了其中四道。

C题英文题学长看着感觉水,就先做了。

G题是判断谁能在游戏中获胜的题,很快找到了思路,由于印刷的题目错了,第一次提交WA了。。想了好久发现109是印刷错误应该为10^9。修改代码之后一次Ac。

J题是计算多边形面积的,其实挺水的,但我们在第一次交对""的处理不到位WA了,修改过后Ac。

H是素数间隙判断,看着像水题,学长在看别的题时,我先写了部分代码。。居然连素数表都打错了。。后来经学长重新打表修改Ac了。。

B题求幸运数问题,一开始我用set做的但是TLE了,后来学长找到了幸运数公式。修改简化循环后Ac。

剩下几道题都没什么思路。。三角形面积的那个可能是需要什么公式吧,感觉其他的都需要学习紫书后面的知识。还是要继续往下学啊。

总的来说这次比赛挺让人满意的,体验了竞赛的感觉,也学到了一些做题的技巧。

至于下一步的打算,当然是继续做题、学习。准备最晚明年三月做完UVa的百题,加入集训队。现在尽量多看紫书上的知识点、和C++Primer上关于C++的函数的讲 解。

以后的路还长,这只是个开始。

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **