弱校连萌 2016 10.3

题目链接

……sad…

果然没睡够，起来就写题，脑子完全就是不清醒的状态。

这个不清醒主要体现在，10+ 次忘记删条件编译。

改着改着就忘记这件事了，好烦啊。本来早就 A 了，结果又接着去改。

题目链接：

就水了三道题。

A 是个暴力，直接 O(n2) 算乘积，然后再 check 一下合法性就好。尼玛 WA 到我怀疑人生，过了好久才考虑也许是不支持条件编译的问题。

代码实现

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年10月03日 星期一 12时37分27秒
 4File Name :code/weakteam/20161003/A.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include <cstring>
 9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <deque>
15#include <map>
16#include <string>
17#include <cmath>
18#include <cstdlib>
19#include <bitset>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=1005;
35int n;
36int a[N];
37int ans = -1;
38int digit[20];
39void check(int x)
40{
41    ms(digit,0);
42    int len = 0 ;
43    int xx = x;
44    while (x)
45    {
46	digit[++len] = x;
47	x/=10;
48    }
49    for ( int i = len-1 ; i>=1 ; i--)
50    {
51	if (digit[i+1]-digit[i]!=-1) return;
52    }
53    ans = max(xx,ans);
54
55}
56int main()
57{
58	#ifndef  ONLINE_JUDGE
59//	freopen("code/in.txt","r",stdin);
60  #endif
61
62	cin>>n;
63	for ( int i = 1 ; i <= n ; i++) scanf("%d",a+i);
64	for ( int i = 1 ; i <= n-1 ; i++)
65	    for ( int j = i+1; j <= n ; j++)
66		check(a[i]*a[j]);
67	printf("%d\n",ans);
68
69  #ifndef ONLINE_JUDGE
70  fclose(stdin);
71  #endif
72    return 0;
73}

B 是 bfs…我的做法是先算每个点有士兵到达的最小时间，然后公主跑到某个点的时候判断当前时间是否小于这个格子士兵到达的最小时间。

不过这样做会 TLE，可以加个剪枝：在处理每个点有士兵到达的最小时间的时候，如果某个点存在比当前士兵到达的时间更短的时间，那么这个士兵其实就没用了，直接不再入队（同时要记得先把所有士兵位置标记一下再跑 bfs）。

代码实现

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年10月03日 星期一 13时10分37秒
  4File Name :code/weakteam/20161003/B.cpp
  5************************************************ */
  6#include <cstdio>
  7#include <cstring>
  8#include <iostream>
  9#include <algorithm>
 10#include <vector>
 11#include <queue>
 12#include <set>
 13#include <deque>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <bitset>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27using namespace std;
 28const double eps = 1E-8;
 29const int dx4[4]={1,0,0,-1};
 30const int dy4[4]={0,-1,1,0};
 31const int inf = 0x3f3f3f3f;
 32const int N=205;
 33int d[N][N];
 34char maze[N][N];
 35int n,m;
 36vector< pi >sol;
 37bool vis[N][N];
 38struct point
 39{
 40    int x,y;
 41    int d;
 42    bool ok ()
 43    {
 44    if (x<0||y<0||x>=n||y>=m||vis[x][y]||maze[x][y]=='#') return false;
 45    return true;
 46    }
 47    void look()
 48    {
 49    printf("x:%d y:%d d:%d\n",x,y,d);
 50    }
 51}s,pri;
 52void bfs( point s)
 53{
 54    ms(vis,false);
 55    vis[s.x][s.y] = true;
 56    d[s.x][s.y] = 0 ;
 57    queue<point>q;
 58    q.push(s);
 59    while (!q.empty())
 60    {
 61    point pre = q.front();
 62    q.pop();
 63    point nxt;
 64    for ( int i = 0 ; i < 4 ; i++)
 65    {
 66        nxt.x = pre.x + dx4[i];
 67        nxt.y = pre.y + dy4[i];
 68        if (!nxt.ok()) continue;
 69	if (d[pre.x][pre.y]+1>=d[nxt.x][nxt.y]) continue;
 70        vis[nxt.x][nxt.y] = true;
 71        d[nxt.x][nxt.y] = min(d[pre.x][pre.y] + 1,d[nxt.x][nxt.y]);
 72        q.push(nxt);
 73    }
 74    }
 75}
 76bool bfs2()
 77{
 78    ms(vis,false);
 79    vis[pri.x][pri.y] = true;
 80    queue<point>q;
 81    q.push(pri);
 82    while (!q.empty())
 83    {
 84    point pre = q.front();
 85    if (maze[pre.x][pre.y]=='%') return true;
 86    q.pop();
 87    point nxt;
 88    for ( int i = 0 ; i < 4 ; i++)
 89    {
 90        nxt.x = pre.x + dx4[i];
 91        nxt.y = pre.y + dy4[i];
 92        nxt.d = pre.d + 1;
 93        if (!nxt.ok()) continue;
 94        if (nxt.d>=d[nxt.x][nxt.y]) continue;
 95        vis[nxt.x][nxt.y] = true;
 96        q.push(nxt);
 97    }
 98    }
 99    return false;
100}
101int main()
102{
103    #ifndef  ONLINE_JUDGE
104    freopen("code/in.txt","r",stdin);
105  #endif
106    scanf("%d%d",&n,&m);
107    for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]);
108    ms(d,0x3f);
109    for ( int i = 0 ; i < n ; i++)
110    {
111        for ( int j = 0 ; j < m ; j++)
112        {
113        if (maze[i][j]=='@')
114        {
115            pri.x = i ;
116            pri.y = j ;
117            pri.d = 0;
118        }
119        if (maze[i][j]=='$')
120        {
121            sol.push_back(make_pair(i,j));
122        }
123        }
124    }
125    int siz = sol.size();
126    for ( int i = 0 ; i < siz ; i ++)
127    {
128	d[sol[i].fst][sol[i].sec]=0;
129    }
130    for ( int i = 0 ; i < siz;  i++)
131    {
132        s.x = sol[i].fst;
133        s.y = sol[i].sec;
134        bfs(s);
135    }
136    if (bfs2())
137        puts("Yes");
138    else puts("No");
139  #ifndef ONLINE_JUDGE
140  fclose(stdin);
141  #endif
142    return 0;
143}

d 题：构造。一开始思路错了，以为让所有的数都是三角形数会比较优秀。然而当 A 为 8 的时候，按照这个思路，答案为)()()))(((

但实际上存在更优的答案为))())(((

造成这个错误的原因是，忽视了每一部分之间的关联，以为减去一个三角形数以后就成了一个新的问题。

但是实际上不是这样。

我们可以手写从 A=6 到 A=10 的情况，规律比较显然。

具体写的时候我预处理了小于等于 A 的三角形数。

代码实现

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年10月03日 星期一 15时22分25秒
 4File Name :code/weakteam/20161003/D.cpp
 5 ************************************************ */
 6#include <cstdio>
 7#include <cstring>
 8#include <iostream>
 9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <deque>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <bitset>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27using namespace std;
28const double eps = 1E-8;
29const int dx4[4]={1,0,0,-1};
30const int dy4[4]={0,-1,1,0};
31const int inf = 0x3f3f3f3f;
32const int N=1E5+7;
33int A;
34int k;
35int a[N];
36vector<int>ans;
37void print(int x)
38{
39    for ( int i = 1 ; i <= x;  i++) printf(")");
40    for ( int i = 1 ; i <= x ; i++) printf("(");
41}
42int main()
43{
44#ifndef  ONLINE_JUDGE
45    freopen("code/in.txt","r",stdin);
46#endif
47    cin>>A;
48    int cnt = 0 ;
49    for (int i = 1 ; k<=A ; i++)
50    {
51	k = i*(i+1)/2;
52	a[++cnt] = k;
53    }
54    int x = upper_bound(a+1,a+cnt+1,A)-a-1;
55    if (A==a[x])
56	print(x);
57    else
58    {
59	int delta = A-a[x];
60	for ( int i = 1 ; i  <= delta ; i++ ) printf(")");
61	printf("(");
62	for ( int i = 1 ; i <= x+1-delta ; i++) printf(")");
63	for ( int i = 1 ; i <= x ; i++) printf("(");
64    }
65#ifndef ONLINE_JUDGE
66    fclose(stdin);
67#endif
68    return 0;
69}

剩下的题没来得及看，不过目测还有 2 道可以做（？

相关文章