BestCoder Round #92

　　现场赛就出了一题= =。

　　A题，水题。但是几天没写代码有点手生，调试了一会才A= =。

　　B题，考虑到只要连续的四个即可，那么枚举中间的两个即可。代码如下：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <vector>
 5 using namespace std;
 6 typedef long long ll;
 7 const int N = 100000 + 50;
 8 
 9 vector<int> B[N];
10 int C[N];
11 int n,m,k;
12 void init()
13 {
14     memset(C,0,sizeof(C));
15     for(int i=1;i<=m;i++) B[i].clear();
16 }
17 
18 int main()
19 {
20     int T;
21     scanf("%d",&T);
22     while(T--)
23     {
24         scanf("%d%d%d",&n,&m,&k);
25         init();
26         for(int i=1;i<=k;i++)
27         {
28             int u,v;
29             scanf("%d%d",&u,&v);
30             B[v].push_back(u);
31             C[u]++;
32         }
33         ll ans = 0;
34         for(int b=1;b<=m;b++)
35         {
36             if(B[b].size() < 2) continue;
37             for(int i=0;i<B[b].size();i++)
38             {
39                 int c = B[b][i];
40                 if(C[c] < 2) continue;
41                 int a_can = B[b].size() - 1;
42                 int d_can = C[c] - 1;
43                 ans += 1LL * a_can * d_can;
44             }
45         }
46         ans *= 2;
47         printf("%I64d
",ans);
48     }
49     return 0;
50 }

　　C题，看数据挺小的，但是想不出什么好方法- -，题解是记忆化搜索。代码如下：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 using namespace std;
 5 const int N = 100 + 5;
 6 
 7 int n,m,cnt,kase;
 8 int dp[N][N][N];
 9 int vis[N][N][N];
10 char s[N];
11 int pos[N];
12 void update(int &a,int b) {if(a < b) a = b;}
13 int dfs(int k,int last_pos,int iq)
14 {
15     if(k > cnt) return n - last_pos >= 2;
16     if(vis[k][last_pos][iq] == kase) return dp[k][last_pos][iq];
17     vis[k][last_pos][iq] = kase;
18     dp[k][last_pos][iq] = -2e9;
19     int L = max(last_pos + 1, pos[k] - iq);
20     int R = min(n, pos[k] + iq);
21     for(int i=L;i<=R;i++)
22     {
23         int cost = std::abs(i - pos[k]);
24         update(dp[k][last_pos][iq], dfs(k+1,i,iq-cost) + (i-last_pos>=3) * (k > 1));
25     }
26     return dp[k][last_pos][iq];
27 }
28 
29 int main()
30 {
31     int T;
32     scanf("%d",&T);
33     kase = 0;
34     while(T--)
35     {
36         kase++;
37         scanf("%d%d",&n,&m);
38         scanf("%s",s+1);
39         m >>= 1;
40         cnt = 0;
41         for(int i=1;i<=n;i++) if(s[i] == '2') pos[++cnt] = i;
42         if(cnt == 0) {puts("0"); continue;}
43         printf("%d
",dfs(1,0,m));
44     }
45     return 0;
46 }