|
|
题意：给你一串只含有关键字write，if，else的语句，要你编程处理并输出结果，无结果则不输出
分析：本题最大的难点就是对字符串的处理。
首先，以if() ..... else ..... 为基结构，碰到write("....")便输出。而碰到嵌套语句.....不断利用递归调用寻找基语句。同时，注意if(0)的情况，在if(0).....else之间的.....通通略过。我做的时候，碰到问题有换行，处理空格，以及对字符串末尾的'\0'的处理。棘手的就是要清楚的看到指针变换的过程与指向位置。
#include <cstdio>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
char s[5000],cmd[20];
void work(char *p)
{
sscanf(p,"%s",cmd);
char *q = cmd;
if (cmd[0] == 'w') //当keyword == "write"
{
while (*q != '"') q ++;
q ++;
while (*q != '"')
{
putchar(*q); q ++;
}
putchar('\n');
while (s[0] != '\0')
gets(s);
}
else if (cmd[0] = 'i') //当 key words == "if"
{
while (*p != '(') p ++;
p ++;
if (*p == '1')//当为true时
{
p = strchr(p,' ');
while (p != NULL &&*p == ' ') p ++;
if (p == NULL)
{
gets(s);
if (s[0] != '\0')
work(s);
else return ;
}
else work(p);
}
else{ //当为false时
int cnt = 0;
//一个 do-while循环忽略if(0)..else之间的语句
do{
p = strchr(p,' ');
while (p != NULL && *p == ' ')
p ++;
if (p == NULL || *p == '\0')
{
gets(s);
if (s[0] == '\0')
return ;
p = s;
}
sscanf(p,"%s",cmd);
if (cmd[0] == 'i')
cnt ++;
else if (cmd[0] == 'e')
cnt --;
while (p != NULL && *p == ' ')
p ++;
}while (cnt >= 0);
p = strchr(p,' ');
while (p!= NULL && *p == ' ')
p ++;
if (p == NULL || *p == '\0')
{
gets(s);
if (s[0] == '\0')
return ;
p = s;
}
work(p);
}
}
else {//当key words为else
p = strchr(p,' ');
while (p != NULL && *p == ' ') p ++;
if (p == NULL || *p == '\0')
{
gets(s);
if (s[0] == '\0')
return ;
p = s;
}
work(p);
}
}
int main()
{
while (gets(s) && s[0] != '\0')
{
work(s);
}
return 0;
}
//考察点: 拆点 + 最大流
//思路: 把城市作为点拆开(把城市i拆成cap数组中的cap[i][i+n].其中i作为城市i的入,i+n作为城市i的出),原来的街道仍然作为边,但是边权是无穷大. 只要注意到BFS的时候 起点/终点是不需要拆的.(在cap[][]数组中就直接把起点/终点的入和出之间的边权赋值为0,使得BFS的时候不走起点/终点,实际上就相当于没有把起点/终点拆开.程序中的处理方法就是 cap[s][s+n] = 0;/cap[e][e+n] = 0;)
//提交情况; Wrong Answer 4次 Accepted 1次
WA 的原因是: BFS写错 做完一个CASE没有初始化cap数组导致错误
//收获: 对BFS有了更深的理解 对抽象出来的算法过程也有了具体的体会 吸取了不初始化的教训
//经验: 在学习一个代码的时候要手动模拟一下过程 好好理解算法的精髓 另外要加强联系 争取掌握用邻接表建图的方法
//ACcode
#include<stdio.h>
#include<memory.h>
#include<stdlib.h>
const int INF = 0x7fffffff;
int cap[201][201];
int s,t;
int que[201],pre[201];
int n,m;
bool vis[201];
bool findroad()
{
memset(vis,0,sizeof(vis));
int i,j;
int head = 0,tail = 0;
que[tail ++] = s;
while(head < tail)
{
j = que[head ++];
for(i = 1; i <= 2*n ;i ++)
{
if(!vis[i] && cap[j][i] > 0)
{
vis[i] = true;
pre[i] = j;
if(i == t) return true;
que[tail ++] = i;
}
}
}
return false;
}
int maxflow()
{
int flow = 0,i,min;
while(findroad())
{
min = INF;
for(i = t; i != s;i = pre[i])
{
if(cap[pre[i]][i] < min)
min = cap[pre[i]][i];
}
flow += min;
for(i = t; i != s;i = pre[i])
{
cap[pre[i]][i] -= min;
cap[i][pre[i]] += min;
}
}
return flow;
}
int main()
{
int T,x,y,i,j,tem,b,e;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d%d",&n,&m,&b,&e);
for(i = 1; i <= n;i ++)
{
scanf("%d",&tem);
cap[i][i+n] = tem;
}
s = b + n;
t = e;
cap[e][e+n]=0;
cap[s][s+n]=0;
for(i = 1; i <= m;i ++)
{
scanf("%d%d",&x,&y);
cap[x+n][y] = INF;
cap[y+n][x] = INF;
}
printf("%d\n",maxflow());
memset(cap,0,sizeof(cap));
}
return 0;
}
题意：给你一棵树，求最长的路程及其数目。
分析： 这道题做的我好辛苦啊，说是树形dp，我的理解此题其实是个树形递推（自顶向下使用递归实现自底向上的递推），唯一的记忆话就是标记访问过的节点，防止倒退。
理解了这个，还有一个难点，就是计数的问题：当有过某个节点有多个最大值时的计数；当子树有相同最大值的计数的补充。
总之，trick多多。还有本题可由任一节点开始递归，并不影响树的性质，倒是要注意第二种计数情况！！
#include <cstdio>
#include <stdlib.h>
const int MAX = 10010;
struct Point{
int id,len;
struct Point *next;
} p[2*MAX],*head[MAX];
struct Recd{
bool flag;//标记
int max,num; //当前节点以下的所有最大值及数目
int max_rout;//以此节点为端点的最大值
int max_num; //以此节点为端点的最大值的数目
} a[MAX]; //记录各顶点的状态
int n,x,y,v,cnt;
inline void addedge(int x,int y,int v)//用邻接表把各节点串起来
{
cnt ++;
p[cnt].id = y;
p[cnt].len = v;
p[cnt].next = head[x];
head[x] = &p[cnt];
}
void dp(int root)
{
a[root].flag = true;
struct Point *q = head[root];
int m[2] = {0,0};
int m_cnt[2] = {1,1};
bool mark = false;
int son_max = -1 , son_num = 0;
int tnum[2] = {0,0};
while (q)
{
if (a[q->id].flag == true)//已访问过
{
q = q->next;
continue;
}
dp(q->id);
x = a[q->id].max_rout + q->len;
y = a[q->id].max_num;
if (x > m[0])
{
mark = false;
m[1] = m[0];
m_cnt[1] = m_cnt[0];
m[0] = x;
m_cnt[0] = y;
tnum[0] = 0; //pay attention
}
else if (x == m[0])
{
mark = true;
tnum[0] += m_cnt[0]*y;
m_cnt[0] += y;
}
else if (x > m[1])
{
m[1] = x;
m_cnt[1] = y;
}
else if(x == m[1])
{
m_cnt[1] += y;
}
if (son_max < a[q->id].max)
{
son_max = a[q->id].max;
son_num = a[q->id].num;
}
else if (son_max == a[q->id].max)
son_num += a[q->id].num;
q = q->next;
}
int temp ,sum;
if (mark)
{
sum = tnum[0];
temp = 2*m[0];
}
else {
temp = m[0] + m[1];
sum = m_cnt[0] * m_cnt[1];
}
if (temp < son_max)
{
temp = son_max;
sum = son_num;
}
else if (temp == son_max)//pay attention
{
sum += son_num;
}
a[root].max_rout = m[0];
a[root].max_num = m_cnt[0];
a[root].max = temp;
a[root].num = sum;
}
int main()
{
while (scanf("%d",&n) != EOF)
{
for (int i = 1; i <= n; i++)
{
a[i].flag = false;
head[i] = NULL;
}
cnt = 0;
for (int i = 1; i < n; i++)
{
scanf("%d %d %d",&x,&y,&v);
addedge(x,y,v);
addedge(y,x,v);
}
dp(1);
printf("%d %d\n",a[1].max,a[1].num);
}
return 0;
}
|