[弱校联萌2016]2016弱校联盟十一专场10.3

比赛链接：https://www.bnuoj.com/v3/contest_show.php?cid=8504#info

A.找两个数乘积是连续上升并且最大的。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 1010;
 5 int n, ret;
 6 int a[maxn];
 7 
 8 int main() {
 9   //freopen("in", "r", stdin);
10   while(~scanf("%d", &n)) {
11     for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
12     ret = -1;
13     for(int i = 1; i <= n; i++) {
14       for(int j = 1; j < i; j++) {
15         int tmp = a[i] * a[j];
16         int p = tmp % 10; tmp /= 10;
17         int q;
18         while(tmp) {
19           q = tmp % 10;
20           if(q + 1 != p) break;
21           tmp /= 10; p = q;
22         }
23         if(tmp == 0) ret = max(ret, a[i]*a[j]);
24       }
25     }
26     printf("%d
", ret);
27   }
28   return 0;
29 }

B.从终点开始bfs，记录各点到终点最短路。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef struct Pair {
 5   int x, y;
 6   Pair() {}
 7   Pair(int x, int y) : x(x), y(y) {}
 8 }Pair;
 9 const int maxn = 220;
10 const int inf = 900000000;
11 const int dx[5] = {0,0,1,-1};
12 const int dy[5] = {1,-1,0,0};
13 int n, m;
14 int sx, sy;
15 int dp[maxn][maxn];
16 char G[maxn][maxn];
17 queue<Pair> q;
18 int rp, rs;
19 
20 bool ok(int x, int y) {
21   return x>=0&&x<n&&y>=0&&y<m;
22 }
23 
24 void bfs() {
25   rp = rs = inf;
26   while(!q.empty()) {
27     Pair p = q.front(); q.pop();
28     if(G[p.x][p.y] == '$') rs = min(rs, dp[p.x][p.y]);
29     if(G[p.x][p.y] == '@') rp = min(rp, dp[p.x][p.y]);
30     for(int i = 0; i < 4; i++) {
31       int x = p.x + dx[i];
32       int y = p.y + dy[i];
33       if(ok(x, y) && G[x][y] != '#' && dp[x][y] == -1) {
34         dp[x][y] = dp[p.x][p.y] + 1;
35         q.push(Pair(x, y));
36       }
37     }
38   }
39 }
40 
41 int main() {
42   //freopen("in" , "r", stdin);
43   while(~scanf("%d%d",&n,&m)) {
44     for(int i = 0; i < n; i++) scanf("%s", G[i]);
45     for(int i = 0; i < n; i++)
46       for(int j = 0; j < m; j++)
47         if(G[i][j] == '%') q.push(Pair(i,j));
48     memset(dp, -1, sizeof(dp));
49     bfs();
50     if(rp < rs) puts("Yes");
51     else puts("No");
52   }
53   return 0;
54 }

D.n对括号最多需要交换n*(n+1)/2次（)))...(((类似这种摆放情况），那么找最短的满足m*(m+1)/2>=n的，然后把额外需要交换的交换完毕就是结果。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n;
 5 string ret;
 6 
 7 int main() {
 8   //freopen("in", "r", stdin);
 9   while(~scanf("%d", &n)) {
10     ret.clear();
11     int m = 1;
12     while(m * (m + 1) / 2 < n) m++;
13     ret = string(m, ')') + string(m, '(');
14     int cur = m;
15     for(int i = 0; i < m * (m + 1) / 2 - n; i++) {
16       swap(ret[cur-1], ret[cur]);
17       cur--;
18     }
19     cout << ret << endl;
20   }
21   return 0;
22 }

E.ULL Hash爆搞。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 typedef unsigned long long ULL;
 6 const ULL mod = ULL(1e9+7);
 7 const int maxn = 100100;
 8 int n;
 9 vector<int> G[maxn];
10 map<ULL, LL> h;
11 map<ULL, LL>::iterator it;
12 
13 ULL dfs(int p, int u) {
14   ULL hs = 0;
15   for(int i = 0; i < G[u].size(); i++) {
16     int v = G[u][i];
17     if(v == p) continue;
18     hs += dfs(u, v);
19   }
20   hs *= mod;
21   h[++hs]++;
22   return hs;
23 }
24 
25 int main() {
26   //freopen("in", "r", stdin);
27   int u, v;
28   while(~scanf("%d",&n)) {
29     h.clear();
30     for(int i = 1; i <= n; i++) G[i].clear();
31     for(int i = 0; i < n-1; i++) {
32       scanf("%d%d",&u,&v);
33       G[u].push_back(v);
34       G[v].push_back(u);
35     }
36     dfs(-1, 1);
37     LL ret = 0;
38     for(it = h.begin(); it != h.end(); it++) ret += (it->second * it->second);
39     cout << (ret - n) / 2 << endl;
40   }
41   return 0;
42 }