SDUT-Team172 Summer Training Practice #1

题目大意：指定一个等差数列的长度，求该等差数列的首项和公差，满足该等差数列所有项均满足p³+q³(0<=p,q<=m),按公差从小到大输出，如果公差相等，按首项从小到大输出。

^代码：
View Code1#include

2#include

3#include

4#include

5#include

6usingnamespacestd;

7structpoint

8{

9intx;

10inty;

11}p[10001];

12inthash[500000];

13intcmp(constvoida,constvoidb)

14{

15structpoint c=(structpoint )a;

16structpoint d=(structpoint )b;

17if(c->y!=d->y)

18returnc->y-d->y;

19else

20returnc->x-d->x;

21}

22intmain()

23{

24inti,j,k,n,m,t,c,d,l,a1,b1,c1;

25inta[50000];

26c=0;

27while(~scanf("%d%d",&n,&m))

28{

29c++;

30l=t=0;

31if(n==0&&m==0)

32break;

33if(c!=1)

34puts("");

35memset(hash,0,sizeof(hash));

36for(i=0;i<=m;i++)

37{

38for(j=0;j<=m;j++)

39{

40d=iii+jjj;

41if(!hash[d])

42{

43hash[d]=1;

44a[t++]=d;

45}

46}

47}

48sort(a,a+t);

49for(i=0;i<t;i++)

50{

51for(j=i+1;j<t;j++)

52{

53a1=a[i];

54b1=a[j]-a[i];

55for(k=3;k<=n;k++)

56{

57c1=a1+(k-1)*b1;

58if(c1>a[t-1]||!hash[c1])

59break;

60}

61if(k>n)

62{

63p[l].x=a1;

64p[l].y=b1;

65l++;

66}

67}

68}

69printf("Case %d:n",c);

70if(!l)

71{

72puts("NONE");

73continue;

74}

75qsort(p,l,sizeof(p[0]),cmp);

76for(i=0;i<l;i++)

77{

78printf("%d %dn",p[i].x,p[i].y);

79}

80}

81return0;

82}

Problem GZOJ 2840File Searching

题目大意：类似于windows的文件查找，给一堆文件名，其中有*，让你匹配。

代码(各种if..else..写的好难看。。)：
View Code1#include

2#include

3#include

4usingnamespacestd;

5intmain()

6{

7intn,m,i,j,p,f,k,t,l1,l2,c=1;

8chars[100][65],s1[65];

9while(~scanf("%d%c",&n))

10{

11for(i=0;i<n;i++)

12scanf("%s",s[i]);

13if(c!=1)

14puts("");

15c++;

16scanf("%d%c",&m);

17while(m--)

18{

19scanf("%s",s1);

20l1=strlen(s1);

21for(i=0;i\
\22\{\
\
\23\\if\(s1[i]==\'\\*\\'\)\
\
\24\{\
\
\25\p=i;\
\
\26\\break\;\
\
\27\}\
\
\28\}\
\
\29\t=\0\;\
\
\30\\if\(!p)\
\
\31\{\
\
\32\\for\(i=\0\;i\\
\33\{\
\
\34\l2=strlen(s[i]);\
\
\35\\if\(l2\1\)\
\
\36\\continue\;\
\
\37\f=\0\;\
\
\38\\for\(j=l1-\1\,k=l2-\1\;j>=\1\&&k>=\0\;j--,k--)\
\
\39\{\
\
\40\\if\(s1[j]!=s[i][k])\
\
\41\{\
\
\42\f=\1\;\
\
\43\\break\;\
\
\44\}\
\
\45\}\
\
\46\\if\(!f)\
\
\47\{\
\
\48\\if\(t>0)

49printf(",");

50t++;

51printf("%s",s[i]);

52}

53}

54}

55elseif(p==l1-1)

56{

57for(i=0;i<n;i++)

58{

59f=0;

60l2=strlen(s[i]);

61if(l2<l1-1)

62continue;

63for(j=0;j1\;j++)\
\
\64\{\
\
\65\\if\(s1[j]!=s[i][j])\
\
\66\{\
\
\67\f=\1\;\
\
\68\\break\;\
\
\69\}\
\
\70\}\
\
\71\\if\(!f)\
\
\72\{\
\
\73\\if\(t>0)

74printf(",");

75t++;

76printf("%s",s[i]);

77}

78}

79}

80else

81{

82for(i=0;i<n;i++)

83{

84l2=strlen(s[i]);

85if(l21\)\
\
\86\\continue\;\
\
\87\f=\0\;\
\
\88\\for\(j=\0\;j\\
\89\{\
\
\90\\if\(s1[j]!=s[i][j])\
\
\91\{\
\
\92\f=\1\;\
\
\93\\break\;\
\
\94\}\
\
\95\}\
\
\96\\if\(!f)\
\
\97\{\
\
\98\\for\(j=l1-\1\,k=l2-\1\;j>p;j--,k--)\
\
\99\{\
\
\100\\if\(s1[j]!=s[i][k])\
\
\101\{\
\
\102\f=\1\;\
\
\103\\break\;\
\
\104\}\
\
\105\}\
\
\106\}\
\
\107\\if\(!f)\
\
\108\{\
\
\109\\if\(t>0)

110printf(",");

111printf("%s",s[i]);

112t++;

113}

114}

115}

116if(!t)

117printf("FILE NOT FOUND");

118puts("");

119}

120}

121return0;

122}

附：

官方题解：

A - Maximize Game Time - by cyang 中等题

一颗节点带权的树，每次可以任意访问一个未被访问过的节点，求访问到节点n - 1时的最大权值和，限制条件是当某个节点有两个儿子被访问时，得立即访问该节点。

树形dp，关键是要理清整个过程，恰当表示各种状态。很显然在访问第二个儿子节点前应尽可能多地访问其余节点。仔细观察可以发现，第一个儿子节点及其子树均可被访问，其余的则必须在保证该节点不被访问的前提下最优化其子树。如果用last[v]表示最后访问节点v的最优解，hold[v]表示以v为根的子树在不访问v的前提下的最优解，subTree[v]表示以v为根的子树的权值和

那么状态转移方程

last[v] = max(last[v1] + subTree[v2] + sum{ hold[v other] })

hold[v] = max(last[v1] + sum{ hold[v other] })

trick是有可能是森林。

B Magic Square - by riveria简单题

给定n*n的方阵，判断是否是幻方

C Number Puzzle - by maone简单题

给定一组数,求不大于m并且至少能被其中之一整除的数的个数，类似的题目应该很常见，就是列出所有组合然后用容斥原理计算。

D Left Library Lift - by xuezaiyue 中等题

从一楼出发，掷筛子决定每次移动的步数，到了顶楼或者底楼则改变方向继续前进，直到到达目标楼层为止，求投掷的期望次数。从目标楼层逆序考虑，这样可以将其余的楼层同等对待。除底楼和顶楼外，每个楼层有两个变量，分别表示上行和下行方向到达该楼层的期望值，这样每个楼层及其之前的六个楼层都可以列出一个方程。最后解方程组即可

E Utopia - by liuyaoting 偏难

题目模型很简单，给一棵高达50000节点的树，每次查询给定点C是否在其余两点A、B之间的路径上，最多有500000次查询

观察可以发现：

1、如果点C当且仅当是其中一个节点的祖先时，那么C肯定在路径上

2、如果C是AB两点的共同祖先即CA（Common Ancestor），只要判断C是否为最低公共祖先（LCA）即可。

3、否则不在路径上

对于问题1，只要dfs一遍记录每个节点的入栈时间intime及出栈时间outtime，然后判断其包含关系即可。

对于问题2，注意到某个节点的所有儿子节点从左到右的intime和outtime是递增的，因此可以二分查找这个CA是否有更低的CA，如果有，说明其不是LCA…其实这题也可以直接用RMQ求LCA。

F Find the Sequences - by adai 简单题，偏难？

给定项数n(n <= 10)，求出所有形如p^3+q^3（0 <= p, q <= m, m <= 50）的等差数列。m，n非常小，暴力就可以了。

首先列出所有p^3 + q^3这样的数，排序后枚举数列的一二项。

G File Searching - by inspire 简单题

给出一堆文件名，求dir命令所匹配的文件。命令中只有一个*。最后时刻补充的一道简单题目，没过估计大部分是被这组数据卡了

Seateadir

Seat*tea

H Galaxy War - by guanyao 难题

给一个弦图及n种颜色，求着色方案，相邻点的颜色不能相同

参考资料参见

《算法艺术与信息学竞赛》270页