弱校连萌 2016 10.3
。。。sad.....
果然没睡够&起来就写题脑子完全就是不清醒的状态。。。
这个不清醒。。。主要体现在。。。。10+次。。。忘记删条件编译。。。
改着改着。。。就忘记这件事了。。。好烦啊。。。本来早就A了。。。结果又接着去改。。。
题目链接：jag2016
就水了三道题。。。。
A是个暴力。。直接O(n2)算乘积，然后再check一下合法性就好。。。尼玛wa到我怀疑人生。。。过了好久才考虑也许是不支持条件编译的问题。
/* ***********************************************
Author :111qqz
Created Time :2016年10月03日 星期一 12时37分27秒
File Name :code/weakteam/20161003/A.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <deque>
9#include <map>
10#include <string>
11#include <cmath>
12#include <cstdlib>
13#include <bitset>
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1005;
7int n;
8int a[N];
9int ans = -1;
10int digit[20];
11void check(int x)
12{
13 ms(digit,0);
14 int len = 0 ;
15 int xx = x;
16 while (x)
17 {
18 digit[++len] = x;
19 x/=10;
20 }
21 for ( int i = len-1 ; i>=1 ; i--)
22 {
23 if (digit[i+1]-digit[i]!=-1) return;
24 }
25 ans = max(xx,ans);
1}
2int main()
3{
4 #ifndef ONLINE_JUDGE
5// freopen("code/in.txt","r",stdin);
6 #endif
1 cin>>n;
2 for ( int i = 1 ; i <= n ; i++) scanf("%d",a+i);
3 for ( int i = 1 ; i <= n-1 ; i++)
4 for ( int j = i+1; j <= n ; j++)
5 check(a[i]*a[j]);
6 printf("%d\n",ans);
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}
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道可以做（？