备战天梯赛第一场 题解
by fengyuming233
A HDU5702 结构体排序
一个很基本的简单的知识点，不会请自行百度
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#define each(a,b,c) for(int a=b;a<=c;a++)//宏定义 简化for循环
#define de(x) cout<<#x<<" "<<(x)<<endl;
const int maxn = 15;
const int INF = 0x3f3f3f3f;
using namespace std;
struct node
{
char color[15];
int num;
}a[15];
bool cmp(node a, node b)//自己定义排序标准
{
return a.num > b.num;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n;
scanf("%d", &n);
each(i, 1, n)
{
scanf("%s", a[i].color);
scanf("%d", &a[i].num);
}
sort(a + 1, a + 1 + n, cmp);
each(i, 1, n)
{
printf("%s", a[i].color);
if (i == n)printf("\n");//注意输出格式，最后一个是回车，其他都是空格
else printf(" ");
}
}
}
B HDU1034 沙雕模拟题
这种模拟题很受天梯赛的待见啊,毕竟不用看着模板敲，着重练习这类题
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#define each(a,b,c) for(int a=b;a<=c;a++)
#define de(x) cout<<#x<<" "<<(x)<<endl;
const int maxn = 1e3+5;
const int INF = 0x3f3f3f3f;
int a[maxn];
int temp[maxn];
int n;
int ans1 = 0;
int ans2 = 0;
bool check()
{
int flag = 1;
each(i, 0, n - 1)
{
int nxt = (i + 1) % n;
if (a[i] != a[nxt])flag = 0;
}
if (flag)ans2 = a[0];
return flag;
}
int main()
{
while (scanf("%d", &n) != EOF&&n)
{
each(i, 0, n - 1)
{
scanf("%d", &a[i]);
}
ans1 = 0;
while (1)
{
if (check())break;
ans1++;
each(i, 0, n - 1)
{
int nxt = (i + 1) % n;
temp[nxt] = a[i] / 2;
a[i] = a[i] / 2;
}
each(i, 0, n - 1)
{
a[i] += temp[i];
temp[i] = 0;
if (a[i] % 2)a[i]++;
}
}
printf("%d %d\n", ans1, ans2);
}
return 0;
}
C HDU1412 set的简单实用
STL是重要的工具，请务必学会set map priority queue stack vector的用法
int main()
{
int a,b;int num;
while(scanf("%d%d",&a,&b)!=EOF)
{
set<int>s;
while(a--)
{
cin>>num;
s.insert(num);
}
while(b--)
{
cin>>num;
s.insert(num);
}
set<int>::iterator it;
int cnt=s.size();
for(it=s.begin();it!=s.end();it++){
printf("%d",*it);
if(cnt-->1)
printf(" ");
}
puts("");
}
}
D CF1077B 贪心
此题目标在于消灭101这样的序列，所以你从左到右扫描时，如果发现101的序列，你只能立即破坏它，消去1个1，如果你消去左边的1，那么不会对后面的序列造成任何影响，如果你消去右边的1，就可能破坏了右边的一个新的101序列，所以每次发现101序列时将其转化为100，就可以使利益最大化
贪心也有可能考到
#define _CRT_SBCURE_NO_DEPRECATE
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <bitset>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define ll long long
#define mm0(a) memset(a,0,sizeof(a))
#define mm(a,b) memset(a,b,sizeof(a))
#define each(a,b,c) for(int a=b;a<=c;a++)
#define de(x) cout << #x << " " << x <<endl
#define rush() int T;scanf("%d",&T);each(kase,1,T)
#define scan(a,b) scanf("%d%d",&a,&b)
#define fin(a) scanf("%d",&a)
using namespace std;
inline int read(){int s=0;char ch=getchar();for(; ch<'0'||ch>'9'; ch=getchar());for(; ch>='0'&&ch<='9'; ch=getchar())s=s*10+ch-'0';return s;}
using namespace std;
const int maxn = 110;
int a[maxn];
const int INF = 0x3f3f3f3f;
int main()
{
int n;
fin(n);
each(i,1,n)
{
fin(a[i]);
}
int cnt=0;
each(i,2,n-1)
{
if(a[i-1]==1&&a[i+1]==1&&a[i]==0)
{
a[i+1]=0;
cnt++;
}
}
printf("%d\n",cnt);
return 0;
}
E HDU2084 数塔 教科书上的动态规划例题
自底向上选择两个儿子中的较大的即可
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <cmath>
#include <string.h>
using namespace std;
int a[101][101],d[101][101];
int main()
{
int t,l,i,j;
scanf("%d",&t);
while(t--){
memset(d,0,sizeof(d));
scanf("%d",&l);
for(i=1;i<=l;i++)
for(j=1;j<=i;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=l;i++)
d[l][i]=a[l][i];
for(i=l-1;i>=1;i--)
for(j=1;j<=i;j++){
d[i][j]=a[i][j]+max(d[i+1][j],d[i+1][j+1]);
}
printf("%d\n",d[1][1]);
}
return 0;
}
F 搜索 mdPOJ崩了没法测试不过应该没有写错
注意方向的写法 visit数组的应用 每轮注意清空visit数组并把全局变量cnt置0
如果没有超界 没有撞墙，则可以继续dfs
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#define each(a,b,c) for(int a=b;a<=c;a++)
#define de(x) cout<<#x<<" "<<(x)<<endl;
const int maxn = 1e3+5;
const int INF = 0x3f3f3f3f;
using namespace std;
char a[25][25];
int vis[25][25];
char c;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int cnt = 0;
int m, n;
void dfs(int x, int y)
{
//de(x);
//de(y);
if (vis[x][y])return;
vis[x][y] = 1;
cnt++;
each(i, 0, 3)
{
int nx = x +dx[i];
int ny = y + dy[i];
//de(nx);
//de(ny);
if (a[nx][ny] != '#'&&nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny])
{
dfs(nx, ny);
}
}
return;
}
int main()
{
while (scanf("%d%d", &m, &n) != EOF&&(m||n)) {
cnt = 0;
getchar();//吃掉那个回车
memset(vis, 0, sizeof(vis));
int sx, sy;
each(i, 1, n)
{
each(j, 1, m)
{
scanf("%c", &a[i][j]);
if (a[i][j] == '@')
{
sx = i;
sy = j;
}
}
getchar();//注意去掉空格
}
dfs(sx, sy);
printf("%d\n", cnt);
/*
each(i, 1, n)
{
each(j, 1, m)
{
printf("%c", a[i][j]);
}
printf("\n");
}*/
}
return 0;
}
这场比赛十分经典，再刷新题之前，不会的题目一定要弄懂，一定要亲手AC！！！
加油！为我吉争光！
