130331周赛 (二)

#include
#include
#include
#include

using namespace std;

bool cmp(int a,int b)
{
return a >b;
}

int a[55];
int n,k;
int main()
{
int i;
while(cin >> n >> k)
{
for(i=1; i<=n; i++)
cin >> a[i];
if(k > n)
{
cout << -1 << endl;
continue;
}
sort(a+1,a+n+1,cmp);
cout << a[k] << ' ' << a[k] << endl;
}
return 0;
}

F. Cycle in Graph

在图中找出环......
先dfs找出一条链，然后从开头开始判断与尾部是否相连
[cpp]
#include
#include
#include
#include
#include
#include
#define MAX 100010
using namespace std;

bool vis[MAX],neigh[MAX];
vectora[MAX];
vectorlis;
int n,m,k;

void dfs(int x)
{
vis[x] = 1;
lis.push_back(x);
for(int i=0; i {
if(vis[a[x][i]] == 1)
continue;
vis[a[x][i]] = 1;
dfs(a[x][i]);
break;
}
}

int main()
{
int i,j,b,c;
while(cin >> n >> m >> k)
{
memset(vis,0,sizeof(vis));
memset(neigh,0,sizeof(neigh));
lis.clear();
for(i=0;i a[i].clear();
for(i=0; i {
scanf("%d%d",&b,&c);
a[b].push_back(c);
a[c].push_back(b);
}
dfs(1);
int t = lis.back();
for(i=0; i {
neigh[a[t][i]] = 1;
}
while(neigh[lis[0]] == 0)
lis.erase(lis.begin());
cout << lis.size() << endl;
for(i=0; i cout << lis[i] << ' ';
cout << endl;
}
return 0;
}

#include
#include
#include
#include
#include
#include
#define MAX 100010
using namespace std;

bool vis[MAX],neigh[MAX];
vectora[MAX];
vectorlis;
int n,m,k;

void dfs(int x)
{
vis[x] = 1;
lis.push_back(x);
for(int i=0; i {
if(vis[a[x][i]] == 1)
continue;
vis[a[x][i]] = 1;
dfs(a[x][i]);
break;
}
}

int main()
{
int i,j,b,c;
while(cin >> n >> m >> k)
{
memset(vis,0,sizeof(vis));
memset(neigh,0,sizeof(neigh));
lis.clear();
for(i=0;i a[i].clear();
for(i=0; i {
scanf("%d%d",&b,&c);
a[b].push_back(c);
a[c].push_back(b);
}
dfs(1);
int t = lis.back();
for(i=0; i {
neigh[a[t][i]] = 1;
}
while(neigh[lis[0]] == 0)
lis.erase(lis.begin());
cout << lis.size() << endl;
for(i=0; i cout << lis[i] << ' ';
cout << endl;
}
return 0;
}

G. Roadside Trees (Simplified Edition)
水题直接模拟

[cpp]
#include
#include
#include
#include

using namespace std;
int n;

int main()
{
int a;
int sum=0,b=0;
cin >> n;
while (n--)
{
scanf("%d",&a);
sum++;
if(a > b)
sum += (a-b);
else if(b > a)
sum += (b-a);
sum++;
b = a;
}

printf("%d\n",sum-1);
return 0;
}

#include
#include
#include
#include

using namespace std;
int n;

int main()
{
int a;
int sum=0,b=0;
cin >> n;
while (n--)
{
scanf("%d",&a);
sum++;
if(a > b)
sum += (a-b);
else if(b > a)
sum += (b-a);
sum++;
b = a;
}

printf("%d\n",sum-1);
return 0;
}

H. Escape from Stones
题目的叙述是二分的思想，可以推断 ：第一次向右边跳时，原所在点肯定是总的边界的最左边（以后不会更靠左边），同理，第一次向左跳时，原所在点为最右端。
直接根据输入输出

[cpp]
#include
#include
#include
#include
#inc