15.5.10 国防科大校赛

题目链接http://acm.csu.edu.cn/OnlineJudge/contest.php?cid=2080

problemset 1609~1618

比赛完几天了却一直没有写题解，比赛中是完全被虐了的，赛后做的差不多了这下就写写题解。

A：Arrays Transformation（YY）

题目是说一个数组每次可以将连续的三个数（a[i-1], a[i], a[a+1]）变为（a[i-1]+a[i], -a[i], a[i+1]+a[i]），现在给定A和B两个序列，问是否可以通过多次操作使得序列由A变为B

方法就是因为每次操作i，相当于把前缀和s[i-1]和s[i]互换位置，认真想一下很好明白，所以最后就转化为判断是否两个数组的前缀和排序后是不是可以通过排序后一一对应起来

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, (L + R)>>1
18 #define rson k<<1|1,  ((L + R)>>1) + 1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FIN freopen("in.txt", "r", stdin)
23 #define FOUT freopen("out.txt", "w", stdout)
24 #define rep(i, a, b) for(int i = a; i <= b; i ++)
25  
26 template<class T> T CMP_MIN(T a, T b) { return a < b; }
27 template<class T> T CMP_MAX(T a, T b) { return a > b; }
28 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
29 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
30 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
31 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
32  
33 //typedef __int64 LL;
34 typedef long long LL;
35 const int MAXN = 51000;
36 const int MAXM = 110000;
37 const double eps = 1e-4;
38 //LL MOD = 987654321;
39  
40 LL a[110000], b[110000];
41 int T, n, x;
42  
43 int main()
44 {
45     //FIN;
46     while(~scanf("%d", &T)) while(T--) {
47         cin >> n;
48         rep (i, 1, n) scanf("%d", &x), a[i] = a[i - 1] + x;
49         rep (i, 1, n) scanf("%d", &x), b[i] = b[i - 1] + x;
50         sort(a + 1, a + n + 1);
51         sort(b + 1, b + n + 1);
52         int ok = 1;
53         rep (i, 1, n) if(a[i] != b[i]) ok = 0;
54         puts(ok ? "Yes" : "No");
55     }
56     return 0;
57 }

View Code

B：Binary Subtraction（二进制高精度减法）

不用说了，水题

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, (L + R)>>1
18 #define rson k<<1|1,  ((L + R)>>1) + 1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FIN freopen("in.txt", "r", stdin)
23 #define FOUT freopen("out.txt", "w", stdout)
24 #define rep(i, a, b) for(int i = a; i <= b; i ++)
25 #define dec(i, a, b) for(int i = a; i >= b; i --)
26  
27 template<class T> T CMP_MIN(T a, T b) { return a < b; }
28 template<class T> T CMP_MAX(T a, T b) { return a > b; }
29 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
30 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
31 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
32 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
33  
34 //typedef __int64 LL;
35 typedef long long LL;
36 const int MAXN = 51000;
37 const int MAXM = 110000;
38 const double eps = 1e-4;
39 //LL MOD = 987654321;
40  
41 int T, n, m, x;
42 int a[1100000], b[1100000];
43  
44 int main()
45 {
46     //FIN;
47     while(~scanf("%d", &T)) while(T--) {
48         cin >> n >> m;
49         rep (i, 1, n) a[i] = 1, b[i] = 0;
50         rep (i, 1, m) {
51             scanf("%d", &x);
52             a[x] = 0; b[x] = 1;
53         }
54         int ji = 0;
55         rep (i, 1, n) {
56             if(ji) {
57                 if(a[i] == 0) { ji = 1; a[i] = !b[i]; }
58                 else { ji = b[i]; a[i] = b[i]; }
59             }
60             else {
61                 if(a[i] == 0) { ji = b[i]; a[i] = b[i]; }
62                 else { ji = 0; a[i] -= b[i]; }
63             }
64         }
65         int f = 0;
66         dec (i, n, 1) {
67             if(a[i]) f = 1;
68             if(f) printf("%d", a[i]);
69         }
70         printf("n");
71     }
72     return 0;
73 }

View Code

C:Concatenation（TSP问题）

题意是说给n(<=12)个字符串，问求一个最短的字符串，使得它包含所有的给定字符串

由于如果一个字符串完全被另一个字符串包含（是另一个字符串的子串），那么这个字符串完全可以不予考虑，将其删除

接下来就是简单的状压DP

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, (L + R)>>1
18 #define rson k<<1|1,  ((L + R)>>1) + 1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FIN freopen("in.txt", "r", stdin)
23 #define FOUT freopen("out.txt", "w", stdout)
24 #define rep(i, a, b) for(int i = a; i <= b; i ++)
25  
26 template<class T> T CMP_MIN(T a, T b) { return a < b; }
27 template<class T> T CMP_MAX(T a, T b) { return a > b; }
28 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
29 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
30 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
31 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
32  
33 //typedef __int64 LL;
34 typedef long long LL;
35 const int MAXN = 51000;
36 const int MAXM = 110000;
37 const double eps = 1e-4;
38 //LL MOD = 987654321;
39  
40 int mer[20][20], len[20], dp[1<<15][20], n, t, vis[55];
41 char s[20][55];
42  
43 int Strstr(char *a, char *b) {
44     int lena = strlen(a), lenb = strlen(b);
45     rep (i, 0, lena - 1) {
46         int j = 0;
47         while(i + j < lena && j < lenb && a[i + j] == b[j]) j++;
48         if(j == lenb) return i;
49     }
50     return -1;
51 }
52  
53 //find suffix of a with the max length is pre of b
54 int findMerge(char *a, char *b) {
55     int lena = strlen(a), lenb = strlen(b);
56     rep (i, 0, lena - 1) {
57         if(Strstr(b, a + i) == 0) return lena - i;
58     }
59     return 0;
60 }
61  
62 int main()
63 {
64     while(~scanf("%d", &t)) while(t--) {
65         scanf("%d", &n);
66         rep(i, 0, n - 1) scanf("%s", s[i]);
67         mem0(vis);
68         rep (i, 0, n - 1) rep (j, i+1, n - 1) {
69             if(Strstr(s[i], s[j]) >= 0) vis[j] = 1;
70             else if(Strstr(s[j], s[i]) >= 0) vis[i] = 1;
71         }
72  
73         int cnt = 0;
74         rep (i, 0, n - 1) {
75             if(!vis[i]) {
76                 strcpy(s[cnt++], s[i]);
77                 len[cnt-1] = strlen(s[cnt-1]);
78             }
79         }
80         rep (i, 0, cnt - 1) rep (j, 0, cnt - 1) {
81             mer[i][j] = findMerge(s[i], s[j]);
82         }
83  
84         mem1(dp);
85         int high = (1 << cnt) - 1;
86         rep (i, 0, cnt - 1) dp[1 << i][i] = len[i];
87         rep (i, 1, high) rep (j, 0, cnt - 1) if((i & (1<<j)) && dp[i][j] != -1) {
88             rep (k, 0, cnt - 1) if(!(i & (1 << k))) {
89                 if(dp[i | (1<<k)][k] == -1) dp[i | (1<<k)][k] = dp[i][j] + len[k] - mer[j][k];
90                 else dp[i | (1<<k)][k] = min(dp[i | (1<<k)][k], dp[i][j] + len[k] - mer[j][k]);
91             }
92         }
93         int ans = 1000000;
94         rep (i, 0, cnt - 1) ans = min(ans, dp[high][i]);
95         cout << ans << endl;
96     }
97     return 0;
98 }
99

View Code

D:Destroy Tunnels（强连通）

见连接

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, (L + R)>>1
18 #define rson k<<1|1,  ((L + R)>>1) + 1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FIN freopen("in.txt", "r", stdin)
23 #define FOUT freopen("out.txt", "w", stdout)
24 #define rep(i, a, b) for(int i = a; i <= b; i ++)
25 #define dec(i, a, b) for(int i = a; i >= b; i --)
26  
27 template<class T> T CMP_MIN(T a, T b) { return a < b; }
28 template<class T> T CMP_MAX(T a, T b) { return a > b; }
29 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
30 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
31 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
32 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
33  
34 //typedef __int64 LL;
35 typedef long long LL;
36 const int MAXN = 11000;
37 const int MAXM = 1100;
38 const double eps = 1e-4;
39 LL MOD = 1000000007;
40  
41 vector<int> G[MAXN];
42 int pre[MAXN], lowlink[MAXN], sccno[MAXN], dfs_clock, scc_cnt;
43 stack<int>S;
44  
45 void dfs(int u)
46 {
47     pre[u] = lowlink[u] = ++dfs_clock;
48     S.push(u);
49     int si = G[u].size();
50     for(int i = 0; i < si; i ++)
51     {
52         int v = G[u][i];
53         if(!pre[v]) {
54             dfs(v);
55             lowlink[u] = min(lowlink[u], lowlink[v]);
56         }
57         else if(!sccno[v]) {
58             lowlink[u] = min(lowlink[u], pre[v]);
59         }
60     }
61     if(lowlink[u] == pre[u]) {
62         scc_cnt++;
63         for(;;) {
64             int x = S.top(); S.pop();
65             sccno[x] = scc_cnt;
66             if(x == u) break;
67         }
68     }
69 }
70  
71  
72 void find_scc(int n)
73 {
74     dfs_clock = scc_cnt = 0;
75     mem0(sccno); mem0(pre);
76     for(int i = 0; i < n; i ++ )
77         if(!pre[i]) dfs(i);
78 }
79  
80 int t, n, x;
81  
82 int main()
83 {
84     while(~scanf("%d", &t)) while(t--) {
85         scanf("%d", &n);
86         rep (i, 0, n) G[i].clear();
87         rep (i, 0, n - 1) rep (j, 0, n - 1) {
88             scanf("%d", &x);
89             if(x) G[i].push_back(j);
90         }
91         find_scc(n);
92         puts(scc_cnt == 1 ? "not exists" : "exists");
93     }
94     return 0;
95 }
96

View Code

E:Elephants（分组背包）

裸的

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, (L + R)>>1
18 #define rson k<<1|1,  ((L + R)>>1) + 1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FIN freopen("in.txt", "r", stdin)
23 #define FOUT freopen("out.txt", "w", stdout)
24 #define rep(i, a, b) for(int i = a; i <= b; i ++)
25 #define dec(i, a, b) for(int i = a; i >= b; i --)
26  
27 template<class T> T CMP_MIN(T a, T b) { return a < b; }
28 template<class T> T CMP_MAX(T a, T b) { return a > b; }
29 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
30 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
31 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
32 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
33  
34 //typedef __int64 LL;
35 typedef long long LL;
36 const int MAXN = 11000;
37 const int MAXM = 1100;
38 const double eps = 1e-4;
39 LL MOD = 1000000007;
40  
41 int t, n, m, c, w, v, f[21][1100];
42  
43 int main()
44 {
45     //FIN;
46     while(~scanf("%d", &t)) while(t--) {
47         scanf("%d %d", &n, &m);
48         mem0(f);
49         rep (i, 1, n) {
50             scanf("%d", &c);
51             rep (j, 1, c) {
52                 scanf("%d %d", &w, &v);
53                 rep (k, 0, w - 1) f[i][k] = max(f[i][k], f[i - 1][k]);
54                 rep (k, w, m) f[i][k] = max(f[i][k], max(f[i - 1][k], f[i - 1][k - w] + v));
55             }
56         }
57         printf("%dn", f[n][m]);
58     }
59     return 0;
60 }

View Code

F:First Blood（水题）

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, (L + R)>>1
18 #define rson k<<1|1,  ((L + R)>>1) + 1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FIN freopen("in.txt", "r", stdin)
23 #define FOUT freopen("out.txt", "w", stdout)
24 #define rep(i, a, b) for(int i = a; i <= b; i ++)
25 #define dec(i, a, b) for(int i = a; i >= b; i --)
26  
27 template<class T> T CMP_MIN(T a, T b) { return a < b; }
28 template<class T> T CMP_MAX(T a, T b) { return a > b; }
29 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
30 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
31 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
32 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
33  
34 //typedef __int64 LL;
35 typedef long long LL;
36 const int MAXN = 11000;
37 const int MAXM = 1100;
38 const double eps = 1e-4;
39 LL MOD = 1000000007;
40  
41 int t, n;
42 double x[110], y[110], r[110];
43  
44 double dis(int i, int j) {
45     double a = x[i] - x[j], b = y[i] - y[j];
46     return (double) sqrt(a * a + b * b);
47 }
48  
49 int main()
50 {
51     //FIN;
52     while(~scanf("%d", &t)) while(t--) {
53         scanf("%d", &n);
54         rep (i, 1, n) scanf("%lf %lf %lf", x + i, y + i, r + i);
55         int ans = 0;
56         rep (i, 1, n) {
57             int ok = 1;
58             rep (j, 1, n) if(i != j) {
59                 if(r[i] + r[j] - dis(i, j) > eps) { ok = 0; break; }
60             }
61             ans += ok;
62         }
63         printf("%dn"<

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/weixin_34224941/article/details/94751541
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2019-09-13 23:43:16
阅读 ( 1158 )
分类：

15.5.10 国防科大校赛

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看