day1: C++STL 요약
57387 단어 2019 여름 캠프
day1: C++STL 요약
A번: hdu 2094: 우승자 탄생
어이가 없네요. 예전에 했던 문제를 풀 줄도 모르고 맵을 쓰려고 했어요. 그리고 WA를 몇 번 했는데 마음이 폭발적이었어요. 문제를 보충하고 보니 set이 제일 잘 풀린 거예요.
코드:#include
#include
#include
#include
#include
using namespace std;
int main()
{
int n;
string s1,s2;
while(~scanf("%d",&n))
{
if(n==0)
break;
set<string>SET1;
set<string>SET2;
for(int i=0;i<n;i++)
{
cin>>s1>>s2;
SET1.insert(s1);
SET1.insert(s2);
SET2.insert(s2);
}
if(SET1.size()-SET2.size()==1)
printf("Yes
");
else
printf("No
");
}
return 0;
}
B:hdu1063:과일
처음부터 맵으로 끼워 넣으려고 했는데 값을 어떻게 부여해야 할지 몰라서 멘탈이 붕괴되고 문제를 보충할 때 알게 됐어요...맵 삽입이 어떻게 값을 부여하는지 해결한 후에 맵을 어떻게 옮겨다니는지 몰라요. 힘든 뒤에 바로 두 개의 교체기를 사용해서 이중순환을 하면 된다는 것을 알게 됐어요.
뒤에 코드를 제출할 때 여러 그룹의 사례에서 큰 비밀을 발견했습니다. 동기화를 닫으면 오류가 발생해서 저는 WA를 여러 번 했습니다.이제 더 이상 끄는 걸로 동기화하고 싶지 않아요.
코드 입력:#include
#include
#include
#include
#include
#include
using namespace std;
int main()
{
int n,m;
string s1,s2;
int num;
scanf("%d",&n);
while(n--)
{
map<string,map<string,int> >mp;
scanf("%d",&m);
for(int i=0;i<m;i++)
{
cin>>s1>>s2>>num;
mp[s2][s1]+=num;
}
map<string,map<string,int> >::iterator it;
map<string,int>::iterator it2;
for(it=mp.begin();it!=mp.end();it++)
{
cout<<it->first<<endl;
for(it2=it->second.begin();it2!=it->second.end();it2++)
{
cout<<" |----"<<it2->first<<'('<<it2->second<<')'<<endl;
}
}
if(n>0)
cout<<endl;
}
return 0;
}
C번: hdu 3877: Special sort
이 문제는 더 어이가 없네,sortWA를 쓰고 Stablesort A 입니다.
코드는 다음과 같습니다.#include
#include
#include
#include
#define ll long long
using namespace std;
struct node
{
ll a,b,c;
int level;
}num[10010];
/** */
int cmp(node x,node y)
{
if(x.c!=y.c)
return x.c>y.c;
else
return x.level<y.level;
}
int main()
{
ll t,n;
scanf("%lld",&t);
while(t--)
{
memset(num,0,sizeof(num));
scanf("%lld",&n);
for(int i=0;i<n;i++)
{
scanf("%lld%lld",&num[i].a,&num[i].b);
num[i].c=num[i].a+num[i].b;
if(num[i].a>num[i].b)
num[i].level=1;
else if(num[i].a==num[i].b)
num[i].level=2;
else
num[i].level=3;
}
stable_sort(num,num+n,cmp);
for(int i=0;i<n;i++)
{
if(num[i].a<num[i].b)
{
printf("%lld+%lld=[,num[i].a,num[i].b,num[i].c);
}
else if(num[i].a>num[i].b)
{
printf("%lld+%lld=[>%lld]
",num[i].a,num[i].b,num[i].c);
}
else
printf("%lld+%lld=[=%lld]
",num[i].a,num[i].b,num[i].c);
}
printf("
");
}
return 0;
}
D번: hdu 1027: Ignatius and the Princess II
직접nextpermutation#include
#include
#include
#include
#include
using namespace std;
int a[10010];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(a,0,sizeof(a));
for(int i=0;i<n;i++)
a[i]=i+1;
int num=0;
do
{
num++;
if(num==m)
{
for(int i=0;i<n;i++)
{
if(i==0)
printf("%d",a[i]);
else
printf(" %d",a[i]);
}
printf("
");
break;
}
}
while(next_permutation(a,a+n));
}
return 0;
}
E번: hdu 6015: Skip the Class
처음부터 구조체를 쓸 생각만 하면 돼요. 오늘의 STL을 쓸 생각은 없었는데 뒤에서 문제풀이를 들었을 때 맵을 쓰면 좀 간단할 것 같았어요. 그런데 처음에는 구조체를 써도 복잡하지 않을 것 같았어요.#include
#include
#include
#include
using namespace std;
struct node
{
char name[20];
int value;
}a[210];
int cmp(node x,node y)
{
if(!strcmp(x.name,y.name)==0)
return strcmp(x.name,y.name)<0;
else
return x.value>y.value;
}
int main()
{
int t;
int n;
scanf("%d",&t);
while(t--)
{
memset(a,0,sizeof(a));
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%s%d",a[i].name,&a[i].value);
}
sort(a,a+n,cmp);
char str[20];
strcpy(str,a[0].name);
int num=0;
int sum=a[0].value;
for(int i=1;i<n;i++)
{
if(strcmp(a[i].name,str)==0)
{
if(num<1)
sum+=a[i].value;
num++;
}
else
{
strcpy(str,a[i].name);
num=0;
sum+=a[i].value;
}
}
printf("%d
",sum);
}
return 0;
}
F번: hdu 1896:Stones
또 예전에 풀었던 문제인데 이번에 풀지 못했어요. 관건은 뒷문제를 잘 못 봐서...
우선 순위 대기열 + 전체 과정을 시뮬레이션하면 됩니다#include
#include
#include
#include
#include
using namespace std;
struct stone
{
int pos;
int dis;
friend bool operator < (stone x,stone y)
{
if(x.pos==y.pos)
return x.dis>y.dis;
else
return x.pos>y.pos;
}
};
int main()
{
int n,m;
stone a;
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
priority_queue<stone>que;
int maxdis;
for(int i=0;i<m;i++)
{
scanf("%d%d",&a.pos,&a.dis);
que.push(a);
}
int i=1;
while(!que.empty())
{
a=que.top();
que.pop();
if(i%2==1)
{
a.pos+=a.dis;
que.push(a);
maxdis=a.pos;
}
i++;
}
printf("%d
",maxdis);
}
return 0;
}
G제목: hdu 1022: Train Problem I
부끄럽다. 제목을 보기도 전에 미처 보지 못했다. 바로 한 창고의 응용 프로그램이다. 그러나 아마도 내가 생각하기 시작하면 좀 어려울 것이다. 아니면 너무 나쁠 것이다...#include
using namespace std;
int main()
{
int n;
char in[20],out[20];
while(~scanf("%d%s%s",&n,in,out))
{
stack<char>sta;
int i=0,j=0;
int len1=strlen(in);
int len2=strlen(out);
sta.push(in[0]);
int t=0;
int vis[210];
vis[t++]=1;
while(i<len1&&j<len2)
{
if(!sta.empty()&&sta.top()==out[j])
{
sta.pop();
j++;
vis[t++]=0;
}
else
{
sta.push(in[++i]);
vis[t++]=1;
}
}
if(!sta.empty())
{
printf("No.
");
}
else
{
printf("Yes.
");
for(int i=0;i<t;i++)
{
if(vis[i]==0)
printf("out
");
else
printf("in
");
}
}
printf("FINISH
");
}
return 0;
}
#include
#include
#include
#include
#include
using namespace std;
int main()
{
int n;
string s1,s2;
while(~scanf("%d",&n))
{
if(n==0)
break;
set<string>SET1;
set<string>SET2;
for(int i=0;i<n;i++)
{
cin>>s1>>s2;
SET1.insert(s1);
SET1.insert(s2);
SET2.insert(s2);
}
if(SET1.size()-SET2.size()==1)
printf("Yes
");
else
printf("No
");
}
return 0;
}
#include
#include
#include
#include
#include
#include
using namespace std;
int main()
{
int n,m;
string s1,s2;
int num;
scanf("%d",&n);
while(n--)
{
map<string,map<string,int> >mp;
scanf("%d",&m);
for(int i=0;i<m;i++)
{
cin>>s1>>s2>>num;
mp[s2][s1]+=num;
}
map<string,map<string,int> >::iterator it;
map<string,int>::iterator it2;
for(it=mp.begin();it!=mp.end();it++)
{
cout<<it->first<<endl;
for(it2=it->second.begin();it2!=it->second.end();it2++)
{
cout<<" |----"<<it2->first<<'('<<it2->second<<')'<<endl;
}
}
if(n>0)
cout<<endl;
}
return 0;
}
#include
#include
#include
#include
#define ll long long
using namespace std;
struct node
{
ll a,b,c;
int level;
}num[10010];
/** */
int cmp(node x,node y)
{
if(x.c!=y.c)
return x.c>y.c;
else
return x.level<y.level;
}
int main()
{
ll t,n;
scanf("%lld",&t);
while(t--)
{
memset(num,0,sizeof(num));
scanf("%lld",&n);
for(int i=0;i<n;i++)
{
scanf("%lld%lld",&num[i].a,&num[i].b);
num[i].c=num[i].a+num[i].b;
if(num[i].a>num[i].b)
num[i].level=1;
else if(num[i].a==num[i].b)
num[i].level=2;
else
num[i].level=3;
}
stable_sort(num,num+n,cmp);
for(int i=0;i<n;i++)
{
if(num[i].a<num[i].b)
{
printf("%lld+%lld=[,num[i].a,num[i].b,num[i].c);
}
else if(num[i].a>num[i].b)
{
printf("%lld+%lld=[>%lld]
",num[i].a,num[i].b,num[i].c);
}
else
printf("%lld+%lld=[=%lld]
",num[i].a,num[i].b,num[i].c);
}
printf("
");
}
return 0;
}
#include
#include
#include
#include
#include
using namespace std;
int a[10010];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(a,0,sizeof(a));
for(int i=0;i<n;i++)
a[i]=i+1;
int num=0;
do
{
num++;
if(num==m)
{
for(int i=0;i<n;i++)
{
if(i==0)
printf("%d",a[i]);
else
printf(" %d",a[i]);
}
printf("
");
break;
}
}
while(next_permutation(a,a+n));
}
return 0;
}
#include
#include
#include
#include
using namespace std;
struct node
{
char name[20];
int value;
}a[210];
int cmp(node x,node y)
{
if(!strcmp(x.name,y.name)==0)
return strcmp(x.name,y.name)<0;
else
return x.value>y.value;
}
int main()
{
int t;
int n;
scanf("%d",&t);
while(t--)
{
memset(a,0,sizeof(a));
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%s%d",a[i].name,&a[i].value);
}
sort(a,a+n,cmp);
char str[20];
strcpy(str,a[0].name);
int num=0;
int sum=a[0].value;
for(int i=1;i<n;i++)
{
if(strcmp(a[i].name,str)==0)
{
if(num<1)
sum+=a[i].value;
num++;
}
else
{
strcpy(str,a[i].name);
num=0;
sum+=a[i].value;
}
}
printf("%d
",sum);
}
return 0;
}
#include
#include
#include
#include
#include
using namespace std;
struct stone
{
int pos;
int dis;
friend bool operator < (stone x,stone y)
{
if(x.pos==y.pos)
return x.dis>y.dis;
else
return x.pos>y.pos;
}
};
int main()
{
int n,m;
stone a;
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
priority_queue<stone>que;
int maxdis;
for(int i=0;i<m;i++)
{
scanf("%d%d",&a.pos,&a.dis);
que.push(a);
}
int i=1;
while(!que.empty())
{
a=que.top();
que.pop();
if(i%2==1)
{
a.pos+=a.dis;
que.push(a);
maxdis=a.pos;
}
i++;
}
printf("%d
",maxdis);
}
return 0;
}
#include
using namespace std;
int main()
{
int n;
char in[20],out[20];
while(~scanf("%d%s%s",&n,in,out))
{
stack<char>sta;
int i=0,j=0;
int len1=strlen(in);
int len2=strlen(out);
sta.push(in[0]);
int t=0;
int vis[210];
vis[t++]=1;
while(i<len1&&j<len2)
{
if(!sta.empty()&&sta.top()==out[j])
{
sta.pop();
j++;
vis[t++]=0;
}
else
{
sta.push(in[++i]);
vis[t++]=1;
}
}
if(!sta.empty())
{
printf("No.
");
}
else
{
printf("Yes.
");
for(int i=0;i<t;i++)
{
if(vis[i]==0)
printf("out
");
else
printf("in
");
}
}
printf("FINISH
");
}
return 0;
}